• 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