Taulukossa on n lukua, jotka on indeksoitu 0,1,\ldots,n-1, ja ovat kaikki aluksi nollia. Lisäksi ylläpidetään lukua 0\leq D\leq n - 1, joka on myös aluksi 0. Toteuta tietorakenne, joka tarjoaa seuraavat operaatiot:

1. kasvata jokaista välillä [(a+D)\bmod n,(b+D)\bmod n] olevaa lukua x:llä
2. laske välin [(a+D)\bmod n,(b+D)\bmod n] lukujen summa modulo n, ja tee siitä uusi luku D

Mikäli x>y, väli [x, y] tarkoittaa tässä samaa kuin [y, x]. x\bmod y on jakojäännös, kun luku x jaetaan luvulla y.

Syöte

Syötteen ensimmäisellä rivillä on luvut n ja q, taulukon koko ja kyselyjen määrä. Tämän jälkeen syötteessä on q riviä, joista jokainen kuvaa yhden kyselyn.

Jos kysely on tyyppiä 1, rivi on muotoa "1 a b x". Tämä tarkoittaa, että välin [(a+D)\bmod n,(b+D)\bmod n] lukuja tulee kasvattaa x:llä.

Jos kysely on tyyppiä 2, rivi on muotoa "2 a b". Tämä tarkoittaa, että tulee laskea välin [(a+D)\bmod n,(b+D)\bmod n] lukujen summa modulo n, tulostaa se, ja tallentaa se uudeksi luvuksi D.

Tuloste

Tulosta jokaisesta tyypin 2 kyselystä lukujen summa modulo n omalle rivilleen.

Rajat

• 1 \le n \le 10^{9}
• 1 \le q \le 3\cdot 10^5
• 0 \le a \le n-1
• 0 \le b \le n-1
• 0 \le x \le n-1

Esimerkki

Syöte:

7 4
1 2 4 3
2 3 6
1 0 4 2
2 4 2

Tuloste:

6
1

Tilanne ja muutettu/kyselty väli kyselyiden jälkeen:
Taulukko (0, 0, \underline{3, 3, 3}, 0, 0), D = 0
Taulukko (0, 0, 3, \underline{3, 3, 0, 0}), D = 6
Taulukko (0, 0, 3, \underline{5, 5, 2, 2}), D = 6
Taulukko (0, \underline{0, 3, 5}, 5, 2, 2), D = 1