Алгоритмы

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

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

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

•  направление лазера, находящегося в начале координат, в виде угла наклона кратного 45 градусам (угол считается против часовой стрелке) (положительное направление оси OX равно 0 градусов, а положительное направление оси OY равно 90 градусам) (угол от 0 до 315 градусов);
•  интенсивность света лазера в нановаттах (целое число от 100 до 5000).
• На второй строке подаётся число N (1 <= N <= 20) – количество металлических коробов (параллелепипедов), которые Оля хочет установить. Далее на N строках подаются через пробел параметры каждого короба:
•  координаты левого верхнего угла, координаты правого нижнего угла короба (целые числа в диапазоне [-100;100]);
•  процент поглощения света (вещественное число в диапазоне [0; 100]).

На последней строке входных данных подаются координаты результирующей точки (целые числа в диапазоне [-100;100])

Выходные данные
Вывести в ответе в случае успеха конструкции интенсивность (только целую часть), с которой луч лазера попадёт в результирующую точку.
Если конструкция не успешна (лазер поглотился более чем на 90% от начальной интенсивности), то вывести координаты первого короба на пути лазерного луча, при отражении от которого интенсивность стала меньше 10% от начального) с указанием полученной интенсивности (только целую часть) (вывод через пробел – координаты левого верхнего угла, правого нижнего, (в том порядке, в котором короб был введена в программу), затем полученная интенсивность).
Гарантируется, что лазер не может улететь в бесконечность, то есть результатом может быть либо поглощение луча, либо попадание в результирующую точку.

