Информатика

Виктор составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Виктор использует 5-буквенные слова, в которых могут быть только буквы Д, Г, И, А, Ш, Э, причём слово не должно начинаться с гласной или заканчиваться согласной. Сколько различных кодовых слов может использовать Виктор?

Маша делает цветные фотографии на телефон, который сохраняет снимки с размером 3840×2160 пикселей и разрешением 17 бит на пиксель. После сохранения снимков в памяти телефона Маша отправляет фотографию через мессенджер, который сжимает снимок до размера 1280x720 пикселей, каждый с разрешением 5 бит. Какое количество памяти (в Кбайт) удастся сэкономить при отправке 120 таких фотографий?
В ответе запишите целое число.

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз (где k – целое число).

Черепахе был дан для исполнения следующий алгоритм:
Направо 30 Повтори 3 [Направо 150 Вперёд 6 Направо 30 Вперёд 12].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, которая ограничена линией, заданной алгоритмом. Точки на линии учитывать не следует.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 610 = 110₂ результатом является число 1000₂ = 8₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 1101₂ = 13₁₀.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 480. В ответе запишите это число в десятичной системе счисления.

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква	Кодовое слово		Буква	Кодовое слово
А	01		Л	1101
Б	1100		Р	1000
Е			С	000
И	001		Т	101
К	1111		У	1001

Укажите кратчайшее кодовое слово для буквы Е, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

В файле приведён фрагмент базы данных «Кондитерские изделия» о поставках конфет и печенья в магазины районов города. База данных состоит из трёх таблиц.
Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой половины июня 2022 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок, шт. внесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.

ID операции

Дата

ID магазина

Артикул

Количество упаковок, шт.

Тип операции

Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Заголовок таблицы имеет следующий вид.

Артикул

Отдел

Наименование товара

Ед_изм

Количество в упаковке

Цена за упаковку

Таблица «Магазин» содержит информацию о местонахождении магазинов. Заголовок таблицы имеет следующий вид.

ID магазина

Район

Адрес

На рисунке приведена схема указанной базы данных.



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

Миша заполнял таблицу истинности логической функции F
\(x \land (z \rightarrow w) \land \neg y\)
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				F
		1		1
	1	0		1
1	0			1

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением \(\neg x \lor y\), зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		F
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
 

	П1	П2	П3	П4	П5	П6	П7
П1	х			17	6		9
П2		х			18	2	3
П3			х	39	42
П4	17		39	х		4
П5	6	18	42		х
П6		2		4		х	31
П7	9	3				31	х

      Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта A в пункт B и из пункта E в пункт F. В ответе запишите целое число.

Радиоуправляемый робот умеет перемещаться по клетчатому полю размером \(n \times m\) (\(n\) строк и \(m\) столбцов) и красить клетки в один из четырех цветов (красный, зеленый, синий и белый). Будем обозначать клетку на пересечении \(i\)-й сверху строки и \(j\)-го слева столбца как \((i, j)\).

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

Настройки представляют собой матрицу \(S\) размера \(n \times m\), каждый элемент которой — либо \(\varnothing\), либо пара из координат клетки и цвета. Если \(S_{i,j} = ((i', j'), c)\), то после того, как робот красит клетку \((i, j)\) в какой-либо цвет, он сразу же перемещается в клетку \((i', j')\) и красит ее в цвет \(c\). Если для новой покрашенной клетки \(S_{i',j'} \neq \varnothing\), процесс продолжается по тем же правилам.

Ограничения бывают двух типов:

1. ограничение на минимальное требуемое число клеток цвета \(c\);

2. запрет наличия на поле квадрата \(2 \times 2\), покрашенного цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\).

Пользователю доступны следующие команды для взаимодействия с роботом:

