Miki si je postavio opasnu rasvjetu u svoju sobu.

Sastoji se od niza žaruljica gdje svaka ima svoj prekidač pored.

Ostavio je tako svoj svijetlosni show te otišao na odmor, no vrativši se dočekao ga je ogroman račun za struju. Ogroman!

Na svu sreću Miki nije od jučer, pa je ugradio pametne žarulje koje bilježe i kompresiraju podatke o tome kad su upaljene i kad su ugašene.

Naime, podaci o paljenju i gašenju kompresirani su u uključene raspone \([l, r]\).

Premda također zna tko mu je kad posjećivao sobu zanima ga koliko je najviše žarulja bilo upaljeno u nizu u rasponima \([l, r]\).

Pomozite mu odgovarati na \(q\) takvih upite uz inicijalno stanje žarulja \(a\) duljine \(n\) gdje \(a_i\) predstavlja \(0\) i \(1\) ovisno o tome je li žarulja upaljena ili ugašena.

Formalnije, postoje dvije vrste upita oznake \(t\) vrijednosti \(0\) i \(1\).

Upit \(0\) sastoji se od brojeva \(l\) i \(r\) te zahtjeva od vas da odgovorite s najduljim uzastopnim brojem upaljenih žarulja u opsegu \([l, r]\).

Upit \(1\) sastoji se od brojeva \(l\), \(r\) i \(v\) te zahtjeva od vas da žarulje u uključenom opsegu \([l, r]\) postavite vrijednosti žarulja na \(v\), gdje \(v\) može biti \(0\) ili \(1\).

Ulazni podatci

U prvom retku nalaze se cijeli brojevi \(n\) i \(q\) \((1 \leq n, q \leq 2 \times 10^5)\)

U sljedećem retku nalazi se polje \(a\) binarnih vrijednosti duljine \(n\) \((0 \leq a_i \leq 1)\).

U sljedećih \(q\) redaka nalaze se upiti tipa \(0\) ili \(1\).

Upit tipa \(0\) oblika je:

\(0\) \(l\) \(r\)

a upit tipa \(1\):

\(1\) \(l\) \(r\) \(v\)

iz teksta zadatka.

Vrijedi:

\((1 \leq l \leq r \leq n)\)

\((0 \leq v \leq 1)\)

Izlazni podatci

Za svaki upit tipa \(0\) ispišite najdulji niz upaljenih žarulja u zadatku.

Podzadatci

Ulaz primjera 1

6 4
1 1 1 0 0 1
0 1 4
0 1 6
1 2 5 1
0 1 6

Izlaz primjera 1

3
3
6

Ulaz primjera 2

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

Izlaz primjera 2

2
2
1
1
1

Ulaz primjera 3

20 10
0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1
0 14 18
1 15 19 0
0 20 20
1 20 20 0
1 4 19 0
1 7 10 0
1 17 20 1
0 15 17
1 9 10 0
0 18 20

Izlaz primjera 3

2
1
1
3

Ulaz primjera 4

20 10
1 0 1 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1
1 20 20 0
1 13 17 0
1 10 17 1
0 1 8
1 2 19 0
0 10 12
0 13 19
1 12 18 0
0 2 2
1 17 20 1

Izlaz primjera 4

5
0
0
0

Objašnjenje prvog primjera:

1 1 1 0 0 1

upit 0 1 4 -> 3 (tri jedinice s početka) upit 0 1 6 -> 3 (tri jedinice s početka) upit 1 2 5 1, polje postane 1 1 1 1 1 1 upit 0 1 6 -> 6 (svi u opsegu)