В разработке находится новая захватывающая игра: Civilizations (не путать с Civilization). Как один из ведущих разработчиков в команде, вы должны написать основной игровой движок.
Мир разделен на $n$ строк и $n$ столбцов элементарных полей. Поле в $i$-й строке и $j$-м столбце изначально принадлежит цивилизации $p_{i,j}$ (можно считать, что для каждого целого числа от $0$ до $n^2 - 1$ включительно существует соответствующая ему цивилизация. Конечно, в любой момент времени многие из них могут не владеть ни одним полем) и имеет значение $v_{i,j}$, которое соответствует ценным ресурсам (или финансовым обязательствам), связанным с этим полем.
Для данной цивилизации $p$ мы определяем две важные характеристики: её богатство ($w_p$) и длину границ ($l_p$). Богатство цивилизации — это суммарная стоимость полей, которыми она владеет, а длина границ — это количество неупорядоченных пар полей $\{a, b\}$, таких что $a$ и $b$ имеют общую сторону, и ровно одно из них принадлежит цивилизации $p$.
Игровой движок должен обрабатывать последовательность событий; в каждом из них меняется владелец одного из полей в результате войны между двумя цивилизациями. Смена владельца является постоянной, по крайней мере до следующей войны. После каждого такого события движок должен определять, насколько могущественна текущая самая могущественная цивилизация (учитываются только цивилизации, владеющие хотя бы одним полем).
Команда разработчиков игры уже решила, что могущество цивилизации $p$ будет вычисляться как $Aw_p + Bl_p + Cw_pl_p$. Здесь всё становится сложнее: определение могущества меняется по мере развития ситуации в игровом мире! После каждого события ваш движок будет получать новые значения коэффициентов $A$, $B$ и $C$.
Конечно, ваш движок также должен быть быстрым — иначе игроки в Civilizations заскучают!
Входные данные
Первая строка входных данных содержит количество тестов $z$ ($1 \le z \le 5000$). Далее следуют описания тестов.
Первая строка каждого теста содержит единственное целое число $n$ ($2 \le n \le 500$) — размер мира.
Следующие $n$ строк содержат по $n$ целых чисел и описывают значения полей $v_{i,j}$ ($|v_{i,j}| \le 100$).
Следующие $n$ строк содержат по $n$ целых чисел и описывают начальных владельцев полей $p_{i,j}$ ($0 \le p_{i,j} < n^2$).
Следующая строка содержит единственное целое число $q$ ($1 \le q \le 10^5$) — количество событий.
Следующие $q$ строк описывают события. Каждая из них содержит шесть целых чисел: $i, j, p, A, B, C$ ($1 \le i, j \le n$; $0 \le p < n^2$; $|A| \le 10^{10}$; $|B| \le 10^{12}$; $|C| \le 10^4$), соответствующих: строке и столбцу поля, которое меняет владельца, новой цивилизации-владельцу и новым коэффициентам для вычисления могущества цивилизаций соответственно. Гарантируется, что до события цивилизация $p$ не владела полем $(i, j)$.
Общее количество элементарных полей во всех тестах не превышает $500\,000$.
Общее количество запросов во всех тестах не превышает $200\,000$.
Выходные данные
Для каждого теста выведите одну строку, содержащую $q$ целых чисел: значение могущества самой могущественной цивилизации после каждого из событий.
Примеры
Пример 1
1 2 1 2 3 4 1 1 2 2 6 2 2 1 1 -1 0 1 2 2 1 2 -1 2 1 3 0 1 -1 1 2 3 2 0 0 1 1 3 1 1 1 2 2 3 -1 -1 -1
Выходные данные 1
5 -7 -2 10 20 -10
Примечание
После первого события цивилизация 2 владеет только полем $(2, 1)$, в то время как цивилизация 1 владеет остальными. Обе цивилизации имеют границы длиной 2, а их богатство равно 7 и 3 соответственно. Цивилизация 1 с могуществом 5 является самой могущественной.
После второго события цивилизация 1 владеет полями на одной диагонали, а цивилизация 2 — на другой. Обе цивилизации имеют границы длиной 4 и богатство 5, поэтому они одинаково могущественны с могуществом -7.
После третьего события на доске теперь три цивилизации: 1, 2 и 3. Цивилизация 6 теперь самая могущественная.
Наконец, в последних трех событиях цивилизация 3 захватывает оставшиеся поля. Заметьте, что теперь 3 является самой могущественной цивилизацией для любых $A, B$ и $C$, так как мы принимаем во внимание только цивилизации, контролирующие хотя бы одно поле. Могущество цивилизации 3 в конце игры равно -10, так как она имеет границы длиной 0 и богатство 10.