По пути на Планету Двух Капитанов звездолёт профессора Селезнёва «Пегас» столкнулся с метеоритом. Двигатель звездолёта получил повреждения и нуждается в ремонте. Современные двигатели работают на двух массивах целых чисел $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$. Метеорит не затронул массив $$$a_1, a_2, \ldots, a_n$$$, но уничтожил массив $$$b_1, b_2, \ldots, b_n$$$.

Капитан Зелёный хочет вставить новый массив $$$b_1, b_2, \ldots, b_n$$$, но если среди чисел $$$|b_i - a_i|$$$ ($$$1 \le i \le n$$$) будет хотя бы одно чётное, двигатель «Пегаса» не заведётся.

Помогите капитану выбрать подходящий массив $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$), чтобы двигатель завёлся и команда смогла продолжить экспедицию.

Можно показать, что подходящий массив всегда существует.

Полезных ископаемых нет. Воды нет. Растительности нет. Населена роботами.

День на планете Шелезяка длится $$$n$$$ часов. Каждый робот, обитающий на этой планете, очень трудолюбивый. За день он по порядку перетаскивает $$$n$$$ ящиков массой $$$a_1, a_2, \ldots, a_n$$$, по ящику в час. Затем наступает следующий день, и он снова перетаскивает ящики массой $$$a_1, a_2, \ldots, a_n$$$. Ровно один раз в день между перетаскиваниями ящиков робот получает порцию смазки.

Механизмы роботов очень чувствительны, поэтому каждый перетащенный ящик наносит роботу урон. Ящик с номером $$$i$$$ моментально нанесёт $$$a_i$$$ урона за каждый час, начиная с $$$i$$$ до следующего получения смазки. Обратите внимание, что смазка может быть получена на следующий день.

Например, если $$$n = 8$$$, а мы выдали роботам смазку после перетаскивания $$$5$$$-го ящика:

• Ящик $$$a_5$$$ нанесёт урон один раз (всего $$$a_5$$$ урона);
• Ящик $$$a_6$$$ нанесёт урон восемь раз (всего $$$a_6 \cdot 8$$$ урона);
• Ящик $$$a_2$$$ нанесёт урон четыре раза (всего $$$a_2 \cdot 4$$$ урона).

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

Это интерактивная задача.

Птица Говорун отличается умом и сообразительностью, умом и сообразительностью.

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

Игра ведётся на доске $$$n \times n$$$. Сначала Говорун тайно расставляет $$$n$$$ ладей, чтобы они не били друг друга, запоминает их позиции и убирает с доски. Затем Алиса расставляет $$$n$$$ ладей, чтобы они не били друг друга.

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

Помогите Алисе выиграть своего умного друга.

Вы можете выполнить не более двух ходов.

Чтобы сделать ход, выведите $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le n$$$) — вертикали ладей, которые выставляет Алиса.

После каждого хода вы должны считать строку, содержащую вердикт.

Существуют три вердикта:

• «WIN» — вы выиграли, ваша программа должна перейти к обработке следующего набора входных данных;
• «LOSE» — вы проиграли, ваша программа должна немедленно завершиться;
• «AGAIN» — вы не выиграли первым ходом, но у вас остался ещё один. Во второй строке дано целое число $$$k$$$ ($$$1 \le k \le n$$$) — количество угаданных ладей Говоруна. В третьей строке даны $$$k$$$ целых чисел — вертикали, на которых вы угадали ладей Говоруна.

Не забывайте сбрасывать буфер после каждого вывода. Для этого можете использовать std::endl в C++ или стандартную функцию print в Python. Не используйте ios_base::sync_with_stdio(false) в C++.

Обратите внимание, что из-за особенностей тестирующей системы вы можете получить вердикт «Ошибка во времени исполнения» вместо вердикта «Неправильный ответ».

Профессор Селезнёв впервые встретился с удивительным зверем тигрокрысом. На лекциях в престижной академии СУНЦ учат, что у этого существа должно быть три хвоста с длинами $$$a$$$, $$$b$$$, $$$c$$$ ($$$a \lt b \lt c$$$). Профессор замерил длины $$$a$$$ и $$$c$$$, но вот незадача, средний хвост длины $$$b$$$ куда-то пропал.

Профессор захотел выяснить длину утраченного хвоста, но продавец тигрокрыса покачал головой и вспомнил только лишь число $$$m = \text{rad}(a \cdot b \cdot c)$$$. Напомним, что $$$\text{rad}(n)$$$ это произведение всех различных простых делителей числа $$$n$$$. Например, $$$\text{rad}(504)$$$ = $$$\text{rad}(2^3 \cdot 3^2 \cdot 7) = 2 \cdot 3 \cdot 7 = 42$$$. А также по определению $$$\text{rad}(1) = 1$$$.

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

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

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

Геном каждого вируса представлен в виде строки, состоящей из строчных латинских букв. Для создания нового супер-вируса У планирует взять два различных вируса с геномами $$$s_1$$$ и $$$s_2$$$ и использовать специальную функцию совместимости:

$$$ L(s_1, s_2) = \text{lcp}(s_1, \text{reverse}(s_2)) + \text{lcp}(\text{reverse}(s_1), s_2) $$$

где $$$\text{lcp}(x, y)$$$ — длина наибольшего общего префикса строк $$$x$$$ и $$$y$$$, а $$$\text{reverse}(s)$$$ — строка $$$s$$$, записанная в обратном порядке.

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