Bir şeyə ehtiyac var
Tutaq ki, N sıra olan bir üçbucaq cədvəl var. Bu cədvəlin birinci sırası bir elementdən, ikinci sırası üç elementdən, üçüncü sırası beş elementdən və bu qayda ilə davam edir. Ümumiyyətlə, i-ci sıra 2i-1 elementdən ibarətdir. Bütün sıraların orta elementləri bir sütun təşkil edir. Beləliklə, cədvəl bərabəryanlı düzbucaqlı üçbucaq şəklindədir. Cədvəlin yuxarı elementində düz bucaq, aşağı sırada isə hipotenusa yerləşir.
Cədvəlin hər bir elementi '0' ilə '9' arasında bir rəqəmdir.
Verilmiş cədvəlin bəzi üçbucaq sahələrinin bütün elementlərinin cəmini tapmaq üçün Q sorğularına cavab vermək lazımdır. Hər bir sorğu aşağıdakı formadadır:
r_i, c_i, k_i
i-ci sorğunun sahəsi (r_i, c_i) nöqtəsində zirvəsi olan k_i sıra ilə bərabəryanlı düzbucaqlı üçbucaqdır:
Birinci sıra yalnız (r_i, c_i) elementindən ibarətdir. İkinci sıra üç elementdən ibarətdir: (r_i+1, c_i), (r_i+1, c_i+1), (r_i+1, c_i+2), üçüncü sıra beş elementdən və s.
Sorğunun üçbucağının bütün elementlərinin cəmini tapmaq lazımdır.
Çünki sorğular çoxdur, onlar proqram vasitəsilə yaradılır:
A_1 = 1
A_i = (1234567·A_{i-1} + 7654321) mod 1000000007, 2 ≤ i ≤ Q üçün
r_i = A_i mod N + 1
c_i = A_i mod (2r_{i }- 1) + 1
k_i = A_i mod (n - r_{i }+ 1) + 1
Giriş verilənləri
Birinci sətirdə N və Q - verilmiş üçbucağın sıra sayı və sorğuların sayı verilir. Sonra N sətirdə cədvəlin təsviri gəlir. Onların hər birində dəqiq 2i-1 rəqəm var - cədvəlin elementləri (rəqəmlər arasında boşluq yoxdur).
Çıxış verilənləri
Çünki sorğular çoxdur, bütün sorğuların cavablarının cəmini bir ədəd olaraq çıxarın.
Məhdudiyyətlər
1 ≤ N ≤ 10^3
0 ≤ Q ≤ 5·10^6
^{ }İzah
Verilmiş üçbucaq:
Birinci sorğu: , cəm 24.
İkinci sorğu: 8, cəm 8.
Üçüncü sorğu: 6, cəm 6.
Dördüncü sorğu: 1, cəm 1.
Beşinci sorğu: 3, cəm 3.