1. <<fill \(i\) \(j\) with \(c\)>> — закрасить клетку \((i, j)\) в цвет \(c\), после чего выполнять действия в соответствии с настройками; процесс останавливается, когда

   • очередное перемещение привело робота за границу поля;

   • очередное перемещение привело робота в клетку, которую он уже красил в процессе выполнения текущей команды;

   • для очередной клетки \(S_{i',j'} = \varnothing\);

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

   Обратите внимание, что если первая же покраска клетки \((i, j)\) в цвет \(c\) приводит к нарушению какого-то из ограничений, робот остановится сразу же, не покрасив ни одну клетку.

2. <<at-least \(x\) \(c\)>> — выставить ограничение на минимальное число клеток цвета \(c\) в \(x\). Если в настоящий момент на поле меньше \(x\) клеток цвета \(c\), команда игнорируется и ограничение не меняется. Для каждого цвета в каждый момент времени действует только последнее введенное на него ограничение на число клеток.

3. <<no-squares \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — запретить появление квадратов \(2 \times 2\), раскрашенных цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\). Если в настоящий момент на поле уже есть квадрат, раскрашенный таким образом, команда игнорируется и ограничение не добавляется.

4. <<allow-squares \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — аналогично, отменить запрет на раскрашенные соответствующим образом квадраты \(2 \times 2\), если такой запрет сейчас есть.

5. <<move \(i\) \(j\) to \(i'\) \(j'\) \(c\)>> — выставить настройки для клетки \((i, j)\) в значение \(((i', j'), c)\), где \((i', j')\) — клетка, в которую надо переместиться, а \(c\) — цвет, в который затем надо ее покрасить.

6. <<no-move \(i\) \(j\)>> — выставить настройки для клетки \((i, j)\) в значение \(\varnothing\), соответствующее отсутствию перемещения после покраски клетки \((i, j)\).

Еще раз повторим, что робот никогда не красит одну и ту же клетку дважды во время исполнения одной команды, а также останавливается до момента первого нарушения какого-либо ограничения. Например, если \(S_{1,1} = ((1, 2), \mathtt{red})\), \(S_{1,2} = ((2, 2), \mathtt{blue})\), \(S_{2,2} = ((2, 1), \mathtt{green})\) и \(S_{2,1} = ((1, 1), \mathtt{red})\), то при поступлении команды <<fill \(1\) \(1\) with blue>>, робот покрасит \((1, 1)\) в синий, \((1, 2)\) в красный, \((2, 2)\) в синий и \((2, 1)\) в зеленый. Затем робот остановится, так как клетка \((1, 1)\) уже была покрашена при исполнении этой команды.

Изначально все настройки равны \(\varnothing\), никакие ограничения не введены, а все клетки поля покрашены в белый цвет. Вам дан список из \(q\) команд пользователя, которые были последовательно отправлены роботу. Выведите раскраску поля после применения всех этих команд.

Формат входных данных
В первой строке записано целое число \(t\) (\(1 \le t \le 1000\)) — число наборов входных данных в тесте.

