Про некоторое положительное вещественное число, меньшее $1$, известно следующее:

1. Если это число умножить на $2^{ 122 }_{10}$, результат окажется целым числом.
2. Если это число умножить на $9_{10}$ и перевести запись в двоичную систему, окажется, что эта запись числа не содержит значащих нулей.

Сколько существует таких чисел?

В ответе укажите целое число. Если таких чисел не существует или их бесконечно много, укажите в ответе $NULL$.

Примечание: число $0.1_2$ содержит значащий ноль.

Пример записи ответа:
17

Петя пишет систему управления роботом, который перемещается по плоскости с гексагональной разметкой — правильными шестиугольниками, примыкающими друг к другу одним из ребер. Каждая команда программы перемещает робота на смежный шестиугольник в одном из шести возможных направлений. Петя решил записывать программу в память робота как последовательность кодов команд, используя для записи каждой команды минимально возможное, одинаковое для всех команд количество бит. Петя посчитал, что тогда в сегмент памяти, который у него есть, можно поместить программу длиной ровно $8192$ команды.

Вася обратил внимание на такую особенность робота Пети — любая его программа всегда имеет количество команд, кратное $128$. Он предложил рассматривать программу робота как последовательность подпрограмм, длиной $128$ команд, кодируя каждую такую подпрограмму минимально возможным, одинаковым для всех возможных подпрограмм количеством бит.

Определите максимальную длину программы (кратную $128$), которую можно записать в сегмент памяти, кодируя по методу Васи. В ответе укажите целое число.

Пример записи ответа:
512

Обозначим за $X$ некоторое натуральное число, записанное с помощью $n + 1$ бит, т.е. $X = (x_{n}x_{n-1}...x_{0})_{2}$. Например, если $n = 3$ и $X = 0101_2$, то $x_3 = 0, x_2 = 1, x_1 = 0, x_0 = 1$.

Даны логические функции $A(X)$ и $B(X)$:

$A(X) =\bigwedge\limits_{i=0}^{n-1} \left( x_{i} \to x_{i+1} \right) \wedge (x_{n} \to x_{0})$

$B(X) = \bigvee\limits_{i=0}^{\lfloor {(n-1)}/{2} \rfloor} \neg \left( M(x_{i}, x_{i+ \lceil {(n+1)}/{2} \rceil }, 1) \equiv M(x_{i}, x_{i+ \lceil {(n+1)}/{2} \rceil }, 0) \right)$

Здесь $\lfloor a \rfloor$ — значение $a$ с округлением вниз, $\lceil a \rceil$ — значение $a$ с округлением вверх.

Функция $M(a, b, c)$ задана таблицей истинности:

Сколько существует чисел $X$ таких, что $A(X) = B(X)$, если $n = 19$? В ответе введите целое положительное число.

Примечание: битовая последовательность может начинаться с нуля.

Пример записи ответа:
17

Вася изучает алгоритмы шифрования и решил придумать свой собственный алгоритм. Он решил, что его алгоритм будет рассчитан на шифрование слов из букв современного латинского алфавита. Для каждой буквы в тексте Вася применяет следующие шаги:

1. Выяснить номер этой буквы в алфавите (Вася пронумеровал буквы от $1$ до $26$).
2. Выяснить номер в алфавите $i$-й буквы ключа.
3. Перемножить два данных числа - это и есть Васин код для буквы текста.
4. Увеличить $i$ на $1$ и взять по модулю длины ключа.

Исходно $i = 0$, а нумерация букв в ключе и в тексте для шифрования начинается с нуля.

Чтобы проверить свой алгоритм, Вася взял фразу «the quick brown fox jumps over the lazy dog», убрал из неё пробелы, повторил её $15$ раз подряд и зашифровал полученный текст.

