реализация

Космическая станция «Орион» принимает сигналы от спутников-разведчиков. Приёмная матрица станции имеет размер 640 строк на 480 позиций. При получении каждого сигнала в журнал записываются координаты активированного элемента матрицы: номер строки и номер позиции в строке.

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

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

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


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

В первой строке записано целое число N — количество принятых сигналов (1 ≤ N ≤ 10000).

В каждой из следующих N строк записаны по два числа через пробел:
- номер строки (целое число от 1 до 640)
- номер позиции в строке (целое число от 1 до 480)

Один и тот же элемент матрицы может получить несколько сигналов (координаты могут повторяться).

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

Два целых числа через пробел: наибольшая длина цепочки активных элементов и номер строки, в которой она находится.
 

В новом датацентре «Кибер-Облако» серверы размещаются в стойках, которые расположены рядами. Ряды пронумерованы натуральными числами. Слоты в каждом ряду также пронумерованы натуральными числами начиная с единицы.

По данным инвентаризации известно, в каких рядах и в каких слотах уже установлены серверы. Администратору нужно разместить новое оборудование: кластер из ровно 25 серверов, которые должны располагаться в соседних слотах одного ряда.

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

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

Гарантируется, что существует хотя бы один ряд, удовлетворяющий условию.

Формат входных данных
В первой строке находится число N — количество установленных серверов (натуральное число, не превышающее 20000).

Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000:
- номер ряда
- номер слота в этом ряду

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

Два целых числа через пробел: наибольший номер ряда и наименьший номер слота в выбранной последовательности из 25 свободных мест.

 

Космическая Академия «Звёздный Путь» проводит ежегодный набор курсантов. Отбор кандидатов происходит по сумме баллов трёх вступительных испытаний (физическая подготовка, математика, астронавигация) и собеседования с приёмной комиссией.

На заранее известное количество мест отбираются кандидаты, набравшие наибольшую сумму баллов по результатам трёх испытаний. Все кандидаты, набравшие определённую сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным.

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

Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование. Если два кандидата с полупроходным баллом имеют одинаковый балл за собеседование, то проходит тот кандидат, значение ID которого выше.

Для данного множества кандидатов определите полупроходной балл, а также ID кандидата с полупроходным баллом, который будет зачислен последним (займёт последнее свободное место).

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

В первой строке находятся два числа:

- N — количество кандидатов (натуральное число, не превышающее 10000)

- S — количество имеющихся мест (натуральное число, S ≤ N)

Каждая из следующих N строк содержит пять чисел:

- ID кандидата (натуральное число, не превышающее 10 000 000)

- три оценки по испытаниям (целые неотрицательные числа, не превышающие 100)

- балл за собеседование (целое неотрицательное число, не превышающее 10)

Гарантируется, что в исходных данных существует полупроходной балл.

 

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

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

Примечание

В первом тестовом примере

- ID=1001: сумма экзаменов = 270, собеседование = 10 → проходит (проходной балл)

- ID=1002: сумма = 240, собеседование = 8 → полупроходной балл, проходит

- ID=1003: сумма = 240, собеседование = 5 → не проходит (собеседование меньше)

- ID=1004: сумма = 210, собеседование = 10

Мест: 2. Кандидат с ID=1001 проходит автоматически. Осталось 1 место, но с суммой 240 — два кандидата. Это полупроходной балл. Между ними выбираем по собеседованию: ID=1002 (собес 8) > ID=1003 (собес 5).

Во втором тестовом примере
Все кандидаты имеют одинаковую сумму баллов (240) и одинаковый балл за собеседование (5). Мест: 2. Выбираем по ID в порядке убывания: сначала 503, затем 502. Последний зачисленный — кандидат с ID=502.

 

На подводной исследовательской станции «Нептун-7» требуется установить новый научный модуль. Станция состоит из M уровней (пронумерованных от 1 до M сверху вниз, где уровень 1 ближе всего к поверхности) и K отсеков на каждом уровне.

Некоторые отсеки уже заняты оборудованием. По требованиям безопасности, новый модуль нужно разместить так, чтобы над ним (на уровнях с меньшими номерами) было как можно больше подряд идущих свободных отсеков с тем же номером — это обеспечивает путь аварийной эвакуации к поверхности.

Если несколько отсеков имеют одинаковое максимальное количество свободных отсеков над ними, выбирается отсек на уровне ближе к поверхности (с меньшим номером уровня).

