#6256. 「CodePlus 2017 12 月赛」可做题1

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

“CodePlus 比赛的时候在做什么?有没有空?能来解决停机问题吗?” qmqmqm 这样问 sublinekelzrip。

当然,sublinekelzrip 并不会停机问题,所以 qmqmqm 改为提出了另一个题目,现在请你帮助 sublinekelzrip 解决这个题目。


这个问题是这样的:

对于任何一个 nn 阶方阵,若任意从其中选择 nn 个不同行不同列的位置,其上的权值之和均相等,则我们称这个矩阵是巧妙的。注意对于 n=1n=1 的任何矩阵都是巧妙的。 例如矩阵 123456789\begin{matrix}1&2&3\\4&5&6\\7&8&9\end{matrix} 是巧妙的,因为 1+5+91+5+9 == 1+6+81+6+8 == 2+4+92+4+9 == 2+6+72+6+7 == 3+5+73+5+7 == 3+4+83+4+8 =15=15,而矩阵 1221\begin{matrix}1&2\\2&1\end{matrix} 不巧妙,因为 1+12+21+1 \neq 2+2

现在有一个 n×mn \times m 大小的矩阵 MM 以及 TT 个询问,每次询问其一个子方阵是否是巧妙的。

输入格式

从标准输入读入数据。

输入第一行包含三个正整数 n,m,Tn,m,T

之后 nn 行每行 mm 个空格分割的非负整数,表示矩阵 MM

之后 TT 行每行 33 个正整数 x,y,kx,y,k,表示询问第 xx 行第 yy 列为左上角的 kk 阶方阵是否是巧妙的。保证这个矩阵完全位于 MM 之中。

输出格式

输出到标准输出。

输出包含 TT 行每行一个字符 Y 或者 NY 表示被询问的方阵是巧妙的,N 表示不是。

样例

样例输入
3 3 4
1 1 1
1 1 1
1 1 2
1 1 2
1 1 3
2 2 2
2 1 2
样例输出
Y
N
N
Y

数据范围与提示

测试点 max(n,m)\max(n,m) TT 其他
1 =5=5 =5=5
2 =100=100 =20=20
3
4
5 =500=500
6
7 =100000=100000 矩阵MM的元素在值域内等概率随机
8
9
10

对于所有的数据,0Mij1090 \leq M_{ij} \leq 10^91xn1 \leq x \leq n1ym1 \leq y \leq m


来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/卢政荣 命题/卢政荣 验题/吕时清,王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。