SPOJ2007

Sphere Online Judge Open Contest 2007 の問題の日本語訳です。

SUD

Input

Output

Score

Example

PCV2

Input

Output

Score

Example

ELC

Input

Output

Score

Example

EMP

Input

Output

Score

Example

CATM

Input

最初の行は行の数n・列の数mを表す(ともに100以下)。 2行目はテストケースの数kを表す(10以下)。

Output

ねずみが逃げられるならYES、さもなくばNO

Example

Input:
5 3
3
2 2 1 1 3 3
2 3 1 3 5 2
3 2 1 2 4 3

Output:
NO
YES
YES

Limits

• 1sec
• 50,000Bytes

NGM

NikiforとTrofimが以下のようなゲームを行う。

• 最初の数を一つ決める
• 順番に数を減らしていって、0にした方が勝ち (Nikiforが先手)
• いくつ減らすかは1〜9の間で自由に決めてよい

2人がベストを尽くしたとき、どちらが勝つかを判断してほしい。

Input

最初の数(2,000,000,000より小さい)。

Output

先手が勝つときは1を、さもなくば2を表示する。先手が勝つときは、2行目に 先手が最初に引く数を出力する。いくつも候補がある場合はそのうちの一つを 出力すればよい。

Example

Input:
14

Output:
1
4

Limits

• 1sec
• 50,000Bytes

GEOM

正方形ABCDがあって、点A,B,C,Dは時計回りに並んでいる。さらに点A,B,C,Dと 一致しない点Pがある。

点Aを通りBPに垂直な直線a、点Bを通りCPに垂直な直線b、点Cを通りDPに垂直な直線c、 点Dを通りAPに垂直な直線dを引く。直線a,b,c,dは一点で交わるだろうか？ (それは点Pの位置によって決まる)。 交わるかどうかと、交わるならその位置を求めるプログラムを書け。

Input

最初の行は正方形の中心(対角線の交わる点)の座標を示す。 2行目は正方形の一辺の長さを示す。 3行目は点Pの座標を示す。 各数字の絶対値は100を超えない。

Output

交点があるならYESを出力し、次の行にその座標を出力する(小数点以下第1位まで)。 ないならNOを出力する。

Example

Input:
10 10
20
5 12

Output:
YES
8.0 5.0

Limits

• 1sec
• 50,000Bytes

FIRM

市場にn人のディーラーがいる。彼らはそれぞれ独自の品物を持っている (同じ品物を持っているディーラーはいない)。また、彼らは市場に存在する別の 品物を買いたいと思っている。これはちょっと奇妙なことだが、 全ての品物について、ちょうど１人だけその品物を欲しがっているディーラーがいる。

詐欺行為を防ぐため、2人でペアになっての「交換」しかこの市場では許されていない。 加えて、各ディーラーは1日に1回の交換しか行えない。

あなたの仕事は、全てのディーラーが彼の欲しい品物を手に入れるまで最低何日 かかるかを計算することである。また、どのような取引を行えばいいかも 求めてほしい。

Input

最初の行はディーラーの数(n <= 5000)を示す。 2行目にはディーラーの欲しい品物をあらわすn個の数が並ぶ。 例えばi番目にjという数があれば、ディーラーiの欲しい品物はディーラーjが最初に 持っていることを意味する。

Output

最初に取引に要する最小日数(m)を出力し、次のm行に各日の取引の様子 (取引数およびディーラー番号を-で繋いだもの)を出力する。 取引方法が複数ある場合は、それらのうちのどれを出力してもよい。

Example

Input:
7
2 1 3 5 6 7 4

Output:
2
3 1-2 4-5 7-6
1 5-7

DIP

SQRT2

√2をできるだけ長く計算する。 タイムリミットは20秒、ソースコードは4096バイトまで。

Input

なし

Output

√2の少数表現 (数字の数は最大2,000,000個まで)

Score

√2に一致しない最初の数字までの長さ

例

1.41421356237309504

この場合19点が与えられる。