nomem

În urma unei afaceri necurate cu mafiotul Ivan, Lunasorab a suferit un accident suspect de maşină. Din această cauză el se confruntă cu o pierdere temporară a memoriei. Acest lucru este foarte neplăcut, deoarece el trebuia să facă inventarul moşiilor sale de creştere a găinilor. Aceastea au forma unui triunghi isoscel dreptunghic, cu catetele paralele cu axele de coordonate. Mai exact, suprafaţa pe care se găsesc moşiile lui Lunasorab poate fi modelată ca o matrice pătratică de $N$ linii şi $N$ coloane (cu linii şi coloanele numerotate de la $1$ la $N$) de numere naturale, reprezentând coeficientul de inteligenţă al unei găini. Un triunghi isoscel dreptunghic de catetă de lungime $L$ cu originea pe linia $x$ şi coloana $y$ va conţine toate celulele din matrice de linie $a$ şi coloană $b$ cu $a \leq x$ şi $b \geq y$ şi cu $|a - x| + |b - y| < L$.

Pentru Lunasorab gradul de risc al unei moşii (reprezentată ca un triunghi isoscel dreptunghic definit ca mai sus) este dată de valoarea minimă a coeficientului de inteligenţă a unei găini de pe moşia respectivă.

Deoarece momentan Lunasorab nu stă prea bine cu memoria, el vă cere suma gradelor de risc ale tuturor moşiilor modulo $1 \ 000 \ 000 \ 007$.

Cerinţă

Ajutaţi-l pe Lunasorab să afle rapid suma tuturor gradelor de risc ale moşiilor sale.

Date de intrare

Pe prima linie a fişierului de intrare nomem.in se găsesc numerele $N$ şi $Q$, separate prin câte un singur spaţiu, reprezentând dimensiunile matricii, respectiv numărul de moşii ale lui Lunasorab. Pe următoarele $N$ linii, fiecare conţinând $N$ elemente, urmează elementele matricii, separate prin câte un singur spaţiu. Următoarele $Q$ linii conţin câte $3$ numere $L \ x \ y$, separate prin câte un singur spaţiu reprezentând moşia cu originea în $x \ y$, de latură $L$.

Date de ieșire

În fişierul de ieşire nomem.out se va găsi un număr natural, reprezentând suma gradelor de risc ale tuturor moşiilor modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$
• $1 \leq Q \leq 1 \ 000 \ 000$
• $1 \leq x, y, L \leq N$
• O moşie se găseşte complet în interiorul unei matrici
• $0 \leq$ gradul de inteligenţă a unei găini $< 1 \ 010 \ 010 \ 010$
• În fişierul de intrare întrebările vor fi ordonate crescător după $L$
• Pot exista găini care nu aparţin niciunei moşii ale lui Lunasorab
• Pentru $20\%$ din teste $N = 200$ şi $Q = 100\ 000$
• Pentru încă $20\%$ din teste $N = 300$ şi $Q = 400 \ 000$
• Pentru încă $20\%$ din teste $N = 700$ şi $Q = 1 \ 000 \ 000$
• Lunasorab vă recomandă să parsaţi citirea pentru a avea mai mult timp ca să-l ajutaţi

Exemplu

nomem.in

3 3
1 2 3
4 5 6
7 8 9
1 2 3
2 3 2
3 3 1

nomem.out

12

Explicație

Pentru prima întrebare răspunsul este $6$, pentru a doua $5$ iar pentru ultima $1$. Dacă le adunăm şi facem restul împărţirii modulo $1 \ 000 \ 000 \ 007$ obţinem $12$.