Это интерактивная задача.
Вы любите физику? Впрочем, это неважно, мы ее обожаем! В этой задаче вам предстоит столкнуться с резисторами, а также с различными способами их соединения.
Напомним, что основной характеристикой резистора является его сопротивление. Резисторы можно объединять друг с другом в цепь, после чего общее сопротивление цепи вычисляется по общеизвестным формулам. В данной задаче мы будем рассматривать два типа соединения резисторов: последовательное и параллельное.
Пусть у нас имеются резисторы с сопротивлениями $$$R_1, R_2, \ldots, R_N$$$. Тогда при их последовательном соединении общее сопротивление полученной цепи будет равно: $$$$$$R = R_1 + R_2 + \ldots + R_N$$$$$$
Такая цепь изображена на рисунке ниже:
При параллельном соединении резисторов общее сопротивление цепи вычисляется по формуле: $$$$$$R = \dfrac{1}{\dfrac{1}{R_1} + \dfrac{1}{R_2} + \ldots + \dfrac{1}{R_N}}$$$$$$
Такая цепь изображена на рисунке ниже:
Представим теперь, что у нас имеется специализированный компьютер для расчетов, связанных с электрическими цепями. У этого компьютера есть $$$128$$$ регистров, в каждом из которых можно сохранить ровно одну электрическую цепь, состоящую только из резисторов. Регистры пронумерованы числами от $$$0$$$ до $$$127$$$. Изначально в регистре с номером $$$0$$$ записана элементарная цепь: один резистор с сопротивлением $$$R_0 = 1$$$. Все остальные регистры изначально пусты.
Перед началом работы вы можете заполнить некоторое количество регистров с номерами от $$$1$$$ до $$$127$$$ корректными электрическими цепями. Электрическая цепь является корректной для записи в регистр с номером $$$i$$$, если:
- Для конструирования данной цепи используются только операции последовательного и параллельного соединения некоторых других цепей;
- Все используемые при соединении цепи были получены в регистрах с номерами, меньшими, чем $$$i$$$ (включая регистр $$$0$$$).
Для удобства обозначим общее сопротивление цепи, полученной в $$$i$$$-м регистре, как $$$R_i$$$.
После того, как вы заполнили необходимое вам количество регистров, к вам будут поступать запросы. Входным параметром каждого запроса является значение сопротивления $$$R = \dfrac{x}{y}$$$. В качестве ответа на запрос вы должны сконструировать электрическую цепь, общее сопротивление которой в точности равно $$$R$$$. Для конструирования цепи вы можете использовать последовательные и параллельные соединения записанных в регистрах цепей. Более того, количество использованных цепей, сохраненных в регистрах, не должно быть слишком большим. Сможете ли вы справиться с поставленной задачей?
Для начала вы должны вывести целое число $$$t$$$ — количество регистров, которые вы собираетесь использовать ($$$1 \leq t \leq 128$$$). Это означает, что вы сможете воспользоваться регистрами с номерами от $$$0$$$ до $$$t - 1$$$.
После этого выведите $$$t$$$ строк, в каждой из которых выведите описание сконструированной цепи. Цепь, выведенная в $$$i + 1$$$-й строке, будет сохранена в регистр с номером $$$i$$$, после чего данную цепь можно будет использовать для построения новых цепей. Сопротивление данной цепи будет обозначено как $$$R_i$$$.
Описание каждой цепи должно быть задано в следующей грамматике (для лучшего понимания смотрите примеры):
$$$\langle circuit \rangle~::=$$$ «R$$$i$$$»$$$~|~\langle series \rangle~|~\langle parallel \rangle$$$
$$$\langle series \rangle~::=$$$ «S(» $$$\langle circuit \rangle$$$ «,» $$$\langle circuit \rangle$$$ «)»
$$$\langle parallel \rangle~::=$$$ «P(» $$$\langle circuit \rangle$$$ «,» $$$\langle circuit \rangle$$$ «)»
При этом при построении цепи, сохраняемой в регистр с номером $$$i$$$, разрешается использовать $$$R_j$$$ только в случае $$$j \lt i$$$.
После этого вы должны считать число $$$q$$$ ($$$1 \leq q \leq 1\,000$$$) — количество запросов.
Для ответа на каждый запрос сначала считайте два целых числа: $$$x$$$ и $$$y$$$ ($$$1 \leq x \leq 10^{18}$$$, $$$1 \leq y \leq 10^{18}$$$). После этого выведите описание построенной цепи в описанной выше грамматике. Общее сопротивление полученной цепи должно быть равно $$$\dfrac{x}{y}$$$. При описании цепи разрешается использовать $$$R_i$$$ для всех $$$0 \leq i \lt t$$$.
Для всех построенных цепей, включая описание регистров, должны быть выполнены следующие ограничения. Описание цепи должно быть записано на одной строке. При описании цепи разрешается использовать сколько угодно пробелов, однако нельзя ставить пробелы между символом $$$R$$$ и номером регистра. Количество использованных $$$R_i$$$ в описании цепи не должно превышать $$$90$$$. Длина полученного выражения не должна превышать $$$10\,000$$$ символов.
Не забудьте сделать операцию flush после каждого ответа на запрос, а также после вывода информации о регистрах в начале общения с интерактором.
В случае несоблюдения протокола взаимодействия вы можете получить любой вердикт!
3 2 5 6 3 17 4
4 S(R0, R0) P(R0, R0, R0) S(R1, R1) P(R1, R1, R1, R1, R1) R1 S(R3, P(R0, R0, P(R0, R0)))
Рассмотрим пример. В начале мы сообщаем, что будем использовать только четыре регистра: $$$R_0, R_1, R_2$$$ и $$$R_3$$$. Изначально $$$R_0 = 1$$$. Далее мы задаем значения еще трех регистров.
В качестве $$$R_1$$$ берется последовательное соединение двух цепей $$$R_0$$$. Получаем общее сопротивление $$$R_1 = R_0 + R_0 = 1 + 1 = 2$$$.
В качестве $$$R_2$$$ берется параллельное соединение трех цепей $$$R_0$$$. Получаем общее сопротивление $$$R_2 = \dfrac{1}{\dfrac{1}{R_0} + \dfrac{1}{R_0} + \dfrac{1}{R_0}} = \dfrac{1}{\dfrac{1}{1} + \dfrac{1}{1} + \dfrac{1}{1}} = \dfrac{1}{3}$$$.
В качестве $$$R_3$$$ берется последовательное соединение двух цепей $$$R_1$$$. Получаем сопротивление $$$R_3 = R_1 + R_1 = 2 + 2 = 4$$$.
Далее интерактор сообщает нам три запроса.
В первом запросе нужно построить сопротивление $$$\dfrac{2}{5}$$$. Для этого мы решили соединить параллельно пять схем $$$R_1$$$. Получается, что сопротивление равно: $$$\dfrac{1}{\dfrac{1}{R_1} + \dfrac{1}{R_1} + \dfrac{1}{R_1} + \dfrac{1}{R_1} + \dfrac{1}{R_1}} = \dfrac{1}{\dfrac{1}{2} + \dfrac{1}{2} + \dfrac{1}{2} + \dfrac{1}{2} + \dfrac{1}{2}} = \dfrac{1}{\dfrac{5}{2}} = \dfrac{2}{5}$$$.
Во втором запросе требуется получить сопротивление $$$\dfrac{6}{3} = 2$$$. Для этого можно просто воспользоваться схемой $$$R_1$$$.
В третьем запросе необходимо построить сопротивление $$$\dfrac{17}{4}$$$. Для этого соединим последовательно схему $$$R_3$$$ с четырьмя параллельно соединенными схемами $$$R_0$$$. Получаем сопротивление $$$R_3 + \dfrac{1}{\dfrac{1}{R_0} + \dfrac{1}{R_0} + \dfrac{1}{R_0} + \dfrac{1}{R_0}} = 4 + \dfrac{1}{\dfrac{1}{1} + \dfrac{1}{1} + \dfrac{1}{1} + \dfrac{1}{1}} = 4 + \dfrac{1}{4} = \dfrac{17}{4}$$$.