В результате он получил следующую последовательность чисел (см. файл по ссылке). Потом Вася решил проверить, можно ли расшифровать результат и понял, что потерял ключ. Единственное, что он помнит: все символы в ключе были различными. Помогите Васе выяснить, каким был ключ. В ответе введите последовательность строчных букв латинского алфавита без пробелов. Если же восстановить ключ невозможно, укажите в качестве ответа $NULL$.

Примечание. Латинский алфавит: abcdefghijklmnopqrstuvwxyz.

Пример записи ответа:
abcdef

Аксель любит строить разные последовательности, и вчера ему пришёл в голову алгоритм, который показан ниже в виде блок-схемы:

В качестве $t$ Аксель вводит массив, содержащий битовую последовательность из $2^{32}$ нулей. Нумерация элементов массива начинается с нуля.

Определите, какая последовательность из $8$ бит будет находиться, начиная с индекса $4294967096$ ($4294967096, 4294967097, ..., 4294967103$). В ответ введите последовательность бит в порядке возрастания их индексов в последовательности без пробелов.

Пример записи ответа:
01010101

Основная задача протокола TCP – обеспечение надежной доставки данных. Одна из возможных проблем – потеря сообщений на промежуточных устройствах в силу ошибок или переполнения памяти. Для предотвращения таких потерь используется управление перегрузкой в TCP.

В управлении перегрузкой отправитель регулирует скорость передачи данных, постепенно увеличивая ее (мы все же хотим передавать данные как можно быстрее) и уменьшая скорость передачи при возникновении ошибки. Существует множество алгоритмов управления перегрузкой. Одни их них – Tahoe. В нем используются следующие понятия:

• RTT (Round-Trip Time) — номинальное время полного пути пакета, то есть интервал между отправкой сегмента TCP и получением соответствующего ACK (подтверждения). Учтите, что это эталонное значение. В течение времени, равного RTT, отправитель может отправить большое количество пакетов, не дожидаясь ACK.

• cwnd (Congestion Window) — окно перегрузки, переменная на стороне отправителя, определяющая максимальное количество неподтверждённых сегментов, которое можно отправить в сеть без ACK. Этим окном как раз ограничивается скорость передачи. Чем больше окно, тем быстрее (интенсивнее) отправляются TCP-сегменты.

• MSS (Maximum Segment Size) — максимальный размер полезной нагрузки TCP-сегмента (обычно $1460$ байт для Ethernet); используется как единица для роста cwnd.

• ssthresh (Slow Start Threshold) — пороговое значение окна перегрузки; разделяет фазы медленного старта (см. далее) и предотвращения перегрузки. В Tahoe изначально ssthresh не задаётся фиксированно (принимается равным бесконечности), а устанавливается динамически при первой потере. Будем считать (несколько упрощая), что при первой потере ssthresh = cwnd$/2$.

• Slow Start — фаза управления перегрузкой, где cwnd удваивается каждый RTT (при начальном значении, равном $1$ MSS), чтобы быстро «нащупать» реальную пропускную способность сети.

• Congestion Avoidance — фаза, наступающая после достижения ssthresh. В этой фазе cwnd растёт линейно ($+1$ MSS за RTT), чтобы стабилизировать передачу без перегрузки.

Сначала скорость передачи растет согласно Slow Start, а как случается первая потеря, рассчитывается ssthresh, после чего cwnd сбрасывается в $1$ MSS, заново запускается Slow Start (cwnd удваивается каждый RTT), но уже до установленного ssthresh. Достигнув ssthresh, алгоритм переходит в режим Congestion Avoidance, при котором рост cwnd $+ 1$ MSS за RTT, пока не произойдет новая потеря, после чего ssthresh уменьшается вдвое снова. Это создаёт «зубчатую» кривую cwnd.

Например, если потеря случилась при cwnd=$256$ MSS, то ssthresh = cwnd$/2$=$128$ MSS, cwnd сбрасывается в $1$ MSS, возврат в Slow Start — cwnd удваивается каждый RTT до нового ssthresh ($128$ MSS). Достигнув ssthresh, переход в Congestion Avoidance — рост cwnd $+1$ MSS за RTT, пока не произойдет новая потеря.