Гарантируется, что хотя бы один свободный отсек на станции существует.

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

В первой строке находятся три числа:

• N — количество занятых отсеков (1 ≤ N ≤ 10 000)
• M — количество уровней (1 ≤ M ≤ 100 000)
• K — количество отсеков на каждом уровне (1 ≤ K ≤ 100 000)

В следующих N строках находятся пары натуральных чисел: номер уровня и номер отсека занятого места соответственно.

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

Два целых числа через пробел:

1. Номер уровня выбранного отсека
2. Количество свободных отсеков над ним (подряд, с тем же номером)

На орбитальной станции «Галактика-7» завершился ежегодный технический осмотр космических кораблей. По его результатам каждый корабль получил:

• Оценки трёх бортовых систем: двигательной, навигационной и системы жизнеобеспечения (по шкале от 2 до 5, где 2 — критическая неисправность, 5 — отличное состояние)
• Статус лицензии пилота: действующая или просроченная

Корабль допускается к полётам, если выполнены оба условия:

1. Все три бортовые системы имеют оценку 3 или выше
2. Лицензия пилота действующая

Корабль не допущен к полётам, если хотя бы одно из условий не выполнено.

Руководство станции решило предоставить возможность экстренного ремонта одной системы одному из кораблей. Корабль может претендовать на ремонт, если:

1. Лицензия пилота действующая
2. Ровно одна система имеет критическую неисправность (оценка 2), а две другие системы исправны (оценка 3 или выше)

Если таких кораблей несколько, выбирается тот, у которого наибольшая сумма оценок всех трёх систем (такой корабль ближе всего к допуску).

Гарантируется, что ровно один корабль удовлетворяет всем критериям отбора.
 

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

В первой строке находится число N — количество кораблей (1 ≤ N ≤ 1000).

Каждая из следующих N строк содержит пять целых чисел через пробел:

• ID — бортовой номер корабля (натуральное число, не превышающее 10⁸)
• S₁, S₂, S₃ — оценки трёх бортовых систем (каждая от 2 до 5)
• L — статус лицензии пилота (1 — действующая, 0 — просроченная)

 

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

Выведите два числа через пробел:

1. Количество кораблей, не допущенных к полётам
2. Бортовой номер корабля, который получит возможность экстренного ремонта

Нарисуйте цветочек из шести окружностей

1. Начало в (0, 0), перо опущено.
2. Нарисуйте окружность радиусом 100.
3. Поверните Черепашку на 60 градусов влево
4. Повторите пункты 2-3 шесть раз

Напишите программу, которая делает реверс строки. То есть переставляет символы строки в обратном порядке. Программу реализуйте с использованием указателей.

Формат входных данных
Строка, содержащая алфаитно-цифровые символы (кроме пробела). Длина строки не более 100 символов.

Формат выходных данных
Выведите строку, получившуюся после реверса

Иван Фёдорович сыщик с очень большим стажем. Однажды в городе произошла серия больших ограблений. На местах ограбления не было обнаружено ни улик, ни зацепок. Однажды грабителей практически застали врасплох, но они смогли скрыться. На месте преступления Иван Фёдорович заметил, что грабители обронили папку с листком и набором картонных карточек, с вырезанными окошками на этих картах. Придя в офис и рассмотрев улики подробнее, было замечено, что на листке напечатана прямоугольная матрица, состоящая из цифр, а карточки все были размером с матрицу, притом отверстия, вырезанные в карточках, отображали какие-то случайные цифры из матрицы.
Иван Фёдорович вспомнил, что когда-то сталкивался с подобной схемой обозначения мест ограбления, что карточки помогали определить координаты следующего места ограбления. Потому Иван Фёдорович решил выписать координаты всех мест преступлений в виде долготы и широты, а далее найти карточки, которые соответствуют координатам следующих мест преступлений.
Помогите ему быстрее найти преступников, определив координаты следующих мест преступлений.
Координаты преступления собираются при помощи карточки следующим образом:

• на матрицу накладывается карточка;
• далее двигаясь по каждой строке по порядку слева-направо, выписываются цифры, которые попали в прорези;
• цифр всегда 18, притом координаты всегда состоят из 8цифр (две целой части, шесть вещественной), значит два символа игнорируются и обозначают точку в вещественном числе в соответствующем порядке.

Пример матрицы и карточки (где белые участки – это вырезы (отверстия)).

