CSES - Ruudukko
  • Time limit: 1.00 s
  • Memory limit: 128 MB

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

  1. muuta ruudukon kohdan (y,x)(y,x) arvoksi uu
  2. laske lukujen summa aliruudukossa ruudusta (y1,x1)(y_1,x_1) ruutuun (y2,x2)(y_2,x_2)

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut nn ja qq: ruudukon koko ja kyselyiden määrä.

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

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

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

Jos kysely on tyyppiä 2, rivi on muotoa "2 y1y_1 x1x_1 y2y_2 x2x_2". Tämä tarkoittaa, että täytyy laskea aliruudukon summa ruudusta (y1,x1)(y_1,x_1) ruutuun (y2,x2)(y_2,x_2).

Tuloste

Tulosta jokaisesta tyypin 2 kyselystä lukujen summa omalle rivilleen.

Rajat

  • 1n10001 \le n \le 1000
  • 106ti,j106-10^6 \le t_{i,j} \le 10^6
  • 1q1051 \le q \le 10^5
  • 1x,yn1 \le x,y \le n
  • 1y1y2n1 \le y_1 \le y_2 \le n
  • 1x1x2n1 \le x_1 \le x_2 \le n
  • 106u106-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