Цивілізації#11108

Цивілізації

7 секунд

128 мегабайтів

Дуже складна

У розробці знаходиться нова популярна гра: Civilizations (не плутати з Civilization). Як один із старших розробників у команді, ви повинні створити основний ігровий рушій.

Світ гри поділений на $n$ рядків і $n$ стовпців квадратних полів. Поле в $i$ -му рядку і $j$ -му стовпці спочатку належить цивілізації $p_{i, j}$ p_{i,j} (можна припустити, що для кожного цілого числа від $0$ до $n^{2} - 1$ n^2 - 1 включно існує цивілізація, що відповідає цьому числу. Звісно, в будь-який момент часу багато з них можуть не володіти жодними полями), і має значення $v_{i, j}$ v_{i,j}, яке відповідає цінним ресурсам (або фінансовим зобов'язанням), пов'язаним з ним.

Для цивілізації $p$ визначимо дві важливі характеристики: її багатство ( $w_{p}$ w_p) і протяжність кордонів ( $l_{p}$ l_p). Багатство цивілізації - це загальна вартість полів, якими вона володіє, а довжина кордонів - це кількість неупорядкованих пар полів ${a, b}$ , таких, що у $a$ і $b$ є спільна сторона, і рівно одне з них належить $p$ .

Ігровий рушій повинен обробляти послідовність подій, у кожній з яких змінюється власник одного з полів в результаті війни між двома цивілізаціями. Зміна власника незворотна, принаймні до наступної війни. Після кожної такої події рушій повинен визначати, наскільки сильна поточна найсильніша цивілізація (враховуються лише цивілізації, що володіють хоча б одним полем).

Команда дизайнерів гри вже вирішила, що сила цивілізації $p$ буде розраховуватися як $A w_{p} + B l_{p} + C w_{p} l_{p}$ Aw_p + Bl_p + Cw_pl_p. Однак, ситуація ускладнюється тим, що визначення сили змінюється в міру розвитку ситуації в ігровому світі! Після кожної події ваш рушій отримуватиме нові значення коефіцієнтів $A$ , $B$ і $C$ .

Звісно, ваш рушій теж повинен бути швидким, інакше гравцям у Civilizations стане нудно!

Вхідні дані

Перша строка містить кількість тестів $z$ ( $1 \leq z \leq 5000$ 1 \le z \le 5000). Далі йдуть описи тестів.

Перша строка кожного тесту складається з одного цілого числа $n$ ( $2 \leq n \leq 500$ 2 \le n \le 500) - розміру світу.

Наступні $n$ рядків містять по $n$ цілих чисел і описують значення полів $v_{i, j}$ v_{i,j} ( $∣ v_{i, j} ∣ \leq 100$ |v_{i,j}| \le 100).

Наступні $n$ рядків містять $n$ цілих чисел кожна і описують початкових власників полів $p_{i, j}$ p_{i,j} ( $0 \leq p_{i, j} < n^{2}$ 0 \le p_{i,j} < n^2).

Наступний рядок складається з одного цілого числа $q$ ( $1 \leq q \leq 1 0^{5}$ 1 \le q \le 10^5) - кількість подій.

Наступні $q$ рядків описують події. Кожна з них містить шість цілих чисел: $i$ , $j$ , $p$ , $A$ , $B$ , $C$ ( $1 \leq i, j \leq n$ 1 \le i, j \le n, $0 \leq p < n^{2}$ 0 \le p < n^2, $∣ A ∣ \leq 1 0^{10}$ |A| \le 10^{10}, $∣ B ∣ \leq 1 0^{12}$ |B| \le 10^{12}, $∣ C ∣ \leq 1 0^{4}$ |C| \le 10^4), що відповідає: рядку і стовпцю поля, яке змінює власників, новій цивілізації-власнику і новим коефіцієнтам для обчислення сил цивілізацій відповідно. Гарантується, що до події цивілізація $p$ не володіла полем $(i, j)$ .

Загальна кількість одиничних полів у всіх тестах не перевищує $500000$ .

Загальна кількість запитів у всіх тестах не перевищує $200000$ .

Вихідні дані

Для кожного тесту виведіть один рядок, що містить $q$ цілих чисел: значення сили наймогутнішої цивілізації після кожної події.

Приклади

Приклад 1

Примітка

Після першої події цивілізація $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$ .