Problem Statement

Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.

Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.

Constraints

• abc is a 3-digit integer abc none of whose digits is 0.

Sample Input 1

123

Sample Output 1

666

We have 123+231+312=666.

Sample Input 2

999

Sample Output 2

2997

We have 999+999+999=2997.

Problem Statement

Given a positive integer N, print a string of N zeros and N+1 ones where 0 and 1 alternate.

Constraints

• N is an integer.
• 1 \leq N \leq 100

Sample Input 1

4

Sample Output 1

101010101

A string of four zeros and five ones where 0 and 1 alternate is 101010101.

Sample Input 2

1

Sample Output 2

101

Sample Input 3

10

Sample Output 3

101010101010101010101

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

• For each i (0\leq i \leq N-1), the length of A_i is i+1.
• For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
  • a_{i,j}=1, if j=0 or j=i.
  • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

• 1 \leq N \leq 30
• N is an integer.

Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Problem Statement

There is an infinitely long piano keyboard. Is there a continuous segment within this keyboard that consists of W white keys and B black keys?

Let S be the string formed by infinitely repeating the string wbwbwwbwbwbw.

Is there a substring of S that consists of W occurrences of w and B occurrences of b?

Constraints

• W and B are integers.
• 0\leq W,B \leq 100
• W+B \geq 1

Sample Input 1

3 2

Sample Output 1

Yes

The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11-th through 15-th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b.

Sample Input 2

3 0

Sample Output 2

No

The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S.

Sample Input 3

92 66

Sample Output 3

Yes

Problem Statement

You are playing a game.

There are N enemies lined up in a row, and the i-th enemy from the front has a health of H_i.

You will repeat the following action until the healths of all enemies become 0 or less, using a variable T initialized to 0.

• Increase T by 1. Then, attack the frontmost enemy with health 1 or more. If T is a multiple of 3, the enemy's health decreases by 3; otherwise, it decreases by 1.

Find the value of T when the healths of all enemies become 0 or less.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq H_i \leq 10^9
• All input values are integers.

Sample Input 1

3
6 2 2

Sample Output 1

8

The actions are performed as follows:

• T becomes 1. Attack the 1st enemy, and its health becomes 6-1=5.
• T becomes 2. Attack the 1st enemy, and its health becomes 5-1=4.
• T becomes 3. Attack the 1st enemy, and its health becomes 4-3=1.
• T becomes 4. Attack the 1st enemy, and its health becomes 1-1=0.
• T becomes 5. Attack the 2nd enemy, and its health becomes 2-1=1.
• T becomes 6. Attack the 2nd enemy, and its health becomes 1-3=-2.
• T becomes 7. Attack the 3rd enemy, and its health becomes 2-1=1.
• T becomes 8. Attack the 3rd enemy, and its health becomes 1-1=0.

Sample Input 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

Sample Output 2

82304529

Sample Input 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Beware of integer overflow.

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

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

Sample Output 3

20

Problem Statement

There are N buildings, Building 1, Building 2, \ldots, Building N, arranged in a line in this order. The height of Building i (1 \leq i \leq N) is H_i.

For each i = 1, 2, \ldots, N, find the number of integers j (i < j \leq N) satisfying the following condition:

• There is no building taller than Building j between Buildings i and j.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq H_i \leq N
• H_i\neq H_j\ (i\neq j)
• All input values are integers.

Sample Input 1

5
2 1 4 3 5

Sample Output 1

3 2 2 1 0

For i=1, the integers j satisfying the condition are 2, 3, and 5: there are three. (Between Buildings 1 and 4, there is a building taller than Building 4, which is Building 3, so j=4 does not satisfy the condition.) Therefore, the first number in the output is 3.

Sample Input 2

4
1 2 3 4

Sample Output 2

3 2 1 0

Sample Input 3

10
1 9 6 5 2 7 10 4 8 3

Sample Output 3

2 3 3 3 2 1 2 1 1 0

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

There are N cards called card 1, card 2, \ldots, card N. On card i (1\leq i\leq N), an integer A_i is written.

For K=1, 2, \ldots, N, solve the following problem.

We have a bag that contains K cards: card 1, card 2, \ldots, card K.
Let us perform the following operation twice, and let x and y be the numbers recorded, in the recorded order.

Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag.

Print the expected value of \max(x,y), modulo 998244353 (see Notes).
Here, \max(x,y) denotes the value of the greater of x and y (or x if they are equal).

Notes

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} with two coprime integers P and Q, it can be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print this R.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 2\times 10^5
• All values in the input are integers.

Sample Input 1

3
5 7 5

Sample Output 1

5
499122183
443664163

For instance, the answer for K=2 is found as follows.

The bag contains card 1 and card 2, with A_1=5 and A_2=7 written on them, respectively.

• If you draw card 1 in the first draw and card 1 again in the second draw, we have x=y=5, so \max(x,y)=5.
• If you draw card 1 in the first draw and card 2 in the second draw, we have x=5 and y=7, so \max(x,y)=7.
• If you draw card 2 in the first draw and card 1 in the second draw, we have x=7 and y=5, so \max(x,y)=7.
• If you draw card 2 in the first draw and card 2 again in the second draw, we have x=y=7, so \max(x,y)=7.

These events happen with the same probability, so the sought expected value is \frac{5+7+7+7}{4}=\frac{13}{2}. We have 499122183\times 2\equiv 13 \pmod{998244353}, so 499122183 should be printed.

Sample Input 2

7
22 75 26 45 72 81 47

Sample Output 2

22
249561150
110916092
873463862
279508479
360477194
529680742