Таким образом начинаем выписывать цифры по строкам слева-направо: 554755831378617673. Знаем, что цифр обозначающих координату 8, а две лишние – обозначающие запятые, получим координаты 55.755831 37.617673.
Также на каждой карточке Иван Фёдорович заметил на углу пометку, которая, как позднее он понял, определяет, как должна быть развёрнута карточка, так как метка должна при наложении всегда находиться в левом верхнем углу при взгляде на неё:

• 1 – метка в левом верхнем углу карточки;
• 2 – метка в правом верхнем углу карточки;
• 3 – метка в правом нижнем углу карточки;
• 4 – метка в левом нижнем углу карточки.

Входные данные
на первой строке подаётся целое число K (2 <= K <= 100) – количество преступлений, которые совершили грабители;
далее на K строках подаются координаты предыдущих мест преступлений в виде вещественных чисел с точкой, разделённых пробелом (например, 55.755831 37.617673)
на следующей строке подаются размеры матрицы и карточек в виде целых чисел N, M (5 <= N,M <= 1000), где N – количество строк матрицы, а M – количество столбцов;
далее на N строках подаются по M цифр матрицы;
после подаётся на новой строке целое число – количество карточек L (K < L <= 100); 
далее подаётся на одной строке L цифр от 1 до 4 через пробел, которые отображаются метки карточка в соответствии с порядком их появления;
затем L раз по N строк и M цифр подаются карточки по порядку их появления, которые содержат либо цифру 1 – обозначающую наличие прорези на ней, либо 0 – если прорези в этом месте на карточке нет.
Выходные данные
выведите все координаты будущих мест преступлений (каждую с новой строки), отсортировав их по возрастанию (если две координаты одинаковые по первой координате, то сортировать по возрастанию по второй), координаты одного места выводить через пробел.
Примечание:
·при выводе дробной части координат выводить всегда 6 знаков, если знаков меньше, то дополнять их незначащими нулями;
·если матрица прямоугольная, то гарантируется, что при совмещении метки на карточке с левым верхним углом матрицы, карточка совпадёт с размером матрицы;
·данные на карточках нельзя отзеркаливать (переворачиватькарточки не в плоскости OXY);
·гарантируется, что если даны метки на карточках, то при повороте карточка совпадёт с размером матрицы, не будет такого, что карточка будет иного размера, чем матрица.

Город имеет форму прямоугольника с вершинами в точках (-W,-H), (-W,H), (W,H),(W,-H).
Плоскость разбита на кварталы. Квартал — это единичная клетка, вершины которой имеют целочисленные координаты. Назовем квартал городским, если все вершины квартала находятся внутри города (считается, что точка на границе принадлежит городу). Всего в городе будет 4·W·H кварталов.
Дорожная сеть состоит из N дорог (часть дорог или все проходят через город).
Дорога — это прямая линия, не параллельная осям координат.
Дорога задается двумя различными точками на ней (точки могут находиться вне города).
Для каждого квартала определим "значимость". Значимость квартала равна количеству дорог, проходящих через этот квартал. Считается, что дорога проходит через квартал, если имеет с кварталом не менее двух общих точек.
Найдите значение "значимости" для каждого квартала. Для каждой полученной "значимости" определите количество кварталов, имеющих эту значимость.

Формат входных данных
В первой строке заданы значения W, H, N (9<W,H<201, 0<N<1001)
В следующих N строках задано по четыре числа (координаты двух точек прямой, определяющих дорогу).

Формат выходных данных
В первой строке выведите число K - количество различных ненулевых значений "значимости".
В следующих K строках выведите по два числа - значение "значимости" и количество кварталов, имеющих такое значение "значимости".


Примечание к примеру

Город расположен в прямоугольнике со сторонами 8 и 6 клеток (всего 48 кварталов)
Через город проходят 4 дороги AB, CD, EF, GH
Значимость 1 будет у 24 кварталов (коричневый цвет на рисунке)
Значимость 2 будет у 5 кварталов (зеленый цвет на рисунке)
Значимость 4 будет у 1 кварталов (красный цвет на рисунке)
18 кварталов будут иметь значимость равную 0 (на печать не выводиться)

