(Қараңғы бөлмелер)
Сізде $n$-$1$ дәліз арқылы қосылған $n$ бөлме бар. Әр бөлмеден, әр бөлмеге жетуге болатыны белгілі. Әр бөлмеде бір шам бар. $1$-ден $m$-ға дейін нөмірленген $m$ батырма бар. $i$-ші батырма $v_i$ бөлмесінен $u_i$ бөлмесіне дейінгі жолында шамдарды өшіреді немесе қосады. Әр бөлменің күйі бір санмен көрсетіледі: $0$ немесе $1$, осында $0$ шамның өшірілгенін, ал $1$ шамның қосылып тұрғанын көрсетеді. Сіздің үйіңізге Алан қонаққа келді. Нөмірлері $1$-ден $n$-ға дейінгі бөлмелердің күйлері $a_1$, $a_2$, ..., $a_n$ тең болған жағдайда, Алан өзін үйіндегіндей сезінеді. Алан өз үйіндегіндей сезінуі үшін батырмаларды қандай ретпен басу керектігін табуыңыз қажет. Және де қонақты көп күттірмес үшін осы реттің ұзындығы $10^5$ батырмадан аспауы қажет. Егер де ретті құрау мүмкін болмаса, -$1$ деп шығарыңыз. Ең алғашында барлық шамдар өшірулі тұр. Бірінші жолда бір бүтін сан $n$ ($1 \le n \le 10^4$) — бөлмелер саны беріледі. Екінші жолда $n$ сан беріледі: $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 1$) тілекті бөлмелердің күйі. Келесі $n$-$1$ жол әр дәлізді екі $v$ және $u$ ($1 \le u, v \le n$) бөлмелердің нөмірлері арқылы бейнелейді, $v$ және $u$ бөлмелері арасында дәліз бар. Келесі жолда бір бүтін сан $m$ ($1 \le m \le 10^4$) — батырмалар саны беріледі. Келесі $m$ жолда батырмалар бейнеленеді. $i$-ші жол $i$-ші батырманы үш саннан $u_i$, $v_i$ және $t_i$ беріледі. $u_i$ мен $v_i$ ($1 \le u_i, v_i \le n$) бөлмелердің нөмірлері, батырманың істейтін бөлмелерін бейнелейді. Егер $t_i$ $0$-ға тең болса, бастырма шамдарды өшіреді, $1$-ге тең болғанда қосады. Батырмалар ретін құрау мүмкін болмаған жағдайда `-$1$'(жақшасыз) шығарыңыз. Мүмкін болған жағдайда, реттегі батырмалардың саны $l$ және келесі жолда $l$ сан — реттегі батырмалардың нөмірлерін шығарыңыз. Бұл есеп бес бөлімнен тұрады:

1. $1 \le n \le 100, 1 \le m \le 8$. Бөлім $11$ ұпайға бағаланады.
2. $1 \le n,m \le 2000$ және барлық батырма үшін $t_i = 1$. Бөлім $15$ ұпайға бағаланады.
3. $1 \le n,m \le 500$. Бөлім $19$ ұпайға бағаланады.
4. $1 \le n,m \le 10^4$ және $i$-ші дәліз $i$ және $i + 1$ бөлмелерді қосады. Бөлім $25$ ұпайға бағаланады.
5. $1 \le n,m \le 10^4$. Бөлім $30$ ұпайға бағаланады.

s Вход

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

Ответ

3
4 2 3

Вход

3
0 0 1
1 3
1 2
1
1 3 1

Ответ

-1

\Note { \center \includegraphics[width=1.0\textwidth]{samplee.eps}
}

(Табиғат қорғаушысы)
Темірұлан - Каспий аймағының табиғаты мен жануарларын қорғаушылар тобының белсенді мұшесі. Жақында өз туған жеріне серуендеп жүргенде ол ЖранУ есімді сирек кездесетін өсімдікті кездестірді. ЖранУ өте ерекше өсімдік. Олар тек үлкен және ескі ағаштардын көлеңкелерінде ғана өседі. Темірұлан бірінен кейін бірі орналасқан $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

(ИГО іріктемесі)
Төрт жыл сайын бүкіл елдер арасында <<Информатика бойынша Гладияторлық Олимпиадсы>> өтеді. Бұл сирек кездесетін жарыс, себебі қатысушыларға тек күшпен ғана жеңіп шығуға болмайды, соған қатар қатысушының ақылы жетік болуы керек. Берляндияда қазір бір жағымды қиындық туып отыр, олимпиадаға $N$ әр түрлі үміткерлер бар. Әр үміткердің зияткерлік деңгейін бір санмен бейнеледі, $i$-үміткердің зияткерлік деңгейі $i$-ге тең. Берляндия информатика бойынша күшті ел болғандықтан, олимпиадаға ел атынан кез-келген қатысушылар санын жіберуге болатыны мәлім. Алайда, оған қарамастан ел ішінде іріктеу жасамақшы. Іріктеу раундына бірнеше үміткер алынып, $M$ тур өткізіледі. $i$-турда осы операциялар орындалады:

1. Егер де осы турда ең болмаса $a_i$ үміткер болса, онда үміткерлердің ішінде ең төмеңгі деңгеймен $a_i$ үміткер кетеді. $i$-тур қайта жүргізіледі.
2. Егер де осы турда үміткерлер саны $a_i$ кіші болса, онда келесі турға барлық үміткерлер өтеді. $i=M$ болған жағдайда іріктеу аяқталады.

Іріктеуден кейінгі қалатын үміткерлер тізімі жалғыз екенін байқауға болады. Тілшілер барлық бола алатын жағдайларды қарастырып, барлық мүмкін бола алатын бастапқы үміткерлердің тізбегінен іріктеуден өткен үмірткерлердің тізбектерінің санын тапқылары келеді. Осы сан тым үлкен болғандықтан $P$ санына бөлгеннен кейінгі қалдығын шығарыңыз. Бірінші жолда үш бүтін сан $M$, $N$ және $P$ ($1 \le M \le 1000$, $1 \le P, N \le 10^9$) — раундтар саны, үміткерлер саны және қалдық алуға арналған сан берілген. Ескертеміз, $P$ саны міндетті түрде жай сан болып келуі шарт емес. Келесі жолда $M$ бүтін сан $a_i$ ($1 \le a_i \le 1000$) — $i$-шы раундтың саны берілген. Бір сан — есептің жауабын шығарыңыз. Есеп бес бөлімнен тұрады, әр бөлімде есепте берілген шектеулер орындалады:

1. $n \le 18$. $10$ ұпайға бағаланады.
2. $n \le 1000$. $18$ ұпайға бағаланады.
3. $n \le 10^6$, $P = 999999937$. $21$ ұпайға бағаланады.
4. Есепте берілген шектеулер. $51$ ұпайға бағаланады.

Вход

3 4 100000
7 3 4

Ответ

17

(Айырмашылық)
Сізде $S$ мультижиыны бар. Мультижиынның жиыннан айырмашылығы: мультижиында сан бірнеше рет кездесуі мүмкін, ал жиында тек қана бір рет. Алғашында, мультижиында $1$-ден $n$-ге дейінгі барлық бүтін сандар бір рет кездеседі. Бір операцияға сіз мультижиыннан екі $a$ және $b$ сандарын таңдап алып, олардың абсолют айырмашылығын |$a$ - $b$| қоса аласыз. Мультижиында тек қана бір $x$ саны болуы үшін сіз кейбір операцияларды орындағыңыз келеді. Бірінші жолда бір бүтін сан $T$ ($1 \le T \le 100$) — тесттердің саны берілген. Келесі $T$ жолда әр тесттің сипаттамасы көрсетілген: екі бүтін сандар $n$ және $x$ ($2 \le n \le 10^5, 0 \le x \le n$) беріледі. Тесттердегі барлық $n$-дердің қосындысы $5 \cdot 10^5$-нен аспайды. Әр тест үшін: егер $x$ санын алу мүмкін емес болса, "NO" (тырнақшасыз) шығарыңыз. Әйтпесе, ол тест үшін: егер $x$ санын алу мүмкін болса, "YES" (тырнақшасыз) шығарыңыз. Келесі $n$-$1$ жолда операцияларды орындау тәртібімен шығарыңыз. Әр операция үшін мультижиыннан таңдалатын екі бүтін санды $a$ және $b$ сандарын шығарыңыз. Берілген тапсырма төрт бөліктен тұрады:

1. $2 \le n \le 4$. Бағалануы $12$ ұпай.
2. $n$ тақ сан және $x = (n + 1) / 2$. Бағалануы $15$ ұпай.
3. $0 \le x \le 1$. Бағалануы $23$ ұпай.
4. $2 \le n \le 10^5$. Бағалануы $50$ ұпай.

Вход

2
5 1
5 0

Ответ

YES
2 3
4 5
1 1
1 0
NO

(Na2a және теңдеу)
Na2a информатика сабағында көп қылжағандықтан, мұғалім оған осы тапсырманы берді. Берілген $a_1,...,a_n,S$ сандары үшін, ($a_1 \oplus x) + (a_2 \oplus x) + ... + (a_n \oplus x) = S$ болатындай оң $x$ санын табу керек. Бұл жерде $\oplus$ операциясы биттік XOR немесе жоюшы НЕМЕСЕ. Бұл операция барлық заманауи бағдарламалау тілдерінде бар, С++ және Java тілінде <<$\string^$>>, ал Pascal тілінде <>. Na2a-ға осы есепті шығаруға көмектесіңіз.

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

Бірінші жолда екі бүтін сан $n$ — берілетін сан тезбегінің санды, және $S (1 \le n \le 10^5, 0 \le S \le 10^{12})$ — берілген қосынды. Екінші жолда $n$ бүтін сан: $a_1$, $a_2$, ..., $a_n(0 \le a_i \le 10^{12})$ берілген.

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

Егер теңдеудің жауабы жоқ болған жағдайда -$1$ шығарыңыз. Басқа жағдайда теңдеу шешілетін $x(x \ge 0)$ санын шығарыңыз. Бірнеше жауап болған жағдайда, кез келген жауап шығаруға болады.

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

Есеп бес бөлімнен тұрады, әр бөлімде есептің берілгеніндегі шарттар орындалады және:

1. $n \le 1000, a_i,s \le 1000$. Бөлім $7$ ұпайға бағаланады.
2. $n = 2, a_i,s \le 10^{12}$. Бөлім $22$ ұпайға бағаланады.
3. $n \le 10^4, a_i,s \le 10^6$. Бөлім $20$ ұпайға бағаланады.
4. $n \le 10^5, a_i,s \le 5 \cdot 10^7$. Бөлім $16$ ұпайға бағаланады.
5. $n \le 10^5, a_i,s \le 10^{12}$. Бөлім $35$ ұпайға бағаланады.

Пример:

Вход

3 4
1 2 3

Ответ

2

\Note Аралас НЕМЕСЕ операциясы төмендегі ақиқаттық кестесіне сәйкес операндтардың (сандардың) қосындысын анықтайды.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Операндтар ондық түрде жазылады, бірақ орындалғанда олар екілік түрге түрлендіріледі. Нәтижесі ондық түрде көрсетіледі. Мысалға, егер $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ сонда: $X$ $\oplus$ $Y$ = $68_{10}$ = $1000100_{2}$.

(Тиманың бапкерлік таңдауы)
Жақын уақыттан бері Тима баскетбол командасын жаттықтыруды бастады. Команданың капитаны ретінде әрқашан бойы ең ұзын ойыншы таңдалады. Ол команданың сәйкес келмеушілік формуласын ойлап тапты. Команданың сәйкес келмеушілігі оның капитатының бойымен қалғандарының бойының айырмаларының қосындысы. Анықтап айтсақ, $h_1, h_2, ... , h_m$ — командадағы ойыншылардың бойларының ұзындығы болсын, $mx = max(h_1, h_2, ..., h_m)$, онда сәйкес келмеушілік = $\sum_{i=1}^{m} mx$-$h_i$. Тимада бір ретте тұрған $n$ ойыншы бар, $i$-ші ойыншының бойы $a_i$. Ол барлық ойыншыны $k$ командаға бөлгісі келеді, әр ойыншы бір командада болу керек және әр команда ретте қатар тұрған ойыншылардан құралуы керек. Тима барлық команданың сәйкес келмеушіліктерінің қосынды аз болатындай бөлгісі келеді. Тимаға командаларды қолайлы бөлуге көмектесіңіз. Бірінші жолда екі бүтін сан берілген $n$ және $k$ ($1 \le n \le 10^5$, $1 \le k \le min(n, 20)$) — ойыншылардың саны және командалардың саны. Екінші жолда $n$ бүтін $a_i$ ($1 \le a_i \le 10^6$) — қатардың сол жағынан $i$-ші тұрған ойыншының бойының ұзындығы. Жалғыз бүтін сан шығарыңыз — есептің жауабын. Есеп алты бөлімнен тұрады, әр бөлімде есептің берілгендегі шарртар орындалады және:

1. $n \le 100$, $k = 1$. Бөлім $5$ ұпайға бағаланады.
2. $n \le 2000$. Бөлім $11$ ұпайға бағаланады.
3. $k = 2$. Бөлім $8$ ұпайға бағаланады.
4. $k = 3$. Бөлім $15$ ұпайға бағаланады.
5. $a_i \le a_{i+1}$, барлық $1 \le i < n$ үшін. Бөлім $19$ ұпайға бағаланады.
6. Есептің еңгізу форматындағы шарттар орындалады. Бөлім $42$ ұпайға бағаланады.

s Вход

7 3
6 4 1 5 3 2 2

Ответ

7

Вход

5 2
4 1 5 5 6

Ответ

5

Вход

9 2
3 7 4 1 3 2 4 6 7

Ответ

22