CSES - 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