Цивілізації
У розробці знаходиться нова популярна гра: 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[p]l[p]. Однак, ситуація ускладнюється тим, що визначення сили змінюється в міру розвитку ситуації в ігровому світі! Після кожної події ваш рушій отримуватиме нові значення коефіцієнтів A, B і C.
Звісно, ваш рушій теж повинен бути швидким, інакше гравцям у Civilizations стане нудно!
Вхідні дані
Перша строка містить кількість тестів z (1 ≤ z ≤ 5000). Далі йдуть описи тестів.
Перша строка кожного тесту складається з одного цілого числа n (2 ≤ n ≤ 500) - розміру світу.
Наступні n рядків містять по n цілих чисел і описують значення полів v[i,j] (|v[i,j]| ≤ 100).
Наступні n рядків містять n цілих чисел кожна і описують початкових власників полів p[i,j] (0 ≤ p[i,j] < n^2 ).
Наступний рядок складається з одного цілого числа q (1 ≤ q ≤ 10^5) - кількість подій.
Наступні q рядків описують події. Кожна з них містить шість цілих чисел: i, j, p, A, B, C (1 ≤ i, j ≤ n, 0 ≤ p < n^2, |A| ≤ 10^10, |B| ≤ 10^12, |C| ≤ 10^4), що відповідає: рядку і стовпцю поля, яке змінює власників, новій цивілізації-власнику і новим коефіцієнтам для обчислення сил цивілізацій відповідно. Гарантується, що до події цивілізація 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.