A - ∴ (Therefore)

### 問題文

いろはちゃんは、人気の日本製ゲーム「ÅtCoder」で遊びたい猫のすぬけ君のために日本語を教えることにしました。

• N1 の位が 2, 4, 5, 7, 9 のとき hon
• N1 の位が 0, 1, 6, 8 のとき pon
• N1 の位が 3 のとき bon

です。

N が与えられるので、「N 本」と言うときの「本」の読みを出力してください。

• N999 以下の正の整数

### 入力

N


### 入力例 1

16


### 出力例 1

pon


161 の位は 6 なので、「本」の読みは pon です。

### 入力例 2

2


### 出力例 2

hon


### 入力例 3

183


### 出力例 3

bon


Score: 100 points

### Problem Statement

The cat Snuke wants to play a popular Japanese game called ÅtCoder, so Iroha has decided to teach him Japanese.

When counting pencils in Japanese, the counter word "本" follows the number. The pronunciation of this word varies depending on the number. Specifically, the pronunciation of "本" in the phrase "N 本" for a positive integer N not exceeding 999 is as follows:

• hon when the digit in the one's place of N is 2, 4, 5, 7, or 9;
• pon when the digit in the one's place of N is 0, 1, 6 or 8;
• bon when the digit in the one's place of N is 3.

Given N, print the pronunciation of "本" in the phrase "N 本".

### Constraints

• N is a positive integer not exceeding 999.

### Input

Input is given from Standard Input in the following format:

N


### Sample Input 1

16


### Sample Output 1

pon


The digit in the one's place of 16 is 6, so the "本" in "16 本" is pronounced pon.

### Sample Input 2

2


### Sample Output 2

hon


### Sample Input 3

183


### Sample Output 3

bon

B - ... (Triple Dots)

### 問題文

S の長さが K 以下であれば、S をそのまま出力してください。

S の長さが K を上回っているならば、先頭 K 文字だけを切り出し、末尾に ... を付加して出力してください。

### 制約

• K1 以上 100 以下の整数
• S は英小文字からなる文字列
• S の長さは 1 以上 100 以下

### 入力

K
S


### 入力例 1

7
nikoandsolstice


### 出力例 1

nikoand...


nikoandsolstice の長さは 15 であり、K=7 を上回っています。

この先頭 7 文字を切り出して末尾に ... を付加した文字列 nikoand... を出力します。

### 入力例 2

40
ferelibenterhominesidquodvoluntcredunt


### 出力例 2

ferelibenterhominesidquodvoluntcredunt


ガイウス・ユリウス・カエサルの名言です。

Score: 200 points

### Problem Statement

We have a string S consisting of lowercase English letters.

If the length of S is at most K, print S without change.

If the length of S exceeds K, extract the first K characters in S, append ... to the end of them, and print the result.

### Constraints

• K is an integer between 1 and 100 (inclusive).
• S is a string consisting of lowercase English letters.
• The length of S is between 1 and 100 (inclusive).

### Input

Input is given from Standard Input in the following format:

K
S


### Output

Print a string as stated in Problem Statement.

### Sample Input 1

7
nikoandsolstice


### Sample Output 1

nikoand...


nikoandsolstice has a length of 15, which exceeds K=7.

We should extract the first 7 characters in this string, append ... to the end of them, and print the result nikoand....

### Sample Input 2

40
ferelibenterhominesidquodvoluntcredunt


### Sample Output 2

ferelibenterhominesidquodvoluntcredunt


The famous quote from Gaius Julius Caesar.

C - : (Colon)

### 問題文

0 時ちょうどに時針と分針は重なっていました。ちょうど HM 分になったとき、2 本の針の固定されていない方の端点は何センチメートル離れているでしょうか。

### 制約

• 入力はすべて整数
• 1 \leq A, B \leq 1000
• 0 \leq H \leq 11
• 0 \leq M \leq 59

### 入力

A B H M


### 入力例 1

3 4 9 0


### 出力例 1

5.00000000000000000000


2 本の針は図のようになるので、答えは 5 センチメートルです。

### 入力例 2

3 4 10 40


### 出力例 2

4.56425719433005567605


2 本の針は図のようになります。各針は常に一定の角速度で回ることに注意してください。

Score: 300 points

### Problem Statement

