Problem Statement

You are given a real number X, which is representable using at most three decimal digits, with three decimal digits.
Round X to the nearest integer and print the result.

Constraints

• 0 \leq X < 100
• X is representable using at most three decimal digits.
• X has three decimal digits in input.

Sample Input 1

3.456

Sample Output 1

3

The digit in the first decimal place of 3.456 is 4, so we should round it down to 3.

Sample Input 2

99.500

Sample Output 2

100

Sample Input 3

0.000

Sample Output 3

0

Problem Statement

We have five cards with integers A, B, C, D, and E written on them, one on each card.

This set of five cards is called a Full house if and only if the following condition is satisfied:

• the set has three cards with a same number written on them, and two cards with another same number written on them.

Determine whether the set is a Full house.

Constraints

• 1 \leq A,B,C,D,E\leq 13
• Not all of A, B, C, D, and E are the same.
• All values in input are integers.

Sample Input 1

1 2 1 2 1

Sample Output 1

Yes

The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.

Sample Input 2

12 12 11 1 2

Sample Output 2

No

The condition is not satisfied.

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

• For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
  • S_1, if the i-th character of T is 1;
  • S_2, if the i-th character of T is 2;
  • S_3, if the i-th character of T is 3.
• Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

• 1 \leq |S_1|, |S_2|, |S_3| \leq 10
• 1 \leq |T| \leq 1000
• S_1, S_2, and S_3 consist of lowercase English letters.
• T consists of 1, 2, and 3.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

a

Problem Statement

There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.

Constraints

• All values in input are integers.
• 1 \le K < N \le 1000
• 1 \le A_1 < A_2 < \dots < A_K \le N
• |X_i|,|Y_i| \le 10^5
• (X_i,Y_i) \neq (X_j,Y_j), if i \neq j.

Sample Input 1

4 2
2 3
0 0
0 1
1 2
2 0

Sample Output 1

2.23606797749978969

This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.

Sample Input 2

2 1
2
-100000 -100000
100000 100000

Sample Output 2

282842.712474619009

Sample Input 3

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

Sample Output 3

130379.280458974768

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

• It is a string of length L+1 consisting of o and -.
• Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

• There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

• 1\leq N\leq 2\times10^5
• S is a string of length N consisting of o and -.

Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7

Problem Statement

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

Problem Statement

You are given a sequence of non-negative integers A=(a_1,a_2,\ldots,a_N).

Let S be the set of non-negative integers that can be the sum of K terms in A (with distinct indices).

Find the greatest multiple of D in S. If there is no multiple of D in S, print -1 instead.

Constraints

• 1 \leq K \leq N \leq 100
• 1 \leq D \leq 100
• 0 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4 2 2
1 2 3 4

Sample Output 1

6

Here are all the ways to choose two terms in A.

• Choose a_1 and a_2, whose sum is 1+2=3.
• Choose a_1 and a_3, whose sum is 1+3=4.
• Choose a_1 and a_4, whose sum is 1+4=5.
• Choose a_2 and a_3, whose sum is 2+3=5.
• Choose a_2 and a_4, whose sum is 2+4=6.
• Choose a_3 and a_4, whose sum is 3+4=7.

Thus, we have S=\{3,4,5,6,7\}. The greatest multiple of 2 in S is 6, so you should print 6.

Sample Input 2

3 1 2
1 3 5

Sample Output 2

-1

In this example, we have S=\{1,3,5\}. Nothing in S is a multiple of 2, so you should print -1.

Problem Statement

You are given a sequence of length M consisting of integers between 1 and N-1, inclusive: A=(A_1,A_2,\dots,A_M). Answer the following question for i=1, 2, \dots, M.

• There is a sequence B=(B_1,B_2,\dots,B_N). Initially, we have B_j=j for each j. Let us perform the following operation for k=1, 2, \dots, i-1, i+1, \dots, M in this order (in other words, for integers k between 1 and M except i in ascending order).
  • Swap the values of B_{A_k} and B_{A_k+1}.
• After all the operations, let S_i be the value of j such that B_j=1. Find S_i.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1 \leq A_i \leq N-1\ (1\leq i \leq M)
• All values in the input are integers.

Sample Input 1

5 4
1 2 3 2

Sample Output 1

1
3
2
4

For i = 2, the operations change B as follows.

• Initially, B = (1,2,3,4,5).
• Perform the operation for k=1. That is, swap the values of B_1 and B_2, making B = (2,1,3,4,5).
• Perform the operation for k=3. That is, swap the values of B_3 and B_4, making B = (2,1,4,3,5).
• Perform the operation for k=4. That is, swap the values of B_2 and B_3, making B = (2,4,1,3,5).

After all the operations, we have B_3=1, so S_2 = 3.

Similarly, we have the following.

• For i=1: performing the operation for k=2,3,4 in this order makes B=(1,4,3,2,5), so S_1=1.
• For i=3: performing the operation for k=1,2,4 in this order makes B=(2,1,3,4,5), so S_3=2.
• For i=4: performing the operation for k=1,2,3 in this order makes B=(2,3,4,1,5), so S_4=4.

Sample Input 2

3 3
2 2 2

Sample Output 2

1
1
1

Sample Input 3

10 10
1 1 1 9 4 4 2 1 3 3

Sample Output 3

2
2
2
3
3
3
1
3
4
4

Problem Statement

There are N items.
Each of these is one of a pull-tab can, a regular can, or a can opener.
The i-th item is described by an integer pair (T_i, X_i) as follows:

• If T_i = 0, the i-th item is a pull-tab can; if you obtain it, you get a happiness of X_i.
• If T_i = 1, the i-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of X_i.
• If T_i = 2, the i-th item is a can opener; it can be used against at most X_i cans.

Find the maximum total happiness that you get by obtaining M items out of N.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• T_i is 0, 1, or 2.
• 1 \leq X_i \leq 10^9
• All input values are integers.

Sample Input 1

8 4
0 6
0 6
1 3
1 5
1 15
2 1
2 10
2 100

Sample Output 1

27

If you obtain the 1-st, 2-nd, 5-th, and 7-th items, and use the 7-th item (a can opener) against the 5-th item, you will get a happiness of 6 + 6 + 15 = 27.
There are no ways to obtain items to get a happiness of 28 or greater, but you can still get a happiness of 27 by obtaining the 6-th or 8-th items instead of the 7-th in the combination above.

Sample Input 2

5 5
1 5
1 5
1 5
1 5
1 5

Sample Output 2

0

Sample Input 3

12 6
2 2
0 1
0 9
1 3
1 5
1 3
0 4
2 1
1 8
2 1
0 1
0 4

Sample Output 3

30