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$