Code Submission Evaluation System Login

Datatähti-valmennus

Ruudukko


Task | Statistics


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