Есеп D. Екі кезек

Екі кезек бар. Біріншісінде $n$ адам тұр, екіншісінде $m$ адам тұр. Бірінші кезек бір адамға $A$ минутта қызмет көрсетеді, екінші кезек бір адамға $B$ минутта қызмет көрсетеді. Санақ $1$-ші минуттан басталады. Әр минут сайын келесілер рет-ретімен болады:

1. Бірінші кезекте тұрған бірінші адамға қызмет көрсетілсе, ол кезектен шығады.
2. Екінші кезекте тұрған бірінші адамға қызмет көрсетілсе, ол кезектен шығады.
3. Бірінші кезекте тұрған соңғы адам, егер ол екінші кезектің соңына ауысқанда оның реттік нөмірі қазіргіден төменірек болса, екінші кезектің соңына ауысады.
4. Екінші кезекте тұрған соңғы адам, егер ол бірінші кезектің соңына ауысқанда оның реттік нөмірі қазіргіден төменірек болса, бірінші кезектің соңына ауысады.

Барлық адамдарға қызмет көрсетіліп біткендегі уақыт $T$-ны хабарлаңыз. Бірінші және жалғыз жолда төрт бүтін сан $n$, $m$, $A$ және $B$ ($1 <= n, m, A, B <= 10^5$) берілген. Бір бүтін сан — барлық адамдарға қызмет көрсетіліп біткендегі уақыт $T$-ны хабарлаңыз. Бұл есеп $5$ ішкі есептен тұрады. Вход

2 3 1 2

Ответ

4

Вход

5 6 4 4

Ответ

24

Вход

3 1 2 4

Ответ

8

Бірінші мысалды қарастырайық. Минут $1$. Бірінші кезекте тұрған адамға қызмет көрсетіледі және ол кезектен шығады. Енді $n=1$, $m=3$. Екінші қатардағы соңғы адам бірінші қатардың соңына ауысады. Енді $n=2$, $m=2$. Минут $2$. Бірінші кезекте тұрған адамға қызмет көрсетіледі және ол кезектен шығады. Енді $n=1$, $m=2$. Екінші кезекте тұрған бірінші адамға қызмет көрсетіліп, ол кезектен шығады. Енді $n=1$, $m=1$. Басқа ештеңе болмайды. Минут $3$. Бірінші кезекте тұрған адамға қызмет көрсетіледі және ол кезектен шығады. Енді $n=0$, $m=1$. Басқа ештеңе болмайды. Минут $4$. Екінші кезекте тұрған бірінші адамға қызмет көрсетіліп, ол кезектен шығады. Енді $n=0$, $m=0$. Барлық адамдарға қызмет көрсетілді, сондықтан жауап $T=4$.

Есеп E. Графты бояу

$N$ төбеден және $M$ бағытталған қырдан тұратын тұзақсыз граф беріледі. Төбелер $1$ден $N$ге дейн сандармен нөмірленген. Графта $1$ мен $N$ төбесін қосатын қыр жоқ. Басында барлық төбе ақ түспен боялған. Мансұрға дәл $B$ төбені қара түске бояу қажет. Боялған соң, екі шетінің түсі бірдей болатын қырлар жойылып кетеді. Екі шетінің түсі бірдей қырлар жойылған соң, $1$-ден $N$-ге жол болмайтындай Мансұрға боялатын $B$ нүктеңі таңдауға көмектесіңіз . Әр тестте бірнеше кіріс жиынтығы бар. Бірінші жолда бір бүтін сан $T$($1 <= T <= 100$) — кіріс деректер жиындарының саны. Әрбір кіріс деректер жиынтығының бірінші жолында үш бүтін сан $N$,$M$ және $B$($3 <= N <= 10^5$, $0 <= M <= min(2 \cdot 10^5,\frac{N \cdot (N - 1)}{2})$, $1 <= B <= N$) беріледі. Келесі $M$ жолда екі бүтін саннан $u$ және $v$($1 <= u, v <= N$, $u \ne v$, $(u,v) \ne (1, N)$) — $u$дан $v$ға бағытталған қыр. Графта қайталанатын қырлар жоқ және граф тұзақсыз. Тұзақсыз деген бір төбеден бастап, бірнеше қыр арқылы өтіп өзіне қайтып келуге болмайды дегенді білдіреді. Әр тесттегі $N$-дердің қосындысы $10^6$дан аспайды. Әр тесттегі $M$-дердің қосындысы $10^6$дан аспайды. Есеп шартына сәйкес бояуға болмаса <<-1>> шығарыңыз. Болса, $B$ бүтін сан — қараға бояу керек төбелердің нөмерлерін шығарыңыз. Егер бірнеше дұрыс жауап болса, кез келгенің шығаруға болады. Вход

2
15 16 5
1 2
1 3
1 4
1 5
2 7
3 7
4 8
5 7
7 9
8 9
9 10
9 11
9 12
10 15
11 15
12 15
3 2 2
2 3
1 2

Ответ

1 8 10 7 9
2 3

Есеп F. XOR-сумма

$n$ бүтін оң саннан тұратын $a$ массиві берілген. $1$-ден $m$-ге дейінгі әрбір бүтін $k$ саны үшін $(a_1 \bmod k) \oplus (a_2 \bmod k) \oplus \ldots \oplus (a_n \bmod k)$ мәнін табыңыз. Бұл жерде $\oplus$ биттік XOR немесе болдырмау НЕМЕСЕ операциясын білдіреді. Бұл операция барлық заманауи бағдарламалау тілдерінде бар, С++, Python және Java тілінде <<^>>, ал Pascal тілінде <>. Бұл жерде $\bmod$ бөлгендегі қалдықты білдіреді. Яғни, $(a \bmod b)$ — $a$ санын $b$ санына бөлгендегі қалдық.

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

Бірінші жолда екі бүтін сан $n$ және $m$ ($1 <= n, m <= 500\,000$) беріледі. Екінші жолда $a_1, a_2, \ldots, a_n$ ($1 <= a_i <= m$) массиві беріледі.

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

Бос орын арқылы $m$ бүтін сан шығарыңыз, ол жерде $k$-ші сан $(a_1 \bmod k) \oplus (a_2 \bmod k) \oplus \ldots \oplus (a_n \bmod k)$ мәніне тең болуы қажет.

Примеры:

Вход

4 5
2 5 4 2

Ответ

0 1 3 1 4

Вход

10 12
1 2 4 8 9 10 11 12 3 5

Ответ

0 1 1 1 0 1 0 5 9 3 11 1