Город имеет форму прямоугольника с вершинами в точках (-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 (на печать не выводиться)

Станция связи принимает блоки сообщений. Каждое сообщение представляет собой последовательность кодовых сигналов. Всего сигналов 26; они перечислены в блоке как цифры числа, записанного в системе с основанием 26.Обработка некоторых кодовых сигналов требует участия операторов;значения таких сигналов кратны 6. На вход подаётся N чисел, записанных вдесятичной системе счисления – блоков сообщений. Определите, в сколькихблоках оказалось менее M₁ или более M₂ команд, требующих участияоператоров.

Формат входных данных
На вход программе в первой строке подается натуральное число N (N ≤ 10000) – количество блоков сообщений. Во второй строке подаются два целых неотрицательных числа M₁ и M₂ (0 ≤ M₁ ≤ M₂ ≤ 1000) – ограничение по количеству кодовых сигналов, требующих обработки оператором. Далее в N строках на вход подаётся по одному целому числу в диапазоне от 0 до 4*10⁹ – блок сообщений, записанных в десятичной системе счисления.
Формат выходных данных
Вывести одно целое число – в скольких блоках оказалось менее M₁ или более M₂ команд, требующих участия операторов.

Словом Чемпернауна называется длинная строка, полученная из натуральных чисел, записанных подряд без пробелов и запятых. Так, для десятичной системы счисления слово Чемпернауна начинается с 123456789101112…, а для семеричной – с 1234561011121314151620…
Найдите, какие цифры стоят на заданных местах (индексах) в слове Чемпернауна, записанном в семеричной системе счисления. Например, под индексом 3 находится цифра «4», а под индексом 1 цифра «2» – нумерация начинается с нуля.

Формат входных данных
На вход программе в первой строке подается натуральное число N (N ≤ 1000) – количество индексов, для которых надо определить цифру в записанном в семеричной системе слове Чемпернауна. Во второй строке даётся последовательность из N неотрицательных чисел, разделённых пробелами, каждое из которых не превосходит 2*10⁹ – индексы, для которых надо найти цифру. Нумерация индексов начинается с 0.

Формат выходных данных
Вывести строку из N цифр – цифр, стоящих на заданных местах в слове Чемпернауна, записанном в семеричной системе счисления.

Шоколад помогает развивать ум и укреплять дух! Старец Летовец после своих занятий угощает своих учеников шоколадом. На следующем занятии у него будет M учеников и каждому из них Старец хочет дать по одной плитке шоколада.

Чтобы купить нужное количество шоколада, старец отправил своего праправнука Летовёнка разузнать, какое минимальное количество денег ему понадобится.
Оказывается, каждый магазин продаёт шоколад по разной цене. В i-м магазине можно купить не более Bi​ плиток шоколада по цене Аi​ рублей за плитку. Летовец хочет потратить как можно меньше денег, но при этом купить ровно M плиток шоколада. 

Помогите Летовёнку посчитать какую минимульную сумму на шоколад потратит старец Летовец. 

Формат входных данных
В первой строке заданы два числа: N и M (1 <= N, M <= 10⁵). Следующие N строк содержат по 2 числа: Ai (1 <= A_i <= 10⁹) и Bi (1 <= В_i <= 10⁵). \(B_1 + B_2 +... + B_N >= M\).


Формат выходных данных
Выведите минимальную сумму денег, необходимую для покупки M плиток шоколада.
 

Примеры

№	Входные данные	Выходные данные
1	2 5 4 9 2 4	12
2	4 30 6 18 2 5 3 10 7 9	130
3	1 100000 1000000000 100000	100000000000000

Летовецкие числа — это положительные целые числа, которые делятся на a, b или c.

Напишите программу, которая находит n-е по счёту летовецкое число.

Формат входных чисел
Программа получает на вход четыре целых положительных числа n, a, b, и c. Каждое число записано в отдельной строке. 
Ограничения на входные данные

• 1 <= n, a, b, c <= 109
• 1 <= a * b * c <= 1018
• Гарантируется, что результат находится в диапазоне [1, 2 * 109].

Формат выходных чисел
Ваша программа должны вывести одное число -  n-е по счёту летовецкое число.
 

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

Для этого Магане может один раз выбрать произвольный набор различных позиций в массиве и заменить элементы на этих позициях на противоположные, то есть умножить их на \(-1\). Например, чтобы сделать массив \([-4, 4, 1, 3, -10]\) отсортированным, она может умножить на \(-1\) числа на позициях \(2\) и \(5\), и получить массив \([-4, -4, 1, 3, 10]\).

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

Помогите ей с этой задачей! Поскольку итоговое количество способов может быть слишком большим, найдите ответ по модулю \(998244353\).

В первой строке ввода записано целое число \(n\) — количество элементов в массиве (\(1 \leqslant n \leqslant 10^6\)).

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

Формат выходных данных
Выведите одно число — количество способов отсортировать массив указанным образом (по модулю \(998244353\)).

 

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

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

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

Формально, Рамазан выбрал \(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\).

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

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

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



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

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

За доставку одного заказа компания-организатор доставки получает \(p\) крипторублей. Стоимость создания одного нового робота равна \(c\) крипторублей. Итоговая прибыль равна суммарному доходу от доставки заказов за вычетом суммарной стоимости создания всех роботов. Компания хочет максимизировать свою прибыль. При этом, она не обязана выполнить все заказы, а роботы могут в любой момент остановиться, и прекратить процесс доставки.

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

Формат входных данных
В первой строке входных данных находятся четыре целых числа \(n\), \(m\), \(c\), \(p\) (\(0 \le n, m \le 100\,000\), \(1 \le c, p \le 10^6\)) — количество препятствий, количество заказов в базе, стоимость создания клона робота и стоимость доставки одного заказа, соответственно.

В следующих \(n+m\) строках идёт описание препятствий и окон, в которые нужно доставить заказы, в порядке следования колонны роботов вдоль общежитий слева направо. Каждая строка содержит два целых числа \(t_i\) и \(h_i\) (\(1 \le t_i \le 2\), \(1 \le h_i \le 10^6\)) — тип объекта \(t_i\) (\(1\) для препятствия и \(2\) для окна) и \(h_i\) "— высота препятствия в этажах или этаж, на котором находится окно.

Гарантируется, что ровно \(n\) объектов имеют тип \(1\), и оставшиеся \(m\) объектов имеют тип \(2\).

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

Пояснения к примерам

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



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

Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.
Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X = 0 или Y = 0 такой фонарь освещает только тот дом, у которого он установлен.
Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.

Формат входных данных
Первая строка входных данных содержит целое число N (1 ≤ N ≤ 10⁵ ). Следующие четыре строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосходят 10⁵ .
Формат выходных данных
Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел — координату фонаря и расстояние, которое он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1 до N, рядом с каждым домом можно поставить только один фонарь. При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не существует, программа должна вывести одно число −1

Замечание
В ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 — также дома 3, 4, 6 и 7, а фонарь у дома 9 — также дома 8 и 10. В результате все дома освещены. Во втором примере фонарей недостаточно.

Старец Летовец, известный своими суперскиллами, решил научить своих учеников создавать "Последовательность Трёх Сил". Он дал им список чисел и сказал: "Отсортируйте эти числа так, чтобы они образовали Последовательность Трёх Сил. Вот правила:"

1. Сила Тройки. Числа, которые делятся на 3, должны идти первыми.

2. Сила Порядка. Среди чисел, делящихся на 3, меньшие числа должны идти перед большими.

3. Сила Простоты. Среди чисел, не делящихся на 3, числа имеющие большее количество делителей должны идти раньше, чем числа имеющие меньшее количество делителей. При равном числе делителей, числа должны идти в порядке убывания.

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

Формат входных данных
В первой строке записано натуральное число n (n <= 10⁵) - количество целых чисел в списке. Далее, в n строках записано по одному целому числу numi ( -10⁵ <= numi <= -10⁵).


Формат выходных данных
Выведите в одной единственной строке Последовательность Трёх Сил, составленную из исходного списка чисел.

Старец Летовец, известный своей любовью к математике, решил проверить смекалку своих учеников. Он дал им n конфет и сказал: "Разложите эти конфеты на три кучки так, чтобы в каждой кучке было не больше, чем limit. И определите сколькими различными способами это можно сделать?"

Напишите программу, которая поможет ученикам получить ответ на вопрос Летовца.

Формат входных данных
В первой строке входных данных записано натуральное число n, во второй - натуральное число limit.

Ограничения

• 1 <= n <= 1000
• 1 <= limit <= 1000

Формат выходных данных
Выведите одно число - количество способов


Примечание
В первом тестовом примере есть 3 способа разложить 5 конфет таким образом, чтобы в каждой кучке было не больше 2 конфет: (1, 2, 2), (2, 1, 2) и (2, 2, 1).
Во втором тестовом примере существует 10 способов распределить 3 конфеты таким образом, чтобы в каждой кучке было бы не больше 3 конфет: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) и (3, 0, 0).
 

