Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

• 1 \le N \le 100
• 1 \le D \le 10^9
• 1 \le T_i \le 10^9(1 \le i \le N)
• T_i < T_{i+1}(1 \le i \le N-1)
• All values in the input are integers.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

1300

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

600

If multiple double clicks were fired, be sure to print only the first such event.

Problem Statement

Takahashi and Aoki decided to jog.
Takahashi repeats the following: "walk at B meters a second for A seconds and take a rest for C seconds."
Aoki repeats the following: "walk at E meters a second for D seconds and take a rest for F seconds."
When X seconds have passed since they simultaneously started to jog, which of Takahashi and Aoki goes ahead?

Constraints

• 1 \leq A, B, C, D, E, F, X \leq 100
• All values in input are integers.

Sample Input 1

4 3 3 6 2 5 10

Sample Output 1

Takahashi

During the first 10 seconds after they started to jog, they move as follows.

• Takahashi walks for 4 seconds, takes a rest for 3 seconds, and walks again for 3 seconds. As a result, he advances a total of (4 + 3) \times 3 = 21 meters.
• Aoki walks for 6 seconds and takes a rest for 4 seconds. As a result, he advances a total of 6 \times 2 = 12 meters.

Since Takahashi goes ahead, Takahashi should be printed.

Sample Input 2

3 1 4 1 5 9 2

Sample Output 2

Aoki

Sample Input 3

1 1 1 1 1 1 1

Sample Output 3

Draw

Problem Statement

Overview: Create an N \times N pattern as follows.

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

You are given a positive integer N.

Consider an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. Initially, no cell is colored.

Then, for i = 1,2,\dots,N in order, perform the following operation:

• Let j = N + 1 - i.
• If i \leq j, fill the rectangular region whose top-left cell is (i,i) and bottom-right cell is (j,j) with black if i is odd, or white if i is even. If some cells are already colored, overwrite their colors.
• If i > j, do nothing.

After all these operations, it can be proved that there are no uncolored cells. Determine the final color of each cell.

Constraints

• 1 \leq N \leq 50
• All input values are integers.

Sample Input 1

11

Sample Output 1

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

This matches the pattern shown in the Overview.

Sample Input 2

5

Sample Output 2

#####
#...#
#.#.#
#...#
#####

Colors are applied as follows, where ? denotes a cell not yet colored:

         i=1      i=2      i=3      i=4      i=5
?????    #####    #####    #####    #####    #####
?????    #####    #...#    #...#    #...#    #...#
????? -> ##### -> #...# -> #.#.# -> #.#.# -> #.#.#
?????    #####    #...#    #...#    #...#    #...#
?????    #####    #####    #####    #####    #####

Sample Input 3

8

Sample Output 3

########
#......#
#.####.#
#.#..#.#
#.#..#.#
#.####.#
#......#
########

Sample Input 4

2

Sample Output 4

##
##

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

• (N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
• (i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

• 1 \le N \le 10
• 1 \le A_{i,j} \le 9
• All values in input are integers.

Sample Input 1

4
1161
1119
7111
1811

Sample Output 1

9786

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

• You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
• The test result is represented by a single English letter R_i.
  • R_i = o means that Door X opened in the i-th test.
  • R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

• N, M, K, C_i, and A_{i,j} are integers.
• 1 \le K \le N \le 15
• 1 \le M \le 100
• 1 \le C_i \le N
• 1 \le A_{i,j} \le N
• A_{i,j} \neq A_{i,k} if j \neq k.
• R_i is o or x.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

2

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

• In the first test, keys 1, 2, 3 were used, and Door X opened.
• In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

• Key 1 is real, key 2 is a dummy, and key 3 is real.
• Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

0

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

Sample Output 3

8

Problem Statement

In AtCoder Country, there is a rule that "a truck driver must take a break of at least B minutes when driving for A minutes or more."

You are given a string S of length N consisting of a and b, and positive integers A and B. Find the number of integer pairs (l,r) that satisfy all of the following conditions.

• 1\leq l \leq r \leq N
• The number of a in the substring from the l-th character through the r-th character of S is greater than or equal to A.
• The number of b in the substring from the l-th character through the r-th character of S is less than B.

Constraints

• 1\leq N \leq 3\times 10^5
• 1 \leq A,B \leq N
• S is a string of length N consisting of a and b.
• All input numbers are integers.

Sample Input 1

11 4 2
abbaaabaaba

Sample Output 1

3

The pairs (l,r) that satisfy the conditions are (4,8),(4,9),(5,9), which is three pairs.

Sample Input 2

13 1 2
bbbbbbbbbbbbb

Sample Output 2

0

There are no pairs (l,r) that satisfy the conditions.

Problem Statement

You are given a tree with N vertices numbered 1,2,\dots,N. The i-th edge connects vertices U_i and V_i.
Each vertex i has an integer A_i written on it.

Answer the following problem for all k=1,2,\dots,N.

• Problem: Among the vertices on the simple path (a path that does not visit the same vertex more than once) from vertex 1 to vertex k, if there exist two distinct vertices with the same integer written on them, output Yes; otherwise, output No.
  • It can be proved that the simple path connecting two vertices on a tree is unique.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le U_i, V_i \le N
• The given graph is a tree.

Sample Input 1

5
1 3 2 1 2
1 2
1 3
3 4
3 5

Sample Output 1

No
No
No
Yes
Yes

• For k=1: the path from vertex 1 to vertex 1 contains only vertex 1. Since the path consists of only one vertex, the answer is No.
• For k=2: the path from vertex 1 to vertex 2 contains vertices 1,2, with integers 1,3 written on them respectively. Thus, the answer is No.
• For k=3: the path from vertex 1 to vertex 3 contains vertices 1,3, with integers 1,2 written on them respectively. Thus, the answer is No.
• For k=4: the path from vertex 1 to vertex 4 contains vertices 1,3,4, with integers 1,2,1 written on them respectively. Since vertices 1 and 4 on the path have the same integer 1 written on them, the answer is Yes.
• For k=5: the path from vertex 1 to vertex 5 contains vertices 1,3,5, with integers 1,2,2 written on them respectively. Since vertices 3 and 5 on the path have the same integer 2 written on them, the answer is Yes.

Sample Input 2

2
1000000000 1000000000
2 1

Sample Output 2

No
Yes

Sample Input 3

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

Sample Output 3

No
Yes
Yes
Yes
Yes
No
No
No
No
Yes

Problem Statement

Given is a positive integer N. Find the value \displaystyle\sum_{i=1}^N \left[ \frac{N}{i} \right].

Here, for a real number x, [x] denotes the largest integer not exceeding x.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

3

Sample Output 1

5

We have \left[ \frac{3}{1} \right]+\left[ \frac{3}{2} \right]+\left[ \frac{3}{3} \right]=3+1+1=5.

Sample Input 2

10000000000

Sample Output 2

231802823220

Note that the input and output may not fit into a 32-bit integer type.

Problem Statement

You are given an integer N. Print a string S that satisfies all of the following conditions. If no such string exists, print -1.

• S is a string of length between 1 and 1000, inclusive, consisting of the characters 1, 2, 3, 4, 5, 6, 7, 8, 9, and * (multiplication symbol).
• S is a palindrome.
• The first character of S is a digit.
• The value of S when evaluated as a formula equals N.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

363

Sample Output 1

11*3*11

S = 11*3*11 satisfies the conditions in the problem statement. Another string that satisfies the conditions is S= 363.

Sample Input 2

101

Sample Output 2

-1

Note that S must not contain the digit 0.

Sample Input 3

3154625100

Sample Output 3

2*57*184481*75*2