Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

• x and y are the same character.
• One of x and y is 1 and the other is l.
• One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

• for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

• N is an integer between 1 and 100.
• Each of S and T is a string of length N consisting of lowercase English letters and digits.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes

Problem Statement

N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.

Two people who did not stand next to each other in any of the photos may be in a bad mood.

How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.

Constraints

• 2 \leq N \leq 50
• 1 \leq M \leq 50
• 1 \leq a_{i,j} \leq N
• a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
• All values in the input are integers.

Sample Input 1

4 2
1 2 3 4
4 3 1 2

Sample Output 1

2

The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.

Sample Input 2

3 3
1 2 3
3 1 2
1 2 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

6

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

Your computer has a keyboard with three keys: 'a' key, Shift key, and Caps Lock key. The Caps Lock key has a light on it. Initially, the light on the Caps Lock key is off, and the screen shows an empty string.

You can do the following three actions any number of times in any order:

• Spend X milliseconds to press only the 'a' key. If the light on the Caps Lock key is off, a is appended to the string on the screen; if it is on, A is.
• Spend Y milliseconds to press the 'a' key and Shift key simultaneously. If the light on the Caps Lock key is off, A is appended to the string on the screen; if it is on, a is.
• Spend Z milliseconds to press the Caps Lock key. If the light on the Caps Lock key is off, it turns on; if it is on, it turns off.

Given a string S consisting of A and a, determine at least how many milliseconds you need to spend to make the string shown on the screen equal to S.

Constraints

• 1 \leq X,Y,Z \leq 10^9
• X, Y, and Z are integers.
• 1 \leq |S| \leq 3 \times 10^5
• S is a string consisting of A and a.

Sample Input 1

1 3 3
AAaA

Sample Output 1

9

The following sequence of actions makes the string on the screen equal to AAaA in 9 milliseconds, which is the shortest possible.

• Spend Z(=3) milliseconds to press the CapsLock key. The light on the Caps Lock key turns on.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend Y(=3) milliseconds to press the Shift key and 'a' key simultaneously. a is appended to the string on the screen.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.

Sample Input 2

1 1 100
aAaAaA

Sample Output 2

6

Sample Input 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

Sample Output 3

40

Problem Statement

A graph with (k+1) vertices and k edges is called a level-k\ (k\geq 2) star if and only if:

• it has a vertex that is connected to each of the other k vertices with an edge, and there are no other edges.

At first, Takahashi had a graph consisting of stars. He repeated the following operation until every pair of vertices in the graph was connected:

• choose two vertices in the graph. Here, the vertices must be disconnected, and their degrees must be both 1. Add an edge that connects the chosen two vertices.

He then arbitrarily assigned an integer from 1 through N to each of the vertices in the graph after the procedure. The resulting graph is a tree; we call it T. T has (N-1) edges, the i-th of which connects u_i and v_i.

Takahashi has now forgotten the number and levels of the stars that he initially had. Find them, given T.

Constraints

• 3\leq N\leq 2\times 10^5
• 1\leq u_i, v_i\leq N
• The given graph is an N-vertex tree obtained by the procedure in the problem statement.
• All values in the input are integers.

Sample Input 1

6
1 2
2 3
3 4
4 5
5 6

Sample Output 1

2 2

Two level-2 stars yield T, as the following figure shows:

Sample Input 2

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

Sample Output 2

2 2 2

Sample Input 3

20
8 3
8 18
2 19
8 20
9 17
19 7
8 7
14 12
2 15
14 10
2 13
2 16
2 1
9 5
10 15
14 6
2 4
2 11
5 12

Sample Output 3

2 3 4 7

Problem Statement

A monster with health H has appeared in front of you, and a turn-based battle has started.

In each turn 1,2,…, you cast one of N spells, spells 1,…,N.

If you cast spell i in turn j, the monster's health reduces by d_i in each turn j,j+1,…,j+t_i －1.

