Hide

Problem C
Pönnukökur

Languages en is

Signý er að baka pönnukökur. Pönnukökurnar hafa tvær hliðar, hlið $0$ og hlið $1$, og liggja þær í röð. Því er hægt að tákna hvaða hlið snýr upp með tvíundarkerfinu. Upprunalega snýr hlið $0$ upp. Stundum þegar hún bakar pönnukökurnar þá snýr hún þeim. Ef hún snýr pönnuköku sem snýr hlið $0$ upp þá eftir snúninginn mun hlið $1$ snúa upp og öfugt. Signý er pínu sérstök og hún vil vita hversu margar pönnukökur snúa hlið $1$ upp á sérstöku bili. Þú átt að fylgjast með snúningum Signýjar og svara spurningum hennar.

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $q$, fjölda pönnukaka og fjölda aðgerða. Næst koma $q$ línur þar sem hver lína lýsir einni aðgerð. Það eru fjórar tegundir af aðgerðum, fyrsta heiltalan í hverri línu segir af hvaða tegund aðgerðin er.

  • Signý snýr pönnuköku $i$. Inntakið er á forminu 1 i, þar sem $1 \leq i \leq n$.

  • Signý snýr öllum pönnukökunum. Inntakið er á forminu 2.

  • Signý spyr hversu margar pönnukökur snúa hlið $1$ upp. Inntakið er á forminu 3.

  • Signý spyr hversu margar pönnukökur snúa hlið $1$ upp frá pönnuköku $l$ að pönnuköku $r$. Inntakið er á forminu 4 l r.

Úttak

Fyrir hverja spurningu skaltu skrifa út eina línu með einni heiltölu, svarið við spurningunni. Svör skulu koma í sömu röð og spurningarnar sem þau svara.

Stigagjöf

Hópur

Stig

Inntaks takmarkanir

1

20

$1 \leq n,q \leq 2 \cdot 10^5$ bara aðgerðir af tegund 1 og 3

2

14

$1 \leq n,q \leq 2 \cdot 10^5$ bara aðgerðir af tegund 1,2 og 3

3

30

$1 \leq n,q \leq 1000$ allar tegundir af aðgerðum

4

36

$1 \leq n,q \leq 2 \cdot 10^5$ allar tegundir af aðgerðum

Sample Input 1 Sample Output 1
3 7
1 1
3
1 2
3
1 3
1 2
3
1
2
2
Sample Input 2 Sample Output 2
2 5
3
1 1
2
3
3
0
1
1
Sample Input 3 Sample Output 3
9 6
3
2
2
1 9
4 2 9
3
0
1
1