Пусть передается файл из $64$ сегментов (по $1460$ байт) передаётся по сети с RTT = $120$ мс. Используется алгоритм TCP Tahoe.

• Slow Start: cwnd удваивается каждый RTT, начиная с $1$ MSS.
• После потери: ssthresh = cwnd $/ 2$, cwnd = $1$ MSS.
• Достигнув ssthresh, переход к Congestion Avoidance ($+1$ MSS/RTT).
• Потеря происходит при cwnd = $16$ MSS.

Найдите общее время передачи всех $64$ сегментов в миллисекундах. Выберите наиболее близкий к полученному значению вариант ответа:

Для анализа социальных сетей часто применяют понятие социального графа. В социальном графе пользователи являются вершинами, а каждое ребро показывает, что пользователи добавили друг друга в список друзей.

Исследователь собрал социальный граф для некоторых пользователей социальной сети $Y$. Этот граф хранится в виде одной таблицы friends со следующими полями:

• first_user_id — целое положительное число, идентификатор первого пользователя;
• second_user_id — целое положительное число, идентификатор второго пользователя.

При этом пара полей (first_user_id, second_user_id) является первичным ключом.

Каждая такая пара для удобства хранится дважды. Например, если пользователи с $ID$ $1$ и $2$ добавили друг друга в список друзей, таблица будет содержать две записи:

Исследователь собирает данные аккуратно и даёт несколько гарантий:

• дружба между двумя пользователями всегда хранится двумя строками;
• нет ситуаций, когда пользователь добавил в список друзей самого себя.

Два различных пользователя знают друг друга через одно рукопожатие, если существует третий пользователь, отличающийся от них и являющийся им другом, но при этом сами пользователи не являются друзьями. Иначе говоря, в социальном графе между этими пользователями нет ребра, но есть путь через одну вершину. Например, если пользователи с $ID$ $1$ и $3$ не добавляли друг друга в список друзей, но пользователь с $ID$ $2$ имеет в списке друзей этих пользователей, то пользователи с $ID$ $1$ и $3$ знают друг друга через одно рукопожатие.

Определите, сколько различных пользователей знает пользователь с $ID$ $10$ через одно рукопожатие. Обратите внимание, что самого пользователя и его прямых друзей считать не нужно. В ответе введите одно целое неотрицательное число. Если пользователь с указанным $ID$ не встречается в таблице, введите $0$.

Пример записи ответа:
17

Примечание. В окне ниже можно вводить SQL-запросы для выборки данных.

База доступна для скачивания по ссылке.

Глеб решил изучить новый для себя язык программирования. Так как C++ показался ему слишком простым, он выбрал язык Bassembly. Язык этот пока молодой, поэтому найти удалось только его документацию.

Доступные регистры на данном языке: $\mathtt{eax}$, $\mathtt{ecx}$, $\mathtt{edx}$, $\mathtt{esi}$ и $\mathtt{edi}$.

Каждый регистр хранит беззнаковое 32-битное целое число. Все арифметические операции над регистрами выполняются по модулю $2^{32}$: при переполнении старшие биты отбрасываются. Например, число $2^{32}$ эквивалентно 0, а число -1 эквивалентно $2^{32}-1$.

Bassembly поддерживает пять команд:

$\mathtt{add},\ \mathtt{sub},\ \mathtt{mul},\ \mathtt{inc},\ \mathtt{print}.$

Обозначим через $\mathtt{reg}$, $\mathtt{reg_1}$, $\mathtt{reg_2}$, $\mathtt{reg_3}$ произвольные регистры из списка выше, а через $\mathtt{const}$ — неотрицательное целое число от $0$ до $2^{32}-1$.

Команда $\mathtt{add}$

Команда $\mathtt{add}$ может иметь несколько форм.

