一位名叫 K 的音乐爱好者非常喜欢吃涮涮锅！最近，她去了 $N$ 家涮涮锅餐厅，编号为 $1, 2, \dots, N$，并遵循以下算法：

1. K 保留一份有序的推荐列表，从餐厅 1 开始。
2. 在第 $i$ 天，她访问列表中的下一个推荐餐厅，该餐厅向她推荐了餐厅 $R_i = \{r_{i,1}, \dots, r_{i,\ell_i}\}$。
3. K 将 $R_i$ 追加到她的待访问餐厅列表中。
4. K 重复步骤 2-4，直到没有推荐餐厅为止。
5. K 写下数组 $A_0, \dots, A_{N-1}$，其中 $A_i$ 等于她在第 $(i+1)$ 天被推荐的餐厅数量。即 $A_i = |R_{i+1}|$。

保证 $\bigcup_{i=1}^N R_i = \{2, \dots, N\}$ 且对于 $i \neq j$ 有 $R_i \cap R_j = \varnothing$，也就是说，除了第一家餐厅外，每家餐厅都恰好被另一家餐厅推荐一次。

当 K 完成她的列表后，她调皮的朋友 H 决定捉弄她！她用另一个数组 $B_0, \dots, B_{N-1}$ 替换了数组 $A_0, \dots, A_{N-1}$。K 认为这个新数组 $B_i$ 可能只是她原数组的一个循环移位，所以她请你确定所有可能的 $0 \le k < N$，使得对于所有 $0 \le i < N$ 以及 K 算法的任何有效输出 $A_0, \dots, A_{N-1}$，都有 $A_i = B_{(i+k) \pmod N}$。

此外，K 将执行 $Q$ 次操作，其中第 $i$ 次操作中，她会交换 $B_{x_i}$ 和 $B_{y_i}$，并要求你在新数组上做同样的事情。你能帮 K 看穿她朋友的恶作剧吗？

输入格式

第一行包含两个整数 $N$ ($1 \le N \le 500\,000$) 和 $Q$ ($0 \le Q \le 300\,000$)。

下一行包含 $N$ 个空格分隔的非负整数 $B_0, B_1, \dots, B_{N-1}$ ($0 \le B_i < N$)，即初始序列。

接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i < N$ 且 $x_i \neq y_i$)，表示你需要交换 $B_{x_i}$ 和 $B_{y_i}$。

下表显示了 25 分的分布情况：

输出格式

对于 $Q+1$ 个数组中的每一个（包括初始数组 $B_0, \dots, B_{N-1}$），令 $S = \{k_1, \dots, k_m\}$ 表示所有满足以下条件的整数 $0 \le k_j < N$ 的集合：存在 K 算法的有效输出 $A_0, \dots, A_{N-1}$，使得对于所有 $0 \le i < N$，都有 $A_i = B_{(i+k_j) \pmod N}$。在一行中输出整数 $m$ 和 $\sum_{i=1}^m k_i \pmod{998\,244\,353}$，中间用空格分隔。

特别地，如果 $S = \varnothing$，你应该输出 0 0。

样例

样例输入 1

5 3
1 2 0 0 1
0 2
1 3
3 2

样例输出 1

1 4
1 1
1 2
1 2

说明

对于样例输出的解释：数组 $A$ 为 $[1, 1, 2, 0, 0]$；可以证明这是 K 的算法对应数组 $B = [1, 2, 0, 0, 1]$ 的唯一有效输出。K 的算法产生此数组 $A$ 的一种输入为： $R_1 = \{2\}$ $R_2 = \{3\}$ $R_3 = \{4, 5\}$ $R_4 = \varnothing$ $R_5 = \varnothing$

交换 $B_0$ 和 $B_2$ 后，我们得到数组 $B = [0, 2, 1, 0, 1]$。 可以证明对应此数组的 K 算法的唯一有效输出为 $A = [2, 1, 0, 1, 0]$。 产生此数组 $A$ 的一种 K 算法输入为： $R_1 = \{2, 3\}$ $R_2 = \{4\}$ $R_3 = \varnothing$ $R_4 = \{5\}$ $R_5 = \varnothing$

Python 提示（仅限 CIW）：如果你正在尝试最后一个子任务，建议使用快速输入（例如 sys.stdin.read() 和 sys.stdout.write()）。