Communication Jamming

JOI 国は平面上に存在する．N 個の村があり，村には 1 から N までの番号がついている．村 i は座標 (i, 0) に存在する点とみなす．現在，JOI 国では村を接続する通信回線を整備しようとしている．障害に備え，通 信回線は二系統整備される予定である．これらを系統 1 と系統 2 と呼ぶ．

系統 k には，ハブが Mk 個存在し，回線が N + Mk − 1 本ある．系統 k のハブには 1 から Mk までの番号 がついており，ハブ j は座標 (Xkj, Ykj) に存在する点とみなす．系統 k の各回線は，村と系統 k のハブ，ま たは系統 k のハブ同士を接続する．各回線は，両端を結ぶ線分とみなす．任意の 2 つの回線は端点同士以 外で共有点を持たないようになっていることが保証されている．系統 1 のハブ j の y 座標 Y1j は 0 より大 きい．また，系統 2 のハブ j の y 座標 Y2j は 0 より小さい．

ある 2 つの地点が通信できるとは，それらの地点が回線により間接的に接続されていることとする．す なわち，回線に沿った移動を繰り返して，片方の地点からもう片方の地点へ移動できるならば，その 2 つ の地点は通信ができる．系統 1 の回線のみを考えても，系統 2 の回線のみを考えても，任意の 2 つの村及 びハブは通信可能である．

下図は通信回線の例である．灰色の円は系統 1 のハブ，黒い円は系統 2 のハブ，白い円は村を表す．

図 1: 通信回線の例 1	図 2: 通信回線の例 2

計画を検討するにあたって，外部からの攻撃で，どの程度攻撃を受けても通信が可能であるかを調べた い．外部からの攻撃は，2 つの数 A, B (A ≥ 0, B ≤ 0) により表現され，y 座標が A より大きい全てのハブと y 座標が B より小さい全てのハブを破壊するものと想定している．ハブが破壊されると，そこを経由した 通信は行えなくなる．

村や各系統の情報が与えられる．また，Q 個のクエリが与えられる．各クエリ q は 1 つの整数 Aq で表 され，y 座標が Aq より大きい全てのハブが破壊される場合を意味する．各クエリに対し，加えて y 座標が いくつ未満のハブまでであれば破壊されても全村間の通信が可能であるかを答えよ．すなわち，整数 Bq で あって，y 座標が Aq より大きい全てのハブと y 座標が Bq より小さい全てのハブを破壊しても全村間の通 信が可能であるような最大の Bq (Bq ≤ 0) を答えよ．

標準入力から以下の入力を読み込め．

• 1 行目には 4 つの整数 N, M1, M2, Q が空白を区切りとして書かれている．

• 続く M1 + (N + M1 − 1) 行には，系統 1 の情報が書かれている．

  • 最初の M1 行の i 行目 (1 ≤ i ≤ M1) には，2 つの整数 X1i, Y1i が書かれている．

  • 続く N + M1 − 1 行の i 行目 (1 ≤ i ≤ N + M1 − 1) には，回線 i の情報を表す 3 つの整数 T1i, C1i, D1i が書かれている (T1i = 1, 2)．

    • T1i が 1 のとき，回線 i は村 C1i とハブ D1i を接続する (1 ≤ C1i ≤ N かつ 1 ≤ D1i ≤ M1)．
    • T1i が 2 のとき，回線 i はハブ C1i とハブ D1i を接続する (1 ≤ C1i, D1i ≤ M1 かつ C1i ≠ D1i)．

  • 続く M2 + (N + M2 − 1) 行には，系統 2 の情報が書かれている．

    • 最初の M2 行の i 行目 (1 ≤ i ≤ M2) には，2 つの整数 X2i, Y2i が書かれている．

    • 続く N + M2 − 1 行の i 行目 (1 ≤ i ≤ N + M2 − 1) には，回線 i の情報を表す 3 つの整数 T2i, C2i, D2i が書かれている (T2i = 1, 2)．

      • T2i が 1 のとき，回線 i は村 C2i とハブ D2i を接続する (1 ≤ C2i ≤ N かつ 1 ≤ D2i ≤ M2)．
      • T2i が 2 のとき，回線 i はハブ C2i とハブ D2i を接続する (1 ≤ C2i , D2i ≤ M2 かつ C2i ≠ D2i)．

• 続く Q 行の i 行目 (1 ≤ i ≤ Q) には 1 つの整数 Ai が書かれている．

標準出力に Q 行出力せよ．i 行目 (1 ≤ i ≤ Q) には，クエリ i への答えを表す整数 Bi を出力せよ． 答えが 0 の場合，-0 と出力してはならない．

• 1 ≤ N, M1, M2 5 100 000.
• −1 000 000 000 ≤ X1i ≤ 1 000 000 000 (1 ≤ i ≤ M1).
• −1 000 000 000 ≤ X2i ≤ 1 000 000 000 (1 ≤ i ≤ M2).
• 1 ≤ Y1i ≤ 1 000 000 000 (1 ≤ i ≤ M1).
• −1 000 000 000 ≤ Y2i ≤ −1 (1 ≤ i ≤ M2).
• X1i, X1j または Y1i, Y1j (1 ≤ i, j ≤ M1 かつ i , j).
• X2i, X2j または Y2i, Y2j (1 ≤ i, j ≤ M2 かつ i , j).
• 1 ≤ Q ≤ 100 000.
• 0 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ Q).
• 任意の 2 つの回線は端点同士以外で共有点を持たない．
• 系統 1 の回線のみを考えても，系統 2 の回線のみを考えても，任意の 2 つの村及びハブは通信可能 である．