Агрохолдинг «Дикое Поле» анализирует результаты сбора урожая. Известно, сколько тонн зерна убрали на каждом из N полей, находящихся в распоряжении холдинга. Так как несколько огромных полей сильно влияют на среднее, в агрохолдинге решили ввести другую метрику. Опорными называются поля, урожай с которых превышает пороговое значение, но меньше среднего. Определите наиболее часто встречающийся урожай с опорного поля.
Формат ввода
На вход программе в первой строке подаётся натуральное число N (N ≤ 1000) – количество полей. Во второй строке подаётся натуральное число M (M≤ 100 т) – пороговое значение урожая с поля. Далее в N строках идёт по одному натуральному числу m_i – масса урожая с поля номер i (1≤ m_i ≤1000 т).
Формат вывода
Вывести одно целое число – наиболее часто встречающийся урожай с опорного поля. Если таких значений несколько, выведите наибольшее. Если таких значений нет, выведите 0.

Рамазан решил заняться серьезным бизнесом — выращиванием капусты.

Поле для выращивания капусты представляет собой бесконечное клетчатое поле. В каждой клетке поля может быть посажен один кочан капусты.

Рамазан засадил только часть поля. Он запланировал использовать несколько прямоугольных участков поля, причём оказалось, что некоторые из них могут пересекаться. Клетка поля принадлежит посадкам, если она лежит хотя бы в одном из прямоугольников.

Формально, Рамазан выбрал \(n\) прямоугольных участков \((x_i^{L}, y_i^{L}, x_i^{R}, y_i^{R})\) (\(x_i^{L} \leq x_i^{R}\), \(y_i^{L} \leq y_i^{R}\), \(1 \leq i \leq n\)). Клетка \((x, y)\) содержит капусту, если существует хотя бы один выбранный прямоугольник \(i\) (\(1 \leq i \leq n\)), такой что \(x_i^{L} \leq x \leq x_i^{R}\) и \(y_i^{L} \leq y \leq y_i^{R}\).

В прошлом Рамазан был программистом (и победителем), поэтому он решил использовать роботов с искусственным интеллектом для периодической обработки посадок. Один робот может обслуживать произвольный горизонтальный участок клеток \((x_1^{robot}, x_2^{robot}, y^{robot})\), то есть все клетки \((x, y)\), такие что \(x_1^{robot} \leq x \leq x_2^{robot}\) и \(y = y^{robot}\).

Важно, чтобы роботы ездили только по участкам с посадками. Он понял, что для минимизации количества роботов важно использовать горизонтальные участки, которые нельзя расширить. Рамазан будет использовать робота на участке клеток \((x_1^{robot}, x_2^{robot}, y^{robot})\), если:

• Все клетки \((x, y)\), такие что \(x_1^{robot} \leq x \leq x_2^{robot}\) и \(y = y^{robot}\) принадлежат посадкам;

• Клетка \((x_1^{robot} - 1, y^{robot})\) не принадлежит посадкам;

• Клетка \((x_2^{robot} + 1, y^{robot})\) не принадлежит посадкам.

Ваша задача собрать важную статистику о роботах, которые будут работать на плантации. Будем говорить, что пара \((x_1, x_2)\) обслуживается в ряду \(y\), если существует робот, работающий ровно на участке \((x_1, x_2, y)\).

• Найдите все пары \((x_1, x_2)\), которые обслуживаются в каком-нибудь ряду.

• Для каждой такой пары \((x_1, x_2)\) найдите количество рядов, в которых она обслуживается.

• Для каждой такой пары \((x_1, x_2)\) найдите максимальное количество подряд идущих рядов, в которых она обслуживается. Другими словами, найдите максимальное число \(k\), такое что существует отрезок \(k\) подряд идущих рядов \([y_1, y_2]\) (\(y_2 - y_1 + 1 = k\)), такой что для любого ряда \(y_1 \leq y \leq y_2\), пара \((x_1, x_2)\) обслуживается в ряду \(y\).

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

В первой строке каждого набора входных данных дано единственное целое число \(n\) (\(1 \leq n \leq 200\,000\))  — количество выбранных прямоугольных участков.

В следующих \(n\) строках дано по четыре целых числа \(x_i^{L}\), \(y_i^{L}\), \(x_i^{R}\), \(y_i^{R}\) (\(1 \leq x_i^{L} \leq x_i^{R} \leq 10^9\), \(1 \leq y_i^{L} \leq y_i^{R} \leq 10^9\)) — описания выбранных прямоугольных участков.

Обозначим за \(N\) сумму \(n\) по всем наборам входных данных в одном тесте. Гарантируется, что \(N \leq 200\,000\).

Формат выходных данных
Для каждого набора входных данных сначала выведите единственное целое число \(p\) (\(p \geq 1\)) — количество пар \((x_1, x_2)\), которые обслуживаются в каком-нибудь ряду.

