010 - PROBOT

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / x 4 /


TLE
1sec
MLE
256MB
得点
100

問題

入出力例の画像を見た方がわかりやすいと思います。

縦 $H$ マス、横 $W$ マスの白い盤面がある。
盤面の左から $x$ マス、上から $y$ マスの位置にあるマスを $(x, y)$ と表記する。
左上のマスは $(1,1)$, 右下のマスは $(W, H)$ である。

この盤面の $H \times W$ マスのうち $N$ マスに印を付ける。
印には $1 〜 N$ までの番号が付けられている。$i$ 番目の印は「印 $i$」と呼び、 $(x_i, y_i)$ のマスに位置している。

あなたは以下の性質を持つロボット「PRO-1719」を持っている。

  • 印のないマスでは、自分の向いている方向に向かって直進する。
  • 印のあるマスでは、自分の向く方向を転換できる。(転換しなくてもよい)
  • 向くことのできる方向は、上、下、左、右 の4方向のみである。
  • 盤面外へ出てしまった場合は、壊れる。

さて、次のようなとてもおもしろいゲームがある。

  1. 盤面上のいずれかの印付きマスをスタート地点、それとは別の印付きマスをゴール地点と決める。
  2. スタートマスに「PRO-1719」を{上,下,左,右}のいずれかの好きな向きで配置して発進させる。
  3. 印付きマスを適切に経由・適切に方向転換させることを繰り返してゴールマスにたどり着いたらゲームクリア。YTAとじゃんけんできる。
  4. 盤面外へ出てしまって壊す、またはゴールへたどり着けなくてリタイアした場合は残念賞。YTAから冷凍のお言葉をいただく。

あなたは、スタートマスとゴールマスの選び方によっては絶対にゴールできない場合があることを知った。
$Q$ 回にわたってスタートマスとゴールマスの位置のセットが与えられるので、各セットにおいて、ゲームクリアできるか調べてほしい。

入力形式

H W N
x1 y1
x2 y2
 :
xN yN
Q
s1 g1
s2 g2
 :
sQ gQ

1行目に、盤面の縦と横のマス数 $H$, $W$ と 印付きマスの個数 $N$ が入力される。
続く$N$行に、$i$ 番目の印付きマスの座標 $(x_i, y_i)$ が入力される。
次行に、スタート地点とゴール地点のセットの数 $Q$ が入力される。
以下 $Q$ 行、スタートの印付きマスの番号 $s$ と ゴールの印付きマスの番号 $g$ が入力される。

出力形式

各スタート・ゴールのセットについて、適切に方向転換してゴールへたどり着ける場合は "yes", たどり着けない場合は "no" を改行区切りで出力せよ。

制約

  • 入力は全て整数である
  • $1 \le H,W \le 10^{5}$
  • $1 \le N \le 10^{5}$
  • $1 \le x_i \le W$
  • $1 \le y_i \le H$
  • 印のマスの位置は重複しない
  • $1 \le Q \le 10^{5}$
  • $1 \le s,g \le N$
  • $s \neq g$

入出力例

入力例1

3 5 4
2 1
5 3
3 2
2 3
2
1 2
1 3

出力例1

yes
no

1つめのセットでは、印 $1$ がスタート、印 $2$ がゴールである。
印 $1$ を下向きで発進して印 $4$ で右向きに方向転換すれば印 $2$ へたどり着ける。

2つ目のセットでは、どうやっても印 $1$ から 印 $3$ へたどり着くことはできない。
ありがたく冷凍のお言葉をいただこう。


※印の中の数字は、印の番号を表している。


入力例2

100 100 5
2 1
2 8
5 8
5 3
7 3
1
1 5

出力例2

yes

印つきマスを $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ の順にたどっていけばゴールできる。