Problem Statement

You are given a string S of length N.
Output the string obtained by removing all leading consecutive os from S.
If all characters in S are o, output an empty string.

Constraints

• N is an integer satisfying 1 \le N \le 50.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

7
ooparts

Sample Output 1

parts

Removing all leading consecutive os from ooparts gives parts.

Sample Input 2

6
abcooo

Sample Output 2

abcooo

The first character may not be o.

Sample Input 3

5
ooooo

Sample Output 3

All characters may be o.

Problem Statement

In a certain measurement, the sensor readings at times 0,1,\dots,T are recorded according to the following rules.

• At time 0, the reading is saved.
• At times 1,2,\dots,T, the reading is saved if and only if the absolute difference between the current reading and the most recently saved reading is at least X.

The sensor reading at time i=0,1,\dots,T was A_i.

Output the times at which readings were saved and the saved values, in ascending order of time.

Constraints

• 1 \le T \le 100
• 1 \le X \le 100
• 0 \le A_i \le 100
• All input values are integers.

Sample Input 1

6 10
30 35 40 21 30 12 31

Sample Output 1

0 30
2 40
3 21
6 31

The measurement proceeds as follows.

• The reading at time 0 is 30. Save it.
• The reading at time 1 is 35. The most recently saved reading is 30, and the absolute difference is less than 10, so it is not saved.
• The reading at time 2 is 40. The most recently saved reading is 30, and the absolute difference is at least 10, so it is saved.
• The reading at time 3 is 21. The most recently saved reading is 40, and the absolute difference is at least 10, so it is saved.
• The reading at time 4 is 30. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
• The reading at time 5 is 12. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
• The reading at time 6 is 31. The most recently saved reading is 21, and the absolute difference is at least 10, so it is saved.

Problem Statement

Takahashi is at coordinate 0.5 on a number line.

He will make N moves.
In the i-th move, he chooses either the positive direction or the negative direction, and moves L_i in that direction.

What is the maximum number of times he can pass through coordinate 0?
Under the constraints of this problem, no move will end at coordinate 0.

Constraints

• 1 \le N \le 20
• 1 \le L_i \le 10^9
• All input values are integers.

Sample Input 1

5
2 5 2 2 1

Sample Output 1

4

For example, by choosing the directions of movement as follows, he can pass through coordinate 0 four times, which is the maximum.

• In the first move, choose the negative direction and move 2. He moves from coordinate 0.5 to -1.5, passing through coordinate 0.
• In the second move, choose the positive direction and move 5. He moves from coordinate -1.5 to 3.5, passing through coordinate 0.
• In the third move, choose the negative direction and move 2. He moves from coordinate 3.5 to 1.5.
• In the fourth move, choose the negative direction and move 2. He moves from coordinate 1.5 to -0.5, passing through coordinate 0.
• In the fifth move, choose the positive direction and move 1. He moves from coordinate -0.5 to 0.5, passing through coordinate 0.

Sample Input 2

5
100 1 2 3 4

Sample Output 2

1

Sample Input 3

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

20

Problem Statement

There is a grid of H rows \times W columns, and Takahashi moves through this grid up, down, left, and right.
The state of the cell at the i-th row from the top and j-th column from the left (1\leq i\leq H, 1\leq j\leq W) is represented by the character S_{i,j}.
S_{i,j} is one of #, ., o, x, S, G.

• If S_{i,j}=#: This cell cannot be entered.
• If S_{i,j}=.: This cell can be freely entered and exited. That is, after entering this cell, Takahashi can move to any adjacent cell (if it exists) in the up, down, left, or right direction.
• If S_{i,j}=o: In this cell, Takahashi must move in the same direction as the immediately preceding move. That is, after entering this cell, he must move to the next cell without changing direction.
• If S_{i,j}=x: In this cell, Takahashi cannot move in the same direction as the immediately preceding move. That is, after entering this cell, he must change direction to move to the next cell. Turning 180 degrees to return to the previous cell is considered as changing direction.
• If S_{i,j}=S: This cell is Takahashi's starting position. This cell can be freely entered and exited.
• If S_{i,j}=G: This cell is Takahashi's destination. This cell can be freely entered and exited.

There is exactly one (i,j) with 1\leq i\leq H, 1\leq j\leq W satisfying S_{i,j}=S, and exactly one satisfying S_{i,j}=G.

Takahashi wants to reach the destination by repeatedly moving to adjacent cells up, down, left, or right from his starting position.
Determine whether this is possible, and if so, output one valid sequence of moves with at most 5\times 10^6 moves between adjacent cells.
It can be proved that if a valid sequence of moves exists under the problem's conditions, then there exists one with at most 5\times 10^6 moves.
As long as the number of moves is at most 5\times 10^6, it is not necessary to minimize the number of moves.

Constraints

• 1 \leq H,W\leq 1000
• S_{i,j} is one of #, ., o, x, S, G.
• There is exactly one (i,j) satisfying S_{i,j}=S and exactly one satisfying S_{i,j}=G.
• H and W are integers.

Sample Input 1

3 5
.#...
.Sooo
..x.G

Sample Output 1

Yes
DRUUDDRR

Let cell (i,j) denote the cell at the i-th row from the top and j-th column from the left.
Following the sample output, the path goes: cell (2,2) \to cell (3,2) \to cell (3,3) \to cell (2,3) \to cell (1,3) \to cell (2,3) \to cell (3,3) \to cell (3,4) \to cell (3,5), reaching the destination.
Other solutions such as DRUURLRRDD are also accepted. On the other hand, since Takahashi cannot go straight through cell (3,3), solutions such as DRRR are not accepted.

