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

You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:

• for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.

Constraints

• 1 \leq N \leq 100
• Each element of A and B is 0 or 1.
• All values in the input are integers.

Sample Input 1

3
0 1 1
1 0 0
0 1 0
1 1 0
0 0 1
1 1 1

Sample Output 1

Yes

Initially, A is :

0 1 1
1 0 0
0 1 0

After performing the operation once, A is :

0 1 0
1 0 1 
0 0 1

After performing the operation once again, A is :

0 1 0
0 0 1
1 1 0

Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.

Sample Input 2

2
0 0
0 0
1 1
1 1

Sample Output 2

Yes

Sample Input 3

5
0 0 1 1 0
1 0 0 1 0
0 0 1 0 1
0 1 0 1 0
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
0 0 1 1 1
1 0 1 0 1
1 1 0 1 0

Sample Output 3

No

Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1

Problem Statement

We have a string S. Initially, S= 1.
Process Q queries in the following formats in order.

• 1 x : Append a digit x at the end of S.
• 2 : Delete the digit at the beginning of S.
• 3 : Print the number represented by S in decimal, modulo 998244353.

Constraints

• 1 \leq Q \leq 6 \times 10^5
• For each query in the first format, x \in \{1,2,3,4,5,6,7,8,9\}.
• A query in the second format is given only if S has a length of 2 or greater.
• There is at least one query in the third format.

Sample Input 1

3
3
1 2
3

Sample Output 1

1
12

In the first query, S is 1, so you should print 1 modulo 998244353, that is, 1.
In the second query, S becomes 12.
In the third query, S is 12, so you should print 12 modulo 998244353, that is, 12.

Sample Input 2

3
1 5
2
3

Sample Output 2

5

Sample Input 3

11
1 9
1 9
1 8
1 2
1 4
1 4
1 3
1 5
1 3
2
3

Sample Output 3

0

Be sure to print numbers modulo 998244353.

Problem Statement

Takahashi and Aoki will play a game of sugoroku.
Takahashi starts at point A, and Aoki starts at point B. They will take turns throwing dice.
Takahashi's die shows 1, 2, \ldots, P with equal probability, and Aoki's shows 1, 2, \ldots, Q with equal probability.
When a player at point x throws his die and it shows i, he goes to point \min(x + i, N).
The first player to reach point N wins the game.
Find the probability that Takahashi wins if he goes first, modulo 998244353.

Constraints

• 2 \leq N \leq 100
• 1 \leq A, B < N
• 1 \leq P, Q \leq 10
• All values in the input are integers.

Sample Input 1

4 2 3 3 2

Sample Output 1

665496236

If Takahashi's die shows 2 or 3 in his first turn, he goes to point 4 and wins.
If Takahashi's die shows 1 in his first turn, he goes to point 3, and Aoki will always go to point 4 in the next turn and win.
Thus, Takahashi wins with the probability \frac{2}{3}.

Sample Input 2

6 4 2 1 1

Sample Output 2

1

The dice always show 1.
Here, Takahashi goes to point 5, Aoki goes to point 3, and Takahashi goes to point 6, so Takahashi always wins.

Sample Input 3

100 1 1 10 10

Sample Output 3

264077814

Problem Statement

We have a grid with 10^9 rows and 10^9 columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For i=1,2,\ldots,N, a positive integer x_i is written on (r_i,c_i). On the other 10^{18}-N squares, 0 is written.

You choose a square (R,C) and compute the sum S of the integers written on the 2 \times 10^9 - 1 squares that share a row or column with (R,C).

Find the maximum possible value of S.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq r_i,c_i,x_i \leq 10^9
• (r_i,c_i) \neq (r_j,c_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4
1 1 2
1 2 9
2 1 8
3 2 3

Sample Output 1

20

If you choose (2,2) as (R,C), then S will be 20, which is the maximum possible value.

Sample Input 2

1
1 1000000000 1

Sample Output 2

1

Sample Input 3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

Sample Output 3

1510053068

Problem Statement

We have a rectangular cake. It is partitioned into H rows and W columns of sections, and the section at the i-th row from the top and j-th column from the left has s_{i,j} strawberries on it.

You will make T cuts to divide the cake into T+1 pieces. Each cut will be done in one of the following two manners.

• Choose an existing piece with two or more rows of sections. Additionally, choose two adjacent rows from that piece, and cut the piece along the boundary between them to divide it into two smaller pieces.
• Choose an existing piece with two or more columns of sections. Additionally, choose two adjacent columns from that piece, and cut the piece along the boundary between them to divide it into two smaller pieces.

You want to distribute the strawberries onto the resulting pieces as evenly as possible.
Let x_1,x_2,\ldots,x_{T+1} be the numbers of strawberries on the resulting T+1 pieces, and M and m be the maximum and minimum among those numbers, respectively. Find the minimum possible value of M－m.

Constraints

• 1 \leq H,W \leq 6
• 1 \leq T \leq HW-1
• 0 \leq s_{i,j} \leq 10^{16}
• All values in the input are integers.

Sample Input 1

2 3 4
2 3 4
4 1 3

Sample Output 1

2

The figure below shows a way to cut the cake so that the top-left, bottom-left, middle, top-right, and bottom-right pieces have 2, 4, 4, 4, and 3 strawberries on them, respectively. Here, the difference between the maximum and minimum number of strawberries is 4-2=2. It is impossible to achieve a smaller difference, so the answer is 2.

Sample Input 2

2 2 3
0 0
0 0

Sample Output 2

0

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i.

Let d(x,y) denote the distance between vertex x and y in this tree. Here, the distance between vertex x and y is the number of edges on the shortest path from vertex x to y.

Answer Q queries in order. The i-th query is as follows.

• You are given integers L_i and R_i. Find \displaystyle\sum_{j = 1}^{N} \min(d(j, L_i), d(j, R_i)).

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq A_i, B_i, L_i, R_i \leq N
• The given graph is a tree.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4
6
3

Let us explain the first query.
Since d(1, 4) = 2 and d(1, 1) = 0, we have \min(d(1, 4), d(1, 1)) = 0.
Since d(2, 4) = 2 and d(2, 1) = 2, we have \min(d(2, 4), d(2, 1)) = 2.
Since d(3, 4) = 1 and d(3, 1) = 3, we have \min(d(3, 4), d(3, 1)) = 1.
Since d(4, 4) = 0 and d(4, 1) = 2, we have \min(d(4, 4), d(4, 1)) = 0.
Since d(5, 4) = 1 and d(5, 1) = 1, we have \min(d(5, 4), d(5, 1)) = 1.
0 + 2 + 1 + 0 + 1 = 4, so you should print 4.

Sample Input 2

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

Sample Output 2

14
16
10
16
14
16
8