statements segtree (PDF)

2012-2013 Òðåíèðîâêà ÑÏáÓ B Çàïðîñû íà îòðåçêå, äåðåâî îòðåçêîâ
ÂÊîíòàêòå, 2 îêòÿáðÿ 2012

Çàäà÷à A. Íàèâíûé RMQ
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

stupid_rmq.in
stupid_rmq.out
2 ñåêóíäû
256 ìåãàáàéò

Âàì äàí ìàññèâ a[℄ èç n ýëåìåíòîâ è m  êîëè÷åñòâî çàïðîñîâ, ñîñòîÿùèõ èç äâóõ ÷èñåë l è r ,
âûâåäèòå ìèíèìàëüíûé ýëåìåíò â ìàññèâå a[℄ ñ èíäåêñàìè îò l äî r .

Ôîðìàò âõîäíîãî àéëà

 ïåðâîé ñòðîêå âõîäíîãî àéëà ñîäåðæèòñÿ ÷èñëî n  äëèííà ìàññèâà a[℄ (1 6 n 6 1000). Âî
âòîðîé ñòðîêå ñîäåðæèòñÿ n ÷èñåë ai  ýëåìåíòû ìàññèâà (−109 6 ai 6 109 ).  ñëåäóþùåé ñòðîêå
ñîäåðæèòñÿ ÷èñëî m  êîëè÷åñòâî çàïðîñîâ (1 6 m 6 1000).  ïîñëåäíèõ m ñòðîêàõ ñîäåðæàòüñÿ
çàïðîñû l, r (1 6 l, r 6 n).

Ôîðìàò âûõîäíîãî àéëà

Äëÿ êàæäîãî çàïðîñà âûâåäèòå îòâåò â íîâîé ñòðîêå.

Ïðèìåðû

stupid_rmq.in

5
1 -2 3 4 1
3
1 3
3 4
1 5
2
-100000 -1111111
2
1 1
1 2

-2
3
-2

-100000
-1111111

Ñòðàíèöà 1 èç 6

stupid_rmq.out

2012-2013 Òðåíèðîâêà ÑÏáÓ B Çàïðîñû íà îòðåçêå, äåðåâî îòðåçêîâ
ÂÊîíòàêòå, 2 îêòÿáðÿ 2012

Çàäà÷à D. Ñóììà 2
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

sum2.in
sum2.out
2 ñåêóíäû
256 ìåãàáàéò

Âàì äàí ìàññèâ a[℄ èç n ýëåìåíòîâ è m  êîëè÷åñòâî çàïðîñîâ, ñîñòîÿùèõ èç äâóõ ÷èñåë l è r ,
âûâåäèòå ñóììó ýëåìåíòîâ â ìàññèâå a[℄ ñ èíäåêñàìè îò l äî r .

Ôîðìàò âõîäíîãî àéëà

 ïåðâîé ñòðîêå âõîäíîãî àéëà ñîäåðæèòñÿ ÷èñëî n  äëèííà ìàññèâà a[℄ (1 6 n 6 100000). Âî
âòîðîé ñòðîêå ñîäåðæèòñÿ n ÷èñåë ai  ýëåìåíòû ìàññèâà (−109 6 ai 6 109 ).  ñëåäóþùåé ñòðîêå
ñîäåðæèòñÿ ÷èñëî m  êîëè÷åñòâî çàïðîñîâ (1 6 m 6 100000).  ïîñëåäíèõ m ñòðîêàõ ñîäåðæàòüñÿ
çàïðîñû l, r (1 6 l, r 6 n).

Ôîðìàò âûõîäíîãî àéëà

Äëÿ êàæäîãî çàïðîñà âûâåäèòå îòâåò â íîâîé ñòðîêå.

Ïðèìåðû

5
1 2 3 4 5
3
1 5
1 1
4 5
6
-1 1 -1 1 -1 1
2
1 6
3 3

sum2.in

15
1
9

0
-1

Ñòðàíèöà 4 èç 6

sum2.out

2013-2014 Òðåíèðîâêà ÑÏáÓ B 7, Äåðåâî îòðåçêîâ
ÂÊîíòàêòå, 17 îêòÿáðÿ 2013

Çàäà÷à A. Ñóììà íà îòðåçêå
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

sum.in
sum.out
2 ñåêóíäû
256 ìåãàáàéò

Äàí ìàññèâ èç N ýëåìåíòîâ, íóæíî íàó÷èòüñÿ íàõîäèòü ñóììó ÷èñåë íà îòðåçêå.

Ôîðìàò âõîäíîãî àéëà

Ïåðâàÿ ñòðîêà âõîäíîãî àéëà ñîäåðæèò äâà öåëûõ ÷èñëà N è K  ÷èñëî ÷èñåë â ìàññèâå è
êîëè÷åñòâî çàïðîñîâ. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Ñëåäóþùèå K ñòðîê ñîäåðæàò çàïðîñû
1. A i x  ïðèñâîèòü i-ìó ýëåìåíòó ìàññèâà çíà÷åíèå x (1 ≤ i ≤ n, 0 ≤ x ≤ 109 )
2. Q l r  íàéòè ñóììó ÷èñåë â ìàññèâå íà ïîçèöèÿõ îò l äî r . (1 ≤ l ≤ r ≤ n)
Èçíà÷àëüíî â ìàññèâå æèâóò íóëè.

Ôîðìàò âûõîäíîãî àéëà

Íà êàæäûé çàïðîñ âèäà Q l r íóæíî âûâåñòè åäèíñòâåííîå ÷èñëî  ñóììó íà îòðåçêå.

Ïðèìåðû
5
A
A
A
Q
Q
Q
Q
Q
Q

9
2
3
4
1
2
3
4
5
1

2
1
2
1
2
3
4
5
5

sum.in

0
2
1
2
0
5

Ñòðàíèöà 1 èç 4

sum.out

2012-2013 Òðåíèðîâêà ÑÏáÓ B Çàïðîñû íà îòðåçêå, äåðåâî îòðåçêîâ 2
ÂÊîíòàêòå, 6 îêòÿáðÿ 2012

Çàäà÷à B. ðèáû
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

mushrooms.in
mushrooms.out
1 ñåêóíäà
256 ìåãàáàéò

 î÷åíü áîëüøîì ëåñó ðàñêèíóëàñü îãðîìíàÿ ïîëÿíà. Ïîñëå ïðîëèâíîãî äîæäÿ íà ïîëÿíå ïîñëåäîâàòåëüíî âûðàñòàþò ãðèáû â òå÷åíèè n ìèíóò. Íà ïåðâîé ìèíóòå â öåíòðå ïîëÿíû âûðàñòàåò
ãðèá âûñòîé h1 ñàíòèìåòðîâ. Íà âòîðîé ìèíóòå íà ðàññòîÿíèè 1 ìåòð âîêðóã ïåðâîãî ãðèáà âûðàñòàþò ãðèáû âûñîòîé h2 . Íà n-îé ìèíóòå íà ðàññòîÿíèè 1 ìåòð âîêðóã óæå ñóùåñòâóþùèõ ãðèáîâ
âûðàñòàþò ãðèáû âûñîòîé hn . ðèáû ðàñòóò êîëüöàìè.
àçóìååòñÿ, ÷òî òàêîé óðîæàé íå ìîã îñòàòüñÿ íåçàìå÷åííûì. Ïîýòîìó áûëà ñîðìèðîâàíà åãèñòðàöèîííàÿ Åäèíàÿ îñóäàðñòâåííàÿ ðèáíàÿ Èíñïåêöèÿ, êîòîðàÿ çàíèìàåòñÿ èññëåäîâàíèåì
âûñîòû ãðèáîâ âûðîñøèõ ïîñëå äîæäÿ. À èìåííî, èíñïåêöèþ èíòåðåñóåò, êàêîé ñàìûé âûñîêèé
ãðèá íàõîäèòüñÿ â êîëüöå îò r äî R. Áóäåì íàçûâàòü êîëüöîì îáëàñòü çàøòðèõîâàííóþ íà ðèñóíêå (âêëþ÷àÿ ãðàíèöû). Ïðè÷åì r - ðàäèóñ ìåíüøåé îêðóæíîñòè, à R - ðàäèóñ áîëüøåé îêðóæíîñòè,
öåíòðû îêðóæíîñòåé íàõîäÿòñÿ â òî÷êå, ãäå âûðîñ ïåðûé ãðèá.

Òàê êàê ïîëÿíà ìîæåò áûòü äîñòàòî÷íî áîëüøîé, òî èíñïåêöèÿ äîëæíà ïðîâåðèòü íåñêîëüêî
êîëåö. Ïðè÷åì, åñëè íà i − 1-îé ïðîâåðêå áûëî âûÿâëåíî, ÷òî ñàìûé âûñîêèé ãðèá èìååò âûñîòó H
(â êîëüöå îò r äî R), òî íà i-îé ïðîâåðêå íåîáõîäèìî âûÿâèòü ãðèá â êîëüöå îò min(R, (r · H + H 2 )
mod n) äî max(R, (r · H + H 2 ) mod n). Äëÿ îò÷åòà èíñïåêöèÿ õî÷åò óçíàòü òîëüêî ñóììó âûñîò
ãðèáîâ ïîëó÷åííûõ, â ðåçóëüòàòå âñåõ ïðîâåðîê.

Ôîðìàò âõîäíîãî àéëà

 ïåðâîé ñòðîêå âõîäíîãî àéëà çàäàíî öåëîå ÷èñëî n (1 6 n 6 2 · 105 )  êîëè÷åñòâî ìèíóò
â òå÷åíèè êîòîðûõ âûðàñòàþò ãðèáû. Âî âòîðîé ñòðîêå çàäàíî n öåëûõ ÷èñåë hi  âûñîòà ãðèáîâ,
âûðîñøèõ íà i ìèíóòå (1 6 hi 6 109 ).  òðåòåé ñòðîêå çàäàíî ÷èñëî m (1 6 m 6 5 · 106 )  êîëè÷åñòâî
ïðîâåðîê. Ïîñëåäíÿÿ ñòðîêà ñîäåðæèò äâà öåëûõ ÷èñëà r è R (0 6 r 6 R < n)  îïèñàíèå ïåðâîé
ïðîâåðêè.

Ôîðìàò âûõîäíîãî àéëà

Âûâåäèòå îòâåò íà çàäà÷ó  ñóììó âûñîò ãðèáîâ, ïîëó÷åííûõ â ðåçóëüòàòå âñåõ ïðîâåðîê.

Ñòðàíèöà 2 èç 7

2012-2013 Òðåíèðîâêà ÑÏáÓ B Çàïðîñû íà îòðåçêå, äåðåâî îòðåçêîâ 2

Ïðèìåð
5
1
3
1
7
1
1
0

ÂÊîíòàêòå, 6 îêòÿáðÿ 2012

mushrooms.in

2 3 4 5

15

4
1 4 2 3 5 1

5

6

Ñòðàíèöà 3 èç 7

mushrooms.out

2012-2013 Òðåíèðîâêà ÑÏáÓ B Çàïðîñû íà îòðåçêå, äåðåâî îòðåçêîâ
ÂÊîíòàêòå, 2 îêòÿáðÿ 2012

Çàäà÷à B. Çàïðîñ èçìåíåíèÿ íà îòðåçêå
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

rvq.in
rvq.out
2 ñåêóíäû
256 ìåãàáàéò

 íà÷àëüíûé ìîìåíò âðåìåíè ïîñëåäîâàòåëüíîñòü an çàäàíà ñëåäóþùåé îðìóëîé: an = n2 mod
12345 + n3 mod 23456.
Òðåáóåòñÿ ìíîãî ðàç îòâå÷àòü íà çàïðîñû ñëåäóþùåãî âèäà:

• íàéòè ðàçíîñòü ìåæäó ìàêñèìàëüíûì è ìèíèìàëüíûì çíà÷åíèåì ñðåäè ýëåìåíòîâ
ai , ai+1 , ..., aj ;
• ïðèñâîèòü ýëåìåíòó ai çíà÷åíèå j .

Ôîðìàò âõîäíîãî àéëà

Ïåðâàÿ ñòðîêà âõîäíîãî àéëà ñîäåðæèò íàòóðàëüíîå ÷èñëî k  êîëè÷åñòâî çàïðîñîâ (k 6
100 000). Ñëåäóþùèå k ñòðîê ñîäåðæàò çàïðîñû, ïî îäíîìó íà ñòðîêå. Çàïðîñ íîìåð i îïèñûâàåòñÿ
äâóìÿ öåëûìè ÷èñëàìè xi , yi .
Åñëè xi > 0, òî òðåáóåòñÿ íàéòè ðàçíîñòü ìåæäó ìàêñèìàëüíûì è ìèíèìàëüíûì çíà÷åíèåì ñðåäè
ýëåìåíòîâ axi ...ayi . Ïðè ýòîì 1 6 xi 6 yi 6 100 000.
Åñëè xi < 0, òî òðåáóåòñÿ ïðèñâîèòü ýëåìåíòó a|xi | çíà÷åíèå yi . Ïðè ýòîì −100 000 6 xi 6 −1 è
|yi | 6 100 000.

Ôîðìàò âûõîäíîãî àéëà

Äëÿ êàæäîãî çàïðîñà ïåðâîãî òèïà â âûõîäíîé àéë òðåáóåòñÿ âûâåñòè îäíó ñòðîêó, ñîäåðæàùóþ
ðàçíîñòü ìåæäó ìàêñèìàëüíûì è ìèíèìàëüíûì çíà÷åíèåì íà ñîîòâåòñòâóþùåì îòðåçêå.

Ïðèìåð

7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3

rvq.in

34
68
250
234
1

Ñòðàíèöà 2 èç 6

rvq.out

2012-2013 Òðåíèðîâêà ÑÏáÓ B Çàïðîñû íà îòðåçêå, äåðåâî îòðåçêîâ 2
ÂÊîíòàêòå, 6 îêòÿáðÿ 2012

Çàäà÷à A. Ýòî êàê ïÿòûé, íî íà îäèí ïîíèæå
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

floor4.in
floor4.out
2 ñåêóíäû
256 ìåãàáàéò

Çíàåòå ëè âû, ïî÷åìó ÷åòâåðòûé ýòàæ çàïåðò è òàì íå îñòàíàâëèâàåòñÿ ëèò? Ïîòîìó ÷òî íà
ñàìîì äåëå ÷åòâåðòûé, çàïåðòûé, ýòàæ, ãäå íå îñòàíàâëèâàåòñÿ ëèò, ñîäåðæèò áåñêîíå÷íîå êîëè÷åñòâî êîìíàò, ïðîíóìåðîâàííûõ íàòóðàëüíûìè ÷èñëàìè. Íà ýòîò ýòàæ ðåãóëÿðíî ïðèåçæàþò äåòè,
êàæäûé èç êîòîðûõ çàðàíåå âûáðàë, â êàêóþ êîìíàòó îí õî÷åò çàñåëèòüñÿ. Åñëè âûáðàííàÿ êîìíàòà
îêàçûâàåòñÿ ñâîáîäíà, òî ðåáåíîê çàíèìàåò åå, â ïðîòèâíîì ñëó÷àå îí çàíèìàåò ïåðâóþ ñâîáîäíóþ
êîìíàòó ñ áîëüøèì íîìåðîì.
Êðîìå òîãî, íåêîòîðûå äåòè óåçæàþò â ñåðåäèíå ñìåíû. Ñðàçó ïîñëå îòúåçäà ðåáåíêà åãî êîìíàòà
ñòàíîâèòñÿ äîñòóïíà äëÿ çàñåëåíèÿ ñëåäóþùåãî.
Ïðîìîäåëèðóéòå ðàáîòó ïðåïîäàâàòåëåé, îòâåòñòâåííûõ çà ÷åòâåðòûé ýòàæ, è íàó÷èòåñü áûñòðî
ñîîáùàòü ïðèåçæàþùèì äåòÿì, êàêóþ êîìíàòó èì ñëåäóåò çàíèìàòü.

Ôîðìàò âõîäíîãî àéëà

Ïåðâàÿ ñòðîêà âõîäíîãî àéëà ñîäåðæèò íàòóðàëüíîå ÷èñëî n  êîëè÷åñòâî ïðèáûòèé è îòúåçäîâ, ïðîèñõîäÿùèõ â òå÷åíèå ñìåíû (n 6 100 000).
Ñëåäóþùèå n ñòðîê ñîäåðæàò èíîðìàöèþ îá äåòÿõ. ×èñëî a > 0 îáîçíà÷àåò, ÷òî ïðèåõàë
øêîëüíèê, æåëàþùèé çàíÿòü êîìíàòó íîìåð a (a 6 100 000). ×èñëî a < 0 îáîçíà÷àåò, ÷òî ñ êîìíàòû
íîìåð |a| óåõàë øêîëüíèê. (àðàíòèðóåòñÿ, ÷òî ýòà êîìíàòà íå áûëà ïóñòà).

Ôîðìàò âûõîäíîãî àéëà

Äëÿ êàæäîãî ïðèåçæàþùåãî øêîëüíèêà âûâåäèòå îäíî íàòóðàëüíîå ÷èñëî  íîìåð êîìíàòû, â
êîòîðóþ îí ïîñåëèòñÿ.

Ïðèìåð
6
5
5
5
-6
5
5

floor4.in

5
6
7
6
8

Ñòðàíèöà 1 èç 7

floor4.out

2012-2013 Òðåíèðîâêà ÑÏáÓ B Çàïðîñû íà îòðåçêå, äåðåâî îòðåçêîâ
ÂÊîíòàêòå, 2 îêòÿáðÿ 2012

Çàäà÷à C. Ñóììà
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

sum.in
sum.out
2 ñåêóíäû
256 ìåáèáàéòà

Äàí ìàññèâ èç N ýëåìåíòîâ, íóæíî íàó÷èòüñÿ íàõîäèòü ñóììó ÷èñåë íà îòðåçêå.

Ôîðìàò âõîäíîãî àéëà

Ïåðâàÿ ñòðîêà âõîäíîãî àéëà ñîäåðæèò äâà öåëûõ ÷èñëà N è K  ÷èñëî ÷èñåë â ìàññèâå è
êîëè÷åñòâî çàïðîñîâ. (1 6 N 6 100 000), (0 6 K 6 100 000). Ñëåäóþùèå K ñòðîê ñîäåðæàò çàïðîñû:
1. A l r x  ïðèñâîèòü ýëåìåíòàì ìàññèâà ñ ïîçèöèÿìè îò l äî r çíà÷åíèå x (1 6 l 6 r 6 n,
0 6 x 6 109 )
2. Q l r  íàéòè ñóììó ÷èñåë â ìàññèâå íà ïîçèöèÿõ îò l äî r . (1 6 l 6 r 6 n)
Èçíà÷àëüíî ìàññèâ çàïîëíåí íóëÿìè.

Ôîðìàò âûõîäíîãî àéëà

Íà êàæäûé çàïðîñ âèäà Q l r íóæíî âûâåñòè åäèíñòâåííîå ÷èñëî  ñóììó íà îòðåçêå.

Ïðèìåðû
5
A
A
A
Q
Q
Q
Q
Q
Q

9
2
3
4
1
2
3
4
5
1

3 2
5 1
5 2
3
2
4
5
5
5

sum.in

3
2
3
4
2
7

Ñòðàíèöà 3 èç 6

sum.out

2013-2014 Òðåíèðîâêà ÑÏáÓ B 8, ðóïïîâûå îïåðàöèè íà äåðåâå îòðåçêîâ, ðàçðåæåííûå òàáëèöû
ÂÊîíòàêòå, 22 îêòÿáðÿ 2013

Çàäà÷à B. Áîëüøàÿ ñòåíà
Èìÿ âõîäíîãî àéëà:
Èìÿ âûõîäíîãî àéëà:
Îãðàíè÷åíèå ïî âðåìåíè:
Îãðàíè÷åíèå ïî ïàìÿòè:

bigwall.in
bigwall.out
2 ñåêóíäû
256 ìåãàáàéò

Æèòåëè ñòðàíû X ïîññîðèëèñü ñ æèòåëÿìè ñòðàíû Y . Â ðåçóëüòàòå êîíëèêòà ïðàâèòåëüñòâî
ñòðàíû X ðåøèëî ïîñòðîèòü ñòåíó íà ïðîòÿæåíèè âñåé ãðàíèöû ñî ñòðàíîé Y (ãðàíèöà èìååò îðìó
îòðåçêà ñ íà÷àëîì â òî÷êå 1 è êîíöîì â òî÷êå n).
Ïðàâèòåëüñòâîì ñòðàíû X áûë òóò æå ñîñòàâëåí ïëàí ñòðîèòåëüñòâà ñòåíû.  ìîìåíò âðåìåíè i ïëàíèðóåòñÿ ïîñòàâèòü íà ó÷àñòîê ãðàíèöû îò òî÷êè li äî ri âêëþ÷èòåëüíî ñòðîéìàòåðèàëîâ
äîñòàòî÷íûõ äëÿ óâåëè÷åíèÿ ñòåíû íà âûñîòó ai .
Êîíå÷íî æå ïðàâèòåëüñòâî ñòðàíû X õî÷åò êîíòðîëèðîâàòü ïðîöåññ âîçâåäåíèÿ ñòåíû. Ïîýòîìó â
ïëàíå ñòðîèòåëüñòâà ïðèñóòñòâóþò ïðîâåðêè ÷èíîâíèêîâ, â íåêîòîðûé ìîìåíò âðåìåíè j ÷èíîâíèêè
ïðèåçæàþò íà ãðàíèöó è çàìåðÿþò ìàêñèìàëüíóþ âûñîòó ÷àñòè ñòåíû îò òî÷êè lj äî òî÷êè rj , î
ðåçóëüòàòàõ îíè äîëæíû íåìåäëåííî ñîîáùèòü â ïðàâèòåëüñòâî ñòðàíû X .
Âàøà çàäà÷à - íàéòè îæèäàåìûå ðåçóëüòàòû ïðîâåðîê, ñ êîòîðûìè áóäåò ñâåðÿòñÿ ïðàâèòåëüñòâî
ñòðàíû X ïðè ïîëó÷åíèè äàííûõ îò ÷èíîâíèêîâ.

Ôîðìàò âõîäíîãî àéëà

 ïåðâîé ñòðîêå âõîäíîãî àéëà äàíû äâà ÷èñëà n - äëèííà ãðàíèöû è m - êîëè÷åñòâî ïóíêòîâ
â ïëàíå (1 ≤ n, m ≤ 2 · 105 ).
 ñëåäóþùèõ m ñòðîêàõ äàíû îïèñàíèÿ ïóíêòîâ ïëàíà äâóõ âèäîâ:

• build l r a - íàäñòðîéêà ñòåíû îò òî÷êè l äî r âêëþ÷èòåëüíî (1 ≤ l ≤ r ≤ n) íà âûñîòó a
(1 ≤ a ≤ 104 ).
• test l r - ïðîâåðêà ñòåíû îò òî÷êè l äî r âêëþ÷èòåëüíî (1 ≤ l ≤ r ≤ n)

Ôîðìàò âûõîäíîãî àéëà

Äëÿ êàæäîãî ïóíêòà ïðîâåðêè âûâåäèòå åäèíñòâåííîå ÷èñëî â íîâîé ñòðîêå - ðåçóëüòàò ïðîâåðêè.

Ïðèìåðû

5 6
build 1 4
build 2 5
test 1 1
test 1 5
build 3 4
test 2 3
3 3
test 1 3
build 2 2
test 1 3

bigwall.in
2
1

2
3
13

10

1

0
1

Ñòðàíèöà 3 èç 6

bigwall.out