В следующих \(p\) строках выведите по четыре целых числа \(x_1\), \(x_2\), \(cnt\), \(k\) (\(1 \leq x_1 \leq x_2 \leq 10^9\), \(0 \leq cnt, k \leq 10^9\)). Число \(cnt\) должно быть равно количеству рядов, в которых обслуживается пара \((x_1, x_2)\). Число \(k\) должно быть равно максимальному количеству подряд идущих рядов, в которых обслуживается пара \((x_1, x_2)\).

Все пары \((x_1, x_2)\) должны быть различны. Каждая пара, которая обслуживается в каком-нибудь ряду, должна быть выведена ровно один раз. Можно вывести пары в произвольном порядке.

Система оценки
Для набора входных данных обозначим за \(w\) ширину поля, то есть \(w = \max\limits_{i=1}^{n} x_i^{R}\), за \(h\) высоту поля, то есть \(h = \max\limits_{i=1}^{n} y_i^{R}\).

• Если для теста ваше решение неправильно находит множество пар \((x_1, x_2)\), которые обслуживаются в каком-нибудь ряду, решение получает вердикт <<Неправильный ответ>>.

• Если во всех тестах подзадачи и необходимых подзадач решение

  • правильно находит множество, но не все \(cnt\) верны, оно получает \(50\%\) баллов за подзадачу.

  • правильно находит множество и все \(cnt\), но не все \(k\) верны, оно получает \(75\%\) баллов за подзадачу.

  • правильно находит множество, все \(cnt\) и все \(k\), оно получает \(100\%\) баллов за подзадачу.

Обратите внимание, что для получения частичных баллов за подзадачу, все равно необходимо вывести какие-нибудь значения \(cnt\) и \(k\) для каждой пары \((x_1, x_2)\), но не обязательно верные.

В первом наборе входных данных будут использоваться роботы на участках \((2, 3, 2)\), \((2, 4, 3)\), \((3, 4, 4)\). Таким образом, пары \((2, 3)\), \((2, 4)\), \((3, 4)\) обслуживаются в каком-нибудь ряду, причем каждая из них обслуживается ровно в одном ряду.

Во втором наборе входных данных будут использоваться роботы на участках \((2, 2, 1)\), \((2, 4, 2)\), \((2, 2, 3)\). Таким образом, пары \((2, 2)\), \((2, 4)\) обслуживаются в каком-нибудь ряду. Пара \((2, 2)\) обслуживается в рядах \(1, 3\), пара \((2, 4)\) обслуживается ряду \(2\).

Авиакомпания <<Флагманский Флот Татарстана>> предлагает в своих самолётах новый вид бизнес-класса. Салон самолёта состоит из \(n\) мест, расположенных в один ряд вдоль прохода. Введём координатную прямую вдоль салона так, что расстояние между креслами будет равно \(1\), и места будут иметь координаты от \(1\) до \(n\).

Во время полёта стюарду нужно пройти по самолету и раздать всем пассажирам напитки. Напитки бывают \(k\) разных видов, пронумерованных числами от \(1\) до \(k\). Каждый пассажир получает одну порцию одного напитка, пассажир заказывает предпочитаемый вид напитков при бронировании билета, поэтому все предпочтения пассажиров известны заранее.

Напитки разлиты по бутылкам, каждая бутылка вмещает \(p\) порций одного напитка. В тележку для напитков можно загрузить не более \(m\) бутылок с любыми видами напитков, гарантируется, что \(m\ge k\).

Пассажиры обслуживаются в порядке возрастания номеров их мест. Первоначально тележка находится в начале салона в точке \(0\), и её можно заполнить любыми видами напитков перед обслуживанием. После завершения обслуживания тележка должна приехать в точку \(n+1\). При этом в точках \(0\) и \(n+1\) могут находиться кладовые: или одна кладовая в одном из концов салона или две кладовые в двух концах, в которых имеется достаточный запас напитков каждого вида. В этих кладовых можно выгрузить из тележки пустые бутылки и погрузить полные бутылки.

