Problem Statement

The Eastern Army and the Western Army are at war in a certain capital.

Takahashi recorded information about the fighting forces as a string S.
S contains only the characters E and W, and the number of Es in S equals the number of soldiers in the Eastern Army, and the number of Ws equals the number of soldiers in the Western Army.

Given the string S that Takahashi recorded, output East if the Eastern Army has more soldiers than the Western Army, or West if the Western Army has more soldiers than the Eastern Army.

The length of S is guaranteed to be odd. Thus, it can be proved that exactly one of the two armies strictly outnumbers the other (that is, the two armies cannot have the same number of soldiers).

Constraints

• S is a string of length between 1 and 99, inclusive, consisting of E and W.
• The length of S is odd.

Sample Input 1

EEWEW

Sample Output 1

East

S contains three Es and two Ws, so the Eastern Army has three soldiers and the Western Army has two soldiers.
Since the Eastern Army has more soldiers than the Western Army, output East.

Sample Input 2

WWWWWWW

Sample Output 2

West

S contains zero Es and seven Ws, so the Eastern Army has zero soldiers and the Western Army has seven soldiers.
Since the Western Army has more soldiers than the Eastern Army, output West.

Problem Statement

There is a black-and-white image of height H pixels and width W pixels. The color of the pixel at the i-th row from the top and j-th column from the left is given as a character C_{i,j}, where . represents white and # represents black.

From the top, bottom, left, and right edges of this image, remove rows and columns where all pixels are white. Specifically, perform the following operations in order:

1. While the topmost row of the image is entirely white, repeat removing the topmost row.
2. While the bottommost row of the image is entirely white, repeat removing the bottommost row.
3. While the leftmost column of the image is entirely white, repeat removing the leftmost column.
4. While the rightmost column of the image is entirely white, repeat removing the rightmost column.

Output the image after processing.

The given image contains at least one black pixel.

Constraints

• 1 \le H, W \le 50
• C_{i,j} is . or #.
• At least one black pixel exists.

Sample Input 1

4 5
.....
..#..
.###.
.....

Sample Output 1

.#.
###

You should remove one row from the top edge, one row from the bottom edge, one column from the left edge, and one column from the right edge.

Sample Input 2

3 4
#...
....
...#

Sample Output 2

#...
....
...#

In this image, all of the topmost row, bottommost row, leftmost column, and rightmost column contain black pixels.
Therefore, without removing any rows or columns, you should output the original image as is.

Sample Input 3

5 6
......
......
...#..
......
......

Sample Output 3

#

Problem Statement

Takahashi observed N birds, numbered 1, 2, \dots, N, over M days.
Each of the birds that Takahashi observed has one of N colors, numbered 1, 2, \dots, N, and these birds have an interesting characteristic: their color can change during the observation period.

Bird i had color A_i in observations on or before day D_i - 1, and color B_i in observations on or after day D_i.
Here, if D_i = 1, then the bird's color was B_i from the observation on day 1, and if A_i = B_i, then the bird's color did not change during the observation period.

For each j = 1, 2, \dots, M, find the number of different colors of birds on day j.

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le M \le 3 \times 10^5
• 1 \le A_i, B_i \le N
• 1 \le D_i \le M
• All input values are integers.

Sample Input 1

6 7
1 3 2
2 6 5
5 5 1
3 3 5
4 1 6
6 3 6

Sample Output 1

5
5
3
3
4
4
4

In this input, six birds are observed over seven days.

• On day 1, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
• On day 2, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
• On day 3, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
• On day 4, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
• On day 5, the color of each bird was 2, 2, 1, 5, 6, 6. There are 4 different colors in total.
• On day 6, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.
• On day 7, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.

Problem Statement

The weather for the upcoming N days is given as a string S.
If the i-th character of S is S, then the weather on day i is sunny; if it is R, then the weather on day i is rainy.
Also, your current happiness is 0.

You can perform the following operation any number of times, possibly zero:

• Choose an integer i with 1 \le i \le N.
• If the weather on day i is sunny, change it to rainy; if it is rainy, change it to sunny.
• However, if you change the weather on day i, your happiness decreases by X_i.

After performing the operations, your happiness increases based on the final weather according to the following condition:

• For each integer i with 1 \le i \le N-1, if the weather on day i after modification is rainy and the weather on day i+1 is sunny, your happiness increases by Y_i.

Find the maximum value of happiness achievable by performing operations.

T test cases are given; solve each.

Constraints

• 1 \le T \le 10^4
• N is an integer between 2 and 2 \times 10^5, inclusive.
• S is a string of length N consisting of S and R.
• X_i is an integer between 1 and 10^9, inclusive.
• Y_i is an integer between 1 and 10^9, inclusive.
• The sum of N in a single input is at most 2 \times 10^5.

Sample Input 1

5
6
SRRRSR
3 1 4 1 5 9
2 6 5 3 5
6
RSRSRS
10 10 10 10 10 10
1 1 1 1 1
2
RR
4 3
2
10
RSSRSSRSSR
75 49 79 37 16 9 38 49 69 54
23 100 73 63 66 23 51 65 67
20
SSSRSSSRRRRSSRSSRSSR
343191362 223147518 135066250 426658267 693515093 8023388 383375974 712283203 40447501 19870690 318452142 356265717 283999278 209219229 418603824 39363351 392058270 254796273 110117486 64951139
576697130 385986330 895027325 654885799 784214084 577658764 761714876 583039741 943991250 446493376 701505924 402891440 963636095 919408713 238125227 871191978 843843821 397910552 529447424

Sample Output 1

5
3
0
165
5201284760

