Problem Statement

M-kun is a competitor in AtCoder, whose highest rating is X.
In this site, a competitor is given a kyu (class) according to his/her highest rating. For ratings from 400 through 1999, the following kyus are given:

• From 400 through 599: 8-kyu
• From 600 through 799: 7-kyu
• From 800 through 999: 6-kyu
• From 1000 through 1199: 5-kyu
• From 1200 through 1399: 4-kyu
• From 1400 through 1599: 3-kyu
• From 1600 through 1799: 2-kyu
• From 1800 through 1999: 1-kyu

What kyu does M-kun have?

Constraints

• 400 \leq X \leq 1999
• X is an integer.

Sample Input 1

725

Sample Output 1

7

M-kun's highest rating is 725, which corresponds to 7-kyu.
Thus, 7 is the correct output.

Sample Input 2

1600

Sample Output 2

2

M-kun's highest rating is 1600, which corresponds to 2-kyu.
Thus, 2 is the correct output.

Problem Statement

M-kun has the following three cards:

• A red card with the integer A.
• A green card with the integer B.
• A blue card with the integer C.

He is a genius magician who can do the following operation at most K times:

• Choose one of the three cards and multiply the written integer by 2.

His magic is successful if both of the following conditions are satisfied after the operations:

• The integer on the green card is strictly greater than the integer on the red card.
• The integer on the blue card is strictly greater than the integer on the green card.

Determine whether the magic can be successful.

Constraints

• 1 \leq A, B, C \leq 7
• 1 \leq K \leq 7
• All values in input are integers.

Sample Input 1

7 2 5
3

Sample Output 1

Yes

The magic will be successful if, for example, he does the following operations:

• First, choose the blue card. The integers on the red, green, and blue cards are now 7, 2, and 10, respectively.
• Second, choose the green card. The integers on the red, green, and blue cards are now 7, 4, and 10, respectively.
• Third, choose the green card. The integers on the red, green, and blue cards are now 7, 8, and 10, respectively.

Sample Input 2

7 4 2
3

Sample Output 2

No

He has no way to succeed in the magic with at most three operations.

Problem Statement

M-kun is a student in Aoki High School, where a year is divided into N terms.
There is an exam at the end of each term. According to the scores in those exams, a student is given a grade for each term, as follows:

• For the first through (K-1)-th terms: not given.
• For each of the K-th through N-th terms: the multiplication of the scores in the last K exams, including the exam in the graded term.

M-kun scored A_i in the exam at the end of the i-th term.
For each i such that K+1 \leq i \leq N, determine whether his grade for the i-th term is strictly greater than the grade for the (i-1)-th term.

Constraints

• 2 \leq N \leq 200000
• 1 \leq K \leq N-1
• 1 \leq A_i \leq 10^{9}
• All values in input are integers.

Sample Input 1

5 3
96 98 95 100 20

Sample Output 1

Yes
No

His grade for each term is computed as follows:

• 3-rd term: (96 \times 98 \times 95) = 893760
• 4-th term: (98 \times 95 \times 100) = 931000
• 5-th term: (95 \times 100 \times 20) = 190000

Sample Input 2

3 2
1001 869120 1001

Sample Output 2

No

Note that the output should be No if the grade for the 3-rd term is equal to the grade for the 2-nd term.

Sample Input 3

15 7
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

Sample Output 3

Yes
Yes
No
Yes
Yes
No
Yes
Yes

Problem Statement

To become a millionaire, M-kun has decided to make money by trading in the next N days. Currently, he has 1000 yen and no stocks - only one kind of stock is issued in the country where he lives.

He is famous across the country for his ability to foresee the future. He already knows that the price of one stock in the next N days will be as follows:

• A_1 yen on the 1-st day, A_2 yen on the 2-nd day, ..., A_N yen on the N-th day.

In the i-th day, M-kun can make the following trade any number of times (possibly zero), within the amount of money and stocks that he has at the time.

• Buy stock: Pay A_i yen and receive one stock.
• Sell stock: Sell one stock for A_i yen.

What is the maximum possible amount of money that M-kun can have in the end by trading optimally?

Constraints

• 2 \leq N \leq 80
• 100 \leq A_i \leq 200
• All values in input are integers.

Sample Input 1

7
100 130 130 130 115 115 150

Sample Output 1

1685

In this sample input, M-kun has seven days of trading. One way to have 1685 yen in the end is as follows:

• Initially, he has 1000 yen and no stocks.
• Day 1: Buy 10 stocks for 1000 yen. Now he has 0 yen.
• Day 2: Sell 7 stocks for 910 yen. Now he has 910 yen.
• Day 3: Sell 3 stocks for 390 yen. Now he has 1300 yen.
• Day 4: Do nothing.
• Day 5: Buy 1 stock for 115 yen. Now he has 1185 yen.
• Day 6: Buy 10 stocks for 1150 yen. Now he has 35 yen.
• Day 7: Sell 11 stocks for 1650 yen. Now he has 1685 yen.

There is no way to have 1686 yen or more in the end, so the answer is 1685.

Sample Input 2

6
200 180 160 140 120 100

Sample Output 2

