「JEOI-R1」棋

| 出题 | 标程 | 数据 | 验题 | 题解 | | -----------: | -----------: | -----------: | -----------: | -----------: | | [RedNebula](/user/478829) | [RedNebula](/user/478829) | [RedNebula](/user/478829) and [gyyyyx](/user/554574) | [gyyyyx](/user/554574) | [RedNebula](/user/478829) | [RedNebula](/user/478829) 和 [_JF_](/user/361141) 在下一盘棋，然后……

现在有一个 $n\times m$ 的棋盘，从上到下依次是 $1\sim n$ 行，从左到右依次是 $1\sim m$ 列，一个位于第 $x$ 行第 $y$ 列的位置被标记为 $(x,y)$。共有 $c$ 个棋子，**不重叠**地摆放在棋盘的某些位置上。一个位于 $(x,y)$ 的棋子可以走向 $(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y+1)$（如果这些位置**存在**且其上**没有棋子**）。 现有若干询问，每次询问给定 $x_1,y_1,x_2,y_2,p$，然后给定 $p$ 个位置，表示一个子矩阵的左上角位置为 $(x_1,y_1)$，右下角位置为 $(x_2,y_2)$，问是否可以移动棋子（无次数限制）使得矩阵内**有且仅有**给定的 $p$ 个位置上有棋子。**询问之间相互独立。** 为了减少程序时间复杂度的常数影响，**建议使用更快的读入方式。**

第一行三个正整数 $n,m,c$，表示棋盘的列数、行数和已有的棋子数。 接下来 $c$ 行，一行两个整数 $a_i,b_i$，表示有一个棋子位于 $a_i$ 行 $b_i$ 列处。 接下来一行一个正整数 $q$。 接下来 $q$ 组询问。每一组询问第一行是五个正整数 $x_1,y_1,x_2,y_2,p$，接下来 $p$ 行每行两个正整数 $c_i,d_i$，表示只希望矩阵内有棋子的位置。

对于每个询问，如果可以移动棋子（无次数限制）使得矩阵内有且仅有给定的位置上有棋子，输出 `YES`，否则输出 `NO`。

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

NO
YES
NO

**【样例解释 \#1】** 解释以 `0` 代表空位，`1` 代表放置了棋子的位置。 初始状态： ```plain 011 100 011 ``` 对于第一个询问，可以证明 $(1,2)$ 处的棋子无法移出 $(1,2)$ 到 $(2,3)$ 的矩阵。 对于第二个询问，考虑把 $(3,2)$ 处的棋子移到 $(2,3)$，得： ```plain 011 101 001 ``` 满足询问要求。移动方式不唯一。 对于第三个询问，可以证明 $(2,1)$ 处的棋子无法移出 $(1,1)$ 到 $(2,3)$ 的矩阵。 **【数据范围】** 对于 $25\%$ 的数据，$n,m,q\le 10$，$c\le 20$。 对于另外 $25\%$ 的数据，保证 $a_i+b_i\equiv 0 \pmod 2$，$c_i+d_i\equiv 0 \pmod 2$。 对于另外 $25\%$ 的数据，保证 $n\cdot m-c\le(x_2-x_1+1)\cdot (y_2-y_1+1)-p$。 对于 $100\%$ 的数据，$2\le n,m\le 10^5$，$1\le c,q\le 10^5$，$c\le n\cdot m$，$1\le a_i\le n$，$1\le b_i\le m$，$\sum p\le 2\times 10^5$。对于每个询问，$1\le p\le (x_2-x_1+1)\cdot (y_2-y_1+1)$，$x_1\le c_i\le x_2$，$y_1\le d_i\le y_2$。 **【提示与说明】** 提供一种较快的读入一个 `int` 类型非负整数的方式。调用下文中的 `read()`，其作用是返回输入中的一个非负整数，同时读取其后的一个字符。 ```cpp int read() { int x(0); char c(getchar()); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } ```