O pequeno W, do departamento de engenharia de software, está fazendo uma prova de desenho técnico, mas trouxe apenas uma régua cujas marcações se apagaram com o tempo e um compasso. Sem alternativa, ele só pode pedir ajuda a você, que tem uma capacidade extraordinária de realizar construções geométricas. Use uma régua sem marcações e um compasso para ajudá-lo a concluir o desenho com rapidez e precisão.

Vamos simplificar o problema. Suponha que o pequeno W já disponha de um sistema de coordenadas e de uma unidade de comprimento. Ele precisa que você construa o comprimento $L_0$, ou seja, obtenha o ponto $(L_0,0)$.

Você pode usar três operações:

1. $line(A,B)$: traçar a reta que passa pelos pontos $A$ e $B$.
2. $circle(O,A,B)$: traçar uma circunferência com centro em $O$ e raio igual à distância entre $A$ e $B$.
3. $intersect(i,j)$: marcar todos os pontos de interseção da figura $i$ com a figura $j$; se houver vários, marcar todos.

Inicialmente, o pequeno W fornece a origem $O(0,0)$, que é o ponto de número $0$. A unidade de comprimento é dada pelo ponto de número $1$, $(1,0)$. Também são fornecidos o eixo $x$ (figura $0$) e o eixo $y$ (figura $1$).

Todos os novos pontos e figuras obtidos pelas operações recebem os números seguintes.

Se o número atual for $n$, o ponto produzido pela operação $intersect$ receberá o número $n+1$.

Se as duas figuras não tiverem interseção, nenhum novo ponto será produzido.

Se houver dois pontos de interseção, o de menor coordenada $x$ (ou, se as coordenadas $x$ forem iguais, o de menor coordenada $y$) receberá o número $n+1$, e o outro receberá $n+2$.

Obtenha o ponto $(L_0,0)$ e indique seu número. Você não precisa obter o valor exato, mas a diferença em relação ao valor exato e o número de operações usadas influenciam sua pontuação.

Entrada

Este é um problema de envio apenas de respostas. Todos os arquivos de entrada, de draw1.in a draw10.in, estão no diretório do problema.

Cada entrada $x_0$ é uma expressão de cálculo em Python. Nela, ** representa a exponenciação: por exemplo, 3 ** 2 representa $3^2$, e 2 ** 0.5 representa $\sqrt{2}$.

Para oferecer maior precisão, os números da expressão são convertidos para o tipo decimal, isto é, números decimais de alta precisão. Por exemplo, Decimal(2) representa $2$.

É garantido que números e símbolos, bem como símbolos consecutivos, estejam separados por um espaço.

O resultado do código Python é o número que deve ser construído.

Observe que o resultado calculado diretamente pelo Python é aproximado, enquanto o valor exigido é o exato: o valor usado para comparar com o resultado do participante é o valor exato.

Também fornecemos o arquivo draw.pdf, que apresenta a expressão de cada entrada em um formato adequado para leitura.

Saída

Para os 10 arquivos de entrada fornecidos, de draw1.in a draw10.in, envie, respectivamente, os arquivos de saída de draw1.out a draw10.out.

A primeira linha do arquivo de saída contém um inteiro $n$, o número de operações. Cada uma das $n$ linhas seguintes contém uma operação. Os formatos das três operações são:

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

Os parâmetros têm o significado descrito no enunciado.

A última linha do arquivo de saída contém um inteiro que indica o número do ponto obtido ao final.

Exemplos

Entrada 1

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

Saída 1

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

Nota

As cinco operações do exemplo têm os seguintes significados:

1. Traçar uma circunferência com centro em $O$ e raio unitário; ela é a figura $2$.
2. Obter as interseções da figura $2$ (circunferência) com o eixo $y$; os pontos são numerados como $2:(0,-1)$ e $3:(0,1)$.
3. Traçar uma circunferência com centro em $O$ e raio igual à distância entre os pontos $1$ e $3$; ela é a figura $3$.
4. Ligar os pontos $(1,0)$ e $(0,1)$; a reta gerada é a figura $4$.
5. Obter as interseções da figura $3$ (circunferência) com o eixo $x$; os pontos são numerados como $4:(-\sqrt{2},0)$ e $5:(\sqrt{2},0)$.

Portanto, o ponto de número $5$ é o ponto que se deseja obter.

Pontuação

Para os 10 arquivos de entrada fornecidos, de draw1.in a draw10.in, fornecemos os respectivos arquivos de parâmetros de pontuação, de draw1.ans a draw10.ans.

Cada arquivo de parâmetros de pontuação tem dez linhas, cada uma com dois números $c_i,x_i$. Se a diferença absoluta entre a abscissa $x$ do ponto final $(x,0)$ e $L_0$ não exceder $10^{-x_i}$, e o número de operações usadas satisfizer $n\le c_i$, você poderá obter $i$ pontos.

A avaliação atribui a maior pontuação entre todas as condições satisfeitas. Se nenhuma condição for satisfeita, a pontuação será $0$.

Como testar sua saída

Fornecemos a ferramenta checker para testar se seu arquivo de saída é aceitável. Para usá-la, abra um terminal e execute o seguinte comando para entrar na pasta do problema:

cd draw

Em seguida, execute:

./checker <case_no>

Aqui, case_no é o número do caso de teste. Por exemplo:

./checker 3

testará se draw3.out é aceitável.

Depois que você executar esse programa, o checker apresentará o resultado do teste com base no arquivo de saída fornecido, incluindo:

1. Encerramento anormal: erro desconhecido.
2. Invalid parameters for checker.: os parâmetros passados ao checker são inválidos.
3. Input/Output file does not exist.: o arquivo de entrada ou de saída não existe.
4. Output invalid: há um erro no arquivo de saída; uma mensagem de erro específica também poderá ser apresentada.
5. Correct! Your answer is n. Your score is s.: a saída é aceitável, foram usadas $n$ operações e a pontuação desse caso de teste é $s$.

Mais funcionalidades

O checker também pode testar arquivos de entrada e saída arbitrários. Para isso, execute no terminal:

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

Aqui, input_file, output_file e ans_file são, respectivamente, os nomes do arquivo de entrada, do arquivo de saída e do arquivo de referência de pontuação.

Por exemplo,

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

testará se draw3.out é aceitável.

A opção -w permite exibir as coordenadas de cada ponto gerado. Cada linha da saída tem o formato:

id x y

Os campos representam, respectivamente, o número do ponto, a coordenada $x$ e a coordenada $y$. O uso é:

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

ou

./checker -w <case_no>

Por exemplo:

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

A opção -i também exibe a saída do participante, facilitando a depuração. O uso é:

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

ou

./checker -i <case_no>

Por exemplo:

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

A opção -e prec permite definir a precisão dos cálculos do checker, em algarismos significativos. Sem essa opção, o valor padrão de $prec$ é $200$. O uso é:

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

ou

./checker -e <prec> <case_no>

Por exemplo:

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

As opções -e prec, -w e -i podem ser usadas juntas, em qualquer ordem. Por exemplo:

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

Dicas

É possível usar Python para obter um valor aproximado da expressão. Para isso, inicie o Python no terminal e digite:

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

Depois, copie a expressão (código Python) do arquivo de entrada para essa janela do terminal e pressione Enter para obter um valor aproximado. O valor 100 do código acima pode ser substituído pela precisão desejada.

Avisos especiais

Se você usar arquivos de entrada gerados por conta própria para depuração, uma instância grande demais poderá causar erros no checker. Se isso acontecer, tente dados menores.

Guarde com cuidado os arquivos de entrada draw*.in, seus arquivos de saída draw*.out e os arquivos de parâmetros de pontuação draw*.ans. Faça cópias de segurança regularmente para evitar exclusões acidentais.