시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB6726936.000%

문제

Watt je uletio u prostoriju. Imao ga je. Napokon je razradio matematiku iza njega i sad ga je mogao pokazati svima. Oduvijek je bio u pravu.

  • PARNI STROJ! - uskliknuo je Watt.

Svi su gledali u nevjerici.

  • Što taj tvoj “parni stroj” radi, ha Watt? - pitao je skeptično Marin.
  • Daš mu niz od $N$ brojeva i nad njim izvodiš operacije. Jedan tip operacije ti je postavljanje intervala na neku vrijednost, a drugi je da mu daš interval, a on ti kaže koliko u njemu postoji uzastopnih podnizova s parnom sumom. Parni stroj!

Marin je rukom poklopio oči.

  • Dobro, ajde, da isprobamo to.

입력

U prvom su retku prirodni brojevi $N$ i $Q$ ($1 ≤ N, Q ≤ 200\,000$), duljina niza zadanog parnom stroju i broj izvedenih operacija.

U sljedećem retku je početni niz od $N$ prirodnih brojeva $a_i$ ($1 ≤ a_i ≤ 1\,000\,000$) zadan parnom stroju.

U sljedećih $Q$ redaka su operacije redom kojim su izvedene na parnom stroju. Svaki od redaka predstavlja jednu operaciju te je u jednom od dva oblika:

  • $1$ $L$ $R$ $v$: U intervalu niza koji počinje $L$-tim, a završava $R$-tim ($1 ≤ L ≤ R ≤ N$) elementom, postavi sve elemente na vrijednost $v$ ($1 ≤ v ≤ 1\,000\,000$).
  • $2$ $L$ $R$: Pitaj parni stroj: u intervalu niza koji počinje $L$-tim, a završava $R$-tim ($1 ≤ L ≤ R ≤ N$) elementom, koliko postoji uzastopnih podnizova s parnom sumom?

Barem jedna operacija bit će drugog oblika.

출력

Za svaku operaciju drugog oblika u zaseban redak ispiši odgovor parnog stroja.

서브태스크

번호배점제한
110

$1 ≤ N, Q ≤ 1000$

210

Nema operacija prvog oblika.

310

Za operacije prvog oblika vrijedi $L=R$, a za operacije drugog oblika vrijedi $L=1$ i $R=N$.

420

Za operacije prvog oblika vrijedi $L=R$.

550

Nema dodatnih ograničenja.

예제 입력 1

5 3
8 7 7 5 1
2 2 4
2 4 4
2 2 4

예제 출력 1

2
0
2

예제 입력 2

8 4
8 2 4 8 2 10 2 5
1 5 5 8
2 4 5
2 3 7
2 1 6

예제 출력 2

3
15
21

예제 입력 3

8 4
4 9 3 8 10 1 9 10
1 1 4 3
1 2 6 7
2 1 8
2 3 5

예제 출력 3

16
2

힌트

Opis prvog probnog primjera: Interval $[2, 4]$ sadrži $6$ različitih uzastopnih podnizova, od kojih $2$ imaju parnu sumu: $[2, 3]$ i $[3, 4]$. Drugi odgovor parnog stroja je $0$ jer je četvrti element niza $5$, tj. neparan broj. Treći odgovor je jednak prvom jer su i pitanja bila jednaka.

채점 및 기타 정보

  • 예제는 채점하지 않는다.