BSUIR Open XII: Student final
A. Обобщенная задача о пушечных ядрах
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задача о пушечных ядрах заключается в том, чтобы найти такое число пушечных ядер, что их можно уложить и в один слой в форме квадрата, и в форме пирамиды с квадратным основанием. Легко заметить, что такую задачу можно свести к тому, чтобы найти такие натуральные $$$n$$$ и $$$m$$$, что:

$$$$$$\sum_{i=1}^{n}i^2 = m^2$$$$$$

Точно известно, что существует ровно два решения: $$$n = 1$$$ и $$$m = 1$$$, то есть одно пушечное ядро, и $$$n = 24$$$ и $$$m = 70$$$, то есть $$$70^2 = 4900$$$ пушечных ядер.

В эру межзвездных путешествий такая укладка может оказаться не совсем удобной. Например, на пиратских космических кораблях используется укладка пушечных ядер в форме усеченной пирамиды, состоящей ровно из $$$k$$$ слоев. Так мы получим обобщенную задачу о пушечных ядрах, которую можно свести к поиску для заданного $$$k$$$ таких натуральных $$$n$$$ и $$$m$$$, что:

$$$$$$\sum_{i=1}^{k}(n+i-1)^2 = m^2$$$$$$

Для эффективной борьбы с космическим пиратством было принято решение исследовать данную задачу. Вас просят найти любое решение задачи для заданного $$$k$$$. Так как $$$m$$$ однозначно определяется из числа $$$n$$$, вас просят найти только $$$n$$$.

Рисунок 1. Пример укладки пушечных ядер в форме усеченной пирамиды ($$$n = 3$$$, $$$k = 3$$$)
Входные данные

В первой строке задано единственное целое число $$$t$$$ — количество значений $$$k$$$, для которых авторы хотят узнать решение.

В следующих $$$t$$$ строках задано единственное целое число $$$k$$$ — значение, для которого необходимо найти хотя бы одно решение.

$$$$$$1 \le t \le 10$$$$$$ $$$$$$1 \le k \le 2500 $$$$$$

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

Для каждого заданного $$$k$$$ в отдельной строке выведите «Yes», если существует решение, в противном случае выведите «No». Если решение существует, то в следующей строке выведите единственное положительное целое число $$$n$$$ — любое решение обобщенной задачи о пушечных ядрах, не превышающее $$$10^{18}$$$.

Гарантируется, что если решение существует, то существует решение не превышающее $$$10^{18}$$$.

Примеры
Входные данные
3
4
6
24
Выходные данные
No
No
Yes
1
Входные данные
1
529
Выходные данные
Yes
255

B. Надежная поставка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Всего предприятие производит $$$m$$$ типов продукции. Вам предоставили график поставки товаров, который представляет из себя $$$n$$$ непересекающихся между собой промежутков времени. В $$$i$$$-й промежуток времени в телепортационную камеру будут загружать контейнеры определенного типа товара $$$t_i$$$ начиная с $$$l_i$$$-й единицы времени до $$$r_i$$$-й единицы времени включительно. Так как телепортация занимает ровно одну единицу времени, то за $$$i$$$-й промежуток будет загружено ровно $$$r_i-l_i+1$$$ контейнеров. Из-за особенностей производства в расписании не может встречаться более двух промежутков времени с поставкой контейнеров одного типа продукции.

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

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

В первой строке задано два целых числа $$$n$$$ и $$$m$$$ — количество промежутков времени в графике поставки и количество типов продукции соответственно.

В следующих $$$n$$$ строках задано по три целых числа $$$t_i$$$, $$$l_i$$$ и $$$r_i$$$ — тип продукции в $$$i$$$-м промежутке времени, а также начало и конец $$$i$$$-го промежутка времени соответственно.

$$$$$$1 \le m \le n \le 10^5$$$$$$ $$$$$$1 \le t_i \le m$$$$$$ $$$$$$1 \le l_i \le r_i \le 10^9$$$$$$ $$$$$$r_i \lt l_{i+1}$$$$$$

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

В первой строке выведите «Yes», если возможно поставить одинаковое количество контейнеров каждого типа продукции, используя не более $$$m$$$ переключений.

Если поставку осуществить невозможно, то в единственной строке выведите «No».

Во второй строке выведите число $$$k$$$ ($$$0 \le k \le m$$$) — количество переключений.

