Ruudukko

• Time limit: 1.00 s
• Memory limit: 128 MB

Annettuna on $n \times n$-ruudukko, jossa on lukuja. Toteuta tietorakenne, joka tarjoaa seuraavat operaatiot:

1. muuta ruudukon kohdan $(y,x)$ arvoksi $u$
   
2. laske lukujen summa aliruudukossa ruudusta $(y_1,x_1)$ ruutuun $(y_2,x_2)$
   

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut $n$ ja $q$: ruudukon koko ja kyselyiden määrä.

Sitten syötteessä on $n$ riviä, joista jokaisella on $n$ lukua muotoa $t_{i,j}$. Nämä luvut kuvaavat ruudukon sisällön alussa.

Lopuksi syötteessä on $q$ riviä, joista jokainen kuvaa yhden kyselyn.

Jos kysely on tyyppiä 1, rivi on muotoa "1 $y$ $x$ $u$". Tämä tarkoittaa, että ruudukon kohtaan $(y,x)$ tulee luku $u$.

Jos kysely on tyyppiä 2, rivi on muotoa "2 $y_1$ $x_1$ $y_2$ $x_2$". Tämä tarkoittaa, että täytyy laskea aliruudukon summa ruudusta $(y_1,x_1)$ ruutuun $(y_2,x_2)$.

Tuloste

Tulosta jokaisesta tyypin 2 kyselystä lukujen summa omalle rivilleen.

Rajat

• $1 \le n \le 1000$
  
• $-10^6 \le t_{i,j} \le 10^6$
  
• $1 \le q \le 10^5$
  
• $1 \le x,y \le n$
  
• $1 \le y_1 \le y_2 \le n$
  
• $1 \le x_1 \le x_2 \le n$
  
• $-10^6 \le u \le 10^6$
  

Esimerkki

Syöte:
3 4
2 3 1
2 1 4
1 5 1
2 2 1 3 3
1 2 2 5
1 3 2 3
2 2 1 3 3

Tuloste:
14
16