国际烹饪预备学院迎来了一批共 $n$ 名学生，编号为 1 到 $n$。每个人都怀揣着成为菲律宾最优秀厨师的梦想。学年初，大家互不相识，但随着学年的推进，一些学生之间会成为“朋友”。

学年期间将发生 $q$ 次事件。每次事件指定两名不同的学生 $u$ 和 $v$，其含义如下： 如果 $u$ 和 $v$ 尚未成为朋友，则他们成为朋友。 如果 $u$ 和 $v$ 已经是朋友，则他们不再是朋友。

在竞技烹饪网站 Cookforces 上，每位用户被分配一个 1 到 $c$ 之间的整数评分。多名用户可以拥有相同的评分。ICPC 的学生被鼓励在 Cookforces 上争取高分。

如果一名学生没有与任何评分严格高于自己的学生成为朋友，则称该学生为“有毒的”。学校的 Ramsay 数等于此时刻有毒学生的数量。

有一天，Cookforces 的创始人对大家对评分的痴迷感到厌倦，决定采取极端手段。他宣布已经对网站进行编程，将在未来某个未知的时间点，毫无预警地将所有评分完全随机化。每位用户的评分将变为从 1 到 $c$ 中均匀随机选择的一个整数。

这当然让学校陷入了彻底的混乱。在上述 $q$ 次事件中的每一次之后，请回答以下问题： * 如果评分在本次事件后立即随机化，学校 Ramsay 数的期望值（模 1224736769）是多少？

假设我们重复进行“随机化所有用户评分”的随机实验，并记录得到的 Ramsay 数。期望值等于我们的运行平均值将收敛到的值（以高概率）。

形式化地，令 $x_1, x_2, x_3, \dots$ 为一个无穷序列，其中 $x_t$ 是前 $t$ 次随机实验中记录的 Ramsay 数的平均值。我们可以证明存在正整数 $p$ 和 $q$，使得 $\lim_{t \to \infty} x_t = p/q$ 几乎必然成立。

你的任务是在每次事件后，报告 $pq^{-1} \pmod{1224736769}$ 的值；更正式地说，输出满足 $p \equiv qr \pmod{1224736769}$ 的值 $r$。我们可以证明在给定约束条件下，这样的 $r$ 总是存在且唯一（模 1224736769）。

输入格式

输入的第一行包含三个空格分隔的整数 $n$、$c$ 和 $q$。

接下来 $q$ 行，按发生顺序描述事件。每行包含两个空格分隔的正整数，即该事件中 $u$ 和 $v$ 的值。

输出格式

输出 $q$ 行，每行包含一个非负整数，即每次事件后 Ramsay 数的期望值（模 1224736769）。

数据范围

• $2 \le n \le 2 \times 10^5$
• $2 \le c \le 10^9$
• $1 \le q \le 3 \times 10^5$
• 每次事件中 $1 \le u, v \le n$ 且 $u \neq v$。

样例

输入 1

3 2 4
1 2
2 3
1 3
1 2

输出 1

612368387
1071644675
153092098
1071644675

说明 1

每次事件后 Ramsay 数的期望值分别为： $5/2$ $17/8$ $15/8$ $17/8$

例如，我们有： $$5/2 \equiv 612368387 \pmod{1224736769}$$ 因为 $$612368387 \cdot 2 \equiv 5 \pmod{1224736769}$$