В последней строке выведите $$$k$$$ целых чисел $$$s_i$$$ ($$$1 \le s_i \le 10^9$$$, $$$s_i \lt s_{i+1}$$$) — время, когда необходимо использовать переключатель. Если существует несколько вариантов ответа, то вы можете вывести любой.

Обратите внимание, что переключение в $$$x$$$-ю единицу времени всегда происходит до телепортации товара в $$$x$$$-ю единицу времени.

Примеры
Входные данные
4 3
1 1 2
2 3 6
3 8 9
1 11 14
Выходные данные
Yes
3
5 9 12 
Входные данные
1 1
1 1 3
Выходные данные
No
Входные данные
5 3
1 1 2
2 3 4
3 5 8
2 9 10
1 11 12
Выходные данные
Yes
1
7 

C. Торт и свечи
ограничение по времени на тест
2 с
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть торт радиусом $$$r$$$, центр которого находится в $$$(0, 0)$$$. Также есть $$$n$$$ свечек, $$$i$$$-я из которых имеет координаты $$$(x_i, y_i)$$$ и находится строго внутри торта. Вадим хочет задуть все эти свечки, ведь только в таком случае его тайная мечта сбудется и у него появится альтушка.

Вадим может встать в произвольную точку на плоскости (на рисунке ниже она обозначена буквой $$$V$$$) и посмотреть в какую угодно сторону. В таком случае он сможет задуть все свечки, которые принадлежат некоторому углу с вершиной в $$$V$$$ и величиной $$$\theta$$$.

  Рисунок 1. Серым цветом обозначены задутые свечки, оранжевым — не задутые. Фиолетовым цветом обозначен Вадим и направление (угол), в котором он задувает свечки. Здесь $$$\theta = 42^{\circ}$$$.

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

Обратите внимание, что торт потом будет съеден, а поэтому Вадиму не стоит на него залезать (иными словами ответ всегда должен быть не меньше $$$r$$$).

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

В первой строке указано $$$t$$$ — количество наборов входных данных.

В первой строке каждого набора указаны натуральные числа $$$n$$$, $$$r$$$, $$$\theta$$$ — количество свечек, радиус торта и величина угла, который может задуть Вадим.

В последующих $$$n$$$ строках указаны пары целых чисел $$$x_i$$$, $$$y_i$$$ — координаты $$$i$$$-й свечки.

$$$$$$1 \le t \le 20\,000$$$$$$ $$$$$$1 \le \sum n \le 200\,000$$$$$$ $$$$$$1 \le r \le 10^9$$$$$$ $$$$$$20 \le \theta \le 120$$$$$$ $$$$$$x_i^2 + y_i^2 \le r^2$$$$$$

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

Для каждого набора введите минимальное расстояние, на которое надо отойти Вадиму. Ответ будет считаться верным, если абсолютная или относительная погрешность не будет превышать $$$10^{-9}$$$.

Примеры
Входные данные
1
5 2 30
0 0
-1 -1
1 1
-1 1
1 -1
Выходные данные
4.574735318057
Входные данные
2
2 2 90
1 0
-1 0
1 2 20
1 1
Выходные данные
2.000000000000
2.000000000000

D. Сложная задача
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для того чтобы посетить центр галактики и увидеть с близкого расстояния квазар, необходимо пройти довольно долгий и опасный путь. Во время путешествия к центру галактики вы столкнулись с космическим патрулем. Вас предупредили, что для дальнейшего передвижения вам нужно назвать пароль — целое положительное число $$$x$$$, в противном случае вы будете уничтожены. У вас есть возможность задать не более $$$32$$$ вопросов вида: сколько существует простых чисел $$$p$$$, таких что найдется такое целое $$$i$$$, что $$$p \cdot i = \lfloor \frac{n}{q} \rfloor$$$, где $$$q$$$ — число, которое вы задаете в вопросе. В ответ вы получите количество таких простых чисел, либо $$$-1$$$, если их бесконечное количество.

Протокол взаимодействия

Для того чтобы задать вопрос вам необходимо вывести строку: «? q», где $$$q$$$ — некоторое целое положительное число. В ответ вы получите единственное число — количество простых чисел, удовлетворяющих условию вашего запроса.

Как только вы определили пароль, выведите в отдельной строке «! x». После этого ваша программа должна немедленно завершить работу.

$$$$$$1 \le x, q \le 10^9$$$$$$