1000

In this sample input, it is optimal to do nothing throughout the six days, after which we will have 1000 yen.

Sample Input 3

2
157 193

Sample Output 3

1216

In this sample input, it is optimal to buy 6 stocks in Day 1 and sell them in Day 2, after which we will have 1216 yen.

Problem Statement

New AtCoder City has an infinite grid of streets, as follows:

• At the center of the city stands a clock tower. Let (0, 0) be the coordinates of this point.
• A straight street, which we will call East-West Main Street, runs east-west and passes the clock tower. It corresponds to the x-axis in the two-dimensional coordinate plane.
• There are also other infinitely many streets parallel to East-West Main Street, with a distance of 1 between them. They correspond to the lines \ldots, y = -2, y = -1, y = 1, y = 2, \ldots in the two-dimensional coordinate plane.
• A straight street, which we will call North-South Main Street, runs north-south and passes the clock tower. It corresponds to the y-axis in the two-dimensional coordinate plane.
• There are also other infinitely many streets parallel to North-South Main Street, with a distance of 1 between them. They correspond to the lines \ldots, x = -2, x = -1, x = 1, x = 2, \ldots in the two-dimensional coordinate plane.

There are N residential areas in New AtCoder City. The i-th area is located at the intersection with the coordinates (X_i, Y_i) and has a population of P_i. Each citizen in the city lives in one of these areas.

The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.
M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose K streets and build a railroad stretching infinitely along each of those streets.

Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad.
M-kun wants to build railroads so that the sum of the walking distances of all citizens, S, is minimized.

For each K = 0, 1, 2, \dots, N, what is the minimum possible value of S after building railroads?

Constraints

• 1 \leq N \leq 15
• -10 \ 000 \leq X_i \leq 10 \ 000
• -10 \ 000 \leq Y_i \leq 10 \ 000
• 1 \leq P_i \leq 1 \ 000 \ 000
• The locations of the N residential areas, (X_i, Y_i), are all distinct.
• All values in input are integers.

Sample Input 1

3
1 2 300
3 3 600
1 4 800

Sample Output 1

2900
900
0
0

When K = 0, the residents of Area 1, 2, and 3 have to walk the distances of 1, 3, and 1, respectively, to reach a railroad.
Thus, the sum of the walking distances of all citizens, S, is 1 \times 300 + 3 \times 600 + 1 \times 800 = 2900.

When K = 1, if we build a railroad along the street corresponding to the line y = 4 in the coordinate plane, the walking distances of the citizens of Area 1, 2, and 3 become 1, 1, and 0, respectively.
Then, S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900.
We have many other options for where we build the railroad, but none of them makes S less than 900.

When K = 2, if we build a railroad along the street corresponding to the lines x = 1 and x = 3 in the coordinate plane, all citizens can reach a railroad with the walking distance of 0, so S = 0. We can also have S = 0 when K = 3.

The figure below shows the optimal way to build railroads for the cases K = 0, 1, 2.
The street painted blue represents the roads along which we build railroads.

Sample Input 2

5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400

Sample Output 2

13800
1600
0
0
0
0

The figure below shows the optimal way to build railroads for the cases K = 1, 2.

Sample Input 3

6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200

Sample Output 3

26700
13900
3200
1200
0
0
0

The figure below shows the optimal way to build railroads for the case K = 3.

Sample Input 4

8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903

Sample Output 4

2576709
1569381
868031
605676
366338
141903
0
0
0

The figure below shows the optimal way to build railroads for the case K = 4.

Problem Statement

M-kun is a brilliant air traffic controller.

On the display of his radar, there are N airplanes numbered 1, 2, ..., N, all flying at the same altitude.
Each of the airplanes flies at a constant speed of 0.1 per second in a constant direction. The current coordinates of the airplane numbered i are (X_i, Y_i), and the direction of the airplane is as follows:

• if U_i is U, it flies in the positive y direction;
• if U_i is R, it flies in the positive x direction;
• if U_i is D, it flies in the negative y direction;
• if U_i is L, it flies in the negative x direction.

To help M-kun in his work, determine whether there is a pair of airplanes that will collide with each other if they keep flying as they are now.
If there is such a pair, find the number of seconds after which the first collision will happen.
We assume that the airplanes are negligibly small so that two airplanes only collide when they reach the same coordinates simultaneously.

Constraints

• 1 \leq N \leq 200000
• 0 \leq X_i, Y_i \leq 200000
• U_i is U, R, D, or L.
• The current positions of the N airplanes, (X_i, Y_i), are all distinct.
• N, X_i, and Y_i are integers.

Sample Input 1

2
11 1 U
11 47 D

Sample Output 1

230

If the airplanes keep flying as they are now, two airplanes numbered 1 and 2 will reach the coordinates (11, 24) simultaneously and collide.

Sample Input 2

4
20 30 U
30 20 R
20 10 D
10 20 L

Sample Output 2

SAFE

No pair of airplanes will collide.

Sample Input 3

8
168 224 U
130 175 R
111 198 D
121 188 L
201 116 U
112 121 R
145 239 D
185 107 L

Sample Output 3

100