Будем назвать натуральное число интересным, если в его десятичной записи первая цифра совпадает с последней.

Дано число \(n\). Найдите количество интересных чисел, не превышающих \(n\).

Формат входных данных
На ввод подается целое число \(n\) (\(1 \le n \le 10^{18}\)).

Обратите внимание, что для считывания этого числа вам может понадобиться 64-битный тип данных (<<long long>> в C++, <<long>> в Java, <<int64>> в Паскале).

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

Недавно в город приехал известный цирк. Всего в этом цирке \(n\) акробатов, и в этот раз в честь проведения СПбКОШП 2022 они подготовили особенный номер.

Известно, что \(i\)-й акробат имеет рост \(a_i\) и вес \(b_i\). Любые три акробата могут собраться вместе и показать необычный трюк. Если трюк показывают акробаты с номерами \(i\), \(j\) и \(k\), то эффектность трюка оценивается как \(a_i b_j + a_j b_k + a_k b_i\).

Тренер акробатов считает упорядоченную тройку акробатов \((i, j, k)\) хорошей, если эффектность их трюка будет не меньше, чем если они расположатся в обратном порядке \((k, j, i)\).

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

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

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

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

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

В городе П для подготовки к празднику решили украсить аллею. Для этого наняли две бригады, одна отвечает за освещение аллеи, а вторая "— за озеленение аллеи, закупку саженцев сосны.

Аллею можно представить как прямую, и её решили украсить следующим образом — начать с сосны, чередовать лампы и сосны. В итоге на аллее будет высажено \(n + 1\) сосен и установлено \(n\) ламп.

Лампы поставили почти сразу же, причём двух типов — <<A>> и <<B>>. Лампы типа <<B>> светят всегда белым светом, а цвет лампы типа <<A>> зависит от её окружения. Если дерево, которое стоит слева от лампы, выше, чем дерево, которое стоит справа от лампы, то она загорается красным цветом, иначе синим.

Когда наконец-то доставили саженцы сосен, оказалось, что высоты всех саженцев попарно различны и принимают значения от \(1\) до \(n + 1\). Решено было разместить сосны так, чтобы количество красных и количество синих ламп были как можно ближе друг к другу.

Помогите ответственным за деревья разместить все \(n + 1\) саженцев так, чтобы разница между количеством красных и синих ламп была минимальна. Формально, если после высадки сосен будет \(r\) красных и \(b\) синих ламп, необходимо минимизировать величину \(|r-b|\).

Формат входных данных
В первой строке вводится одно единственное число \(n\) — количество ламп (\(1 \leq n \leq 2 \cdot 10^5\)). Во второй строке вводится \(n\) символов, \(i\)-й из которых равен <<A>> или <<B>> — тип \(i\)-й лампы.

Формат выходных данных
Выведите \(n + 1\) различных чисел от \(1\) до \(n + 1\) — высоты сосен при оптимальном размещении. Если оптимальных ответов несколько, можно вывести любой из них.

Иллюстрация ко второму примеру