This input contains five test cases.

For the first test case, for example, you can maximize happiness by performing the following operations:

• Change the weather on day 3 from rainy to sunny. Happiness decreases by X_3 = 4, and the weather on each day becomes sunny, rainy, sunny, rainy, sunny, rainy.
• As a result of this operation, since day 2 is rainy and day 3 is sunny, happiness increases by Y_2 = 6, and since day 4 is rainy and day 5 is sunny, happiness increases by Y_4 = 3.
• The total happiness is (-4) + 6 + 3 = 5, which is the achievable maximum.

For the second and third test cases, performing no operations may be optimal.

For the fifth test case, note that the answer may not fit in a 32-bit integer type.

Problem Statement

There is an H \times W grid. Initially, every cell has A written on it. The cell at the i-th row from the top and j-th column from the left is denoted by (i, j).

We will perform Q operations in order.
In the i-th operation, overwrite all cells in the rectangle with upper-left cell (1, 1) and lower-right cell (R_i, C_i) with the uppercase English letter X_i.

Output the grid after all operations have been performed.

Constraints

• 1 \le H, W
• H \times W \le 10^6
• 1 \le Q \le 2 \times 10^5
• 1 \le R_i \le H
• 1 \le C_i \le W
• X_i is an uppercase English letter.
• All input numbers are integers.

Sample Input 1

2 3 3
2 2 B
1 3 C
2 1 D

Sample Output 1

DCC
DBA

The operations proceed as shown in the figure.

Sample Input 2

1 7 7
1 7 E
1 6 C
1 5 N
1 4 A
1 3 V
1 2 D
1 1 A

Sample Output 2

ADVANCE

Sample Input 3

10 10 15
8 9 B
6 7 C
5 8 D
10 6 E
8 5 F
3 10 G
7 3 H
4 6 I
3 1 J
10 2 K
3 6 L
3 3 M
2 5 N
9 1 O
1 4 P

Sample Output 3

PPPPNLGGGG
ONNNNLGGGG
OMMLLLGGGG
OKIIIIDDBA
OKHFFEDDBA
OKHFFECBBA
OKHFFEBBBA
OKFFFEBBBA
OKEEEEAAAA
KKEEEEAAAA

Problem Statement

Kowasugi Bank has N safes. Safe i contains A_i yen.

One day, a robber entered the bank. The robber repeats the following operation until the total amount stolen reaches at least X yen:

• Choose one safe uniformly at random from the safes not yet opened, open it, and steal all the money inside.

Find the expected value, modulo 998244353, of the total amount stolen by the robber.

Constraints

• 1 \le N \le 40
• 1 \le A_i \le 10^{16}
• 1 \le X \le \sum_{i=1}^{N} A_i
• All input values are integers.

Sample Input 1

2 5
3 10

Sample Output 1

499122188

There are two choices for the first safe to open.
If safe 1 is opened first, the robber also opens safe 2, so the total amount stolen is 13 yen.
If safe 2 is opened first, the total already reaches at least X yen at that point, so the total amount stolen is 10 yen.
Thus, the expected value is \frac{13 + 10}{2} = \frac{23}{2}.

Sample Input 2

3 2
1 1 1

Sample Output 2

2

Regardless of the order in which they are opened, the total amount stolen when two safes have been opened is 2 yen. Thus, the expected value is 2.

Sample Input 3

11 60
2 3 5 7 11 13 17 19 23 29 31

Sample Output 3

525950964

Problem Statement

The weather for the upcoming N days is given as a string S.
If the i-th character of S is S, then the weather on day i is sunny; if it is R, then the weather on day i is rainy.

You can perform the following operation between 0 and k times, inclusive:

• Choose an integer i with 1 \le i \le N.
• If the weather on day i is sunny, change it to rainy; if it is rainy, change it to sunny.

After performing the operations, you gain happiness based on the final weather according to the following condition:

• For each integer i with 1 \le i \le N-1, if the weather on day i after modification is rainy and the weather on day i+1 is sunny, your happiness increases by 1.

For each k = 0, 1, \dots, N, find the maximum total happiness you can gain by performing the operation at most k times.

T test cases are given; solve each.

Constraints

• 1 \le T \le 10^4
• N is an integer between 2 and 10^6, inclusive.
• S is a string of length N consisting of S and R.
• The sum of N in a single input is at most 10^6.

Sample Input 1

5
4
SSSR
2
SR
6
RSRSRS
10
RSRSRRRRRR
20
SSRRSSSSRRRSSRRSRSRS

Sample Output 1

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

This input contains five test cases.

For the 1st test case:

• The weather on each day before any operations is sunny, sunny, sunny, rainy in order.
• For k = 0, no operations can be performed.
  • The weather on each day after operations is sunny, sunny, sunny, rainy, and the total happiness is 0, which is the achievable maximum.
• For k = 1, for example, changing the weather on day 2 is optimal.
  • The weather on each day after operations is sunny, rainy, sunny, rainy, and the total happiness is 1, which is the achievable maximum.
• For k = 2, for example, changing the weather on days 1 and 2 is optimal.
  • The weather on each day after operations is rainy, rainy, sunny, rainy, and the total happiness is 1, which is the achievable maximum.
• For k = 3, for example, changing the weather on days 1, 3, and 4 is optimal.
  • The weather on each day after operations is rainy, sunny, rainy, sunny, and the total happiness is 2, which is the achievable maximum.
• For k = 4, for example, changing the weather on days 1, 3, and 4 is optimal.
  • The weather on each day after operations is rainy, sunny, rainy, sunny, and the total happiness is 2, which is the achievable maximum.