← 返回题目列表

AtCoder · utpc2020_k

K. 专用筷子

中文机器翻译题面 查看原题

問題文

为了给妈妈送筷子礼物,诺伊米酱和诺伊姆君决定与筷子制作师高桥老师一起制作筷子。 筷子是指长度相等的木片组合。

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 次操作如下。

  1. 现阶段留在红色木片中的小闪选出长度为 C_{L_i} 和长度 给出了 C_{R_i} 的木片,并将它们连接起来,交给高桥老师长度为 C_{L_i} + C_{R_i} 的木片。
  2. 小闪 S_i 号蓝色木片和 T_i 号黄色木片连接起来,如果长度为 A_{S_i} + B_{T_i} 的木片。
  3. 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 书籍的筷子已经完成。