В разработке находится новая популярная игра: Civilizations (не путать с Civilization). Как один из старших разработчиков в команде, Вы должны написать основной игровой движок.

Мир разделен на n строк и n столбцов единичных полей. Поле в i-й строке и j-м столбце изначально принадлежит цивилизации pi,j (можно предположить, что для каждого целого числа между 0 и n2 - 1 включительно, существует цивилизация, соответствующая этому целому числу. Конечно, в любой момент времени многие из них могут не владеть никакими полями), и имеет значение vi,j , что соответствует драгоценным ресурсам (или финансовым обязательствам), связанным с ним.

Для цивилизации p определим две важные меры: ее богатство (wp) и протяженность границ (lp). Богатство цивилизации - это общая стоимость принадлежащих ей полей, а длина границ - это количество неупорядоченных пар полей {a, b}, таких, что у a и b одна сторона, и ровно одна из них принадлежит p.

Игровой движок должен будет обрабатывать последовательность событий, в каждом из которых меняется владелец одного из полей в результате войны двух цивилизаций. Смена владельца необратима, по крайней мере, до следующей войны. После каждого такого события движок должен определять, насколько сильна текущая самая сильная цивилизация (считаются только цивилизации, владеющие хотя бы одним полем).

Команда дизайнеров игры уже решила, что сила цивилизации p будет рассчитываться как Awp + Blp + Cwplp. Однако здесь все становится сложнее: определение силы меняется по мере развития ситуации в игровом мире! После каждого события ваш движок будет получать новые значения коэффициентов A, B и C.

Конечно, ваш движок тоже должен быть быстрым, иначе игрокам в Цивилизациях станет скучно!

Входные данные

Первая строка содержит количество тестов z (1 ≤ z ≤ 5000). Далее следуют описания тестов.

Первая строка каждого теста состоит из одного целого числа n (2 ≤ n ≤ 500) - размера мира.

Следующие n строк содержат по n целых чисел и описывают значения полей vi,j (|vi,j| ≤ 100).

Следующие n строк содержат n целых чисел каждая и описывают начальных владельцев полей pi,j (0 ≤ pi,j < n2).

Следующая строка состоит из одного целого числа q (1 ≤ q ≤ 105) - количества событий.

Следующие q строк описывают события. Каждое из них содержит шесть целых чисел: i, j, p, A, B, C (1 ≤ i, j ≤ n, 0 ≤ p < n2, |A| ≤ 1010, |B| ≤ 1012, |C| ≤ 104), что соответствует: строке и столбцу поля, которое меняет владельцев, новой цивилизации-владельцу и новых коэффициентов для вычисления сил цивилизаций соответственно. Гарантируется, что до события цивилизация p не владела полем (i, j).

Общее количество единичных полей во всех тестах не превышает 500 000.

Общее количество запросов во всех тестах не превышает 200 000.

Выходные данные

Для каждого теста выведите одну строку, содержащую q целых чисел: значение силы самой могущественной цивилизации после каждого события.

Примечание

После первого события цивилизация 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.