AT_utpc2020_k Special Chopsticks

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_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 $ $ 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 $ 条件を満たす解が複数存在する場合は、どれを出力してもよい。

### 制約 - 入力は全て整数である。 - $ 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 $ 回現れる。 ### Sample Explanation 1 ただし、このサンプルは制約を満たしていないため\*\*テストケースには含まれない\*\*ことに注意してください。 高橋先生が用意した $ 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 $ 本のお箸が完成しました。