小 W z wydziału inżynierii oprogramowania jest na egzaminie z rysunku technicznego, lecz przyniósł tylko linijkę, której podziałka starła się z upływem lat, i cyrkiel. Bezradny prosi o pomoc ciebie, osobę o niezwykłych umiejętnościach konstrukcji geometrycznych. Pomóż 小 W szybko i dokładnie wykonać rysunek za pomocą linijki bez podziałki i cyrkla.

Uprośćmy problem: załóżmy, że 小 W ma już układ współrzędnych i odcinek jednostkowy. Musisz skonstruować długość $L_0$, czyli otrzymać punkt $(L_0,0)$.

Możesz wykonywać trzy rodzaje operacji:

1. $line(A,B)$: narysuj prostą przechodzącą przez punkty $A$ i $B$.
2. $circle(O,A,B)$: narysuj okrąg o środku $O$ i promieniu równym odległości $AB$.
3. $intersect(i,j)$: zaznacz wszystkie punkty przecięcia figury $i$ z figurą $j$; jeśli jest ich kilka, zaznacz wszystkie.

Początkowo 小 W udostępnia początek układu $O(0,0)$ jako punkt numer $0$. Długość jednostkową wyznacza punkt numer $1$ o współrzędnych $(1,0)$. Dostępne są też oś $x$ (figura numer $0$) i oś $y$ (figura numer $1$).

Wszystkie nowe punkty i figury otrzymane podczas operacji dostają kolejne numery.

Jeśli bieżący numer to $n$, punkt utworzony przez operację $intersect$ otrzymuje numer $n+1$.

Jeśli figury nie mają punktu wspólnego, nowy punkt nie powstaje.

Jeśli są dwa punkty przecięcia, punkt o mniejszej współrzędnej $x$ (a przy równych $x$ — mniejszej $y$) otrzymuje numer $n+1$, a drugi numer $n+2$.

Otrzymaj punkt $(L_0,0)$ i podaj jego numer. Wynik nie musi być dokładny, ale różnica względem wartości dokładnej oraz liczba wykonanych operacji wpływają na punktację.

Wejście

To zadanie z przesyłaniem samych odpowiedzi. Wszystkie pliki wejściowe draw1.in–draw10.in znajdują się w katalogu zadania.

Każda dana wejściowa $x_0$ jest wyrażeniem obliczeniowym w Pythonie. Operator ** oznacza potęgowanie: na przykład 3 ** 2 oznacza $3^2$, a 2 ** 0.5 oznacza $\sqrt2$.

Aby zapewnić wysoką precyzję, liczby w wyrażeniu są przekształcone do typu decimal, czyli liczb dziesiętnych wysokiej precyzji. Na przykład Decimal(2) oznacza $2$.

Liczby i symbole oraz kolejne symbole są w wejściu rozdzielane pojedynczą spacją.

Wynik kodu Pythona jest liczbą, którą należy skonstruować.

Uwaga: wynik obliczony bezpośrednio w Pythonie jest przybliżeniem, natomiast wymagana jest wartość dokładna; to z nią porównywany będzie twój wynik.

Udostępniamy też plik draw.pdf z wyrażeniami dla wszystkich danych w postaci wygodnej do czytania.

Wyjście

Dla dziesięciu plików wejściowych draw1.in–draw10.in należy przesłać odpowiednio pliki wyjściowe draw1.out–draw10.out.

Pierwszy wiersz pliku wyjściowego zawiera liczbę całkowitą $n$, oznaczającą liczbę operacji. Kolejnych $n$ wierszy zawiera po jednej operacji. Formaty trzech operacji to:

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

Znaczenie parametrów podano w treści zadania.

Ostatni wiersz pliku wyjściowego zawiera liczbę całkowitą oznaczającą numer ostatecznie otrzymanego punktu.

Przykład

Wejście 1

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

Wyjście 1

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

Uwagi

Pięć operacji w przykładzie oznacza:

1. Narysuj okrąg o środku $O$ i promieniu jednostkowym. Jest to figura numer $2$.
2. Wyznacz przecięcia figury $2$ (okręgu) z osią $y$: punkt $2$ ma współrzędne $(0,-1)$, a punkt $3$ — $(0,1)$.
3. Narysuj okrąg o środku $O$ i promieniu równym odległości punktów $1$ i $3$. Jest to figura numer $3$.
4. Połącz punkty $(1,0)$ i $(0,1)$ prostą, która otrzymuje numer $4$.
5. Wyznacz przecięcia figury $3$ (okręgu) z osią $x$: punkt $4$ ma współrzędne $(-\sqrt2,0)$, a punkt $5$ — $(\sqrt2,0)$.

Zatem punkt numer $5$ jest szukanym punktem.

Podzadania

Dla dziesięciu plików wejściowych draw1.in–draw10.in udostępniamy odpowiednio pliki parametrów punktacji draw1.ans–draw10.ans.

Plik parametrów ma dziesięć wierszy, każdy z dwiema liczbami $c_i,x_i$. Jeśli różnica bezwzględna między współrzędną $x$ ostatecznego punktu $(x,0)$ a $L_0$ nie przekracza $10^{-x_i}$ i liczba operacji spełnia $n\le c_i$, otrzymasz $i$ punktów.

Ocena jest największą liczbą punktów spośród spełnionych warunków. Jeśli żaden warunek nie jest spełniony, otrzymasz $0$ punktów.

Testowanie wyjścia

Udostępniamy narzędzie checker, które sprawdza, czy twój plik wyjściowy jest akceptowalny. Najpierw otwórz terminal i przejdź do katalogu zadania:

cd draw

Następnie wykonaj:

./checker <case_no>

Tutaj case_no jest numerem testu. Na przykład:

./checker 3

sprawdzi, czy draw3.out jest akceptowalny.

Po uruchomieniu checker poda wynik sprawdzenia twojego pliku wyjściowego. Możliwe wyniki to:

1. Nieprawidłowe zakończenie: nieznany błąd.
2. Invalid parameters for checker.: przekazano nieprawidłowe argumenty.
3. Input/Output file does not exist.: plik wejściowy lub wyjściowy nie istnieje.
4. Output invalid: plik wyjściowy jest niepoprawny; komunikat może zawierać szczegółowy opis błędu.
5. Correct! Your answer is n. Your score is s.: wyjście jest akceptowalne, użyto $n$ operacji, a wynik za test to $s$ punktów.

Dodatkowe funkcje

checker może też sprawdzać dowolne pliki wejściowe i wyjściowe. W tym celu wykonaj w terminalu:

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

Tutaj input_file, output_file i ans_file są nazwami odpowiednio pliku wejściowego, wyjściowego i parametrów punktacji.

Na przykład:

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

sprawdzi, czy draw3.out jest akceptowalny.

Opcja -w wypisuje współrzędne każdego otrzymanego punktu. Każdy wiersz ma format:

id x y

Pola oznaczają odpowiednio numer punktu oraz współrzędne $x$ i $y$. Sposób użycia:

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

lub:

./checker -w <case_no>

Na przykład:

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

Opcja -i dodatkowo wypisuje wyjście uczestnika, co ułatwia debugowanie. Sposób użycia:

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

lub:

./checker -i <case_no>

Na przykład:

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

Opcja -e prec ustala precyzję obliczeń checker (liczbę cyfr znaczących). Bez tej opcji domyślna wartość $prec$ wynosi $200$. Sposób użycia:

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

lub:

./checker -e <prec> <case_no>

Na przykład:

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

Opcje -e prec, -w i -i można łączyć w dowolnej kolejności, na przykład:

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

Wskazówki

Python pozwala obliczyć przybliżoną wartość wyrażenia. Uruchom python w terminalu, a następnie wpisz:

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

Potem skopiuj wyrażenie z pliku wejściowego (kod Pythona) do terminalu i naciśnij Enter, aby uzyskać przybliżoną wartość. Liczbę 100 w powyższym kodzie możesz zastąpić żądaną precyzją.

Szczególne wskazówki

Jeśli do debugowania używasz własnych plików wejściowych, zbyt duży rozmiar danych może spowodować błąd checker. W takim przypadku spróbuj mniejszych danych.

Dbaj o pliki wejściowe draw.in, swoje pliki wyjściowe draw.out i pliki parametrów draw*.ans. Rób na bieżąco kopie zapasowe, aby uniknąć przypadkowego usunięcia.