В первой строке каждого набора данных даны три целых положительных числа \(n\), \(m\) и \(q\) — размеры поля и число команд. Гарантируется, что сумма \(n \cdot m \cdot q\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(q\) строках дано описание команд, посланных роботу в формате, описанном в условии. Цвета задаются строками <<red>> (красный), <<green>> (зеленый), <<blue>> (синий) и <<white>> (белый).

Формат выходных данных
Для каждого набора входных данных выведите итоговую раскраску поля, полученную после обработки всех команд. Для обозначения красного, зеленого или синего цвета используйте первую букву его английской записи (‘r’, ‘g’ или ‘b’); для обозначения белого цвета используйте символ ‘.’.

В первом примере из условия

1. Команда <<fill 1 1 with red>> красит \((1, 1)\) в красный, после чего из-за \(S_{1,1} = ((2, 1), \mathtt{red})\) клетка \((2, 1)\) тоже красится в красный, а из-за \(S_{2,1} = ((3, 1), \mathtt{red})\) затем и \((3, 1)\) красится в красный.

2. При выполнении <<fill 2 1 with green>> робот красит \((2, 1)\) в зеленый. \(S_{2,1}\) в этот момент уже равно \(((2, 2), \mathtt{blue})\), поэтому после этого клетка \((2, 2)\) должна быть покрашена в синий, но это бы нарушило ограничение <<at-least 3 white>>, поэтому процесс останавливается до этого.

3. После этого поле выглядит как

   r.
   g.
   r.

4. Затем <<fill 2 2 with R>> должен покрасить \((2, 2)\) в красный (ограничение на число белых уже снято), но это бы привело к получению квадрата с цветами r.gr, который запрещен, поэтому выполнение команды сразу останавливается.

5. Последняя команда покраски <<fill 2 2 with B>> выполняется. После чего, в соответствии с \(S_{2,2} = ((1, 2), \mathtt{green})\), клетка \((1, 2)\) красится в зеленый.

6. Итоговый рисунок:

   rg
   gb
   r.

Радиоуправляемый робот умеет перемещаться по клетчатому полю размером \(n \times m\) (\(n\) строк и \(m\) столбцов) и красить клетки в один из четырех цветов (красный, зеленый, синий и белый). Будем обозначать клетку на пересечении \(i\)-й сверху строки и \(j\)-го слева столбца как \((i, j)\).

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

Настройки представляют собой матрицу \(S\) размера \(n \times m\), каждый элемент которой — либо \(\varnothing\), либо пара из направления (вправо, вверх, влево, вниз) и цвета. Если \(S_{i,j} = (d, c)\), то после того, как робот красит клетку \((i, j)\) в какой-либо цвет, он сразу же смещается на одну клетку в направлении \(d\) и красит ее в цвет \(c\). Если для новой покрашенной клетки \(S_{i',j'} \neq \varnothing\), процесс продолжается по тем же правилам.

Ограничения бывают двух типов:

1. ограничение на максимальное разрешенное число клеток цвета \(c\);

2. запрет наличия на поле квадрата \(2 \times 2\), покрашенного цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\).

Пользователю доступны следующие команды для взаимодействия с роботом:

1. <<color \(i\) \(j\) \(c\)>> — закрасить клетку \((i, j)\) в цвет \(c\), после чего выполнять действия в соответствии с настройками; процесс останавливается, когда

   • очередное перемещение привело робота за границу поля;

   • очередное перемещение привело робота в клетку, которую он уже красил в процессе выполнения текущей команды;

   • для очередной клетки \(S_{i',j'} = \varnothing\);

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

   Обратите внимание, что если первая же покраска клетки \((i, j)\) в цвет \(c\) приводит к нарушению какого-то из ограничений, робот остановится сразу же, не покрасив ни одну клетку.

2. <<limit \(c\) \(x\)>> — выставить ограничение на максимальное число клеток цвета \(c\) в \(x\). Если в настоящий момент на поле уже больше \(x\) клеток цвета \(c\), команда игнорируется и ограничение не меняется. Для каждого цвета в каждый момент времени действует только последнее введенное на него ограничение на число клеток.

3. <<block \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — запретить появление квадратов \(2 \times 2\), раскрашенных цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\). Если в настоящий момент на поле уже есть квадрат, раскрашенный таким образом, команда игнорируется и ограничение не добавляется.

4. <<allow \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — аналогично, отменить запрет на раскрашенные соответствующим образом квадраты \(2 \times 2\), если такой запрет сейчас есть.

5. <<settings \(i\) \(j\) \(d\) \(c\)>> — выставить настройки для клетки \((i, j)\) в значение \((d, c)\), где \(d\) — направление перемещения, а \(c\) — цвет, в который затем будет раскрашена клетка, в которую робот переместится.

6. <<settings \(i\) \(j\) none>> — выставить настройки для клетки \((i, j)\) в значение \(\varnothing\), соответствующее отсутствию перемещения после покраски клетки \((i, j)\).