Sample Input 2

3 3
#So
xoG
..#

Sample Output 2

Yes
DDLURR

Sample Input 3

2 2
So
oG

Sample Output 3

No

It is impossible to reach the destination while satisfying the conditions.

Problem Statement

Divide N players, player 1, player 2, \ldots, player N, into two (distinguishable) teams A and B satisfying all of the following conditions.

• Each team consists of at least one player.
• Each player belongs to either team A or team B, but not both.
• The number of players in the team that player i belongs to is at least L_i and at most R_i.

Find the number of ways to divide the players satisfying the conditions, and output the count modulo 998244353.
Two divisions are considered different if there exists a player who belongs to different teams in the two divisions.

Constraints

• 2\leq N\leq 2\times 10^5
• 1\leq L_i\leq R_i\leq N-1
• All input values are integers.

Sample Input 1

3
1 1
1 2
2 2

Sample Output 1

2

The following two divisions satisfy the conditions.

• Player 1: Team A, Player 2: Team B, Player 3: Team B
• Player 1: Team B, Player 2: Team A, Player 3: Team A

Since 2 modulo 998244353 is 2, output 2.

Sample Input 2

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

Sample Output 2

30

There are 30 valid divisions.

Problem Statement

You are given a tree with N vertices.
The vertices are numbered vertex 1, vertex 2, \ldots, vertex N, and the i-th edge (1\leq i\leq N-1) connects vertices U_i and V_i.

Takahashi will color each vertex with one of colors 1, 2, \ldots, K.
Color i can be used to color at most C_i vertices.

Determine whether it is possible to color the vertices satisfying the following condition, and if so, output one valid coloring.

• For every edge, there exists some i (1\leq i\leq K) such that both of the two subtrees obtained by cutting the tree at that edge contain at least one vertex colored with color i.

You are given T test cases; solve each of them.

Constraints

• 1\leq T\leq 10^5
• 2\leq N\leq 3\times 10^5
• 1\leq K\leq N
• 1\leq U_i,V_i\leq N
• The given graph is a tree.
• 1\leq C_i\leq N
• C_1+C_2+\cdots+C_K\geq N
• All input values are integers.
• The sum of N over all test cases does not exceed 3\times 10^5.

Sample Input 1

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

Sample Output 1

3 2 2 1 1
-1

For the first test case, suppose the vertices are colored as in the sample output.
That is, vertex 1 is colored with color 3, vertex 2 with color 2, vertex 3 with color 2, vertex 4 with color 1, and vertex 5 with color 1.

If we cut the edge connecting vertices 1 and 2, the tree splits into the subtree consisting of vertices 1,3 and the subtree consisting of vertices 2,4,5; both subtrees contain a vertex colored with color 2 (vertex 3 or vertex 2, respectively).
Such a color exists no matter which edge of the given tree is cut, so the coloring in the sample output satisfies the condition.

For the second test case, there is no valid coloring satisfying the condition.

Problem Statement

There are N sequences of length M: A_1,A_2,\dots,A_N. Initially, all elements of all sequences are 0.
Hereafter, the j-th element of sequence A_i is denoted by A_{i,j}.

Process the following three types of queries in the given order, Q queries in total.

• Type 1: Overwrite sequence A_{X_i} with sequence A_{Y_i}. That is, for every integer j (1 \le j \le M), change A_{X_i,j} to A_{Y_i,j}.
• Type 2: Change the Y_i-th element of sequence A_{X_i}, that is, A_{X_i,Y_i}, to Z_i.
• Type 3: For sequence A_{X_i}, output the sum of elements from the L_i-th through the R_i-th, that is, A_{X_i,L_i}+A_{X_i,L_i+1}+\dots+A_{X_i,R_i}.

Constraints

• 1 \le N,M \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• Type 1 queries satisfy the following constraints:
  • 1 \le X_i,Y_i \le N
• Type 2 queries satisfy the following constraints:
  • 1 \le X_i \le N
  • 1 \le Y_i \le M
  • 0 \le Z_i \le 10^9
• Type 3 queries satisfy the following constraints:
  • 1 \le X_i \le N
  • 1 \le L_i \le R_i \le M
• All input values are integers.

Sample Input 1

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

Sample Output 1

15
18
10

In this input, prepare four sequences of length 5.

• In the 1st query, set A_{2,1}=2. At this point, A_2=(2,0,0,0,0).
• In the 2nd query, set A_{2,2}=7. At this point, A_2=(2,7,0,0,0).
• In the 3rd query, set A_{2,4}=8. At this point, A_2=(2,7,0,8,0).
• In the 4th query, overwrite sequence A_1 with sequence A_2. At this point, A_1=(2,7,0,8,0).
• In the 5th query, set A_{2,3}=1. At this point, A_2=(2,7,1,8,0).
• In the 6th query, overwrite sequence A_3 with sequence A_2. At this point, A_3=(2,7,1,8,0).
• In the 7th query, set A_{3,2}=10. At this point, A_3=(2,10,1,8,0).
• In the 8th query, output A_{1,2}+A_{1,3}+A_{1,4}=7+0+8=15.
• In the 9th query, output A_{2,1}+A_{2,2}+A_{2,3}+A_{2,4}=2+7+1+8=18.
• In the 10th query, output A_{3,2}=10.