Problem Statement

Team Takahashi and Team Aoki played N matches. In the i-th match (1\leq i\leq N), Team Takahashi scored X _ i points, and Team Aoki scored Y _ i points.

The team with the higher total score from the N matches wins.

Print the winner. If the two teams have the same total score, it is a draw.

Constraints

• 1\leq N\leq 100
• 0\leq X _ i\leq 100\ (1\leq i\leq N)
• 0\leq Y _ i\leq 100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

4
10 2
10 1
10 2
3 2

Sample Output 1

Takahashi

In four matches, Team Takahashi scored 33 points, and Team Aoki scored 7 points. Team Takahashi wins, so print Takahashi.

Sample Input 2

6
5 4
4 5
2 4
1 6
7 1
3 2

Sample Output 2

Draw

Both teams scored 22 points. It is a draw, so print Draw.

Sample Input 3

4
0 0
10 10
50 50
0 100

Sample Output 3

Aoki

One or both teams may score no points in a match.

Problem Statement

Takahashi had a job interview.

You are given the number of interviewers, N, and a string S of length N representing the interviewers' evaluations of him.
For each i=1,2,\ldots,N, the i-th character of S corresponds to the i-th interviewer's evaluation; o means Good, - means Fair, and x means Poor.

Takahashi will pass if both of the following conditions are satisfied, and fail otherwise.

• At least one interviewer's evaluation is Good.
• No interviewer's evaluation is Poor.

Determine whether Takahashi passes.

Constraints

• 1 \leq N \leq 100
• S is a string of length N consisting of o, -, and x.

Sample Input 1

4
oo--

Sample Output 1

Yes

The first and second interviewers' evaluations are Good, and no interviewer's evaluation is Poor, so he passes.

Sample Input 2

3
---

Sample Output 2

No

No interviewer's evaluation is Good, so he fails.

Sample Input 3

1
o

Sample Output 3

Yes

Sample Input 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

Sample Output 4

No

The 100-th interviewer's evaluation is Poor, so he fails.

Problem Statement

There are non-negative integers A, B, C, D, E, and F, which satisfy A\times B\times C\geq D\times E\times F.
Find the remainder when (A\times B\times C)-(D\times E\times F) is divided by 998244353.

Constraints

• 0\leq A,B,C,D,E,F\leq 10^{18}
• A\times B\times C\geq D\times E\times F
• A, B, C, D, E, and F are integers.

Sample Input 1

2 3 5 1 2 4

Sample Output 1

22

Since A\times B\times C=2\times 3\times 5=30 and D\times E\times F=1\times 2\times 4=8,
we have (A\times B\times C)-(D\times E\times F)=22. Divide this by 998244353 and print the remainder, which is 22.

Sample Input 2

1 1 1000000000 0 0 0

Sample Output 2

1755647

Since A\times B\times C=1000000000 and D\times E\times F=0,
we have (A\times B\times C)-(D\times E\times F)=1000000000. Divide this by 998244353 and print the remainder, which is 1755647.

Sample Input 3

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

0

We have (A\times B\times C)-(D\times E\times F)=0. Divide this by 998244353 and print the remainder, which is 0.

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

• S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

• a
• y
• ay
• ya
• yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54

Problem Statement

For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:

• The length |A| is at least 4.
• A_1 < A_2.
• There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
• There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.

Constraints

• 4 \leq N \leq 3 \times 10^5
• P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
• All input values are integers.

Sample Input 1

6
1 3 6 4 2 5

Sample Output 1

2

Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).

Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

0

Sample Input 3

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

Sample Output 3

4

Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• 1 \leq N \leq 10
• 1 \leq Q_i \leq 10^6
• 0 \leq A_i \leq 10^6
• There is an i such that A_i \geq 1.
• 0 \leq B_i \leq 10^6
• There is an i such that B_i \geq 1.
• All input values are integers.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

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

Sample Output 4

222222

Problem Statement

There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:

• If the j-th character of S_i is P, then (i, j) is an empty cell with a player on it.

• If the j-th character of S_i is ., then (i, j) is an empty cell without a player.

• If the j-th character of S_i is #, then (i, j) contains an obstacle.

Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.

• Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.

Constraints

• N is an integer between 2 and 60, inclusive.
• S_i is a string of length N consisting of P, ., and #.
• There are exactly two pairs (i, j) where the j-th character of S_i is P.

Sample Input 1

5
....#
#..#.
.P...
..P..
....#

Sample Output 1

3

Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.

For example, doing the following brings the two players to the same cell in three moves:

• Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).

• Choose up. Player 1 does not move, and Player 2 moves to (3, 2).

• Choose left. Player 1 does not move, and Player 2 moves to (3, 1).

Sample Input 2

2
P#
#P

Sample Output 2

-1

Sample Input 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

Sample Output 3

10

Problem Statement

Determine whether there exists a weighted undirected tree with N vertices satisfying the following condition.

• For any two integers i and j with 1 \le i \lt j \le N, the distance between vertices i and j is A_{i,j}.

Here, the distance between vertices i and j is defined as the sum of the weights of the edges on the unique simple path connecting these two vertices.

Constraints

• 2 \le N \le 3000
• 1 \le A_{i,j} \le 9999
• All input values are integers.

Sample Input 1

4
2 5 4
3 2
5

Sample Output 1

Yes

For example, the tree with the following edges satisfies the condition.

• Edge (1, 2) has weight 2.
• Edge (2, 3) has weight 3.
• Edge (2, 4) has weight 2.

Thus, output Yes.

Sample Input 2

4
2 5 4
3 2
6

Sample Output 2

No

No tree satisfying the condition exists. Thus, output No.

Sample Input 3

10
1039 1802 3781 231 5828 1944 392 262 1481
763 2742 1270 4789 905 1431 1301 442
1979 2033 5552 142 2194 2064 1205
4012 7531 2121 4173 4043 3184
6059 2175 161 493 1712
5694 6220 6090 5231
2336 2206 1347
654 1873
1743

Sample Output 3

Yes

Problem Statement

You are given N intervals numbered 1 to N. Interval i is [L_i, R_i].

Two intervals [l_a, r_a] and [l_b, r_b] are said to intersect if and only if they satisfy either (l_a < l_b < r_a < r_b) or (l_b < l_a < r_b < r_a).

Define f(l, r) as the number of intervals i (1 \leq i \leq N) that intersect with the interval [l, r].

Among all pairs of integers (l, r) satisfying 0 \leq l < r \leq 10^{9}, find the pair (l, r) that maximizes f(l, r). If there are multiple such pairs, choose the one with the smallest l. If there are still multiple pairs, choose the one with the smallest r among them. (Since 0 \leq l < r, the pair (l, r) to be answered is uniquely determined.)

Constraints

• 1 \leq N \leq 10^{5}
• 0 \leq L_i < R_i \leq 10^{9} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
1 7
3 9
7 18
10 14
15 20

Sample Output 1

4 11

The maximum value of f(l, r) is 4, and among the pairs (l, r) that achieve f(l, r) = 4, the smallest l is 4. The pairs (l, r) that satisfy f(l, r) = 4 and l = 4 are the following five:

• (l, r) = (4, 11)
• (l, r) = (4, 12)
• (l, r) = (4, 13)
• (l, r) = (4, 16)
• (l, r) = (4, 17)

Among these, the smallest r is 11, so print 4 and 11.

Sample Input 2

11
856977192 996441446
298251737 935869360
396653206 658841528
710569907 929136831
325371222 425309117
379628374 697340458
835681913 939343451
140179224 887672320
375607390 611397526
93530028 581033295
249611310 775998537

Sample Output 2

396653207 887672321