Еще раз повторим, что робот никогда не красит одну и ту же клетку дважды во время исполнения одной команды, а также останавливается до момента первого нарушения какого-либо ограничения. Например, если \(S_{1,1} = (\rightarrow, \mathtt{red})\), \(S_{1,2} = (\downarrow, \mathtt{blue})\), \(S_{2,2} = (\leftarrow, \mathtt{green})\) и \(S_{2,1} = (\uparrow, \mathtt{red})\), то при поступлении команды <<color \(1\) \(1\) blue>>, робот покрасит \((1, 1)\) в синий, \((1, 2)\) в красный, \((2, 2)\) в синий и \((2, 1)\) в зеленый. Затем робот остановится, так как клетка \((1, 1)\) уже была покрашена при исполнении этой команды.

Изначально все настройки равны \(\varnothing\), никакие ограничения не введены, а все клетки поля покрашены в белый цвет. Вам дан список из \(q\) команд пользователя, которые были последовательно отправлены роботу. Выведите раскраску поля после применения всех этих команд.

Формат входных данных
В первой строке записано целое число \(t\) (\(1 \le t \le 1000\)) — число наборов входных данных в тесте.

В первой строке каждого набора данных даны три целых положительных числа \(n\), \(m\) и \(q\) — размеры поля и число команд. Гарантируется, что сумма \(n \cdot m \cdot q\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(q\) строках дано описание команд, посланных роботу в формате, описанном в условии. Направления задаются строками <<right>> (вправо), <<up>> (вверх), <<left>> (влево), <<down>> (вниз). Цвета задаются заглавными буквами ‘R’ (красный), ‘G’ (зеленый), ‘B’ (синий) и ‘W’ (белый).

Формат выходных данных
Для каждого набора входных данных выведите итоговую раскраску поля, полученную после обработки всех команд.

В первом примере из условия

1. Команда <<color 1 1 R>> красит \((1, 1)\) в красный, после чего из-за \(S_{1,1} = (\downarrow, \mathtt{red})\) клетка \((2, 1)\) тоже красится в красный, а из-за \(S_{2,1} = (\downarrow, \mathtt{red})\) затем и \((3, 1)\) красится в красный.

2. При выполнении <<color 2 1 G>> робот красит \((2, 1)\) в зеленый. \(S_{2,1}\) в этот момент уже равно \((\rightarrow, \mathtt{blue})\), поэтому после этого клетка \((2, 2)\) должна быть покрашена в синий, но это бы нарушило ограничение <<limit B 0>>, поэтому процесс останавливается до этого.

3. После этого поле выглядит как

   RW
   GW
   RW

4. Затем <<color 2 2 R>> должен покрасить \((2, 2)\) в красный, но это бы привело к получению квадрата с цветами RWGR, который запрещен, поэтому выполнение команды сразу останавливается.

5. Последняя команда покраски <<color 2 2 B>> отрабатывает корректно, так как до этого было разрешено иметь на поле не больше \(1\) синей клетки. После чего, в соответствии с \(S_{2,2} = (\uparrow, \mathtt{green})\), клетка \((1, 2)\) красится в зеленый.

6. Итоговый рисунок:

   RG
   GB
   RW

Женя готовится к городским спортивным соревнованиям, где хочет показать себя самым сильным. Он тренируется по системе шаолиньских монахов. Тренировка должна состоять из N подходов, каждый из которых длится M минут и S секунд, между каждой парой подряд идущих подходов должен быть перерыв длительностью P секунд.
Помогите Жене определить, сколько всего времени займёт тренировка.

Формат входных данных
Первая строка содержит целое число N (1 ≤ N ≤ 100) — количество подходов.
Вторая строка содержит целое число M (0 ≤ M ≤ 59) — количество минут в одном подходе.
Третья строка содержит целое число S (0 ≤ S ≤ 59) — количество секунд в одном подходе.
Четвёртая строка содержит целое число P (0 ≤ P ≤ 120) — длительность паузы между подходами, выраженная в секундах.
Гарантируется, что один подход занимает ненулевое время.
Формат выходных данных
Выведите два целых числа — продолжительность тренировки в минутах и секундах. Первое число должно быть равно количеству полных минут в тренировке. Второе число — количеству секунд в тренировке, находящемуся в диапазоне от 0 до 59 включительно.

Замечание
В примере из условия Жене нужно выполнить 4 подхода, каждый из которых имеет длительность 3 минуты 24 секунды. При этом между походами у него будет 3 перерыва, каждый из которых имеет длительность 70 секунд. Следовательно, вся тренировка займёт 17 минут и 6 секунд.

В деревне Летовецк, где живут мудрые старцы и их ученики, существует древняя игра, которая называется "Летовецкая дуэль". В этой игре два игрока сражаются друг с другом, используя стопку из 10 уникальных карточек, каждая из которых имеет значение от 0 до 9. Карточки раздаются поровну: каждому игроку достаётся по 5 карточек.

Правила игры просты:

1. Игроки одновременно открывают верхнюю карточку своей стопки.

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

3. Игра продолжается до тех пор, пока у одного из игроков не закончатся карточки. Этот игрок проигрывает.

4. Особое правило: карточка со значением 0 побеждает карточку со значением 9, даже если 9 обычно старше 0.

Напишите программу, которая определяет, кто побеждает в данной игре. Вам заранее известно номера карточек первого и второго игрока! 

Формат входных данных
Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карточек первого игрока, вторая – аналогично 5 карточек второго игрока. Карточки перечислены сверху вниз, то есть каждая строка начинается с той карточки, которая будет открыта первой.

Формат выходных данных
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

 

В деревне Летовецк, где живут мудрые старцы и их ученики, существует древний банк, который хранит богатства в виде ле́токоинов — особых монет, обладающих магической силой. Однако банк установил строгие правила: чтобы снять деньги, нужно использовать только определённые суммы за одну операцию:

• за одну операцию можно снять только 1 ле́токоин,

• за одну операцию можно снять сумму 6^x, где x  - любое натуральное число (можно снять сумму равную 6, 36, 216, и т.д.),

• за одну операцию можно снять сумму 9^x, где x  - любое натуральное число  (можно снять сумму равную 9, 81, 729, ...).

Старец Летовец спросил своих учеников: за какое минимальное количество операций вы сможете снять ровно N ле́токоинов?

Примечание: невозможно повторно вносить снятые деньги в банк!

Формат входных данных
На вход подается целое число N (\(1<=N<=100000\)).

Формат выходных данных
Выведите ответ на задачу.

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 летокоинов за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

 

Что отличает задачу классификации от задачи регрессии?

Варианты ответа:
1) Классификация предсказывает непрерывные значения, а регрессия — категориальные.
2) Классификация и регрессия обе предсказывают только непрерывные значения.
3) Классификация предсказывает категориальные метки, а регрессия — непрерывные значения.
4) Классификация и регрессия обе предсказывают только категориальные метки.