• $\mathtt{add}\ 0\ \mathtt{const}$ — выполнить операцию $\mathtt{eax} += \mathtt{const}$.

• $\mathtt{add}\ 1\ \mathtt{reg}$ — выполнить операцию $\mathtt{eax} += \mathtt{reg}$.

• $\mathtt{add}\ 2\ \mathtt{reg_1}\ \mathtt{reg_2}$ — выполнить операцию $\mathtt{reg_1} += \mathtt{reg_2}$.

Команда $\mathtt{sub}$

Команда $\mathtt{sub}$ также может иметь несколько форм.

• $\mathtt{sub}\ 0\ \mathtt{const}$ — выполнить операцию $\mathtt{eax} -= \mathtt{const}$.

• $\mathtt{sub}\ 1\ \mathtt{reg}$ — выполнить операцию $\mathtt{eax} -= \mathtt{reg}$.

• $\mathtt{sub}\ 2\ \mathtt{reg_1}\ \mathtt{reg_2}$ — выполнить операцию $\mathtt{reg_1} -= \mathtt{reg_2}$.

Команда $\mathtt{mul}$

Команда $\mathtt{mul}$ имеет две формы.

• $\mathtt{mul}\ 1\ \mathtt{reg_1}$ — вычислить произведение $\mathtt{eax} \cdot \mathtt{reg_1}$ и сохранить его в пару регистров $[\mathtt{ecx}:\mathtt{eax}]$.

• $\mathtt{mul}\ 2\ \mathtt{reg_1}\ \mathtt{reg_2}$ — вычислить произведение $\mathtt{reg_1} \cdot \mathtt{reg_2}$ и сохранить его в пару регистров $[\mathtt{ecx}:\mathtt{eax}]$.

Здесь запись $[\mathtt{ecx}:\mathtt{eax}]$ обозначает 64-битное число, у которого старшие 32 бита записываются в $\mathtt{ecx}$, а младшие 32 бита — в $\mathtt{eax}$.

Команда $\mathtt{inc}$

Команда $\mathtt{inc}\ \mathtt{reg}$ выполняет операцию $\mathtt{reg} += 1$.

Команда $\mathtt{print}$

Команда $\mathtt{print}\ \mathtt{reg}$ выводит текущее значение регистра $\mathtt{reg}$.

Все регистры в начале выполнения программы равны $0$.

Но Глеб ещё только учится писать программы на этом языке, поэтому иногда допускает опечатки.

Если название команды в строке записано неверно, то строка считается ошибочной. Если же название команды записано верно, то гарантируется, что все остальные элементы этой строки корректны, кроме, возможно, названий регистров. Таким образом, при корректно записанной команде опечатки могут встречаться только в названиях регистров.

Программа обрабатывается построчно сверху вниз. Если в некоторой строке обнаруживается опечатка, то все предыдущие корректные строки считаются уже выполненными. В частности, должны быть выведены все значения, которые были напечатаны командами $\mathtt{print}$ в предыдущих строках.

После этого необходимо вывести номер первой ошибочной строки и завершить выполнение.

Если ошибочных строк в программе нет, требуется выполнить все команды по порядку и вывести все значения, которые будут напечатаны командами $\mathtt{print}$.

Формат входных данных

В первой строке дано одно число $n$ — количество команд ($1 \le n \le 10^5$).

В следующих $n$ строках содержится описание программы, по одной строке на каждую команду.

Строки программы нумеруются от $1$ до $n$ в порядке их следования во входных данных.

Формат выходных данных

Если в программе встречается ошибочная строка, необходимо вывести все значения, которые были напечатаны командами $\mathtt{print}$ до первой ошибки, по одному в строке. После этого в отдельной строке необходимо вывести номер первой ошибочной строки.

Если ошибочных строк в программе нет, требуется вывести все значения, которые будут напечатаны командами $\mathtt{print}$, по одному в строке.

