Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i \leq 10^9
• 0 \leq Y_i \leq 10^9
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All X_i and Y_i are integers.
• S is a string of length N consisting of L and R.

Sample Input 1

3
2 3
1 1
4 1
RRL

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

2
1 1
2 1
RR

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

Sample Output 3

Yes

Problem Statement

There are N toys numbered from 1 to N, and N-1 boxes numbered from 1 to N-1. Toy i\ (1 \leq i \leq N) has a size of A_i, and box i\ (1 \leq i \leq N-1) has a size of B_i.

Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:

1. Choose an arbitrary positive integer x and purchase one box of size x.
2. Place each of the N toys into one of the N boxes (the N-1 existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy's size, and no box can contain two or more toys.

He wants to execute step 2 by purchasing a sufficiently large box in step 1, but larger boxes are more expensive, so he wants to purchase the smallest possible box.

Determine whether there exists a value of x such that he can execute step 2, and if it exists, find the minimum such x.

Constraints

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

Sample Input 1

4
5 2 3 7
6 2 8

Sample Output 1

3

Consider the case where x=3 (that is, he purchases a box of size 3 in step 1).

If the newly purchased box is called box 4, toys 1,\dots,4 have sizes of 5, 2, 3, and 7, respectively, and boxes 1,\dots,4 have sizes of 6, 2, 8, and 3, respectively. Thus, toy 1 can be placed in box 1, toy 2 in box 2, toy 3 in box 4, and toy 4 in box 3.

On the other hand, if x \leq 2, it is impossible to place all N toys into separate boxes. Therefore, the answer is 3.

Sample Input 2

4
3 7 2 5
8 1 6

Sample Output 2

-1

No matter what size of box is purchased in step 1, no toy can be placed in box 2, so it is impossible to execute step 2.

Sample Input 3

8
2 28 17 39 57 56 37 32
34 27 73 28 76 61 27

Sample Output 3

37

Problem Statement

Your computer has a keyboard with three keys: 'a' key, Shift key, and Caps Lock key. The Caps Lock key has a light on it. Initially, the light on the Caps Lock key is off, and the screen shows an empty string.

You can do the following three actions any number of times in any order:

• Spend X milliseconds to press only the 'a' key. If the light on the Caps Lock key is off, a is appended to the string on the screen; if it is on, A is.
• Spend Y milliseconds to press the 'a' key and Shift key simultaneously. If the light on the Caps Lock key is off, A is appended to the string on the screen; if it is on, a is.
• Spend Z milliseconds to press the Caps Lock key. If the light on the Caps Lock key is off, it turns on; if it is on, it turns off.

Given a string S consisting of A and a, determine at least how many milliseconds you need to spend to make the string shown on the screen equal to S.

Constraints

• 1 \leq X,Y,Z \leq 10^9
• X, Y, and Z are integers.
• 1 \leq |S| \leq 3 \times 10^5
• S is a string consisting of A and a.

Sample Input 1

1 3 3
AAaA

Sample Output 1

9

The following sequence of actions makes the string on the screen equal to AAaA in 9 milliseconds, which is the shortest possible.

• Spend Z(=3) milliseconds to press the CapsLock key. The light on the Caps Lock key turns on.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend Y(=3) milliseconds to press the Shift key and 'a' key simultaneously. a is appended to the string on the screen.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.

Sample Input 2

1 1 100
aAaAaA

Sample Output 2

6

Sample Input 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

Sample Output 3

40

Problem Statement

Aoki, an employee at AtCoder Inc., has his salary for this month determined by an integer N and a sequence A of length N as follows.
First, he is given an N-sided die (dice) that shows the integers from 1 to N with equal probability, and a variable x=0.

Then, the following steps are repeated until terminated.

• Roll the die once and let y be the result.
  • If x<y, pay him A_y yen and let x=y.
  • Otherwise, terminate the process.

Aoki's salary for this month is the total amount paid through this process.
Find the expected value of Aoki's salary this month, modulo 998244353.

Constraints

• All inputs are integers.
• 1 \le N \le 3 \times 10^5
• 0 \le A_i < 998244353

Sample Input 1

3
3 2 6

Sample Output 1

776412280

Here is an example of how the process goes.

• Initially, x=0.
• Roll the die once, and it shows 1. Since 0<1, pay him A_1 = 3 yen and let x=1.
• Roll the die once, and it shows 3. Since 1<3, pay him A_3 = 6 yen and let x=3.
• Roll the die once, and it shows 1. Since 3 \ge 1, terminate the process.

In this case, his salary for this month is 9 yen.

It can be calculated that the expected value of his salary this month is \frac{49}{9} yen, whose representation modulo 998244353 is 776412280.

Sample Input 2

1
998244352

Sample Output 2

998244352

Sample Input 3

9
3 14 159 2653 58979 323846 2643383 27950288 419716939

Sample Output 3

545252774

Problem Statement

We have a grid with H rows and W columns. Each square is painted either white or black. For each integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, the color of the square at the i-th row from the top and j-th column from the left (we simply denote this square by Square (i, j)) is represented by A_{i, j}. Square (i, j) is white if A_{i, j} = 0, and black if A_{i, j} = 1.

You may perform the following operations any number of (possibly 0) times in any order:

• Choose an integer i such that 1 \leq i \leq H, pay R_i yen (the currency in Japan), and invert the color of each square in the i-th row from the top in the grid. (White squares are painted black, and black squares are painted white.)
• Choose an integer j such that 1 \leq j \leq W, pay C_j yen, and invert the color of each square in the j-th column from the left in the grid.

Print the minimum total cost to satisfy the following condition:

• There exists a path from Square (1, 1) to Square (H, W) that can be obtained by repeatedly moving down or to the right, such that all squares in the path (including Square (1, 1) and Square (H, W)) have the same color.

We can prove that it is always possible to satisfy the condition in a finite number of operations under the Constraints of this problem.

Constraints

• 2 \leq H, W \leq 2000
• 1 \leq R_i \leq 10^9
• 1 \leq C_j \leq 10^9
• A_{i, j} \in \lbrace 0, 1\rbrace
• All values in input are integers.

Sample Input 1

3 4
4 3 5
2 6 7 4
0100
1011
1010

Sample Output 1

9

We denote a white square by 0 and a black square by 1. On the initial grid, you can pay R_2 = 3 yen to invert the color of each square in the 2-nd row from the top to make the grid:

0100
0100
1010

Then, you can pay C_2 = 6 yen to invert the color of each square in the 2-nd row from the left to make the grid:

0000
0000
1110

Now, there exists a path from Square (1, 1) to Square (3, 4) such that all squares in the path have the same color (such as the path (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)). The total cost paid is 3+6 = 9 yen, which is the minimum possible.

Sample Input 2

15 20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78
39 97 12 53 62 32 38 84 49 93 53 26 13 25 2 76 32 42 34 18
01011100110000001111
10101111100010011000
11011000011010001010
00010100011111010100
11111001101010001011
01111001100101011100
10010000001110101110
01001011100100101000
11001000100101011000
01110000111011100101
00111110111110011111
10101111111011101101
11000011000111111001
00011101011110001101
01010000000001000000

Sample Output 2

125