A - Equal Weight 解説 /

実行時間制限: 2 sec / メモリ制限: 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 つの握りを作ることはできません。