Problem Statement

One day, Takahashi got up at exactly B minutes past A o'clock (in 24-hour clock), and Aoki got up at exactly D minutes and 1 second past C o'clock.
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Constraints

• 0 \leq A \leq 23
• 0 \leq B \leq 59
• 0 \leq C \leq 23
• 0 \leq D \leq 59
• All values in input are integers.

Sample Input 1

7 0 6 30

Sample Output 1

Aoki

Takahashi got up at 7 sharp, and Aoki got up at 30 minutes and 1 second past 6 o'clock. Aoki was the first to get up, so Aoki should be printed.

Sample Input 2

7 30 7 30

Sample Output 2

Takahashi

Takahashi got up at exactly half past 7, and Aoki got up at 30 minutes and 1 second past 7 o'clock. Just by one second, Takahashi was the first to get up, so Takahashi should be printed.

Sample Input 3

0 0 23 59

Sample Output 3

Takahashi

0:00 in a day is one minute before 0:01, not one minute past 23:59 ("24:00"). Thus, Takahashi was the first to get up, so Takahashi should be printed.

Problem Statement

You are given N integers A_1, A_2, \dots, A_N. Also, define B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1).

Print B_1, B_2, \dots, B_{N-1} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

3
3 4 6

Sample Output 1

12 24

We have B_1 = A_1 \times A_2 = 12, B_2 = A_2 \times A_3 = 24.

Sample Input 2

5
22 75 26 45 72

Sample Output 2

1650 1950 1170 3240

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

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

• Each tile is either a white tile or a black tile.
• Every square in a white tile is painted white; every square in a black tile is painted black.
• Tile (1,1) is a white tile.
• Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

• 1 \leq N,A,B \leq 10
• All values in input are integers.

Sample Input 1

4 3 2

Sample Output 1

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

Sample Input 2

5 1 5

Sample Output 2

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

Sample Input 3

4 4 1

Sample Output 3

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

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

Problem Statement

You are given a string S of length N consisting only of lowercase English letters.

Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.

Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.

Constraints

• 2 \leq K \leq N \leq 10
• N and K are integers.
• S is a string of length N consisting only of lowercase English letters.

Sample Input 1

3 2
aab

Sample Output 1

1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.

Sample Input 2

5 3
zzyyx

Sample Output 2

16

There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

440640

Problem Statement

There is a grid with N horizontal rows and N vertical columns, where each square is painted white or black.
The state of the grid is represented by N strings, S_i. If the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is painted black. If the character is ., then the square is painted white.

Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain 6 or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing 6 or more consecutive squares painted black aligned diagonally if the grid with N rows and N columns completely contains a subgrid with 6 rows and 6 columns such that all the squares on at least one of its diagonals are painted black.

Constraints

• 6 \leq N \leq 1000
• \lvert S_i\rvert =N
• S_i consists of # and ..

Sample Input 1

8
........
........
.#.##.#.
........
........
........
........
........

Sample Output 1

Yes

By painting the 3-rd and the 6-th squares from the left in the 3-rd row from the top, there will be 6 squares painted black aligned horizontally.

Sample Input 2

6
######
######
######
######
######
######

Sample Output 2

Yes

While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.

Sample Input 3

10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

Sample Output 3

No

Problem Statement

There are N people numbered 1 to N on a coordinate plane.
Person 1 is at the origin.

You are given M pieces of information in the following form:

• From person A_i's perspective, person B_i is X_i units away in the positive x-direction and Y_i units away in the positive y-direction.

Determine the coordinates of each person. If the coordinates of a person cannot be uniquely determined, report that fact.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1\leq A_i, B_i \leq N
• A_i \neq B_i
• -10^9 \leq X_i,Y_i \leq 10^9
• All input values are integers.
• The given information is consistent.

Sample Input 1

3 2
1 2 2 1
1 3 -1 -2

Sample Output 1

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 2

3 2
2 1 -2 -1
2 3 -3 -3

Sample Output 2

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 3

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

Sample Output 3

0 0
0 0
0 0
undecidable
undecidable

The same piece of information may be given multiple times, and multiple people may be at the same coordinates.

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and an integer K.
There are 2^{N-1} ways to divide A into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to K? Find the count modulo 998244353.

Here, "to divide A into several contiguous subsequences" means the following procedure.

• Freely choose the number k (1 \leq k \leq N) of subsequences and an integer sequence (i_1, i_2, \dots, i_k, i_{k+1}) satisfying 1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1.
• For each 1 \leq n \leq k, the n-th subsequence is formed by taking the i_n-th through (i_{n+1} - 1)-th elements of A, maintaining their order.

Here are some examples of divisions for A = (1, 2, 3, 4, 5):

• (1, 2, 3), (4), (5)
• (1, 2), (3, 4, 5)
• (1, 2, 3, 4, 5)

Constraints

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

Sample Input 1

3 3
1 2 3

Sample Output 1

2

There are two divisions that satisfy the condition in the problem statement:

• (1), (2, 3)
• (1, 2, 3)

Sample Input 2

5 0
0 0 0 0 0

Sample Output 2

0

Sample Input 3

10 5
-5 -1 -7 6 -6 -2 -5 10 2 -10

Sample Output 3

428

Problem Statement

You are given N integers A_1, A_2, \dots, A_N.
Find the number of triples of integers (i, j, k) that satisfy the following conditions:

• 1 \le i, j, k \le N
• A_i \times A_j = A_k

Constraints

• 1 \le N \le 1000
• \color{red}{1 \le A_i < 10^{1000}}

Sample Input 1

5
2
3
6
12
24

Sample Output 1

6

The following six triples (i, j, k) satisfy the conditions in the problem statement:

• (1, 2, 3)
• (1, 3, 4)
• (1, 4, 5)
• (2, 1, 3)
• (3, 1, 4)
• (4, 1, 5)

Sample Input 2

11
1
2
3
4
5
6
123456789123456789
123456789123456789
987654321987654321
987654321987654321
121932631356500531347203169112635269

Sample Output 2

40

Note that the values of each integer A_i can be huge.

Sample Input 3

9
4
4
4
2
2
2
1
1
1

Sample Output 3

162

Note that there may be duplicates among the values of A_i.