Для наглядности, на иллюстрации красные лампы имеют формулу пятиугольника, а синие имеют форму звезды.

Тогда \(r = 1\), \(b = 1\), \(|r - b| = 0\) и это размещение будет одним из оптимальных.

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

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

1. color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.

2. Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат выходных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).

Всемирно известный маг Дэвид Копперфильд любит показывать следующий трюк. Квадрат из N столбцов и N строк, в каждой клетке которого находится какая-нибудь картинка, появляется на экране телевизора. Пусть все картинки пронумерованы следующим образом:

1	2	…	N
N+1	N+2	…	2*N
:	:	…	:
N*(N–1)+1	N*(N–1)+2	…	N*N

Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем — на одну клетку вниз, затем — на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и — что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).

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

Входные данные
Во входном файле записано одно число N — размер квадрата (2<=N<=100).

Выходные данные
В выходной файл ваша программа должна печатать следующие строки чисел:

K₁ X_1,1 X_1,2 … X_1,m1

K₂ X_2,1 X_2,2 … X_2,m2

…

K_e X_e,1 X_e,.2 … X_e,me

где K_i — это число ходов, которые должны сделать телезрители, а X_i,1 … X_i,mi — номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все K_i должны удовлетворять условию 2N<=K_i<=10000 и все K_i должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать K_i ходов, Дэвид должен убирать хотя бы одну картинку. Каждое K_i должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.

Алексей работает системным администратором в локальной домовой сети. Его сеть соединяет множество квартир и располагается в нескольких зданиях.

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

Компания, в которой работает Алексей покупает кабель только в одном специализированном магазине. В магазине продается кабель пятой и шестой категорий по цене P5 и P6 рублей за метр. При этом в наличии имеется только Q5 метров кабеля пятой категории и Q6 метров кабеля шестой категории.

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

Входные данные

В первой строке входного файла содержится число N — количество квартир, которые необходимо соединить и M — количество возможных соединений (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10 000).

Следующие M строк содержат описание возможных соединений. Каждое описание состоит из трех чисел A, B и L — где A и B задают номера квартир, а L — длина соединения между ними (1 ≤ L ≤ 100). Квартиры занумерованы от 1 до N.

Последняя строка входного файла содержит числа P5, Q5, P6, Q6 – цену и количество кабеля пятой и шестой категории соответственно (1 ≤ P, Q ≤ 10 000) .

Выходные данные

Если все квартиры можно соединить в сеть, то следует вывести N строк, описывающих план сети. Первая строка должна содержать стоимость прокладки сети. Следующие N-1 строк должны содержать описание соединений, представленных двумя числами каждое: A_i и C_i, где A_i — номер соединения в списке возможных соединений (от 1 до M), а C_i задает категорию кабеля и может принимать значения 5 или 6. Если планов несколько — выведите любой из них.

Если все квартиры соединить невозможно выведите слово Impossible.

Фонд изучения дикой природы в течение \(t\) лет ежегодно выделяет денежные гранты в поддержку исследований северной фауны. На гранты претендуют три организации, одна из которых занимается изучением тюленей, вторая "— оленей, третья "— белых медведей.

Для упрощения бухгалтерского учёта фонд принял следующие решения:

В \(i\)-м году фонд планирует полностью распределить \(n_i\) денежных единиц, выделенных на гранты. Сравнивать результативность использования средств возможно только для грантов одинакового размера, выделенных каждой из трёх организаций. Такие гранты называются целевыми. Распределение денежных единиц на гранты между тремя организациям считается оптимальным, если как можно бОльшая часть общей суммы выделена на целевые гранты.

Например, если в текущем году на все гранты выделено 47 денежных единиц, то оптимальным вариантом распределения будет: выделить каждой из организаций целевые гранты размерами по 2 и 8 денежных единиц, что составит в сумме 30 единиц. Остальные 17 единиц можно распределить, например, выделив первой организации 16 денежных единиц, а третьей — 1 денежную единицу. Выделить более 30 денежных единиц на целевые гранты, распределяя 47 денежных единиц, нельзя.

Требуется написать программу, которая по заданной в \(i\)-м году общей сумме грантов \(n_i\) определяет, сколько денежных единиц следует выделить каждой из трёх организаций при оптимальном распределении грантов.

В первой строке входных данных записано целое число \(t\) — количество лет (\(1 \le t \le 100\)). В каждой из последующих \(t\) строк записано целое число \(n_i\)"— общая сумма грантов, которую необходимо полностью распределить в \(i\)-м году.

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