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

Помогите Василию разобраться, может ли он найти в слове две заглавные буквы V и K, чтобы забрать их себе на холодильник. Если таких букв нет, то проверьте найдутся ли две строчные буквы v и k в слове (в крайнем случае Василий готов составить надпись vk из двух строчных букв).

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

За одну операцию Робин Гуд может выбрать три подряд идущих элемента массива и заменить их на медиану этих трёх элементов.

Медианой набора чисел $$$a_1, a_2, \ldots, a_{2m-1}$$$ называется число $$$c_m$$$, где $$$c_1, c_2, \ldots, c_{2m-1}$$$ — набор чисел $$$a_1, a_2, \ldots, a_{2m-1}$$$, отсортированный по неубыванию. Например, медиана набора чисел $$$5, 2, 3$$$ равна $$$3$$$, а медиана набора чисел $$$4, 8, 4$$$ равна $$$4$$$.

Можно показать, что такими операциями всегда можно уравнять массив длины хотя бы $$$3$$$. Например, массив $$$[2, 4, 5, 5, 9]$$$ можно уравнять так: $$$[2, 4, 5, 5, 9] \to [2, 5, 5, 5, 9] \to [5, 5, 5, 5, 9] \to [5, 5, 5, 5, 5]$$$.

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

Магнус Карлсен и Хикару Накамура вышли в финал чемпионата мира по быстрым шахматам. После серии ничейных партий в тай-брейке им предстоит сыграть партию-армагеддон. Правила этой партии аналогичны обычным, за исключением одного: при ничейном исходе партии победителем объявляется шахматист, игравший черными.

У Хикару и Магнуса есть стратегия, как быстро получить ничью за черных, но для этого им нужно, чтобы изначально на часах у них было не меньше $$$k$$$ минут и $$$s$$$ секунд. Если времени на часах будет меньше, то шахматист не успеет сделать ничью и проиграет.

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

• Магнус и Хикару загадывают определенное количество времени.
• Играть за черных будет тот, кто предложил наименьшую ставку, при этом на часах у него будет время равное наибольшей ставке.
• При равенстве ставок, шахматист, который играет за черных, выбирается случайным образом.

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

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

Гильдия предлагает $$$n$$$ воинов и у $$$i$$$-го воина $$$h_i$$$ единиц здоровья и $$$d_i$$$ единиц атаки. У монстра, которого надо убить, $$$a$$$ единиц здоровья.

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

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

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

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

Вместо этого рассмотрим наибольшее общее простое двух натуральных чисел $$$\operatorname{gcp}(a, b)$$$ — это такое наибольшее простое число, на которое одновременно делится и $$$a$$$, и $$$b$$$.

Заметим, что не для любой пары чисел определено их наибольшее общее простое. Например, $$$\operatorname{gcp}(10, 15) = 5$$$, a $$$\operatorname{gcp}(2, 3)$$$ не определено.

Вам предстоит ответить на $$$t$$$ запросов, содержащих пару чисел $$$l$$$ и $$$r$$$. Для каждого запроса вам нужно:

• найти наибольшее простое число $$$p$$$ такое, что существуют два числа $$$a$$$ и $$$b$$$ $$$(a \neq b)$$$ на отрезке $$$[l;r]$$$ такие, что $$$\operatorname{gcp}(a, b)=p$$$,
• или сообщить, что такого простого числа $$$p$$$ не существует.

Например, пусть заданы $$$l = 3$$$, $$$r = 10$$$. Тогда $$$p = 5$$$, так как $$$\operatorname{gcp}(5, 10) = 5$$$.

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