問題文
この「ただ奇妙な異世界 (Just Odd Isekai)」でも、夜空には星が浮かびます。
夜空は左右 $W$ マス上下 $H$ のマス目で、星はそのうちの $1$ マスで表されます。
左から $x$ 番目、下から $y$ 番目のマスを $(x,y)$ と表します。
$i$ 番目の星の場所は $(x_i, y_i)$ です。
この世界の「占い師」の仕事は、星が全く写っていないような写真を撮ることです。
あなたは、この「占い師」からの $Q$ 個の質問に答えるプログラムを作成する必要があります。
各質問では $4$ つの整数 $X,A,S,T$ が与えられるので、以下の条件を満たす写真の範囲をとれるような正整数 $P$ の最大値を求めて出力してください。そのような正整数 $P$ が存在しなければ、代わりに $0$ を出力してください。
- 写真の範囲は、夜空のうち左右 $SP$ マス、上下 $TP$ マスの連続した領域である。
- 写真の範囲には星が含まれない。
- 写真の範囲は $(X,A)$ を含む。
- $2\leq A$ の場合、写真の範囲は $(X,A-1)$ を含まない。
下の図は、 $S=T=1$ において必要な条件を満たす写真（の撮影範囲）と満たさない写真の例を表しています。細い線の長方形が夜空、太い線の長方形が写真の範囲、黒のマスが星、青のマスが $(X,A)$ です。
- 上左 : $P=5$ のよい写真です。
- 上中央 ： $P=3$ のよい写真ですが、 $P$ が最大ではありません。
- 上右 ： 星を含んでいるため不適です。
- 下左 ： 写真の範囲が左右 $SP$ 、上下 $TP$ の長方形ではありません。
- 下中央 ： $(X,A-1)$ が範囲に含まれているため不適です。
- 下右 ： $(X,A)$ が範囲に含まれていないため不適です。
制約例
- 値はすべて整数
- $1 \leq W \leq 1\, 000\, 000\, 000 = 10^9$
- $1 \leq H \leq 1\, 000\, 000\, 000 = 10^9$
- $1 \leq N \leq 200\, 000$
- $1 \leq x_i \leq W$
- $1 \leq y_i \leq H$
- $i \neq j$ ならば、 $(x_i, y_i) \neq (x_j, y_j)$
- $1 \leq Q \leq 200\, 000$
- $1 \leq X \leq W$
- $1 \leq A \leq H$
- $1 \leq S \leq W$
- $1 \leq T \leq H$
入力
$Q$ 個の質問を質問 $1$ 、質問 $2$ 、 $\ldots$ 、質問 $Q$ とします。質問 $i$ で与えられる $A,X,S,T$ を $A_i,X_i,S_i,T_i$ と表します。
入力は以下の形式で与えられます。
$W$ $H$ $N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$
$Q$
$X_1$ $A_1$ $S_1$ $T_1$
$X_2$ $A_2$ $S_2$ $T_2$
$\vdots$
$X_Q$ $A_Q$ $S_Q$ $T_Q$
出力
$Q$ 行出力してください。 $i$ 行目には、質問 $i$ の答えとなる整数を出力してください。
入出力例
入力例 1
10 10 6
10 1
3 2
8 4
6 8
2 9
9 10
5
5 3 1 1
4 1 1 2
3 2 1 1
10 5 4 4
10 5 1 6出力例 1
5
3
0
1
1$1$ つ目の質問は問題文中の図と同じ状況です。 $P$ の最大値は $5$ です。
$3$ つ目の質問において、 $(X,A)$ には星があるため、適切な写真の範囲が存在しません。よって $0$ を出力する必要があります。
解けたらマシュマロでもください
