布隆过滤器（Bloom filter）是一种空间效率极高的概率型数据结构，用于测试一个元素是否属于某个集合。元素可以被添加到集合中，但不能被删除。

针对全集 $S$ 的布隆过滤器是一个包含 $m$ 个比特的数组，初始时所有位均置为零，并配有 $l$ 个不同的哈希函数 $S \to [0, m): h_1, \dots, h_l$。

要将元素 $s \in S$ 添加到集合中，将其输入到每个哈希函数中，并将对应的位 $h_1(s), \dots, h_l(s)$ 置为 1。要测试一个元素是否在集合中，查看位 $h_1(s), \dots, h_l(s)$。如果其中任何一位为 0，则该元素“肯定不在集合中”；否则，该元素“可能在集合中”。因此，布隆过滤器允许假阳性匹配，但不允许假阴性。

你的队友为 $0$ 到 $10^9$ 之间的整数实现了他自己的布隆过滤器。他选择了一个素数 $m$，并定义了一个哈希函数（因为对他来说太复杂了）：$h(s) = (As + B) \pmod m$，其中 $0 \le A, B < m$。然后他选择了 $n$ 个数字 $a_1, \dots, a_n$ 并将它们添加到过滤器中。操作完成后，有 $k$ 个位被置为 1：$b_1, \dots, b_k$。

你想要重现他的实验。不幸的是，你不知道 $A$ 和 $B$ 的值。因此，你决定找出所有的数对 $(A, B)$，使得使用这些参数将所有数字 $a_1, \dots, a_n$ 添加到布隆过滤器后，恰好会将这些位设置为 1。

输入格式

第一行包含三个整数 $n, k$ 和 $m$ ($1 \le n, k \le 10^6, 2 \le m \le 10^6, m$ 为素数)。 第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$)，这些是添加到过滤器中的数字。 第三行包含 $k$ 个整数 $b_1, \dots, b_k$ ($0 \le b_j < m$)，这些是添加所有元素到过滤器后必须被置为 1 的位。所有其他位必须为零。

输出格式

在输出的第一行，打印一个整数 $p$，表示满足条件的数对数量。在接下来的 $p$ 行中，每行打印两个整数 $A$ 和 $B$，表示一组参数，使得使用这些参数将所有数字 $a_1, \dots, a_n$ 添加到布隆过滤器后，恰好会将位 $b_1, \dots, b_k$ 置为 1。

保证数对的数量 $p$ 最多为 $10^6$。

样例

样例输入 1

4 4 11
1 6 8 9
0 2 8 9

样例输出 1

1
3 6

样例输入 2

4 4 11
1 6 8 9
1 2 3 4

样例输出 2

0

样例输入 3

6 2 11
11 12 22 23 33 34
0 1

样例输出 3

2
1 0
10 1