2018 учебный год

(Табиғат қорғаушысы)

Ограничение по времени:

2 seconds

Ограничение по памяти:

512 megabytes

Темірұлан - Каспий аймағының табиғаты мен жануарларын қорғаушылар тобының белсенді мұшесі. Жақында өз туған жеріне серуендеп жүргенде ол ЖранУ есімді сирек кездесетін өсімдікті кездестірді. ЖранУ өте ерекше өсімдік. Олар тек үлкен және ескі ағаштардын көлеңкелерінде ғана өседі. Темірұлан бірінен кейін бірі орналасқан $n$ ағашты тексерді де, әр ағаштың түбіне ЖранУ өсімдігін отырғызуға болатынын немесе болмайтындығын тексерді. ЖранУ өсімдігі Темірұланға ұнағаны сонша, ол әр жыл сайын, $q$ жыл бойы осы өсімдікті отырғызуға бел байлады. Бұл өсімдікті отырғызу кезінде ол $l$ мен $r$ арасында бірінен кейін бірі орналасқан ағаштарды алып, егер ЖранУ өсімдігін отырғызуға болытын болса отырғызады. Өсімдікті отырғызып болған соң, оларды міндетті түрде суғару керек. Ол үшін Темірұлан өзімен бірге өлшемі $k$ болатын суға арналған шелек алды, бұл шелек арқылы қатарынан орналасқан $k$ ағаштардың көлеңкесінде отырғызылған өсімдіктерді суғаруға болады. Темірұлан әр отырғызылған өсімдікті кем дегенде бір рет суғарғысы келеді. Барлық жаңадан отырғызылған өсімдіктерді суғару үшін кем дегенде қанша суға арналған шелек қажет? Назар аударыңыз, Темірұлан әр жыл сайын алдыңғы жылда отырғызылған өсімдіктерді есептемей суғарады.

Формат входного файла

Бірінші жолда екі бүтін сандар беріледі $n$ және $t$ $(1 \le n \le 2\cdot10^5, 0 \le t \le 1)$ — ағаштардың саны және енгізілетін сандарды оқуға арналған тұрақты сан. Келесі $n$ сан $i$-ші ағашты сипаттайды, егер $i$-ші сан 0 болса, онда өсімдікті $i$-ші ағаштың түбіне отырғызуға болмайды, олай болмаса болады. Ағаштар нөлден бастап реттеледі Келесі жолда $q$ $(1 \le q \le 2\cdot10^5)$ саны беріледі — өсімдікті отырғызу саны. Ал келесі $q$ жолдарда үш бүтін саннан беріледі: $a_i$ $b_i$ $c_i$ $(0 \le a_i, b_i, c_i \le 10^9)$ Назар аударыңыз, кесінділердің шеттері $[l_i, r_i]$ және $k_i$ саны кодталған және оларды алу үшін келесі түрлендіруді қолдану керек. { \center $l_i = (a_i \oplus (t*lastans)) \mod n, \quad r_i = (b_i \oplus (t*lastans)) \mod n, \quad k_i = ((c_i \oplus (t*lastans)) \mod n) +1 $ \center
} $lastans$ — соңғы сұраққа жауап (алғашқыда $lastans$ $0$-ге тең). Егер $l_i$ мәні $r_i$ мәнінен үлкен болса, онда $l_i$ мен $r_i$ мәндерінің орынын ауыстыру қажет. Бұл жерде $\oplus$ операциясы биттік XOR немесе жоюшы НЕМЕСЕ. Бұл операция барлық заманауи бағдарламалау тілдерінде бар, С++ және Java тілінде <<$\string^$>>, ал Pascal тілінде <>. $a \mod b$ операциясы $a$-ны $b$-ға бөлгендегі қалдықты алуды білдіреді.

Формат выходного файла

$q$ жол шығарыңыз. $i$-ші жолда бір сан шығарыңыз — $i$-ші сұраққа жауап.

Система оценки

Бұл есеп бес бөлімнен тұрады, әр бөліменде берілген шектеулер орындалады.

1. $n \le 100$, $k_i = 1$, $t = 0$. $7$ баллға бағаланады.
2. $n \le 2000$, $q \le 2000$. $12$ баллға бағаланады.
3. $n \le 10^5$, $q \le 10^5$, $k_i \le 10$, $t = 0$ . $21$ баллға бағаланады.
4. $n \le 2\cdot10^5$, $q \le 2\cdot10^5$, $t = 0$ . $23$ баллға бағаланады.
5. Есепте берілген шектеулер. $37$ баллға бағаланады.

Пример:

Вход

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

Ответ

1
4
2
2
1
1

( Aidos Nurmash )