По ходу обслуживания напитки будут расходоваться, поэтому время от времени возникает необходимость пополнить запас напитков на тележке в одной из кладовых. Если в текущий момент тележка находится напротив кресла номер \(i\), то для того, чтобы доехать до кладовой в точке \(0\) необходимо проехать расстояние \(i\), а для того, чтобы доехать до кладовой в точке \(n + 1\) необходимо проехать расстояние \(n+1-i\). В кладовых можно выгрузить пустые бутылки из тележки и загрузить на свободные места бутылки с напитками любых видов. Выгружаемые бутылки должны быть пустыми, нельзя выгружать бутылки, в которых остались напитки, или выливать напитки. Нельзя переливать остатки напитков между разными бутылками. Можно загружать на тележку более одной бутылки одного вида. После этого тележка должна проехать расстояние от кладовой до кресла первого необслуженного пассажира, чтобы продолжить обслуживание.

Определите, какое минимальное расстояние должна проехать тележка, чтобы переместиться из точки \(0\) в точку \(n+1\) и обслужить всех пассажиров.

Формат входных данных
Первая строка входных данных содержит четыре целых числа \(n\), \(m\), \(k\), \(p\) (\(3 \leq n \leq 10^6\), \(1 \leq p \leq 10^6\), \(1 \leq k \leq m \leq 10^6\)) — количество мест в салоне, вместимость тележки, количество типов напитков и вместимость каждой бутылки соответственно.

В следующей строке содержится целое число \(c\) (\(1 \leq c \leq 3\)) — параметр, описывающий наличие кладовых в салоне. Если \(c=1\), то кладовая находится только в точке \(n+1\). Если \(c=2\), то кладовая находится только в точке \(0\). Если \(c=3\), то кладовые находятся в обоих концах салона.

В следующей строке содержатся \(n\) целых чисел \(a_i\) (\(1 \leq a_i \leq k\)) — типы напитков, которые заказали пассажиры.

Формат выходных данных
Программа должна вывести одно целое число — минимальное расстояние, которое должна проехать тележка.

Пояснения к примерам
В первом примере в тележку вмещается \(m=2\) бутылки по \(p=1\) порции в каждой. Кладовая находится в конце салона. Первоначально тележку нужно загрузить бутылками с напитками вида \(1\) и \(2\), которые будут налиты пассажирам на местах \(1\) и \(2\), тележка проедет расстояние \(2\) от точки \(0\) до точки \(2\). После этого тележке нужно будет проехать до кладовой в конце салона (расстояние \(4\)), загрузить тележку бутылками вида \(1\) и \(2\) и вернуться к креслу номер \(3\) (тележка проедет расстояние \(3\)). Пассажирам на местах \(3\) и \(4\) выдаются напитки вида \(1\) и \(2\) (тележка проезжает расстояние \(1\) от места \(3\) до места \(4\)). После этого тележке понадобится ещё раз съездить в кладовую (от кресла \(4\) до кладовой расстояние \(2\)), вернуться из кладовой до кресла \(5\) (расстояние \(1\)), и проехать ещё \(1\) до конца салона. Общее расстояние равно \(2+4+3+1+2+1+1=14\).

Во втором примере в тележку вмещаются \(m=3\) бутылки по \(p=2\) порции в каждой. Кладовая находится в начале салона. Необходимо загрузить тележку тремя бутылками вида \(1\), обслужить пассажиров на местах с номерами от \(1\) до \(4\). После этого опустошатся две бутылки вида \(1\), нужно будет сразу съездить в кладовую, чтобы загрузить две бутылки вида \(2\), затем обслужить пассажиров на местах с номерами от \(5\) до \(8\).

В третьем примере в тележку вмещаются \(m=3\) бутылки по \(p=2\) порции в каждой, кладовые находятся в обоих концах салона. Для обслуживания пассажиров нужны две бутылки вида \(2\) и по одной бутылке видов \(1\) и \(3\), поэтому понадобится один раз съездить в кладовую для того, чтобы заменить пустую бутылку вида \(2\) на полную. Это лучше сделать после обслуживания пассажира на месте \(3\), тележка должна съездить в кладовую в начале салона.

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

В пятом примере понадобится два пополнения тележки, один раз тележке придётся вернуться в кладовую в начало салона после обслуживания пассажира \(3\), второй раз — в конец салона после обслуживания пассажира \(6\).

Новая татарская игра <<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. Выводит корни уравнения.

Напишите программу, которая выполняет глобальное выравнивание двух ДНК-последовательностей, и выводит все выравнивания и их score (балл).

Формат входных данных
Две строки содержит две последовательности ДНК, далее вводятся настройки параметров:

• Балл за совпадение
• Балл за несовпадение
• Балл за открытие гэпа
• Балл за продолжение гэпа

Формат выходных данных
Выведите все выравнивания и их score (балл).