Problem Statement

You are given an integer X between 1 and 10, inclusive.

Output the string obtained by deleting only the X-th character from the string HelloWorld.

Constraints

• X is an integer between 1 and 10, inclusive.

Sample Input 1

5

Sample Output 1

HellWorld

Deleting the 5-th character of HelloWorld gives HellWorld. Thus, output HellWorld.

Sample Input 2

9

Sample Output 2

HelloWord

Sample Input 3

1

Sample Output 3

elloWorld

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters.

Define N digits C_1, C_2, \ldots, C_N as follows:

• If the first character of S_i is one of a, b, c, then C_i= 2
• If the first character of S_i is one of d, e, f, then C_i= 3
• If the first character of S_i is one of g, h, i, then C_i= 4
• If the first character of S_i is one of j, k, l, then C_i= 5
• If the first character of S_i is one of m, n, o, then C_i= 6
• If the first character of S_i is one of p, q, r, s, then C_i= 7
• If the first character of S_i is one of t, u, v, then C_i= 8
• If the first character of S_i is one of w, x, y, z, then C_i= 9

Output the string obtained by concatenating C_1, C_2, \ldots, C_N in this order.

Constraints

• 1 \leq N \leq 10
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.

Sample Input 1

2
algorithm heuristic

Sample Output 1

24

• The first character of S_1= algorithm is a, so C_1= 2.
• The first character of S_2= heuristic is h, so C_2= 4.

Thus, output 24, which is their concatenation.

Sample Input 2

3
i love you

Sample Output 2

459

Problem Statement

There are N cells arranged in a row from left to right. Initially, no blocks are placed in any cell.

You are given Q queries, so process them in order. Each query is one of the following two types:

• 1 x: Place 1 block in the x-th cell from the left. Then, if every cell has at least 1 block, remove 1 block from every cell.
• 2 y: Output the number of cells that have at least y blocks.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq Q \leq 3 \times 10^5
• 1 \leq x \leq N
• 1 \leq y \leq 3 \times 10^5
• All input values are integers.
• At least one query of the second type exists.

Sample Input 1

3 7
1 1
1 3
1 3
2 1
2 2
1 2
2 1

Sample Output 1

2
1
1

N=3, and initially the numbers of blocks placed in the 1-st, 2-nd, 3-rd cells from the left are (0, 0, 0). The queries are processed in order as follows:

• Place 1 block in the 1-st cell from the left. There exist cells with no blocks, so no further action is taken. The numbers of blocks in the 1-st, 2-nd, 3-rd cells become (1, 0, 0).
• Place 1 block in the 3-rd cell from the left. The numbers of blocks in the 1-st, 2-nd, 3-rd cells become (1, 0, 1).
• Place 1 block in the 3-rd cell from the left. The numbers of blocks in the 1-st, 2-nd, 3-rd cells become (1, 0, 2).
• The cells with at least 1 block are the 1-st and 3-rd cells from the left, so there are 2 such cells. Thus, output 2.
• The cells with at least 2 blocks is only the 3-rd cell from the left, so there is 1 such cell. Thus, output 1.
• Place 1 block in the 2-nd cell from the left. At this point, every cell has at least 1 block, so 1 block is removed from every cell. The numbers of blocks in the 1-st, 2-nd, 3-rd cells become (0, 0, 1).
• The cells with at least 1 block is only the 3-rd cell from the left, so there is 1 such cell. Thus, output 1.

Thus, output 2, 1, 1 in this order, one per line.

Problem Statement

You are given a string S consisting of lowercase English letters.

Determine whether it is possible to rearrange the characters of S so that no two adjacent characters are the same, and if so, find one such rearrangement.

You are given T test cases; solve each.

Constraints

• 1 \le T \le 3 \times 10^5
• S is a string of length between 1 and 10^6, inclusive, consisting of lowercase English letters.
• The total length of S across all test cases is at most 10^6.

Sample Input 1

3
aiiw
doodoo
aabbababcacababaaba

Sample Output 1

Yes
iwai
No
Yes
ababacabababacababa

Consider the first test case.

iwai is a rearrangement of aiiw in which no two adjacent characters are the same. Thus, outputting iwai is correct.

Other correct outputs include wiai and iawi.

Problem Statement

There is a rooted tree T with N vertices, where the vertices are numbered as vertex 1, vertex 2, \ldots, vertex N.
Vertex 1 is the root of T, and the (direct) parent of vertex i (2 \leq i \leq N) is P_i.

Additionally, vertex i (1 \leq i \leq N) has C_i candies. All (C_1 + C_2 + \cdots + C_N) candies are distinguishable from each other.

Takahashi gave instructions to N squirrels. Specifically, he gave the following instruction to the i-th squirrel (1 \leq i \leq N):