Find the earliest turn that you can make the monster's health 0 or less.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq H \leq 10^{18}
• 1 \leq t_i,d_i \leq 10^9
• All values in the input are integers.

Sample Input 1

2 20
2 2
5 1

Sample Output 1

6

The following procedure makes the monster's health 0 or less in turn 6, which is the earliest.

• Cast spell 1 in turn 1. Due to the spell cast in turn 1, the monster's health reduces by 2 and becomes 18.
• Cast spell 2 in turn 2. Due to the spells cast in turns 1 and 2, the monster's health reduces by 2+1=3 and becomes 15.
• Cast spell 1 in turn 3. Due to the spells cast in turns 2 and 3, the monster's health reduces by 1+2=3 and becomes 12.
• Cast spell 2 in turn 4. Due to the spells cast in turns 2,3 and 4, the monster's health reduces by 1+2+1=4 and becomes 8.
• Cast spell 1 in turn 5. Due to the spells cast in turns 2,4 and 5, the monster's health reduces by 1+1+2=4 and becomes 4.
• Cast spell 2 in turn 6. Due to the spells cast in turns 2,4,5 and 6, the monster's health reduces by 1+1+2+1=5 and becomes -1.

Sample Input 2

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

Sample Output 2

9

Problem Statement

N bags are arranged in a row. The i-th bag contains x_i yen (the currency in Japan).

Takahashi and Aoki, who have sufficient money, take alternating turns to perform the following action:

• choose one of the following three actions and perform it.
  • choose the leftmost or rightmost bag and take it.
  • pay A yen to Snuke. Then, repeat the following action \min(B,n) times (where n is the number of the remaining bags): choose the leftmost or rightmost bag and take it.
  • pay C yen to Snuke. Then, repeat the following action \min(D,n) times (where n is the number of the remaining bags): choose the leftmost or rightmost bag and take it.

When all the bags are taken, Takahashi's benefit is defined by "(total amount of money in the bags that Takahashi took) - (total amount of money that Takahashi paid to snuke)"; let this amount be X yen. We similarly define Aoki's benefit, denoting the amount by Y yen.

Find X-Y if Takahashi and Aoki make optimal moves to respectively maximize and minimize X-Y.

Constraints

• 1 \leq N \leq 3000
• 1 \leq x_i \leq 10^9
• 1 \leq A,C \leq 10^9
• 1 \leq B,D \leq N
• All values in the input are integers.

Sample Input 1

5 10 2 1000000000 1
1 100 1 1 1

Sample Output 1

90

If Takahashi and Aoki make optimal moves, it ends up being X=92 and Y=2.

Sample Input 2

10 45 3 55 4
5 10 15 20 25 30 35 40 45 50

Sample Output 2

85

Sample Input 3

15 796265 10 165794055 1
18804175 185937909 1934689 18341 68370722 1653 1 2514380 31381214 905 754483 11 5877098 232 31600

Sample Output 3

302361955

Problem Statement

You are given an integer N and a set S=\lbrace S_1,S_2,\ldots,S_K\rbrace consisting of integers between 1 and N-1.

Find the number, modulo 998244353, of trees T with N vertices numbered 1 through N such that:

• d_i\in S for all i\ (1\leq i \leq N), where d_i is the degree of vertex i in T.

Constraints

• 2\leq N \leq 2\times 10^5
• 1\leq K \leq N-1
• 1\leq S_1 < S_2 < \ldots < S_K \leq N-1
• All values in the input are integers.

Sample Input 1

4 2
1 3

Sample Output 1

4

A tree satisfies the condition if the degree of one vertex is 3 and the others' are 1. Thus, the answer is 4.

Sample Input 2

10 5
1 2 3 5 6

Sample Output 2

68521950

Sample Input 3

100 5
1 2 3 14 15

Sample Output 3

888770956

Print the count modulo 998244353.