说明

给出一个n * m的矩阵M，和两个整数a和b，判断是否可以通过重复选择a * b的子矩阵并使子矩阵中所有元素的值减1，使得矩阵M中的所有元素变为0。如果可行，输出"^_^" , 否则输出"QAQ"

输入格式

第一行包括一个整数T (1 <= T <= 100), 表示测试用例的组数

对于每组测试用例:

第一行包括四个整数n,m,a,b(1 <= n, m <= 1000, 1 <= a <= n, 1 <= b <= m), 分别表示给出的矩阵大小和选择的子矩阵大小

接下来n行每行m个数M(i, j) (0 <= M(i, j) <= 1e9), 表示矩阵中(i, j)位置的元素

数据保证在所有测试用例下n * m <= 1e6

输出格式

输出T行, 每行一个字符串"^_^" or "QAQ", 表示每组测试用例的结果

样例

2
2 2 1 2
1 2
1 2
2 3 1 2
1 2 1
1 2 1

QAQ
^_^

提示

对于第二个测试用例, 一种可行的选择是

(1,1)−(1,2), (1,2)−(1,3), (2,1)−(2,2), (2,2)−(2,3)

使得原矩阵为空