• Choose and collect D_i candies from the subtree rooted at vertex i.

Different squirrels cannot take the same candy.
Output the number, modulo 998244353, of possible ways to choose the candies.

Here, even if the set of candies ultimately chosen is the same, if the squirrels that chose them are different, they are counted as different ways.
If it is impossible for all squirrels to bring back candies as instructed, output 0.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N
• 1 \leq C_i \leq 10^9
• 1 \leq D_i
• D_1 + D_2 + \cdots + D_N \leq 10^6
• All input values are integers.
• T is a rooted tree with vertex 1 as the root.

Sample Input 1

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

Sample Output 1

144

We call the candies so that we have candy 1 at vertex 1, candies 2, 3 at vertex 2, candy 4 at vertex 3, candies 5, 6 at vertex 4, and candies 7, 8, 9 at vertex 5.

One possible way to choose the candies is as follows:

• Squirrel 1 collects candy 3 from the tree rooted at vertex 1 (consisting of vertices 1, 2, 3, 4, 5).
• Squirrel 2 collects candy 2 from the tree rooted at vertex 2 (consisting of vertex 2).
• Squirrel 3 collects candies 4, 7, 9 from the tree rooted at vertex 3 (consisting of vertices 3, 4, 5).
• Squirrel 4 collects candy 6 from the tree rooted at vertex 4 (consisting of vertex 4 only).
• Squirrel 5 collects candy 8 from the tree rooted at vertex 5 (consisting of vertex 5 only).

Note that this is counted as a different way from the following:

• Squirrel 1 collects candy \mathbf{2} from the tree rooted at vertex 1 (consisting of vertices 1, 2, 3, 4, 5).
• Squirrel 2 collects candy \mathbf{3} from the tree rooted at vertex 2 (consisting of vertex 2).
• Squirrel 3 collects candies 4, 7, 9 from the tree rooted at vertex 3 (consisting of vertices 3, 4, 5).
• Squirrel 4 collects candy 6 from the tree rooted at vertex 4 (consisting of vertex 4 only).
• Squirrel 5 collects candy 8 from the tree rooted at vertex 5 (consisting of vertex 5 only).

There are 144 valid ways in total, so output 144 modulo 998244353, that is, 144.

Sample Input 2

2
1
1 1
2 1

Sample Output 2

0

The tree has only two candies across vertices 1 and 2, so it is impossible for both squirrels to collect candies as instructed.
Thus, output 0.

Sample Input 3

3
3 1
1000000000 1 1
1 1 1

Sample Output 3

1755647

Remember to output the count modulo 998244353.

Problem Statement

You are given a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) of length N.

You can perform the following operation on A zero or more times:

• Choose an integer i with 1 \le i \le N - 1, decrease A_i by 1, and increase A_{i+1} by 1.

Find the minimum number of operations required to make A strictly increasing.

It can be proved that the answer is less than 2^{63}.

You are given T test cases; solve each.

Constraints

• 1 \le T \le 3 \times 10^5
• 1 \le N \le 2 \times 10^5
• 0 \le A_i \le 10^9
• The sum of N across all test cases is at most 6 \times 10^5.
• All input values are integers.

Sample Input 1

4
3
0 1 0
4
4 6 3 5
7
1 2 3 4 5 6 7
10
11 9 1 3 17 19 10 19 17 3

Sample Output 1

3
5
0
78

Consider the first test case.

By performing the following operations, A can be made strictly increasing in three operations:

• Choose i=1. A becomes (-1, 2, 0).
• Choose i=2. A becomes (-1, 1, 1).
• Choose i=2. A becomes (-1, 0, 2).

It is impossible to make A strictly increasing in fewer than three operations, so output 3.

Problem Statement

You are given integers A, B, X, Y.

A piece is placed on a two-dimensional plane. Initially, the piece is at coordinates (0, 0).

You can perform the following operation zero or more times:

• Let (x, y) be the current coordinates of the piece. Move the piece to coordinates (x', y') satisfying one of the following conditions:
  • |x - x'| = A and |y - y'| = B
  • |x - x'| = B and |y - y'| = A

Determine whether it is possible to move the piece to coordinates (X, Y), and if so, find the minimum number of operations required.

You are given T test cases; solve each.

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le A < B \le 10^6
• 0 \le X, Y \le 10^6
• All input values are integers.

Sample Input 1

4
1 2 1 0
4 6 3 5
459 2026 0 0
19 2026 523 459459

Sample Output 1

3
-1
0
2670

Consider the first test case.

By moving the piece from (0, 0) to (1, 2), then to (-1, 1), then to (1, 0) in order, the piece can be moved to coordinates (1, 0) in three operations.

It is impossible to move the piece to coordinates (1, 0) in fewer than three operations, so output 3 on the first line.