/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
のいみちゃんとのいむくんはお母さんにお箸をプレゼントするため、箸作り職人の高橋先生とお箸を作ることにしました。 お箸とは、長さが等しい木片の組のことです。
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 本のお箸が完成しました。