PROGRAMING PROBLEMS

Шаардлагагүй бол гэрлээ унтрааж хэвших нь цахилгаан эрчим хүчний нөөц, цаашлаад улс орны эдийн засагийн хэмнэлтэд маш сайнаар нөлөөлдөг зуршил юм. Энэ талаар олж мэдсэн нэгэн гудамжны оршин суугчид зөвлөлдөн дараах байдлаар хамтран ажиллаж цахилгаан эрчим хүчний хэмнэлт хийхээр шийджээ.
 
●     Гудамжинд N айл оршин суудаг ба тэдгээр нь 1, 2, 3, ... N гэж дугаарлагддаг.
●     Айл бүр зөвхөн нэг гэрэлтэй ба түүнийгээ асааж, унтрааж чаддаг.
●     Гудамжний ахлагчийн зааварчилгаагаар гэрлийнхээ төлвийг сольдог (асаалттай бол унтраах, унтраалттай бол асаах үйлдэл).
●     Гудамжний ахлагч L ээс R дугаартай айлууд гэрлээ эсрэгээр нь солих зааварчилгаа өгдөг. Энд мөн L, R дугаартай айлууд орно. Энэхүү зааварчилгааг айл бүр дагаж мөрддөг ба гудамжний ахлагч ч гэрлээ эсрэгээр нь солихоо мартдаггүй.
 
 
Мөн гудамжний ахлагч танаас одоогоор L ээс R дугаартай айлууд дунд хэдэн ширхэг айл гэрлээ асаасан байгааг олж өгөхийг хүсдэг. Энэ нь тэр гудамжинд олон айл оршин суудаг тул маш хүнд даалгавар юм.
 
Даалгавар
Та гудамжний ахлагчийн асуултад хариулах програм бичнэ үү. Таны програм стандарт оролдоос мэдээлэл уншиж стандарт гаралтруу хэвлэдэг байх шаардлагатай.
 
Оролт
Оролтын эхний мөрөнд гудамжний оршин суугчдийн тоо болох N тоо.
Дараагийн мөрөнд N ширхэн 0 эсвэл 1 утгатай бүхэл тоо нэг ширхэг хоосон зайгаарлагдан байхлана. i-р (1 ≤ i ≤ N) тоо нь i-р айлын гэрлийн төлөв юм. 1 утагай бол ассан, 0 утгатай бол унтарсан төлөвт байгааг илэрхийлнэ.
Дараагийн мөрөнд гудамжний ахлагчийн зааварчилгаа болон хүсэлтүүдийн тооны нийлбэр болох Q тоо байна.
Дараагийн Q мөр бүрт T, L, R, (T = 0 эсвэл T = 1, 1 ≤ L ≤ R ≤ N) гурван бүхэл тоо байна.
T нь 0 утгатай бол L ээс R дураартай айлууд гэрлийнхээ төлвийг өөрчлөх зааварчилгааг.
T нь 1 утгатай бол яг одоогоор L ээс R дураартай айлууд дунд хэдэн айл гэрлээ унтраасан байгааг мэдэхийг хүссэн хүсэлтийг илэрхийлнэ.
 
Гаралт
Гудамжний ахлагчийн хүсэлт бүрийн гариуг дарааллаар нь тус бүр нь нэг мөрөнд байрлахаар хэвлэнэ.
 
Жишээ
 




Жишээ оролт


Жишээ гаралт




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


2
1
2
3
 




 
Тайлбар
 
Анхны төлөв                                                                (1 0 1 0 1)
[1, 4] завсарт 2 айлийн гэрэл асаалттай байна.       (2) - Гаралт
[1, 3] завсрын айлууд гэрлээ эсэргээр нь сольсон   (0 1 0 0 1)
[1, 4] завсарт 1 айлийн гэрэл асаалттай байна.       (1) - Гаралт
[2, 5] завсарт 2 айлийн гэрэл асаалттай байна.       (2) - Гаралт
[1, 5] завсрын айлууд гэрлээ эсэргээр нь сольсон   (1 0 1 1 0)
[1, 5] завсарт 3 айлийн гэрэл асаалттай байна.       (3) - Гаралт
 
Дэд даалгаварууд
Үндсэн даалгавар нийт 4 дэд даалгаварт огтлолцолгүйгээх хуваагдна.
 
Дэд даалгавар 1
N ≤ 5000 ба Q ≤ 5000. Энэ тохиолдолд бодвол та нийт 100 онооноос 10 оноо авна.
 
Дэд даалгавар 2
N ≤ 10000, Q ≤ 100000 ба гудамжний ахлагч гэрлийн төлөв солих тухай зааварчилгаа өгдөггүй. Зөвхөн хүсэлтүүд гаргадаг. Энэ тохиолдолд бодвол та нийт 100 онооноос 20 оноо авна.
Дэд даалгавар 3
N ≤ 10000, Q ≤ 100000 ба гудамжний ахлагч 1 ≤ L=R ≤ N буюу зөвхөн нэг айлыг гэрлийн төлвөө солих талаар зааварчилгаа өгдөг. Энэ тохиолдолд бодвол та нийт 100 онооноос 20 оноо авна.
 
Дэд даалгавар 4
Үлдсэн хязгаарлалт буюу N ≤ 10000, Q ≤ 100000 ба 1 ≤ L ≤ R ≤ N. Энэ тохиолдолд бодвол та нийт 100 онооноос 50 оноо авна. Энэ даалгавар нь өмнөх 3 дэд даалгаварыг агуулна.