В городе монстров есть большой парк, состоящий из нескольких достопримечательностей и соединяющих их односторонних дорог. Всего в парке $v$ достопримечательностей, пронумерованных от $1$ до $v$. Среди них есть $n$ входов (достопримечательности с номерами $1, 2, \dots, n$) и $1$ выход (достопримечательность с номером $v$). В парке проложено $e$ дорог, где $i$-я дорога ведет из достопримечательности $a_i$ в достопримечательность $b_i$.
Каждая достопримечательность $i$ имеет метку $s_i$, которая может быть либо &, либо |. Аналогично, каждая дорога $i$ имеет метку $t_i$, которая может быть одной из пяти: &, |, ~, <, >. Если $t_i$ не равно ~, то у дороги $i$ также есть вес $l_i$.
Каждый день в парк входит группа из $n$ монстров. В $i$-й день $n$ монстров с начальными уровнями здоровья $h_{i,1}, h_{i,2}, \dots, h_{i,n}$ одновременно входят в соответствующие входы $1, 2, \dots, n$ и начинают перемещаться по парку. Каждую минуту каждый монстр размножается на $k$ копий (где $k$ — количество дорог, выходящих из текущей достопримечательности), и каждая копия перемещается по одной из этих дорог.
Прохождение одной дороги занимает ровно $1$ минуту. После прохождения дороги $i$ уровень здоровья монстра $h$ изменяется на $h'$. Правила изменения приведены в таблице ниже.
| $t_i=$ | $h'=$ | Описание | |
|---|---|---|---|
& |
$h\ \mathrm{AND}\ l_i$ | Побитовое И между $h$ и $l_i$ | |
| ` | ` | $h\ \mathrm{OR}\ l_i$ | Побитовое ИЛИ между $h$ и $l_i$ |
~ |
$\mathrm{NOT}\ h$ | Побитовое отрицание $h$ | |
< |
$h\ \mathrm{SHL}\ l_i$ | Побитовый сдвиг влево на $l_i$ (младшие биты заполняются $0$) | |
> |
$h\ \mathrm{SHR}\ l_i$ | Побитовый сдвиг вправо на $l_i$ (старшие биты заполняются $0$) |
В таблице $\mathrm{AND}, \mathrm{OR}, \mathrm{NOT}, \mathrm{SHL}, \mathrm{SHR}$ соответствуют побитовым операциям. Все значения $h, l_i$ и $h'$ являются $32$-битными беззнаковыми целыми числами. Для операций $\mathrm{AND}, \mathrm{OR}$ выполняется $0 \le l_i < 2^{32}$. Для операций $\mathrm{SHL}, \mathrm{SHR}$ выполняется $0 \le l_i < 32$.
Когда несколько монстров с уровнями здоровья $h_1, h_2, \dots, h_c$ встречаются в одной достопримечательности $i$, они объединяются в одного монстра с уровнем здоровья $h'$, равным результату операции $s_i$ над всеми $h_j$. То есть, если $s_i$ — &, то $h'=h_1\ \mathrm{AND}\ h_2\ \mathrm{AND}\ \dots\ \mathrm{AND}\ h_c$; если $s_i$ — |, то $h'=h_1\ \mathrm{OR}\ h_2\ \mathrm{OR}\ \dots\ \mathrm{OR}\ h_c$. После этого, если монстр находится на выходе из парка, он покидает парк. Первый монстр, покинувший парк в каждой группе, называется Победителем (Winner). Начальные уровни здоровья всех монстров и уровень здоровья Победителя в момент выхода из парка записываются.
Монстр погибает тогда и только тогда, когда выполняется одно из следующих условий (погибший монстр больше не совершает действий и не участвует в объединениях):
- Из текущей достопримечательности не выходит ни одной дороги, и это не выход из парка.
- Уровень здоровья монстра равен $0$. Это означает, что монстр мог погибнуть на дороге или мгновенно после объединения.
- Время, прошедшее с момента входа монстров в парк, превысило $k$ минут, где $k$ — срок жизни монстра.
Считается, что к началу $(i+1)$-го дня все монстры, вошедшие в $i$-й день, либо покинули парк, либо погибли.
Однако спустя $m$ дней стихийное бедствие разрушило парк. Город монстров хочет восстановить парк на основе записей за эти $m$ дней. Ваша задача — спроектировать любую конфигурацию парка, удовлетворяющую всем записям за $m$ дней.
Входные данные
Все входные данные rebuild1.in ~ rebuild10.in см. в архиве с данными.
Первая строка содержит три целых числа $n, m, k$, обозначающие количество монстров в день, количество дней и срок жизни монстров соответственно.
Со второй строки по $(2m+1)$-ю строку содержатся записи за $m$ дней. В строке $2i$ содержатся $n$ целых чисел $h_{i,1}, h_{i,2}, \dots, h_{i,n}$, обозначающих начальные уровни здоровья монстров в $i$-й день. В строке $2i+1$ содержится одно целое число $w_i$, обозначающее уровень здоровья Победителя в $i$-й день. Гарантируется, что Победитель существует каждый день.
Выходные данные
Для каждого из 10 входных файлов rebuild1.in ~ rebuild10.in вы должны предоставить соответствующие выходные файлы rebuild1.out ~ rebuild10.out.
Первая строка должна содержать два целых числа $v$ и $e$, количество достопримечательностей и дорог соответственно ($n < v \le 100$, $0 \le e \le 500$).
Вторая строка должна содержать строку $s$ длины $v$, где $i$-й символ $s_i$ — это & или |, обозначающий метку $i$-й достопримечательности.
С третьей по $(e+2)$-ю строку опишите дороги. Каждая строка должна содержать четыре элемента: $a_i, b_i, t_i, l_i$, где $a_i, b_i$ — начальная и конечная достопримечательности, $t_i$ — метка, $l_i$ — вес. $1 \le a_i, b_i \le v$. Метка $t_i$ может быть &, |, ~, <, >. Примечание: если $t_i$ равно ~, значение $l_i$ не выводится. Допускается наличие нескольких дорог между двумя достопримечательностями, а также дороги, начинающиеся и заканчивающиеся в одной и той же достопримечательности.
Вы можете вывести любой подходящий вариант. Гарантируется, что решение существует.
Примеры
Входные данные 1
2 4 2 11 1 20 11 2 18 11 3 16 18 12 12
Выходные данные 1
4 4 ||&& 1 3 | 0 2 3 ~ 2 4 & 12 3 4 < 1
Примечание
Пример вывода — один из возможных вариантов восстановления парка. Рассмотрим монстров в 1-й день:
Изначально есть 2 монстра в достопримечательностях 1 и 2 с уровнями здоровья 11 и 1.
На 1-й минуте монстр из достопримечательности 1 переходит по дороге в достопримечательность 3, его здоровье становится $11\ \mathrm{OR}\ 0=11$. Монстр из достопримечательности 2 размножается на 2 копии: одна переходит в достопримечательность 3 со здоровьем $\mathrm{NOT}\ 1=4294967294$, другая переходит в достопримечательность 4 со здоровьем $1\ \mathrm{AND}\ 12=0$ (погибает до входа). В достопримечательности 3 два монстра объединяются в одного с уровнем здоровья $11\ \mathrm{AND}\ 4294967294=10$.
На 2-й минуте монстр из достопримечательности 3 переходит в достопримечательность 4, его здоровье становится $10\ \mathrm{SHL}\ 1=20$. Достопримечательность 4 — выход, поэтому монстр покидает парк и становится Победителем.
Таким образом, уровень здоровья Победителя равен 20.
Как тестировать ваш вывод
В терминале перейдите в директорию с задачей (пользователям Windows рекомендуется использовать cmd). Предположим, что все файлы находятся в папке rebuild.
cd rebuild
Для проверки вашего решения используйте инструмент checker. Запустите его в терминале:
./checker_linux64 <case_no>
где <case_no> — номер теста. Например, ./checker_linux64 3 протестирует файл rebuild3.out. (Пользователи Windows используют checker_win32 3).
Для Linux-систем также доступны версии checker_linux32. Если программа не запускается, выполните chmod +x checker_linux64 или chmod +x checker_linux32.
Также вы можете использовать команду:
./checker_linux64 –w <case_no>
чтобы вывести процесс перемещения монстров в файл report.log. Внимание: файл report.log может достигать размера 150 МБ.
Подзадачи
Для каждого из 10 входных файлов предоставляется соответствующий файл оценки rebuild1.ans ~ rebuild10.ans. Каждый файл содержит 10 строк, где $i$-я строка содержит параметр $a_i$.
Каждый тест оценивается отдельно. Если формат вывода неверный, начисляется 0 баллов. Если формат верный, но удовлетворены не все $m$ записей, вы можете получить частичные баллы.
Если количество удовлетворенных записей равно $x_{user}$, ваш балл определяется по таблице:
| Баллы | Условие | Баллы | Условие |
|---|---|---|---|
| $10$ | $x_{user}\ge a_{10}$ | $5$ | $x_{user}\le a_5$ |
| $9$ | $x_{user}\ge a_9$ | $4$ | $x_{user}\ge a_4$ |
| $8$ | $x_{user}\ge a_8$ | $3$ | $x_{user}\ge a_3$ |
| $7$ | $x_{user}\ge a_7$ | $2$ | $x_{user}\ge a_2$ |
| $6$ | $x_{user}\ge a_6$ | $1$ | $x_{user}\ge a_1$ |
Если ни одно из условий не выполняется, начисляется 0 баллов. Если выполняется несколько условий, засчитывается наибольший балл.