Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋くんは寿司職人です。 今高橋くんの前には、0 から N-1 までの番号のついた N 個のシャリと、0 から M-1 までの番号のついた M 個のネタがあります。 シャリ i の重さは A_i です。 また、ネタ i の重さは B_i です。
高橋くんは、寿司の握りを 2 つ作りたいです。 1 つの握りは、ちょうど 1 つのシャリとネタを組み合わせることで作られます。
高橋くんは、2 つの握りの重さが等しくなるようにしたいです。 これが可能かどうか判定し、可能ならば作り方を 1 つ示してください。 なお、同じシャリやネタを 2 回使うことはできません。
制約
- 2 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 2 \times 10^5
- 1 \leq A_i \leq 10^6
- A_i \neq A_j (i \neq j)
- 1 \leq B_i \leq 10^6
- B_i \neq B_j (i \neq j)
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_0 A_1 \cdots A_{N-1} B_0 B_1 \cdots B_{M-1}
出力
重さの等しい 2 つの握りが作れる場合は、 4 つの整数 x,y,z,w (0 \leq x,z \leq N-1,\ 0 \leq y,w \leq M-1,\ x \neq z,\ y \neq w) を空白区切りで出力せよ。 これは、シャリ x とネタ y を組み合わせた握りと、シャリ z とネタ w を組み合わせた握りを作ることを意味する。 解が複数存在する場合、どれを出力しても正解と判定される。
重さの等しい 2 つの握りが作れない場合は、-1 を出力せよ。
入力例 1
3 4 1 2 4 3 6 10 15
出力例 1
0 1 2 0
シャリ 0 とネタ 1 を組み合わせた握りの重さは 1+6=7 です。
また、シャリ 2 とネタ 0 を組み合わせた握りの重さは 4+3=7 です。
よって、0 1 2 0
という出力は正解と判定されます。
入力例 2
3 3 3 2 1 30 20 10
出力例 2
-1
重さの等しい 2 つの握りを作ることはできません。