ソフトウェア工学科の小 W は工学製図の試験会場にいますが、長年の使用で目盛りが消えてしまった定規とコンパスしか持ってきていません。困り果てた彼は、驚異的な幾何作図能力を持つあなたに助けを求めるしかありません。目盛りのない定規とコンパスを使って、小 W がすばやく正確に製図を完成できるよう手伝ってください。

問題を単純化しましょう。小 W はすでに座標系と単位長さを得ており、あなたには定規とコンパスで長さ $L_0$、すなわち点 $(L_0,0)$ を作図してほしいと考えています。

次の3種類の操作を使えます。

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$ が付けられます。

2つの図形に交点がなければ、新しい点は生じません。

交点が2つある場合、$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$ を表します。

数と記号の間、および記号同士の間には、必ず1つの空白が入っています。

Python コードの出力が、作図すべき数です。

Python で直接計算して得られる結果は近似値ですが、実際に求められるのは正確な値です。すなわち、競技者の得た結果と比較される値は正確な値です。

また、各データの式を読みやすい形で示したファイル draw.pdf も用意しています。

出力

与えられた10個の入力ファイル draw1.in～draw10.in に対し、それぞれの出力ファイル draw1.out～draw10.out を提出してください。

出力ファイルの1行目には操作数を表す整数 $n$ を出力します。続く $n$ 行には、1行につき1つの操作を出力します。3種類の操作の形式は次のとおりです。

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

注記

例の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$ が最終的に求める点です。

小課題

与えられた10個の入力ファイル draw1.in～draw10.in に対し、それぞれ採点パラメータファイル draw1.ans～draw10.ans を用意しています。

採点パラメータファイルは10行からなり、各行に2つの数 $c_i,x_i$ が書かれています。最終的に得た点 $(x,0)$ の $x$ 座標と $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 を適切に保存し、誤って削除しないよう、こまめにバックアップしてください。