Consider an analog clock whose hour and minute hands are A and B centimeters long, respectively.

An endpoint of the hour hand and an endpoint of the minute hand are fixed at the same point, around which each hand rotates clockwise at constant angular velocity. It takes the hour and minute hands 12 hours and 1 hour to make one full rotation, respectively.

At 0 o'clock, the two hands overlap each other. H hours and M minutes later, what is the distance in centimeters between the unfixed endpoints of the hands?

### Constraints

• All values in input are integers.
• 1 \leq A, B \leq 1000
• 0 \leq H \leq 11
• 0 \leq M \leq 59

### Input

Input is given from Standard Input in the following format:

A B H M


### Output

Print the answer without units. Your output will be accepted when its absolute or relative error from the correct value is at most 10^{-9}.

### Sample Input 1

3 4 9 0


### Sample Output 1

5.00000000000000000000


The two hands will be in the positions shown in the figure below, so the answer is 5 centimeters.

### Sample Input 2

3 4 10 40


### Sample Output 2

4.56425719433005567605


The two hands will be in the positions shown in the figure below. Note that each hand always rotates at constant angular velocity.

D - .. (Double Dots)

### 問題文

あるところに、洞窟があります。

• その部屋から出発し、「いまいる部屋にある道しるべを見て、それが指す部屋に移動する」ことを繰り返すと、部屋 1 に最小の移動回数でたどり着く。

### 制約

• 入力はすべて整数
• 2 \leq N \leq 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
• A_i \neq B_i\ (1 \leq i \leq M)
• どの 2 部屋間も、通路をいくつか通って行き来できる

### 入力

N M
A_1 B_1
:
A_M B_M


### 入力例 1

4 4
1 2
2 3
3 4
4 2


### 出力例 1

Yes
1
2
2


• 部屋 2 から出発した場合 (2) \to 11 回移動することになり、これが最小です。
• 部屋 3 から出発した場合 (3) \to 2 \to 12 回移動することになり、これが最小です。
• 部屋 4 から出発した場合 (4) \to 2 \to 12 回移動することになり、これが最小です。

したがって、出力例のように道しるべを置けば目標を達成できます。

### 入力例 2

6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6


### 出力例 2

Yes
6
5
5
1
1


Score: 400 points

### Problem Statement

There is a cave.

The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.

It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.

Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.

• If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.

Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

### Constraints

• All values in input are integers.
• 2 \leq N \leq 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
• A_i \neq B_i\ (1 \leq i \leq M)
• One can travel between any two rooms by traversing passages.

### Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M


### Output

If there is no way to place signposts satisfying the objective, print No.

Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

### Sample Input 1

4 4
1 2
2 3
3 4
4 2


### Sample Output 1

Yes
1
2
2


If we place the signposts as described in the sample output, the following happens:

• Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.
• Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.
• Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.

Thus, the objective is satisfied.

### Sample Input 2

6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6


### Sample Output 2

Yes
6
5
5
1
1


If there are multiple solutions, any of them will be accepted.

E - ∙ (Bullet)

### 問題文

N 匹のイワシが釣れました。i 匹目のイワシの美味しさは A_i、香り高さは B_i です。

この中から 1 匹以上のイワシを選んで同じクーラーボックスに入れますが、互いに仲が悪い 2 匹を同時に選ぶことはできません。

i 匹目と j (\neq i) 匹目のイワシは、A_i \cdot A_j + B_i \cdot B_j = 0 を満たすとき(また、その時に限り)仲が悪いです。

イワシの選び方は何通りあるでしょう？答えは非常に大きくなる可能性があるので、1000000007 で割ったあまりを出力してください。

### 制約

• 入力はすべて整数
• 1 \leq N \leq 2 \times 10^5
• -10^{18} \leq A_i, B_i \leq 10^{18}

### 入力

N
A_1 B_1
:
A_N B_N


### 入力例 1

3
1 2
-1 1
2 -1


### 出力例 1

5


• 1 匹目
• 1, 2 匹目
• 2 匹目
• 2, 3 匹目
• 3 匹目

### 入力例 2

10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4


### 出力例 2

479


Score: 500 points

### Problem Statement

We have caught N sardines. The deliciousness and fragrantness of the i-th sardine is A_i and B_i, respectively.

We will choose one or more of these sardines and put them into a cooler. However, two sardines on bad terms cannot be chosen at the same time.

