2 次元のハッシュテーブルを使おう (paizaランク B 相当)

今までは 1 つのハッシュ値をキーとしてハッシュテーブルを作成していましたが、今回は入力から 2 種類のハッシュ値を計算し、2 次元のハッシュテーブルを作成してみましょう。

N 個の点の X 座標を表す数列 X_1, X_2, ..., X_N と Y 座標を表す数列 Y_1, Y_2, ..., Y_N が与えられます。(X_i, Y_i) (1 ≦ i ≦ N) が点 i の座標を表します。入力で与えられる整数 A と B を用いたハッシュ関数 Hx(X) = X % A と Hy(Y) = Y % B を用いて、この N 個の座標データを 2 次元のハッシュテーブルに格納してください。ハッシュテーブルは A × B の 2 次元配列とし、配列の各要素にはデータのリストを格納することとします。なお、各要素の初期値は空リストとします。また、このハッシュテーブルにはチェイン法を採用し、各リストに複数のデータが含まれる場合は、格納した順番にデータが並ぶように実装してください。

その後、M 個の整数の組 (p_j, q_j) (1 ≦ j ≦ M)が与えられます。ハッシュテーブルの p_j 行目の q_j 列目のリストにデータが存在するなら、最後にそのリストに追加されたデータを出力し、データが存在しないなら -1 を出力してください。

入力例 1 を用いてハッシュテーブルの動きを説明します。A = 10、B = 5 です。

最初に格納するデータは (17,188) です。X 座標のハッシュ値は 17 % 10 = 7、Y 座標のハッシュ値は 188 % 5 = 3 であるので、7 行目の 3 列目の位置にあるリストにデータ (17,188) を格納します。リストは [(17,188)] となります。

次に格納するデータは (777, 265) で X 座標のハッシュ値は 7、Y 座標のハッシュ値は 0 となるので、7 行目の 0 列目の位置にあるリストにデータ (777, 265) を格納します。リストは [(777,265)] となります。

次に格納するデータは (137, 63) で X 座標のハッシュ値は 7、Y 座標のハッシュ値は 3 となるので、7 行目の 3 列目の位置にあるリストにデータ (137, 63) を格納します。リストは [(17,188),(137,63)] となります。

以上で全データの格納が終了しました。ハッシュテーブルの状態は、

[[],[],[],[],[]]
[[],[],[],[],[]]
[[],[],[],[],[]]
[[],[],[],[],[]]
[[],[],[],[],[]]
[[],[],[],[],[]]
[[],[],[],[],[]]
[[(777,265)],[],[],[(17,188),(137,63)],[]]
[[],[],[],[],[]]
[[],[],[],[],[]]
[[],[],[],[],[]]

となります。

よって、0 行目の 0 列目のリストにはデータが存在しないので -1 と出力し、7 行目の 3 行目のリストにはデータが存在するので、最後に追加されたデータである 137 63 を出力します。