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

Упростим задачу: предположим, что у 小W уже есть система координат и единичный отрезок. Нужно построить длину $L_0$, то есть получить точку $(L_0,0)$.

Можно выполнять три вида операций:

1. $line(A,B)$: провести прямую через точки $A$ и $B$.
2. $circle(O,A,B)$: построить окружность с центром $O$ и радиусом, равным расстоянию между $A$ и $B$.
3. $intersect(i,j)$: отметить все точки пересечения фигур $i$ и $j$; если их несколько, отметить каждую.

Изначально 小W предоставляет начало координат $O(0,0)$ — точку с номером $0$. Единичную длину задаёт точка $1$ с координатами $(1,0)$. Также даны ось $x$ (фигура $0$) и ось $y$ (фигура $1$).

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

Если текущий номер равен $n$, точка, полученная операцией $intersect$, получает номер $n+1$.

Если фигуры не пересекаются, новые точки не появляются.

Если точек пересечения две, точка с меньшей координатой $x$, а при равенстве $x$ — с меньшей координатой $y$, получает номер $n+1$, а другая — номер $n+2$.

Получите точку $(L_0,0)$ и укажите её номер. Точное значение получать необязательно, но количество баллов зависит от отклонения от точного значения и числа использованных операций.

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

Это задача с отправкой только ответов. Все входные файлы draw1.in–draw10.in находятся в каталоге задачи.

Каждое входное значение $x_0$ задано вычисляемым выражением на Python. Оператор ** означает возведение в степень: например, 3 ** 2 означает $3^2$, а 2 ** 0.5 — $\sqrt2$.

Для обеспечения высокой точности числа в выражении преобразованы в тип decimal, то есть десятичные числа высокой точности. Например, Decimal(2) означает $2$.

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

Результат выполнения кода Python — число, которое требуется построить.

Обратите внимание: непосредственное вычисление на Python даёт приближение, тогда как в задаче требуется точное значение. Именно с точным значением сравнивается ваш результат.

Кроме того, предоставлен файл draw.pdf, содержащий выражение для каждого набора данных в удобном для чтения виде.

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

Для десяти заданных входных файлов draw1.in–draw10.in отправьте соответствующие выходные файлы draw1.out–draw10.out.

Первая строка выходного файла содержит целое число $n$ — количество операций. Следующие $n$ строк содержат по одной операции. Форматы трёх операций:

line: L A B
circle: C O A B
intersect: I i j

Значения параметров приведены в условии задачи.

Последняя строка выходного файла содержит целое число — номер полученной итоговой точки.

Примеры

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

Decimal( 2 ) ** ( Decimal( 1 ) / Decimal( 2 ) )

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

5
C 0 0 1
I 1 2
C 0 1 3
L 1 3
I 0 3
5

Примечание

Пять операций в примере имеют следующий смысл:

1. Построить окружность с центром $O$ и единичным радиусом. Она получает номер $2$.
2. Найти пересечения фигуры $2$ (окружности) с осью $y$. Точки пересечения получают номера $2$ с координатами $(0,-1)$ и $3$ с координатами $(0,1)$.
3. Построить окружность с центром $O$ и радиусом, равным расстоянию между точками $1$ и $3$. Она получает номер $3$.
4. Соединить точки $(1,0)$ и $(0,1)$. Полученная прямая имеет номер $4$.
5. Найти пересечения фигуры $3$ (окружности) с осью $x$. Точки пересечения получают номера $4$ с координатами $(-\sqrt2,0)$ и $5$ с координатами $(\sqrt2,0)$.

Таким образом, точка $5$ — искомая итоговая точка.

Подзадачи

Для десяти входных файлов draw1.in–draw10.in предоставлены соответствующие файлы параметров оценивания draw1.ans–draw10.ans.

Файл параметров оценивания содержит десять строк. В строке $i$ находятся два числа $c_i,x_i$: если абсолютная разность абсциссы $x$ полученной точки $(x,0)$ и $L_0$ не превышает $10^{-x_i}$, а число операций $n\le c_i$, можно получить $i$ баллов.

Из всех выполненных условий выбирается наибольшая оценка. Если ни одно условие не выполнено, начисляется 0 баллов.

Проверка выходных файлов

Предоставлен инструмент checker для проверки допустимости ваших выходных файлов. Для его использования сначала откройте терминал и перейдите в каталог задачи командой

cd draw

Затем выполните:

./checker <case_no>

Здесь case_no — номер набора данных. Например,

./checker 3

проверяет допустимость draw3.out.

После запуска checker проверит указанный выходной файл и сообщит результат, в том числе:

1. Аварийное завершение: неизвестная ошибка.
2. Invalid parameters for checker.: недопустимые параметры, переданные checker.
3. Input/Output file does not exist.: входной или выходной файл не существует.
4. Output invalid: выходной файл некорректен; сообщение может содержать подробности ошибки.
5. Correct! Your answer is n. Your score is s.: ответ допустим, использовано $n$ операций, за этот тест начислено $s$ баллов.

Дополнительные возможности

checker также может проверять произвольные входные и выходные файлы. Для этого выполните в терминале:

cd draw
./checker <input_file> <output_file> <ans_file>

Здесь input_file, output_file и ans_file — имена входного файла, выходного файла и файла параметров оценивания соответственно.

Например,

./checker draw3.in draw3.out draw3.ans

проверяет допустимость draw3.out.

Параметр -w позволяет вывести координаты каждой построенной точки. Формат каждой строки:

id x y

Это номер точки, координата $x$ и координата $y$ соответственно. Использование:

./checker -w <input_file> <output_file> <ans_file>

или

./checker -w <case_no>

Например,

./checker -w draw3.in draw3.out draw3.ans

Параметр -i позволяет также выводить ответ участника, что удобно при отладке. Использование:

./checker -i <input_file> <output_file> <ans_file>

или

./checker -i <case_no>

Например,

./checker -i draw3.in draw3.out draw3.ans

Параметр -e prec задаёт точность вычислений checker — число значащих цифр. Без этого параметра значение prec по умолчанию равно 200. Использование:

./checker -e <prec> <input_file> <output_file> <ans_file>

или

./checker -e <prec> <case_no>

Например,

./checker -e 50 draw3.in draw3.out draw3.ans

Параметры -e prec, -w и -i можно указывать одновременно в любом порядке, например:

./checker -w -i -e 50 draw3.in draw3.out draw3.ans

Примечание

Приближённое значение выражения можно получить с помощью Python. Запустите python в терминале, затем введите:

from math import *
from decimal import *
getcontext().prec = 100

После этого скопируйте выражение (код Python) из входного файла в это окно терминала и нажмите Enter, чтобы получить приближённое значение. Число 100 в приведённом коде можно заменить нужной точностью.

Особое примечание

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

Бережно храните входные файлы draw*.in, свои выходные файлы draw*.out и файлы параметров оценивания draw*.ans; своевременно делайте резервные копии, чтобы избежать случайного удаления.