Сайтама выполняет последовательные удары по силомеру. Силомер представляет из себя массив целых чисел длины \(n\). Изначально \(i\)-е число массива равно \(a_i\) для всех \(i\).

Вам необходимо обработать \(q\) событий, происходящих с силомером. Событие номер \(i\) может быть одного из трех типов:

1. подходит наблюдатель и просит посчитать сумму чисел массива на отрезке \([l_i; r_i]\), то есть величину \(a_{l_i} + a_{{l_i}+1} + \ldots + a_{r_i}\);

2. Сайтама наносит обычный удар силы \(x_i\) по отрезку \([l_i; r_i]\): всем элементам массива на позициях от \(l_i\) до \(r_i\) включительно присваивается значение \(x_i\)

3. Сайтама наносит сильный удар по отрезку \([l_i; r_i]\): для всех \(j\) от \(l_i\) до \(r_i\) включительно происходит присваивание \(a_j \gets \mathtt{popcount}(a_j)\).

Здесь \(\mathtt{popcount}(x)\) — это количество единичных бит в двоичной записи числа \(x\). Иными словами, при событии третьего типа каждое число на отрезке события заменяется на количество своих единичных бит.

На каждый подход наблюдателя, то есть событие первого типа, сообщите ему интересующую его сумму.

Формат входных данных
В первой строке записаны два целых числа \(n\) и \(q\) — длина массива и количество событий (\(1 \leqslant n, q \leq 2 \cdot 10^5\)).

