AT_pakencamp_2025_day2_e Grand Paken

パケン王国の一角にある建物、グランド・パケンは縦 $ H $ 行、横 $ W $ 列の長方形の形をしており、内部は $ 1 \times 1 $ の正方形の区画に分割されている。上から $ a $ 列目、左から $ b $ 列目の区画を区画 $ (a,b) $ と呼ぶ。グランド・パケンには $ N $ 個の出口があり、 $ i $ 個目の出口は区画 $ (A_{i},B_{i}) $ に位置している。 --- ある晴天の日、グランド・パケンで、火災が発生した。 火災の発生源は $ M $ 箇所あり、 $ i $ 個目の発生源は $ (C_i,D_i) $ にある。すべての火災は 時刻 $ 0 $ に同時に発生する。 火災は単位時間 $ 1 $ ごとに上下左右に隣接する区画へ広がる。区画 $ (x,y) $ が時刻 $ t $ に **燃えている** とは、ある火災発生源からのマンハッタン距離が $ t $ 以下であることをいう。なお、区画は一度燃え始めるとその後も燃え続ける。 --- 救助隊として派遣されたあなたは、建物の中に取り残された人々を助けるため、次の $ Q $ 個のクエリに答える必要がある。 $ i $ 番目のクエリでは、次の状況を考える。 - 時刻 $ 0 $ に、人が区画 $ (X_{i},Y_{i}) $ にいる。 - 人は単位時間 $ 1 $ ごとに上下左右に隣接する区画へ移動できる。 - 人は、滞在する全ての時刻に置いて、その区画がまだ燃えていない場合にのみ行動できる。 すなわち、人がある区画に時刻 $ t $ に到達するためには、その区画が燃え始める時刻が $ t $ より厳密に大きくなければならない。この条件の下で、その人がいずれかの出口のある区画に到達できるかを判定せよ。到達可能であれば `Yes`、不可能であれば `No` を出力せよ。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $ $ M $ $ C_1 $ $ D_1 $ $ \vdots $ $ C_M $ $ D_M $ $ Q $ $ X_1 $ $ Y_1 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### 小課題 1. ( $ 10 $ 点) $ H \times W \leq 300 $ 2. ( $ 20 $ 点) $ H,W \leq 300 $ 3. ( $ 30 $ 点) $ H,W \leq 2000 $ 4. ( $ 40 $ 点) 追加の制約はない ### Sample Explanation 1 $ 1,2 $ つ目のクエリについて、どのような移動を行ったとしても条件を満たして移動することはできません。 $ 3 $ つ目のクエリについて、人は時刻 $ 0 $ に $ (1,5) $ にいます。時刻 $ 1 $ に $ (2,5) $ に移動することによって、条件を満たして移動することができます。 $ (2,5) $ は時刻 $ 3 $ から燃え始めます。 ### Constraints - $ 1 \le H, W \le 2 \times 10^5 $ - $ 1 \le N, M, Q \le 2 \times 10^5 $ - $ 1 \le A_i \le H $ - $ 1 \le B_i \le W $ - $ 1 \le C_i \le H $ - $ 1 \le D_i \le W $ - $ 1 \le X_i \le H $ - $ 1 \le Y_i \le W $ - 入力は全て整数