Если ваша программа задаст больше $$$32$$$ вопросов, то она получит вердикт «Wrong Answer».

Примеры
Входные данные
? 4

? 8

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

1

0
Входные данные
? 4

? 8

? 21

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

2

1

1

E. Безопасная работа с памятью
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Во время путешествия к звездной системе, где будет проходить выставка одежды, на корабле Лоренцо произошел сбой. Из-за неверных настроек параметров варп прыжка, корабль попал в квантовую турбулентность и оказался в пиратской системе PRS-1. К сожалению, корабль был захвачен пиратами, а во время переговоров Лоренцо несколько раз слышал фразу: «Please, use Rust. Use it blazingly fast».

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

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

let X = new();

Здесь и далее «X» означает имя переменной, состоящее только из строчных букв латинского алфавита.

Для явного освобождения памяти пираты используют следующую конструкцию:

drop(X);

Язык автоматически освобождает память при выходе переменной за пределы области видимости. Для того, чтобы задать начало и конец области видимости, используются символы «{» и «}» соответственно:

{
let X = new();
}

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

{
let a = new();
let b = new();
let c = new();
let d = new();
drop(c);
}

Будет преобразовано компилятором в:

let a = new();
let b = new();
let c = new();
let d = new();
drop(c);
drop(d); // <-
drop(b); // <-
drop(a); // <-

В качестве выкупа корабля пираты предложили Лоренцо улучшить предложенный код на Rust. Так как пираты используют только явное управление памятью и не используют автоматическое освобождение (области видимости), они просят вас переписать их код так, чтобы минимизировать количество конструкций явного освобождения памяти, при этом не изменяя порядок выделения и освобождения памяти.

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

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

В первой строке задано единственное целое число $$$n$$$ — количество строк в коде пиратов.

В следующих $$$n$$$ строках идет код пиратов. Каждая строка имеет один из двух форматов:

  • «let X = new();» — выделение памяти переменной с именем 'X'.
  • «drop(X);» — освобождение памяти переменной с именем 'X'.

Гарантируется, что все создаваемые переменные имеют уникальные названия, состоящие только из строчных букв латинского алфавита, длина которых не превышает $$$16$$$ символов. Также гарантируется, что каждому выделению памяти соответствует единственное освобождение памяти (выделение памяти всегда предшествует ее освобождению).

$$$$$$2 \le n \le 1000$$$$$$

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

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

Каждая строка должна иметь один из четырех форматов:

  • «let X = new();» — выделение памяти переменной с именем 'X'.
  • «drop(X);» — освобождение памяти переменной с именем 'X'.
  • «{» — начало области видимости.
  • «}» — конец области видимости.

Вы также можете добавить любое количество пробелов в начале каждой строки (но не более $$$4\,000$$$).

Примеры
Входные данные
6
let aba = new();
let caba = new();
let daba = new();
drop(aba);
drop(daba);
drop(caba);
Выходные данные
let aba = new();
let caba = new();
let daba = new();
drop(aba);
Входные данные
8
let a = new();
let b = new();
drop(b);
let c = new();
drop(c);
drop(a);
let e = new();
drop(e);
Выходные данные
{
  let a = new();
  {
    let b = new();
  }
  let c = new();
}
let e = new();

F. Кротовые норы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как всем известно, Александр любит путешествовать по космосу. Сам космос представляет из себя поле размером $$$n$$$ на $$$m$$$ клеток. Каждая клетка бывает одного из двух видов: первый вид — это самая обычная клетка космоса, второй вид — это кротовая нора, которая моментально перемещает из этой клетки в соседнюю (вверх, вправо, вниз и влево). В данный момент Александр хочет полететь на своем корабле из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$.

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

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

Помогите Александру потратить минимальное количество денег и за минимальное количество часов попасть из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$.

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

В первой строке задано два числа $$$n$$$ и $$$m$$$ — размеры космоса.

Далее идет $$$n$$$ строк, в каждой из которых содержится по $$$m$$$ символов.

Каждый символ является одним из ниже перечисленных:

  • «.» — если эта клетка является обычной клеткой космоса.
  • «U» — если эта клетка с кротовой норой, которая переносит корабль из данной клетки в клетку выше данной.
  • «R» — если эта клетка с кротовой норой, которая переносит корабль из данной клетки в клетку правее данной.
  • «D» — если эта клетка с кротовой норой, которая переносит корабль из данной клетки в клетку ниже данной.
  • «L» — если эта клетка с кротовой норой, которая переносит корабль из данной клетки в клетку левее данной.

