Problem Statement

The magnitude of an earthquake is a logarithmic scale of the energy released by the earthquake. It is known that each time the magnitude increases by 1, the amount of energy gets multiplied by approximately 32.
Here, we assume that the amount of energy gets multiplied by exactly 32 each time the magnitude increases by 1. In this case, how many times is the amount of energy of a magnitude A earthquake as much as that of a magnitude B earthquake?

Constraints

• 3\leq B\leq A\leq 9
• A and B are integers.

Sample Input 1

6 4

Sample Output 1

1024

6 is 2 greater than 4, so a magnitude 6 earthquake has 32\times 32=1024 times as much energy as a magnitude 4 earthquake has.

Sample Input 2

5 5

Sample Output 2

1

Earthquakes with the same magnitude have the same amount of energy.

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

• choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

• Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
• S and T have the same length.

Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.

Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.

Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

Problem Statement

You are given an integer N. Consider permuting the digits in N and separate them into two positive integers.

For example, for the integer 123, there are six ways to separate it, as follows:

• 12 and 3,
• 21 and 3,
• 13 and 2,
• 31 and 2,
• 23 and 1,
• 32 and 1.

Here, the two integers after separation must not contain leading zeros. For example, it is not allowed to separate the integer 101 into 1 and 01. Additionally, since the resulting integers must be positive, it is not allowed to separate 101 into 11 and 0, either.

What is the maximum possible product of the two resulting integers, obtained by the optimal separation?

Constraints

• N is an integer between 1 and 10^9 (inclusive).
• N contains two or more digits that are not 0.

Sample Input 1

123

Sample Output 1

63

As described in Problem Statement, there are six ways to separate it:

• 12 and 3,
• 21 and 3,
• 13 and 2,
• 31 and 2,
• 23 and 1,
• 32 and 1.

The products of these pairs, in this order, are 36, 63, 26, 62, 23, 32, with 63 being the maximum.

Sample Input 2

1010

Sample Output 2

100

There are two ways to separate it:

• 100 and 1,
• 10 and 10.

In either case, the product is 100.

Sample Input 3

998244353

Sample Output 3

939337176

Problem Statement

There is an online game with N registered players.
Today, which is the 10^{100}-th day since its launch, the developer Takahashi examined the users' login history. It turned out that the i-th player logged in for B_i consecutive days from Day A_i, where Day 1 is the launch day, and did not log in for the other days. In other words, the i-th player logged in on Day A_i, A_i+1, \ldots, A_i+B_i-1, and only on those days.
For each integer k such that 1\leq k\leq N, find the number of days on which exactly k players logged in.

Constraints

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

Sample Input 1

3
1 2
2 3
3 1

Sample Output 1

2 2 0

The first player logged in on Day 1, 2, the second player logged in on Day 2, 3, 4, and the third player logged in on Day 3 only.

Thus, we can see that Day 1, 4 had 1 player logged in, Day 2, 3 had 2 players logged in, and the other days had no players logged in.

The answer is: there were 2 days with exactly 1 player logged in, 2 days with exactly 2 players logged in, and 0 days with exactly 3 players logged in.

Sample Input 2

2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0 1000000000

There may be two or more players who logged in during the same period.

Problem Statement

Given is a sequence of N integers: A = (A_1, A_2, \dots, A_N).

Find the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the following condition:

• A'_1 \leq A'_k.

Since the count can be enormous, print it modulo 998244353.

Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

Constraints

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

Sample Input 1

3
1 2 1

Sample Output 1

3

A=(1,2,1) has four (not necessarily contiguous) subsequences of length at least 2: (1,2), (1,1), (2,1), (1,2,1).

Three of them, (1,2), (1,1), (1,2,1), satisfy the condition in Problem Statement.

Sample Input 2

3
1 2 2

Sample Output 2

4

Note that two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

In this Sample, there are four subsequences, (1,2), (1,2), (2,2), (1,2,2), that satisfy the condition.

Sample Input 3

3
3 2 1

Sample Output 3

0

There may be no subsequence that satisfies the condition.

Sample Input 4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

Sample Output 4

830

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1, 2, \ldots, N, and for each 1\leq i\leq N-1, the i-th edge connects Vertex U_i and Vertex V_i. Let D be the diameter of the tree. Find the number, modulo 998244353, of ways to choose two or more of the vertices and paint them red so that all distances between two red vertices are D.

Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of the tree is the maximum distance between two vertices.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq U_i,V_i \leq N
• U_i \neq V_i
• All values in input are integers.
• The given graph is a tree.

Sample Input 1

5
1 2
1 3
1 4
4 5

Sample Output 1

2

The given tree has five vertices and a diameter of 3.
There are just two pairs of vertices whose distance is 3: (2,5) and (3,5), so there are two ways to paint the tree to satisfy the condition: \lbrace 2,5\rbrace and \lbrace 3,5\rbrace .
Note that painting 2,3,5 does not satisfy the condition since the distance between Vertex 2 and Vertex 3 is 2.

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

4

The diameter is 2, and the four ways to paint the tree to satisfy the condition are: \lbrace 2,3\rbrace , \lbrace 2,4\rbrace , \lbrace 3,4\rbrace , \lbrace 2,3,4\rbrace .

Problem Statement

Consider an infinite two-dimensional coordinate plane. Takahashi, who is initially standing at (0,0), will do N jumps in one of the four directions he chooses every time: up, down, left, or right. The length of each jump is fixed. Specifically, the i-th jump should cover the distance of D_i. Determine whether it is possible to be exactly at (A, B) after N jumps. If it is possible, show one way to do so.

Here, for each direction, a jump of length D from (X, Y) takes him to the following point:

• up: (X,Y) \to (X,Y+D)
• down: (X,Y) \to (X,Y-D)
• left: (X,Y) \to (X-D,Y)
• right: (X,Y) \to (X+D,Y).

Constraints

• 1 \leq N \leq 2000
• \lvert A\rvert, \lvert B\rvert \leq 3.6\times 10^6
• 1 \leq D_i \leq 1800
• All values in input are integers.

Sample Input 1

3 2 -2
1 2 3

Sample Output 1

Yes
LDR

If he jumps left, down, right in this order, Takahashi moves (0,0)\to(-1,0)\to(-1,-2)\to(2,-2) and ends up at (2, -2), which is desired.

Sample Input 2

2 1 0
1 6

Sample Output 2

No

It is impossible to be exactly at (1, 0) after the two jumps.

Sample Input 3

5 6 7
1 3 5 7 9

Sample Output 3

Yes
LRLUR

Problem Statement

Given are positive integers N and M.

For each k=1,2,\ldots,N, find the following number and print it modulo 998244353.

• The number of multisets A containing k positive integers that satisfy both of the following conditions:
  • the sum of the elements of A is N;
  • for every positive integer x, A contains at most M occurrences of x.

Constraints

• 1 \leq M \leq N \leq 5000
• All values in input are integers.

Sample Input 1

4 2

Sample Output 1

1
2
1
0

• For k=1, there is one multiset A that satisfies the conditions: \{4\}.
• For k=2, there are two multisets A that satisfy the conditions: \{1,3\} and \{2,2\}.
• For k=3, there is one multiset A that satisfies the conditions: \{1,1,2\}.
• For k=4, there is no multiset A that satisfies the conditions.

Sample Input 2

7 7

Sample Output 2

1
3
4
3
2
1
1