题目背景

出题	标程	数据	验题	题解
RedNebula		RedNebula and gyyyyx	gyyyyx	RedNebula

RedNebula 和 JF 在下一盘棋，然后……

题目描述

现在有一个 $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 代表放置了棋子的位置。

初始状态：

011
100
011

对于第一个询问，可以证明 $(1,2)$ 处的棋子无法移出 $(1,2)$ 到 $(2,3)$ 的矩阵。

对于第二个询问，考虑把 $(3,2)$ 处的棋子移到 $(2,3)$，得：

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()，其作用是返回输入中的一个非负整数，同时读取其后的一个字符。

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;
}