Клетка $$$(1, 1)$$$ и $$$(n, m)$$$ всегда будут обычными клетками космоса.

$$$$$$1 \le n \le 10^5$$$$$$ $$$$$$1 \le m \le 10^5$$$$$$ $$$$$$1 \le n \cdot m \le 10^6$$$$$$

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

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

Примеры
Входные данные
1 4
.RR.
Выходные данные
0 1
Входные данные
2 3
.D.
.D.
Выходные данные
1 2
Входные данные
5 5
.U...
.U.D.
.U.D.
.U.D.
...D.
Выходные данные
0 16

G. Игровые автоматы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Жили-были три друга — Саша, Кирилл и Юра. В какой-то момент у них закончились деньги. Поэтому они решили построить казино и стали придумывать правила:

  • Саша: — В автомате будет лежать $$$a$$$ камней, и за ход можно забрать произвольное количество камней от $$$1$$$ до $$$k$$$;
  • Кирилл: — Если кто-то взял столько же камней из автомата, сколько из него брали в предыдущий раз, то он проиграл.
  • Юра: — Автоматов будет $$$n$$$ штук, и в $$$i$$$-м из них будет лежать $$$a_i$$$ камней.

Постоянно играть в одну и ту же игру скучно, к тому же нет никакого элемента случайности. Поэтому друзья решили уточнить правила:

  • Саша: — При входе для игрока генерируется пара случайных чисел $$$(l,r)$$$ ($$$1 \le l \le r \le n$$$). За один ход можно забрать камни из любого автомата с номером $$$i$$$, таким что $$$l \le i \le r$$$.
  • Кирилл: — С игроком играет специально обученный персонал, они делают ходы по очереди, при чем первый ход делает игрок.
  • Юра: — Игрок проиграл, если не может сделать ни одного хода по правилам игры, в таком случае он отдает свою квартиру владельцам казино.

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

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

В первой строке указаны числа $$$n$$$ и $$$k$$$ — количество автоматов и максимальное количество камней, которые можно брать за ход.

Во второй строке указаны числа $$$a_1, \ldots, a_n$$$ — исходное количество камней в каждом из автоматов.

$$$$$$1 \le n \le 1\,000\,000$$$$$$ $$$$$$2 \le k \le 100$$$$$$ $$$$$$1 \le a_i \le 10^{18}$$$$$$

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

Выведите единственное число — ответ на задачу.

Примеры
Входные данные
3 2
1 2 3
Выходные данные
3
Входные данные
2 10
308 693
Выходные данные
3
Примечание

Рассмотрим первый пример:

  • $$$(l,r)=(1,1)$$$. Побеждает игрок, так как он может за первый ход взять все камни.
  • $$$(l,r)=(2,2)$$$. Побеждает игрок, так как он может за первый ход взять все камни.
  • $$$(l,r)=(3,3)$$$. Побеждает казино. Пусть игрок на первом ходу взял $$$x$$$ камней, тогда казино возьмет $$$3-x$$$.
  • $$$(l,r)=(1,2)$$$. Побеждает казино. Заметим, что из кучки размера $$$2$$$ забрать камни можно только один раз (если забрали только $$$1$$$ камень, то еще один нельзя будет забрать никогда, так как это повтор хода). Поэтому игрока всегда будет заканчиваться за два хода.
  • $$$(l,r)=(2,3)$$$. Побеждает игрок, так как первым ходом он может забрать все камни из второй кучки.
  • $$$(l,r)=(1,3)$$$. Побеждает казино, так как у него есть стратегия ответных ходов:
    • Если игрок берет камни из первой кучки, то казино берет камни из второй, и наоборот.
    • Если игрок берет $$$x$$$ камней из третьей кучки, то казино берет $$$3-x$$$ камней из этой же кучки.

Из всевозможных пар $$$(l, r)$$$ нам подходят $$$3$$$ пары $$$(3,3)$$$, $$$(1,2)$$$, $$$(1,3)$$$, поэтому ответ равен $$$3$$$.

H. Космический бар
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ежегодное соревнование ICPC (Intergalactic Collegiate Programming Contest) вновь готово принять своих гостей (на этот раз, к счастью, без переносов). На соревнование в том числе приехала небезызвестная команда Вселенской Школы Экспертов, которая, согласно правилам этого года, состоит ровно из $$$n$$$ участников. Участник команды под номером $$$i$$$ оценивает свою силу решения задач ровно в $$$a_i$$$ единиц.

