Камила и Даниэль — непревзойдённые соперники по головоломкам в Мексике. Много лет они состязались друг с другом в самых сложных числовых играх страны, а теперь обратили внимание на вас. Вы хотите доказать им, что способны соревноваться на их уровне, и потому они предлагают вам следующую задачу.
Даны две квадратные матрицы $$$a$$$ и $$$b$$$ размера $$$n \times n$$$. Подматрица $$$(r_1, c_1, r_2, c_2)$$$ матрицы состоит из элементов в строках с $$$r_1$$$-й по $$$r_2$$$-ю и столбцах с $$$c_1$$$-го по $$$c_2$$$-й. Строки нумеруются от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — от $$$1$$$ до $$$n$$$ слева направо.
За один ход над подматрицей $$$a$$$ вы выбираете одну из её строк или один из её столбцов и прибавляете произвольную константу (возможно, отрицательную) ко всем элементам этой строки или этого столбца внутри подматрицы. Подматрица $$$(r_1, c_1, r_2, c_2)$$$ матрицы $$$a$$$ называется сопоставимой, если некоторой последовательностью ходов её можно сделать равной такой же подматрице матрицы $$$b$$$. Иными словами, она сопоставима тогда и только тогда, когда можно выбрать значение $$$h_i$$$ для каждой строки $$$i$$$ и значение $$$w_j$$$ для каждого столбца $$$j$$$ так, чтобы $$$a_{i,j} + h_i + w_j = b_{i,j}$$$ выполнялось для всех $$$r_1 \le i \le r_2$$$ и $$$c_1 \le j \le c_2$$$.
Вам предстоит выполнить $$$q$$$ операций.
Операции бывают двух типов:
Запросы не изменяют ни одну из матриц: ходы являются воображаемыми и для каждого запроса выбираются независимо. Матрицу $$$a$$$ изменяют только операции обновления, а матрица $$$b$$$ не изменяется никогда.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 1000$$$, $$$1 \le q \le 2 \cdot 10^4$$$) — размерность матриц и количество операций.
В следующих $$$n$$$ строках каждого набора входных данных содержится по $$$n$$$ целых чисел ($$$-10^4 \le a_{i,j} \le 10^4$$$) — начальное состояние матрицы $$$a$$$.
В следующих $$$n$$$ строках каждого набора входных данных содержится по $$$n$$$ целых чисел ($$$-10^4 \le b_{i,j} \le 10^4$$$) — матрица $$$b$$$.
Затем для этого набора входных данных следуют $$$q$$$ строк. Каждая строка начинается с символа U или Q:
Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$.
Для каждого запроса выведите «YES» (без кавычек), если подматрица является сопоставимой, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
32 20 00 -11 23 4U 1 1 1 1 1Q 1 1 2 23 51 1 12 2 23 3 32 3 46 7 810 11 12Q 1 1 2 3U 1 1 1 1 5Q 1 1 2 3U 1 2 1 3 5Q 1 1 2 35 61 0 0 0 02 0 0 0 03 0 0 0 04 0 0 0 05 0 0 0 02 2 3 4 54 3 4 5 66 4 5 6 78 5 6 7 810 6 7 8 9U 2 2 3 3 7U 2 4 4 5 -5Q 1 1 4 5Q 2 4 4 5Q 2 1 3 5Q 1 1 2 3
YesYesNoYesNoYesYesNo
В первом наборе входных данных после обновления матрица $$$a$$$ принимает вид $$$$$$\begin{bmatrix}1 & 0 \\ 0 & -1\end{bmatrix}.$$$$$$ Если для запроса выбрать $$$h_1=0$$$, $$$h_2=3$$$, $$$w_1=0$$$ и $$$w_2=2$$$, подматрицы совпадут, поэтому ответ — YES.
Во втором наборе входных данных ответ на первый запрос — YES: выберите $$$h_1=1$$$, $$$h_2=4$$$, $$$w_1=0$$$, $$$w_2=1$$$ и $$$w_3=2$$$. После первого обновления подматрицы $$$a$$$ и $$$b$$$ во втором запросе имеют вид $$$$$$\begin{bmatrix}6 & 1 & 1 \\ 2 & 2 & 2\end{bmatrix}, \quad \begin{bmatrix}2 & 3 & 4 \\ 6 & 7 & 8\end{bmatrix},$$$$$$ и можно доказать, что ответ — NO. После второго обновления в третьем запросе они имеют вид $$$$$$\begin{bmatrix}6 & 6 & 6 \\ 2 & 2 & 2\end{bmatrix}, \quad \begin{bmatrix}2 & 3 & 4 \\ 6 & 7 & 8\end{bmatrix},$$$$$$ поэтому при выборе $$$h_1=-4$$$, $$$h_2=4$$$, $$$w_1=0$$$, $$$w_2=1$$$ и $$$w_3=2$$$ они совпадут, и ответ будет YES.
В третьем наборе входных данных после обоих обновлений подматрицы $$$a$$$ и $$$b$$$ в первом запросе имеют вид $$$$$$\begin{bmatrix}1 & 0 & 0 & 0 & 0 \\ 2 & 7 & 7 & -5 & -5 \\ 3 & 7 & 7 & -5 & -5 \\ 4 & 0 & 0 & -5 & -5\end{bmatrix}, \quad \begin{bmatrix}2 & 2 & 3 & 4 & 5 \\ 4 & 3 & 4 & 5 & 6 \\ 6 & 4 & 5 & 6 & 7 \\ 8 & 5 & 6 & 7 & 8\end{bmatrix},$$$$$$ и можно доказать, что ответ — NO. Во втором запросе они имеют вид $$$$$$\begin{bmatrix}-5 & -5 \\ -5 & -5 \\ -5 & -5\end{bmatrix}, \quad \begin{bmatrix}5 & 6 \\ 6 & 7 \\ 7 & 8\end{bmatrix},$$$$$$ поэтому при выборе $$$h_2=10$$$, $$$h_3=11$$$, $$$h_4=12$$$, $$$w_4=0$$$ и $$$w_5=1$$$ они совпадут, и ответ будет YES. В третьем запросе при выборе $$$h_2=0$$$, $$$h_3=1$$$, $$$w_1=2$$$, $$$w_2=-4$$$, $$$w_3=-3$$$, $$$w_4=10$$$ и $$$w_5=11$$$ подматрицы совпадут, поэтому ответ — YES. Можно доказать, что ответ на четвёртый запрос — NO.