Пример

5
add 0 1000000000
mul 2 eax eax
print eax
print ecx
mal 2 eax eax

2808348672
232830643
5

7
add 0 10
sub 2 ecx eax
inc ecx
print ecx
sub 2 ecx ecx
print ecx
print eax

4294967287
0
10

Примечание

Обратите внимание, что ввод и вывод осуществляется через стандартный ввод и стандартный вывод. В случае отрицательного ответа системы проверки заданий по программированию советуем ознакомиться с "Рекомендациями по решению задач по программированию".

Андрею на день рождения подарили две очень интересные вещи: лабиринт и лазер.

Лабиринт представляет собой матрицу из $n$ строк и $m$ столбцов. В матрице могут встречаться пустые клетки ., стены #, а также два типа зеркал: L и R.

После этого Андрей начинает запускать лазер из различных точек лабиринта. Когда луч оказывается в некоторой клетке, происходит следующее:

• если луч находится в пустой клетке, то он продолжает двигаться в том же направлении;
• если луч находится в клетке с зеркалом L, то направление луча изменяется следующим образом:
  • вверх $\to$ влево;
  • влево $\to$ вниз;
  • вниз $\to$ вправо;
  • вправо $\to$ вверх;
• если луч находится в клетке с зеркалом R, то направление луча изменяется следующим образом:
  • вверх $\to$ вправо;
  • вправо $\to$ вниз;
  • вниз $\to$ влево;
  • влево $\to$ вверх.

После этого луч пытается перейти в соседнюю клетку в новом направлении.

Если луч пытается выйти за границы лабиринта или перейти в клетку со стеной, его движение немедленно заканчивается.

Вам необходимо ответить на $q$ запросов. В каждом запросе заданы клетка $(x, y)$ и начальное направление луча. Для каждого запроса требуется определить:

• количество переходов между соседними клетками, которое совершит луч до остановки;
• либо вывести $-1$, если луч будет двигаться бесконечно, то есть попадёт в цикл.

Формат входных данных

В первой строке дано два целых числа $n$ и $m$ — количество строк и столбцов в матрице соответственно ($1 \le n, m \le 500$).

В следующих $n$ строках дано по $m$ символов — описание соответствующей строки матрицы. Гарантируется, что каждая клетка содержит один из символов ., #, L или R.

В следующей строке дано одно целое число $q$ — количество запросов ($1 \le q \le 10^5$).

В следующих $q$ строках дано описание запросов, по одному в строке.

Каждый запрос имеет вид $x$ $y$ $dir$ — стартовая позиция луча и его начальное направление ($1 \le x \le n$, $1 \le y \le m$, $dir \in \{ \mathtt{left}, \mathtt{right}, \mathtt{up}, \mathtt{down} \}$).

Направления $\mathtt{left}, \mathtt{right}, \mathtt{up}$ и $\mathtt{down}$ соответствуют движению влево, вправо, вверх и вниз соответственно.

Гарантируется, что клетка $(x, y)$ не является стеной.

Формат выходных данных

Для каждого запроса выведите одно целое число в отдельной строке.

Если луч в некоторый момент остановится, выведите количество переходов между соседними клетками, которое он совершит. Если же луч будет двигаться бесконечно, выведите $-1$.

Обратите внимание, что если луч несколько раз посещает одну и ту же клетку, но с разными направлениями, то это считаются разными состояниями.

Пример

3 3
L.L
...
L.L
4
1 2 left
1 2 right
1 2 up
1 2 down

-1
2
1
3

3 3
...
.L.
#LL
5
1 1 down
2 3 left
2 3 right
2 3 down
2 1 right

2
6
1
2
3

Примечание

Обратите внимание, что ввод и вывод осуществляется через стандартный ввод и стандартный вывод. В случае отрицательного ответа системы проверки заданий по программированию советуем ознакомиться с "Рекомендациями по решению задач по программированию".