Решив не нарушать хорошую традицию, вечером за день перед началом основного тура участники команды решили посетить не менее известный бар «DRYga». Поскольку команда довольно опытная, они знают интересную закономерность, которая характерна для них. Изначально $$$i$$$-й участник команды способен решить ровно $$$0$$$ задач на соревновании. После каждого выпитого «особого экстремального шота» силы $$$k$$$ участник команды под номером $$$i$$$ приобретает очень важные знания, что позволяет решить ему на соревновании ровно $$$(x + k) \bmod (a_i + 1)$$$ задач, где $$$x$$$ — количество задач, которые мог решить участник до того как выпил шот, а $$$a \bmod b$$$ — операция взятия остатка от целочисленного деления числа $$$a$$$ на число $$$b$$$. Весь вечер команда заказывает только «особые экстремальные шоты» силы $$$k$$$, участник команды может заказать неограниченное количество шотов.

Поскольку команда намерена выиграть соревнования в этом году, они хотят заказать в баре ровно столько «особых экстремальных шотов» силы $$$k$$$, чтобы каждый участник команды решил ровно $$$a_i$$$ задач. Помогите легендарной команде посчитать какое минимальное суммарное количество шотов в баре необходимо заказать.

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

Первая строка входных данных содержит два разделенных пробелами натуральных числа $$$n$$$ и $$$k$$$ — количество участников команды и сила «особого экстремального шота».

Вторая строка входных данных содержит $$$n$$$ натуральных чисел $$$a_1, a_2, a_3, \ldots, a_n$$$ — сила решения задач участника под номером $$$i$$$.

$$$$$$ 1 \le n \le 10^5 $$$$$$ $$$$$$ 1 \le k \le 10^5 $$$$$$ $$$$$$ 0 \le a_i \le 10^5 $$$$$$ $$$$$$ \sum{a_i} \le 10^6 $$$$$$

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

Выведите единственное число — минимальное количество шотов, которое необходимо заказать команде.

Если не существует такого количества шотов, чтобы каждый участник команды решил ровно $$$a_i$$$ задач, выведите $$$-1$$$.

Примеры
Входные данные
5 5
1 2 3 5 7
Выходные данные
9
Входные данные
5 6
28 16 4 18 20
Выходные данные
-1
Примечание

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

I. Open BSUIR
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Привет, меня зовут Стив. Приглашаю тебя на открытую олимпиаду БГУИР. Записывай координаты: звезда называется Солнце, а планета — третья по счёту от звезды. В олимпиаде примут участие $$$n$$$ команд со всей галактики Млечный Путь, а твоя команда будет $$$n + 1$$$-й. Ах, да, не забудь придумать какую-нибудь задачку, ведь это открытая олимпиада и каждая команда должна предложить ровно одну задачу. Олимпиада будет проходить на свежем воздухе и да, за решение каждой задачки твоя команда получит шарик. Но помни, во время олимпиады запрещено общаться с другими участниками и покидать зону проведения олимпиады, в противном случае команда будет дисквалифицирована. Пусть победит сильнейший, а точнее тот, кто решит как минимум на одну задачу больше, чем все остальные команды.

Стив передал вам некоторый список. В этом списке указана информация по каждой из $$$n$$$ команд: $$$s_i$$$ — сила $$$i$$$-й команды, $$$w_i$$$ — суммарный вес $$$i$$$-й команды и $$$d_i$$$ — сложность задачи, которую предложила $$$i$$$-я команда. По правилам олимпиады, за решение задачи сложности $$$x$$$ команда получает шарик с грузоподъемностью $$$x$$$. Каждая команда (в том числе и ваша) всегда решает задачи, сложность которых не превышает силу команды. Команда всегда решает свою собственную задачу не зависимо от сложности. Если в какой-то момент суммарная грузоподъемность шариков оказывается строго больше веса команды, то она взлетает в воздух и покидает зону проведения олимпиады, что в свою очередь приводит к дисквалификации.

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

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

В первой строке задано три целых числа $$$n$$$, $$$s_0$$$ и $$$w_0$$$ — количество команд, сила и вес вашей команды соответственно.

В следующих $$$n$$$ строках задано по три целых числа $$$s_i$$$, $$$w_i$$$ и $$$d_i$$$ — сила и вес $$$i$$$-й команды, а также сложность задачи, предложенной $$$i$$$-й командой.

