問題ヴィジュアル

問題文

女子校に通っている女子高生のチェリーちゃんは, この夏仲間と一緒に海に行くことになった. そのため, 水着販売店「チェリーリゾート」へ行き, 水着を買うことになった.

チェリーちゃんは「チェリーリゾート」で発売されている $N$ 種類のトップと $M$ 種類のボトムからそれぞれ $1$ つを選んで買うことにした.

それぞれのトップとボトムには値段と色が以下のように設定されている. ここで, 価格は正の整数, 色は $1$ 以上 $K$ 以下の整数で表される.

• $i=1,2,\dots,N$ に対して, $i$ 番目のトップの価格は $T_i$ であり, 色は $C_i$ である.
• $j=1,2,\dots,M$ に対して, $j$ 番目のボトムの価格は $B_j$ であり, 色は $D_j$ である.

「チェリーリゾート」ではトップとボトムを $1$ つずつ買った場合, 以下のようにしてセット価格が決定される.

• トップとボトムの色が異なる場合: トップとボトムの価格の和である.
• トップとボトムの色が同じ場合: トップとボトムの (同じ) 色を $k$ として, トップとボトムの価格の和から $S_k$ を引いた価格である.

なお, どのセットについても, セット価格は正の整数であることが保証されている.

「チェリーリゾート」におけるトップとボトムのセットは $NM$ 通り考えられる.

このうち, チェリーちゃんはその $NM$ 通り全てのセット価格を考えたときの昇順 (価格が安い方から数え, 同じ値段のセットも区別して) $P$ 番目になるトップとボトムのセット $1$ つを買うことにした.

では, チェリーちゃんが買うと思われる, $NM$ 通り全てのセット価格を考えたときの昇順 $P$ 番目になり得るトップとボトムのセットを $1$ つ挙げよ.

$Q$ 個のテストケースについて答えよ.

制約

• $1 \leq Q \leq 6 \times 10^4$
• 各テストケース毎の制約
  • $1 \leq N \leq 6 \times 10^4$.
  • $1 \leq M \leq 6 \times 10^4$.
  • $1 \leq K \leq N + M$.
  • $1 \leq P \leq NM$.
  • $1 \leq T_i \leq 10^9 \quad (1 \leq i \leq N)$.
  • $1 \leq C_i \leq K \quad (1 \leq i \leq N)$.
  • $1 \leq B_j \leq 10^9 \quad (1 \leq j \leq M)$.
  • $1 \leq D_j \leq K \quad (1 \leq j \leq M)$.
  • $1 \leq S_k \leq 2 \times 10^9 \quad (1 \leq k \leq K)$.
  • $C_i = D_j = k$ ならば, $T_i + B_j - S_k > 0$ である $\quad (1 \leq i \leq N, 1 \leq j \leq M, 1 \leq k \leq K)$.
• テストファイル全体の制約
  • $Q$ 個のテストケースにおける $N$ の総和は $6 \times 10^4$ 以下である.
  • $Q$ 個のテストケースにおける $M$ の総和は $6 \times 10^4$ 以下である.
  • 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.

$Q$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_Q$

各テストケースは以下の形式である.

$N$ $M$ $K$ $P$
$T_1$ $T_2$ $\dots$ $T_N$
$C_1$ $C_2$ $\dots$ $C_N$
$B_1$ $B_2$ $\dots$ $B_M$
$D_1$ $D_2$ $\dots$ $D_M$
$S_1$ $S_2$ $\dots$ $S_K$

出力

出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ テストケースには, 第 $q$ テストケースに対する解答を以下で説明する方法で出力せよ.

「$I$ 番目のトップと $J$ 番目のボトムのセット」を解答するとき, $I, J$ をこの順で空白区切りで出力せよ. つまり, 以下の形式で出力せよ.

$I$ $J$

最後に改行を忘れないこと.

なお, この形式に沿っていない出力に関するジャッジの結果は不定である (WA になるとは限らない).

サンプル

3
2 2 3 2
100 150
1 2
200 250
2 3
50 100 150
3 4 7 10
10 10 10
1 2 3
10 10 10 10
4 5 6 7
1 2 3 4 5 6 7
10 10 9 46
31415 92653 58979 32384 62643 38327 95028 84197 16939 93751
3 9 5 3 6 3 9 8 1 9
14142 13562 37309 50488 1688 72420 96980 78569 67187 53769
2 2 9 8 8 8 2 8 9 7
2718 2818 2845 9045 2353 6028 7471 3526 6249

1 1
3 2
6 9