The i-th and j-th sardines (i \neq j) are on bad terms if and only if A_i \cdot A_j + B_i \cdot B_j = 0.

In how many ways can we choose the set of sardines to put into the cooler? Since the count can be enormous, print it modulo 1000000007.

### Constraints

• All values in input are integers.
• 1 \leq N \leq 2 \times 10^5
• -10^{18} \leq A_i, B_i \leq 10^{18}

### Input

Input is given from Standard Input in the following format:

N
A_1 B_1
:
A_N B_N


### Output

Print the count modulo 1000000007.

### Sample Input 1

3
1 2
-1 1
2 -1


### Sample Output 1

5


There are five ways to choose the set of sardines, as follows:

• The 1-st
• The 1-st and 2-nd
• The 2-nd
• The 2-nd and 3-rd
• The 3-rd

### Sample Input 2

10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4


### Sample Output 2

479

F - . (Single Dot)

### 問題文

この草原上に、大きさが無視できるほど小さい 1 頭の牛がいます。牛の今いる点から南に x\ \mathrm{cm}、東に y\ \mathrm{cm} 移動した点を (x, y) と表します。牛自身のいる点は (0, 0) です。

また、草原には N 本の縦線と M 本の横線が引かれています。i 本目の縦線は点 (A_i, C_i) と点 (B_i, C_i) とを結ぶ線分、j 本目の横線は点 (D_j, E_j) と点 (D_j, F_j) とを結ぶ線分です。

### 制約

• 入力はすべて -10^9 以上 10^9 以下の整数
• 1 \leq N, M \leq 1000
• A_i < B_i\ (1 \leq i \leq N)
• E_j < F_j\ (1 \leq j \leq M)
• (0, 0) はどの与えられた線分上にも位置しない

### 入力

N M
A_1 B_1 C_1
:
A_N B_N C_N
D_1 E_1 F_1
:
D_M E_M F_M


### 出力

(この問題の制約下で、牛が動き回れる範囲の面積が有限である場合、その面積は必ず整数であることが示せる。)

### 入力例 1

5 6
1 2 0
0 1 1
0 2 2
-3 4 -1
-2 6 3
1 0 1
0 1 2
2 0 2
-1 -4 5
3 -2 4
1 2 4


### 出力例 1

13


### 入力例 2

6 1
-3 -1 -2
-3 -1 1
-2 -1 2
1 4 -2
1 4 -1
1 4 1
3 1 4


### 出力例 2

INF


Score: 600 points

### Problem Statement

There is a grass field that stretches infinitely.

In this field, there is a negligibly small cow. Let (x, y) denote the point that is x\ \mathrm{cm} south and y\ \mathrm{cm} east of the point where the cow stands now. The cow itself is standing at (0, 0).

There are also N north-south lines and M east-west lines drawn on the field. The i-th north-south line is the segment connecting the points (A_i, C_i) and (B_i, C_i), and the j-th east-west line is the segment connecting the points (D_j, E_j) and (D_j, F_j).

What is the area of the region the cow can reach when it can move around as long as it does not cross the segments (including the endpoints)? If this area is infinite, print INF instead.

### Constraints

• All values in input are integers between -10^9 and 10^9 (inclusive).
• 1 \leq N, M \leq 1000
• A_i < B_i\ (1 \leq i \leq N)
• E_j < F_j\ (1 \leq j \leq M)
• The point (0, 0) does not lie on any of the given segments.

### Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
:
A_N B_N C_N
D_1 E_1 F_1
:
D_M E_M F_M


### Output

If the area of the region the cow can reach is infinite, print INF; otherwise, print an integer representing the area in \mathrm{cm^2}.

(Under the constraints, it can be proved that the area of the region is always an integer if it is not infinite.)

### Sample Input 1

5 6
1 2 0
0 1 1
0 2 2
-3 4 -1
-2 6 3
1 0 1
0 1 2
2 0 2
-1 -4 5
3 -2 4
1 2 4


### Sample Output 1

13


The area of the region the cow can reach is 13\ \mathrm{cm^2}.

### Sample Input 2

6 1
-3 -1 -2
-3 -1 1
-2 -1 2
1 4 -2
1 4 -1
1 4 1
3 1 4


### Sample Output 2

INF


The area of the region the cow can reach is infinite.