$$$$$$1 \le n \le 10^5$$$$$$ $$$$$$1 \le s_0, s_i \le 10^5$$$$$$ $$$$$$1 \le w_0, w_i \le 10^9$$$$$$ $$$$$$1 \le d_i \le 10^5$$$$$$

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

В единственной строке выведите «Yes», если ваша команда сможет одержать победу в олимпиаде. В противном случае выведите «No».

Примеры
Входные данные
2 1 20
10 29 20
25 59 30
Выходные данные
Yes
Входные данные
3 5 20
10 29 20
25 69 30
1 50 49
Выходные данные
No

J. Модный костюм
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

У вас есть план выставки, представляющий из себя клетчатое поле размером $$$w$$$ клеток в ширину и $$$h$$$ клеток в высоту. Клетки пронумерованы сверху вниз, слева направо, начиная с единицы. На границах клеток могут стоять перегородки. Известно, что всего есть $$$n$$$ перегородок покрытых тканью (липких) и $$$m$$$ обычных (не липких). Вам известно, к какой перегородке с какой стороны прилип Лоренцо. Вам необходимо найти минимальное количество действий, выполняя которые, Лоренцо сможет свободно перемещаться. Всего существует три вида действий:

  1. Сделать один поворот по часовой стрелке. Тогда Лоренцо переместится на соседнюю по стороне перегородку, либо на обратную сторону перегородки, если соответствующей соседней стены нет.
  2. Сделать один поворот против часовой стрелки. Аналогично предыдущему действию.
  3. Со всей силы оттолкнуться от перегородки. В таком случае, Лоренцо будет лететь в противоположном от стены направлении, либо пока не врежется в другую стену, либо не вылетит за пределы выставки.
Рисунок 1. Примеры возможных действий
Входные данные

В первой строке задано четыре целых числа $$$w$$$, $$$h$$$, $$$n$$$ и $$$m$$$ — ширина и высота выставки, а также количество перегородок покрытых тканью и обычных перегородок соответственно.

В следующих $$$n$$$ строках задано два целых числа $$$x$$$ ($$$1 \le x \le w$$$) и $$$y$$$ ($$$1 \le y \le h$$$) и один символ $$$t$$$ — координаты клетки и ее граница, на которой расположена липкая перегородка. Символ $$$L$$$ означает, что перегородка расположена на левой границе, $$$R$$$ — на правой, $$$U$$$ — на верхней и $$$D$$$ — на нижней.

В следующих $$$m$$$ строках задано описание обычных перегородок в таком же формате.

В последней строке задано два целых числа $$$sx$$$ ($$$1 \le sx \le w$$$) и $$$sy$$$ ($$$1 \le sy \le h$$$) и один символ $$$st$$$ — координаты клетки и ее граница, к которой прилип Лоренцо. Гарантируется, что Лоренцо прилип к стене, покрытой тканью.

Гарантируется, что каждая стена не может быть одновременно липкой и обычной (даже различные стороны). Также обратите внимание, что например «1 1 D» и «1 2 U» описывают одну и ту же стену.

$$$$$$1 \le w, h \le 10^5$$$$$$ $$$$$$1 \le n \le 5 \cdot 10^5$$$$$$ $$$$$$0 \le m \le 5 \cdot 10^5$$$$$$ $$$$$$n + m \le 5 \cdot 10^5$$$$$$

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

В первой строке выведите «No», если Лоренцо не сможет освободиться.

В противном случае в первой строке выведите «Yes», а в следующей строке выведите строку, описание маршрута Лоренцо.

Символ «>» означает поворот по часовой стрелке, «<» — против часовой стрелки, а «^{}» означает, что Лоренцо необходимо оттолкнуться от стены. Если существует несколько вариантов ответа, вам необходимо вывести любой, состоящий из наименьшего числа действий.

Примеры
Входные данные
1 1 3 1
1 1 L
1 1 R
1 1 D
1 1 U
1 1 D
Выходные данные
Yes
^
Входные данные
1 1 3 1
1 1 L
1 1 R
1 1 D
1 1 U
1 1 L
Выходные данные
Yes
<
Входные данные
2 2 8 0
1 1 U
2 1 U
1 1 L
1 2 L
2 1 R
2 2 R
2 2 D
1 1 D
1 1 U
Выходные данные
Yes
^>^
Входные данные
1 1 3 0
1 1 U
1 1 D
1 1 L
1 1 D
Выходные данные
Yes
>^
Входные данные
1 1 4 0
1 1 U
1 1 D
1 1 L
1 1 R
1 1 L
Выходные данные
No
Примечание
Рисунок 2. Визуализация для тестовых примеров 1-3

