CSES - Lumisade
  • Time limit: 2.00 s
  • Memory limit: 128 MB

Talven aikana Uolevin kotikadulle satoi useaan otteeseen lunta. Yllättävää kyllä, yhtään lunta ei sulanut pois ennen kevättä.

Tehtäväsi on mallintaa seuraavia tapahtumia:

  1. Talojen aba \ldots b alueelle sataa ss senttiä lunta.

  2. Laske lumen määrä talon xx pihalla.

Tapahtumat alkavat siitä, kun maassa ei ole vielä lunta.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja qq: talojen määrä ja tapahtumien määrä. Talot on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten syötteessä on qq riviä, jotka kuvaavat tapahtumat. Rivillä on ensin luku tt, tapahtuman tyyppi. Jos t=1t=1, rivillä on vielä kolme kokonaislukua aa, bb ja ss. Jos t=2t=2, rivillä on vielä yksi kokonaisluku xx.

Tuloste

Ohjelmasi tulee tulostaa tapahtuman 2 yhteydessä lumen määrä talon xx pihalla.

Rajat

  • 1n1051 \le n \le 10^5
  • 1q1051 \le q \le 10^5
  • 1t21 \le t \le 2
  • 1abn1 \le a \le b \le n
  • 1s1091 \le s \le 10^9
  • 1xn1 \le x \le n

Esimerkki

Syöte:

10 5
1 5 10 3
2 3
2 8
1 7 8 2
2 8

Tuloste:

0
3
5