Во второй строке через пробел записаны \(n\) целых чисел \(a_1\), …, \(a_n\) — изначальные элементы массива силомера (\(0 \leqslant a_i \leqslant 10^9\)).

Следующие \(q\) строк описывают события. Первое число \(t_i\) в описании события — тип события (\(1 \leqslant t \leqslant 3\)). Следующие два заданные через пробел числа — это границы отрезка \(l_i\) и \(r_i\) (\(1 \leqslant l_i \leqslant r_i \leqslant n\)). Если это событие второго типа, то есть \(t_i = 2\), далее следует число \(x_i\), обозначающее, что надо выполнить присваивания \(a_j \gets x_i\) для всех \(l_i \leqslant j \leqslant r_i\) (\(0 \leqslant x_i \leqslant 10^9\)).

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

 

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

Замок на двери подвала устроен следующим образом:

• на нем есть два кодовых механизма, первый из которых изначально указывает на число \(a\), а второй — на число \(b\);

• первый кодовый механизм сломан, поэтому изменить значение \(a\) нельзя;

• второй кодовый механизм можно вращать только в одном направлении, тем самым увеличивая значение \(b\);

• замок открывается тогда и только тогда, когда существует целое число \(d > 1\), делящее и \(a\), и \(b\) (иными словами, когда у \(a\) и \(b\) есть общий делитель больше единицы).

За одну секунду Эрен может повернуть второй кодовый механизм так, что \(b\) увеличится ровно на \(1\). Определите, за какое минимальное время Эрен сможет открыть подвал.

Формат входных данных
В первой строке дано единственное целое число \(t\) — количество тестовых случаев \((1 \leqslant t \leqslant 1000)\).

В \(i\)-й из следующих \(t\) строк через пробел даны два целых числа \(a_i\) и \(b_i\) — начальные значения, на которые указывают кодовые механизмы в \(i\)-м тесте (\(2 \leqslant a_i, b_i \leqslant 10^9\)).

Формат выходных данных
Для каждого теста выведите в отдельной строке минимальное время, за которое Эрен откроет подвал.

 

Новая татарская игра <<2026>> ведется на прямоугольной клетчатой доске, состоящей из \(m\) строк и \(n\) столбцов. Доска разбита на \(m \times n\) единичных клеток размером \(1 \times 1\). На некоторых клетках стоят квадратные фишки размером \(1 \times 1\), на каждой фишке написана одна из \(26\) английских букв.

С фишками производятся \(q\) операций. Каждая операция состоит в перемещении всех фишек до упора в одном из четырех направлений. Таким образом, последовательность операций задается строкой \(s\) длины \(q\), состоящей из символов, соответствующих направлениям: <<L>> — влево, <<R>> — вправо, <<U>> — вверх и <<D>> — вниз.

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

Определите, как будет выглядеть доска после выполнения всех операций.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке теста задано целое число \(t\) — количество наборов входных данных в тесте (\(1 \le t \le 200\,000\)). Далее следуют описания наборов входных данных. Каждый набор входных данных описывается следующим образом:

В первой строке набора заданы целые числа \(m\) и \(n\) — размеры доски (\(1 \le m, n \le 10^6\), \(1 \le m\times n \le 10^6\)).