K. Звёздное небо
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как классно прогуляться на свежем воздухе ночью и поразглядывать созвездия на небе! На этот раз вы решили подготовиться и изучить карту звёздного неба. Карта представляет из себя $$$n$$$ точек на плоскости, где $$$i$$$-я точка расположена в координатах $$$(x_i, y_i)$$$. Также на карту нанесено $$$m$$$ отрезков, соединяющих какие-то пары точек. Связный набор точек образует созвездие, причем гарантируется, что каждое созвездие не содержит циклов.

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

К сожалению, Ваш фотоаппарат сломался, поэтому каждый раз он фотографирует абсолютно случайную прямоугольную область. Для этого фотоаппарат независимо друг от друга выбирает две координаты (не обязательно целочисленные) $$$x_a$$$ и $$$x_b$$$ равновероятно, на промежутке $$$[x_{\min}, x_{\max}]$$$. Аналогично, он выбирает две координаты $$$y_a$$$ и $$$y_b$$$ на промежутке $$$[y_{\min}, y_{\max}]$$$ В результате на снимок попадают все точки $$$(x_i, y_i)$$$ для которых выполняются условия $$$\min \{ x_a, x_b \} \le x_i \le \max \{ x_a, x_b \}$$$ и $$$\min \{ y_a, y_b \} \le y_i \le \max \{ y_a, y_b \}$$$.

Отрезок, соединяющий пару точек попадает на фотографию только, если оба его конца также оказались на фотографии.

Вы интересуетесь, чему равно математическое ожидание количества мнимых созвездий на снимке.

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

В первой строке задано шесть целых чисел $$$n$$$, $$$m$$$, $$$x_{\min}$$$, $$$x_{\max}$$$, $$$y_{\min}$$$, $$$y_{\max}$$$ — количество точек на звездной карте и количество прямых отрезков, соединяющих точки. ' Во второй строке задано $$$n$$$ целых чисел $$$x_i$$$ — координата $$$x$$$ $$$i$$$-й звезды.

В третьей строке задано $$$n$$$ целых чисел $$$y_i$$$ — координата $$$y$$$ $$$i$$$-й звезды.

В четвертой строке задано $$$m$$$ целых чисел $$$a_i$$$ — номер звезды, соединенный одним концом $$$i$$$-го отрезка.

В пятой строке задано $$$m$$$ целых чисел $$$b_i$$$ — номер звезды, соединенный другим концом $$$i$$$-го отрезка.

$$$$$$1 \le m \lt n \le 10^5$$$$$$ $$$$$$0 \le x_{\min} \lt x_{\max} \le 10^9, 0 \le y_{\min} \lt y_{\max} \le 10^9$$$$$$ $$$$$$0 \le x_i, y_i \le 10^9$$$$$$ $$$$$$1 \le a_i, b_i \le n$$$$$$ $$$$$$a_i \ne b_i$$$$$$

Гарантируется, что все точки имеют различные координаты.

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

Пусть $$$p$$$ — матожидание количества мнимых созвездий на фотографии. Можно показать, что ответ можно представить в виде $$$\frac{a}{b}$$$, где $$$a$$$ и $$$b$$$ взаимнопростые целые числа ($$$b \not\equiv 0 \pmod{10^9+7}$$$). При этом как $$$b^{-1}$$$ обознчается целое число, для которого верно $$$b \cdot b^{-1} \equiv 1 \pmod{10^9+7}$$$. Выведите значение $$$a \cdot b^{-1}$$$ по модулю $$$10^9+7$$$.

Примеры
Входные данные
2 1 0 3 0 3
1 2
1 2
1
2
Выходные данные
456790127
Входные данные
2 1 0 2 0 2
1 3
1 3
1
2
Выходные данные
250000002
Входные данные
12 8 0 16 0 8
1 5 1 5 6 8 10 6 11 11 15 15
1 7 7 1 7 4 7 1 1 7 7 1
1 3 5 6 6 9 9 11
2 4 6 7 8 10 11 12
Выходные данные
286376956