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

Число $$$x$$$ называется $$$k$$$-страшным, если количество множителей в его разложении на простые числа равно $$$k$$$. Пока что, возможно, вам не кажется страшным такое определение, но вы еще не видели, в чем заключается вопрос задачи!

Требуется ответить на $$$q$$$ запросов, каждый из которых описывается тремя целыми числами $$$l$$$, $$$r$$$ и $$$k$$$. Ответом на запрос является количество $$$k$$$-страшных чисел, лежащих на отрезке от $$$l$$$ до $$$r$$$. Если вас все еще не пугает эта задача, ответьте на все $$$q$$$ запросов.

You are given a box with an interesting device on its lid, represented as a plane with the following elements:

1. A circle $$$C$$$ with center at point $$$(x_0, y_0)$$$ and radius $$$r$$$.
2. A line $$$L$$$ given by equation $$$ax + by + c = 0$$$.
3. Two marked points with coordinates $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$.

You can rotate the circle around its center, and the marked points that are located on it will rotate along with it.

Determine whether it is possible to rotate the circle so that the line $$$L$$$ and the line passing through the marked points are parallel.

Как известно, во всех фильмах ужасов кому-то рано или поздно приходит в голову гениальная мысль разделиться и исследовать страшное и подозрительное место небольшими группами.

В этот раз компания из $$$n + 2$$$ человек, исследуя заброшенную хижину в темном лесу, решила разделиться на две группы. В компании есть два лидера, имеющих степень безрассудства $$$a_1$$$ и $$$a_2$$$, соответственно. Также для исследования доступны два помещения, с подозрительностью, равной $$$b_1$$$ и $$$b_2$$$, соответственно.

В каждой группе должен быть ровно один из двух лидеров, при чем если группа $$$i$$$-го лидера из $$$k_i$$$ человек (не считая лидера) идет исследовать $$$j$$$-е помещение, опасность такого исследования равна $$$D = a_i \cdot k_i \cdot b_j$$$.

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

Доктор Франкенштейн решил заняться самым интересным занятием на Земле — смешиванием колб с реагентами.

Каждый реагент описывается одним действительным числом — коэффицентом. От этого числа зависит какому классу принадлежит этот реагент. Существуют четыре класса:

1. $$$\mathbb{N}$$$: если коэффицент является натуральным числом, т.е. число, возникающее естественным образом при счёте (например, $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ и так далее).
2. $$$\mathbb{Z}$$$: если коэффицент — целое число. Целые числа включают в себя натуральные числа, числа, противоположные натуральным, и $$$0$$$. (например, $$$5$$$, $$$-1$$$, $$$0$$$)
3. $$$\mathbb{Q}$$$: если коэффицент — рациональное число, или же число, которые можно представить в виде дроби $$$\frac{m}{n}$$$, где $$$m$$$ и $$$n$$$ — целые числа (например, $$$1$$$, $$$2.7$$$, $$$4.(3)$$$)
4. $$$\mathbb{R}$$$: если коэффицент — действительное число. Действительные числа включают в себя и те, которые возможно представить в виде дроби, и те, которые невозможно. (например, $$$\pi$$$, $$$\sqrt{2}$$$)

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

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

Теперь задача — Франкенштейн взял два реагента и смешал их. Дана реакция и классы, которым принадлежат реагенты. Определить класс, которому принадлежит результат реакции. Считайте, что надо определить класс в общем случае (так, например, существуют конкретные примеры вида $$$\sqrt{2} \cdot \sqrt{2} = 2 \in \mathbb{N}$$$, но в общем случае произведение двух вещественных чисел всегда будет вещественным, и не всегда хотя бы рациональным).

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

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

Как известно, на качество истории влияют не только слова, содержащиеся в ней, но и символы, содержащиеся в этих словах.

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

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

Ловушка представляет из себя матрицу размера $$$n \times m$$$. Некоторые клетки матрицы пусты, а в некоторых нарисованы стрелочки в соседние по стороне или углу клетки. Каждую секунду все стрелочки поворачиваются на $$$45^\circ$$$ градусов по часовой стрелке.

Обозначим направление вверх как $$$0$$$, вправо-вверх как $$$1$$$ и так далее, пустую клетку обозначим точкой. Вы находитесь в клетке с координатами $$$(a_x, a_y)$$$, и,

• находясь в пустой клетке, можете либо секунду подождать в ней, либо за секунду переместиться в соседнюю по стороне клетку;
• попадая на клетку со стрелочкой, вы моментально (за $$$0$$$ секунд) переноситесь туда, куда она указывает.

Когда вы переходите на клетку со стрелкой, она уже успевает повернуться за ту секунду, что вы шагали. Ваша задача — выбраться из ловушки как можно скорее. Попадите из стартовой точки $$$(a_x, a_y)$$$ в конечную $$$(b_x, b_y)$$$ за минимальное количество секунд, либо определите, что это невозможно, и смиритесь с тем, что вам не выбраться.

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

В один не очень прекрасный вечер два друга нашли уиджа на чердаке, и решили с ней поиграть. Для этого они расчертили на ней клетчатое поле $$$n \times m$$$ и приклеили указатель к левой верхней клетке доски.

Затем друзья по очереди делали ходы. Каждый ход заключается в разрезании доски по горизонтали или по вертикали по границам клеток, после чего та часть, на которой приклеен указатель, остается в игре, а вторая половина выкидывается. Тот, кто не может сделать ход, то есть держит перед своим ходом доску размера $$$1 \times 1$$$, проигрывает.

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

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

В рамках взаимодействия с интерактором первым действием ваша программа должна вывести число «1» (без кавычек), если вы выбираете ходить первым, и «2», если вторым.

После чего в соответствии с выбранной очередностью ваша программа и интерактор совершают ходы. Каждый ход описывается парой из символа «R» или «C», обозначающего разрезание по горизонтали или по вертикали, соответственно, и числа $$$t$$$, обозначающего номер строки/столбца, после которой/которого делается разрез. Например, если размеры оставшейся доски равны $$$13 \times 17$$$, ход «R 5» означает, что доска разрезается по горизонтали на части размеров $$$5 \times 17$$$ и $$$8 \times 17$$$. Строки и столбцы нумеруются с единицы слева-направо и сверху-вниз, начиная от края оставшейся в игре части доски.

Если ваша программа выводит некорректный ход, интерактор выводит в ответ «FAIL» и завершается с вердиктом Wrong Answer. Считав слово «FAIL», ваша программа должна также завершиться во избежание вердиктов Time Limit Exceeded и Idleness Limit Exceeded.

Если интерактор не может сделать ход, он выводит «YOU WIN» и завершается с вердиктом OK, после чего ваша программа также должна завершиться с нулевым кодом возврата. Обратите внимание, что интерактор не завершается, если после его хода у вашей программы не остается возможности походить — чтобы в таком случае получить вердикт Wrong Answer, следует вывести произвольный некорректный ход и завершиться.

После каждой выведенной строки необходимо сбрасывать буфер потока вывода (sys.stdout.flush() в Python, System.out.flush() в Java, cout.flush() в C++).

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

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

Монстры, конечно, знают друг друга, а вот обычные люди не знают, кто есть кто.

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

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