Sivilizasiyalar
Yeni bir populyar oyun hazırlanır: Civilizations (Civilization ilə qarışdırmayın). Siz, baş inkişafçılardan biri olaraq, əsas oyun mühərrikini yazmalısınız.
Dünya n sətir və n sütunlu vahid sahələrə bölünür. i-ci sətirdə və j-ci sütunda yerləşən sahə əvvəlcə p[i,j] sivilizasiyasına məxsusdur (hər bir tam ədəd üçün 0 və n^2 - 1 daxil olmaqla, bu tam ədədə uyğun bir sivilizasiya mövcuddur. Əlbəttə ki, hər an bir çoxu heç bir sahəyə sahib olmaya bilər) və onunla əlaqəli qiymətli resursları (və ya maliyyə öhdəliklərini) göstərən v[i,j] dəyərinə malikdir.
p sivilizasiyası üçün iki vacib ölçü müəyyən edək: onun zənginliyi (w[p]) və sərhəd uzunluğu (l[p]). Sivilizasiyanın zənginliyi ona məxsus sahələrin ümumi dəyəridir, sərhəd uzunluğu isə {a, b} qeyri-sıralı sahə cütlərinin sayıdır ki, burada a və b bir tərəfdədir və yalnız biri p-yə məxsusdur.
Oyun mühərriki müharibə nəticəsində sahələrdən birinin sahibinin dəyişdiyi hadisələr ardıcıllığını emal etməlidir. Sahibin dəyişməsi geri dönməzdir, ən azı növbəti müharibəyə qədər. Hər belə hadisədən sonra mühərrik ən güclü sivilizasiyanın nə qədər güclü olduğunu müəyyən etməlidir (ən azı bir sahəyə sahib olan sivilizasiyalar nəzərə alınır).
Oyun dizaynerləri komandası artıq qərara alıb ki, p sivilizasiyasının gücü Aw[p] + Bl[p] + Cw[p]l[p] kimi hesablanacaq. Lakin burada hər şey çətinləşir: gücün müəyyən edilməsi oyun dünyasında vəziyyətin inkişafı ilə dəyişir! Hər hadisədən sonra mühərrikiniz yeni A, B və C əmsallarını alacaq.
Əlbəttə ki, mühərrikiniz də sürətli olmalıdır, əks halda Civilizations oyunçuları darıxacaq!
Giriş məlumatları
Birinci sətir testlərin sayı z (1 ≤ z ≤ 5000) ehtiva edir. Daha sonra testlərin təsvirləri gəlir.
Hər testin birinci sətiri dünyanın ölçüsünü göstərən bir tam ədəd n (2 ≤ n ≤ 500) ehtiva edir.
Növbəti n sətir hər biri n tam ədəd ehtiva edir və sahələrin v[i,j] dəyərlərini təsvir edir (|v[i,j]| ≤ 100).
Növbəti n sətir hər biri n tam ədəd ehtiva edir və sahələrin ilkin sahiblərini p[i,j] (0 ≤ p[i,j] < n^2) təsvir edir.
Növbəti sətir hadisələrin sayı olan bir tam ədəd q (1 ≤ q ≤ 10^5) ehtiva edir.
Növbəti q sətir hadisələri təsvir edir. Hər biri altı tam ədəd ehtiva edir: i, j, p, A, B, C (1 ≤ i, j ≤ n, 0 ≤ p < n^2, |A| ≤ 10^10, |B| ≤ 10^12, |C| ≤ 10^4), bu, sahənin sahibini dəyişən sətir və sütunu, yeni sivilizasiya sahibini və sivilizasiyaların gücünü hesablamaq üçün yeni əmsalları göstərir. Hadisədən əvvəl p sivilizasiyasının sahə (i, j) üzərində sahibliyi olmadığı təmin edilir.
Bütün testlərdəki vahid sahələrin ümumi sayı 500 000-i keçmir.
Bütün testlərdəki sorğuların ümumi sayı 200 000-i keçmir.
Çıxış məlumatları
Hər test üçün bir sətir çıxarın, hər biri q tam ədəd ehtiva edir: hər hadisədən sonra ən güclü sivilizasiyanın güc dəyəri.
Qeyd
Birinci hadisədən sonra 2 sivilizasiyası yalnız (2, 1) sahəsinə sahibdir, 1 sivilizasiyası isə qalanlarına sahibdir. Hər iki sivilizasiya 2 uzunluğunda sərhədlərə malikdir və onların zənginliyi müvafiq olaraq 7 və 3-dür. 1 sivilizasiyası 5 gücü ilə ən güclüdür.
İkinci hadisədən sonra 1 sivilizasiyası bir diaqonaldakı sahələrə, 2 sivilizasiyası isə digərinə sahibdir. Hər iki sivilizasiya 4 uzunluğunda sərhədlərə və 5 zənginliyə malikdir, buna görə də onlar -7 gücü ilə eyni dərəcədə güclüdürlər.
Üçüncü hadisədən sonra lövhədə üç sivilizasiya qalıb: 1, 2 və 3. 6 sivilizasiyası indi ən güclüdür.
Nəhayət, son üç hadisədə 3 sivilizasiyası qalan sahələri ələ keçirir. Qeyd edək ki, indi 3 ən güclü sivilizasiyadır, çünki biz yalnız ən azı bir sahəyə nəzarət edən sivilizasiyaları nəzərə alırıq. Oyunun sonunda 3 sivilizasiyasının gücü -10-dur, çünki onun sərhəd uzunluğu 0, zənginliyi isə 10-dur.