В следующих \(m\) строках задано изначальное расположение фишек на доске.

В \(i\)-й строке (\(1 \le i \le m\)) находится строка \(a_{i1}a_{i2}\ldots a_{in}\) длины \(n\), задающая \(i\)-ю строку доски. Каждый символ \(a_{ij}\) является либо строчной буквой английского алфавита от <<a>> до <<z>>, либо точкой <<.>>. Если \(a_{ij}=\mbox{<<.>>}\), то клетка в \(i\)-й строке и \(j\)-м столбце является пустой, иначе в ней находится фишка, на которой написана буква \(a_{ij}\).

В последней строке заданы \(q\) символов \(s_1s_2\ldots s_q\) без пробелов, задающие последовательность операций (\(1 \le q \le 10^6\)). Каждый символ \(s_i\) является одним из символов <<L>>, <<R>>, <<U>> или <<D>>.

Сумма значений \(m \times n\) по всем наборам входных данных не превышает \(2\cdot 10^6\). Сумма значений \(q\) по всем наборам входных данных не превышает \(2\cdot 10^6\).

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

Обозначим через \(\sum mnq\) сумму \(mnq\) по всем наборам входных данных.

Обозначим через \(\sum mq\) сумму \(mq\) по всем наборам входных данных.

Назовем расположение фишек лестницей, если \(m=n\), \(a_{ij}={<<\texttt{.}>>}\) для всех \(1 \le i \le j \le n\) и \(a_{ij}\ne{<<\texttt{.}>>}\) для всех \(1 \le j < i \le n\). Иными словами, все фишки находятся на клетках ниже главной диагонали доски, и на каждой клетке ниже главной диагонали есть фишка.

Пояснения к примерам
В первом наборе входных данных из примера доска изначально выглядит так:

Первая операция сдвигает все фишки влево, так как \(s_1={<<\texttt{L}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Вторая операция сдвигает все фишки вправо, так как \(s_2={<<\texttt{R}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Третья и последняя операция сдвигает все фишки наверх, так как \(s_3={<<\texttt{U}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Совсем недавно Васе на день рождения подарили строку, состоящую только из символов «0» и «1». Обрадованный этим подарком, он тут же начал эту строку изучать — искать в ней гармоничные части. Для начала Васю интересует только количество различных непустых гармоничных подстрок. А поскольку подарок оказался слишком большим, мальчик решил обратиться за помощью к вам. Помогите Васе!
В понимании Васи, строка является гармоничной, если и символов 0, и символов 1 в ней чётное количество.
Подстрокой строки s называется строка, полученная из s выкидыванием нескольких символов с начала и с конца (возможно, нуля или всех). Так, строка «12» является подстрокой строки «123», а строка «13» — нет. Подстроки считаются одинаковыми, если у них совпадает количество удалённых символов с начала и с конца.

Формат входных данных
В первой строке дано одно число n — длина подарка (1 ≤ n ≤ 2 · 10⁵ ). Во второй строке дана строка s длины n — Васин подарок. Гарантируется, что s состоит только из нулей и единиц.
Формат выходных данных
Выведите единственное число — количество различных гармоничных подстрок в s.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64- битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Замечание
В первом примере из условия подходят следующие подстроки (выделены жирным): 001100, 001100, 001100, 001100, 001100, 001100, 001100.

Напишите программу на Python, которая:

1. Считывает уравнения из строки, разделенных запятой.

2. Преобразует строку в символьное уравнение с помощью SymPy.

3. Решает уравнение.

4. Выводит корни уравнения.

Напишите программу, которая запрашивает математическое выражение в виде строки и два параметра целого типа, использует библиотеку SymPy для его парсинга и вычисления, а затем выводит результат.
Программа должна обрабатывать простые арифметические операции, такие как сложение, вычитание, умножение и деление, а также возведение в степень.