問題文
为了给妈妈送筷子礼物,诺伊米酱和诺伊姆君决定与筷子制作师高桥老师一起制作筷子。 筷子是指长度相等的木片组合。
N 已准备好了蓝色木片 N 已准备好了黄色木片,分别是 1 减去 N 被赋予了编号。 i 第几根蓝色木片的长度是 A_i、i 第几根黄色木片的长度是 B_i 。另外,A_i 同士、B_i 彼此彼此各不相同。
的小意味和小意味君想要送给妈妈 K 一本筷子作为礼物。 高桥老师 2 为了某个人 K 决定准备不同长度的红色木片,每种各 2 一根。 i 第几种红色木片的长度为 C_i ,这些需要彼此不同。
2 人和高桥老师通过重复以下步骤 K 次来制作筷子。 K 第 i 次操作如下。
- 现阶段留在红色木片中的小闪选出长度为 C_{L_i} 和长度 给出了 C_{R_i} 的木片,并将它们连接起来,交给高桥老师长度为 C_{L_i} + C_{R_i} 的木片。
- 小闪 S_i 号蓝色木片和 T_i 号黄色木片连接起来,如果长度为 A_{S_i} + B_{T_i} 的木片。
- 2 的木片长度差是 M 的倍数,高桥老师就会把长度为 M 的木片连在一起做成筷子。否则,做筷子就失败了。
的诺依酱已经决定了 L_i, R_i 。通过高桥老师与诺依君适当地决定 C_i, S_i, T_i ,可以判断是否能完成 K 双筷子,如果可能的话,这样的决定在 1 请输出一个。
制約
- 所有输入均为整数。
- N = 2 \times 10^5
- M = 10 ^ 6 + 3 (素数)
- K = 4 \times 10 ^ 4
- 1 \le A_i, B_i \le M
- A_i 是不同的。
- B_i 是不同的。
- 1 \le L_i, R_i \le K
- 各 x(1 \le x \le K) 是 您也可以写 L_i, R_i 中恰好出现 2 次。
入力
输入是按以下格式从标准输入给出的。
N M K A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N L_1 R_1 \vdots L_K R_K
出力
如果不可能,则输出 -1 。如果可能,按照以下格式表示 K+1 行。
C_1 C_2 \ldots C_K S_1 T_1 \vdots S_K T_K
但是, 运算前设定中包含的S_i, T_i 分别是 它总是能被 i 次操作中诺依君选择的蓝色和黄色木片的编号。此外,输出必须满足以下条件。
- 1 \le C_i \le M
- C_i 是不同的。
- 1 \le S_i, \, T_i \le N
- S_i 是不同的。
- T_i 是不同的。
- A_{S_i} + B_{T_i} \equiv C_{L_i} + C_{R_i} \pmod M
入力例1
3 5 3 1 3 4 1 2 4 1 1 2 3 3 2
但是,这个样例不符合限制条件,因此不包含在测试用例中。。
出力例1
2 3 5 2 1 3 3 1 2
高桥老师准备的 3 各种红色木片的长度依次为,2, 3, 5 。
1 在第 回操作中,乃依米酱 1 第 种红色木片 2 选择后连接制作长度为 4 的木片。 野井君 2 号蓝色木片和 1 第黄色木片连接后制作长度为 4 的木片。 2 金木片的长度一致,因此高桥老师无需进行任何操作。
2 在第 回操作中,乃依米酱 2 第种红色木片和 3 第种红色木片连接后制作长度为 8 的木片。 野井君 3 号蓝色木片和 3 第黄色木片连接后制作长度为 8 的木片。 2 金木片的长度一致,因此高桥老师无需进行任何操作。
3 在第 回操作中,乃依米酱 3 第种红色木片和 2 第种红色木片连接后制作长度为 8 的木片。 野井君 1 号蓝色木片和 2 第黄色木片连接后制作长度为 3 的木片。 高桥老师在野井君制作的木片上长度 5 的木片 1 通过加上...长度会变为 8 的木片。 根据
以上,3 书籍的筷子已经完成。