Problem Statement

You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.

• Among the digits of N, the digit 1 appears exactly once.
• Among the digits of N, the digit 2 appears exactly twice.
• Among the digits of N, the digit 3 appears exactly three times.

Constraints

• N is an integer satisfying 100000 \le N \le 999999.

Sample Input 1

123233

Sample Output 1

Yes

123233 satisfies the conditions in the problem statement, so print Yes.

Sample Input 2

123234

Sample Output 2

No

123234 does not satisfy the conditions in the problem statement, so print No.

Sample Input 3

323132

Sample Output 3

Yes

Sample Input 4

500000

Sample Output 4

No

Problem Statement

You are given a positive integer D.

Find the area of a circle with diameter D.

Constraints

• 1\le D\le 100
• The input value is an integer.

Sample Input 1

2

Sample Output 1

3.141592653589793

The area of a circle with diameter 2 is 3.141592653589793\ldots.

Sample Input 2

7

Sample Output 2

38.48451000647496

Sample Input 3

98

Sample Output 3

7542.9639612690935

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

• First, choose an integer i between 1 and N-1, inclusive.
• Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
  • Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

• All input values are integers.
• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq T_i \leq S_i \leq 10^9

Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
• Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
• Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

45

Problem Statement

Takahashi made purchases at N stores. Initially, he had 10000 yen.
At the i-th store, he bought an item worth A_i yen and paid B_i yen. Here, A_i \leq B_i holds. If S_i = keep, he did not receive the change, and if S_i = take, he received the change.
Find the amount of money he lost compared to the case where he received the change at every store. To be precise,

• let X yen be Takahashi's final amount of money, and
• let Y yen be Takahashi's final amount of money in the case where he received the change at every store.

Find Y - X.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq B_i \leq 100
• S_i is keep or take.
• N, A_i, B_i are all integers.

Sample Input 1

3
1 2 keep
3 6 take
5 9 keep

Sample Output 1

5

Takahashi's actions are as follows.

• At the first store, he bought an item worth 1 yen, paid 2 yen, and did not receive the change.
• At the second store, he bought an item worth 3 yen, paid 6 yen, and received the change.
• At the third store, he bought an item worth 5 yen, paid 9 yen, and did not receive the change.

Sample Input 2

8
36 49 take
38 73 keep
27 85 take
65 71 take
52 86 keep
48 60 keep
37 98 keep
5 38 keep

Sample Output 2

175

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

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

10 13
1 2 1
1 10 1
2 3 1
3 4 4
4 7 2
4 8 1
5 8 1
5 9 3
6 8 1
6 9 5
7 8 1
7 9 4
9 10 3

Sample Output 3

20

Problem Statement

Given is a string S consisting of X and ..

You can do the following operation on S between 0 and K times (inclusive).

• Replace a . with an X.

What is the maximum possible number of consecutive Xs in S after the operations?

Constraints

• 1 \leq |S| \leq 2 \times 10^5
• Each character of S is X or ..
• 0 \leq K \leq 2 \times 10^5
• K is an integer.

Sample Input 1

XX...X.X.X.
2

Sample Output 1

5

After replacing the Xs at the 7-th and 9-th positions with X, we have XX...XXXXX., which has five consecutive Xs at 6-th through 10-th positions.
We cannot have six or more consecutive Xs, so the answer is 5.

Sample Input 2

XXXX
200000

Sample Output 2

4

It is allowed to do zero operations.

Problem Statement

You are given a sequence of N-1 integers S = (S_1, S_2, \ldots, S_{N-1}), and M distinct integers X_1, X_2, \ldots, X_M, which are called lucky numbers.

A sequence of N integers A = (A_1, A_2, \ldots, A_N) satisfying the following condition is called a good sequence.

A_i + A_{i+1} = S_i holds for every i = 1, 2, \ldots, N-1.

Find the maximum possible number of terms that are lucky numbers in a good sequence A, that is, the maximum possible number of integers i between 1 and N such that A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10
• -10^9 \leq S_i \leq 10^9
• -10^9 \leq X_i \leq 10^9
• X_1 \lt X_2 \lt \cdots \lt X_M
• All values in input are integers.

Sample Input 1

9 2
2 3 3 4 -4 -7 -4 -1
-1 5

Sample Output 1

4

A good sequence A = (3, -1, 4, -1, 5, -9, 2, -6, 5) contains four terms that are lucky numbers: A_2, A_4, A_5, A_9, which is the maximum possible count.

Sample Input 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

Sample Output 2

8

Problem Statement

There is an N\times N grid. Let cell (i,j) denote the cell in the i-th row from the top and j-th column from the left. Each cell contains a digit from 1 to 9; cell (i,j) contains A_{i,j}.

Initially, a token is on cell (1,1). Let S be an empty string. Repeat the following operation 2N-1 times:

• Append to the end of S the digit in the current cell.
• Move the token one cell down or one cell to the right. However, do not move it in the (2N-1)-th operation.

After 2N-1 operations, the token is on cell (N,N) and the length of S is 2N-1.

Interpret S as an integer. The score is the remainder when this integer is divided by M.

Find the maximum achievable score.

Constraints

• 1 \leq N \leq 20
• 2 \leq M \leq 10^9
• 1 \leq A_{i,j} \leq 9
• All input values are integers.

Sample Input 1

2 7
1 2
3 1

Sample Output 1

5

There are two ways to move the token:

• Move through (1,1),(1,2),(2,2). Then S= 121, and the score is the remainder when 121 is divided by 7, which is 2.
• Move through (1,1),(2,1),(2,2). Then S= 131, and the score is the remainder when 131 is divided by 7, which is 5.

The maximum score is 5, so print 5.

Sample Input 2

3 100000
1 2 3
3 5 8
7 1 2

Sample Output 2

13712

Sample Input 3

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

Sample Output 3

384