Problem Statement

Takahashi has two sheets A and B, each composed of black squares and transparent squares, and an infinitely large sheet C composed of transparent squares.
There is also an ideal sheet X for Takahashi composed of black squares and transparent squares.

The sizes of sheets A, B, and X are H_A rows \times W_A columns, H_B rows \times W_B columns, and H_X rows \times W_X columns, respectively.
The squares of sheet A are represented by H_A strings of length W_A, A_1, A_2, \ldots, A_{H_A} consisting of . and #.
If the j-th character (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is ., the square at the i-th row from the top and j-th column from the left is transparent; if it is #, that square is black.
Similarly, the squares of sheets B and X are represented by H_B strings of length W_B, B_1, B_2, \ldots, B_{H_B}, and H_X strings of length W_X, X_1, X_2, \ldots, X_{H_X}, respectively.

Takahashi's goal is to create sheet X using all black squares in sheets A and B by following the steps below with sheets A, B, and C.

1. Paste sheets A and B onto sheet C along the grid. Each sheet can be pasted anywhere by translating it, but it cannot be cut or rotated.
2. Cut out an H_X\times W_X area from sheet C along the grid. Here, a square of the cut-out sheet will be black if a black square of sheet A or B is pasted there, and transparent otherwise.

Determine whether Takahashi can achieve his goal by appropriately choosing the positions where the sheets are pasted and the area to cut out, that is, whether he can satisfy both of the following conditions.

• The cut-out sheet includes all black squares of sheets A and B. The black squares of sheets A and B may overlap on the cut-out sheet.
• The cut-out sheet coincides sheet X without rotating or flipping.

Constraints

• 1\leq H_A, W_A, H_B, W_B, H_X, W_X\leq 10
• H_A, W_A, H_B, W_B, H_X, W_X are integers.
• A_i is a string of length W_A consisting of . and #.
• B_i is a string of length W_B consisting of . and #.
• X_i is a string of length W_X consisting of . and #.
• Sheets A, B, and X each contain at least one black square.

Sample Input 1

3 5
#.#..
.....
.#...
2 2
#.
.#
5 3
...
#.#
.#.
.#.
...

Sample Output 1

Yes

First, paste sheet A onto sheet C, as shown in the figure below.

     \vdots
  .......  
  .#.#...  
\cdots.......\cdots
  ..#....  
  .......  
     \vdots

Next, paste sheet B so that its top-left corner aligns with that of sheet A, as shown in the figure below.

     \vdots
  .......  
  .#.#...  
\cdots..#....\cdots
  ..#....  
  .......  
     \vdots

Now, cut out a 5\times 3 area with the square in the first row and second column of the range illustrated above as the top-left corner, as shown in the figure below.

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

This includes all black squares of sheets A and B and matches sheet X, satisfying the conditions.

Therefore, print Yes.

Sample Input 2

2 2
#.
.#
2 2
#.
.#
2 2
##
##

Sample Output 2

No

Note that sheets A and B may not be rotated or flipped when pasting them.

Sample Input 3

1 1
#
1 2
##
1 1
#

Sample Output 3

No

No matter how you paste or cut, you cannot cut out a sheet that includes all black squares of sheet B, so you cannot satisfy the first condition. Therefore, print No.

Sample Input 4

3 3
###
...
...
3 3
#..
#..
#..
3 3
..#
..#
###

Sample Output 4

Yes

Problem Statement

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

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

Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

110

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.

Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

201

Sample Input 3

3 2
100 100 100
80 120

Sample Output 3

100

Problem Statement

You are given a string S that is a permutation of atcoder.
On this string S, you will perform the following operation 0 or more times:

• Choose two adjacent characters of S and swap them.

Find the minimum number of operations required to make S equal atcoder.

Constraints

• S is a string that is a permutation of atcoder

Sample Input 1

catredo

Sample Output 1

8

You can make S equal atcoder in 8 operations as follows:
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
This is the minimum number of operations achievable.

Sample Input 2

atcoder

Sample Output 2

0

In this case, the string S is already atcoder.

Sample Input 3

redocta

Sample Output 3

21

Problem Statement

We have a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W).

Each square is one of the following: the initial point, a road, and an obstacle.
A square (i, j) is represented by a character C_{i, j}. The square is the initial point if C_{i, j} = S, a road if C_{i, j} = ., and an obstacle if C_{i, j} = #. There is exactly one initial point.

Determine whether there is a path of length 4 or greater that starts at the initial point, repeats moving vertically or horizontally to an adjacent square, and returns to the initial point without going through an obstacle or visiting the same square multiple times except at the beginning and the end.
More formally, determine whether there are an integer n and a sequence of squares (x_0, y_0), (x_1, y_1), \dots, (x_n, y_n) that satisfy the following conditions.

• n \geq 4.
• C_{x_0, y_0} = C_{x_n, y_n} = S.
• If 1 \leq i \leq n - 1, then C_{x_i, y_i} = ..
• If 1 \leq i \lt j \leq n - 1, then (x_i, y_i) \neq (x_j, y_j).
• If 0 \leq i \leq n - 1, then square (x_i, y_i) and square (x_{i+1}, y_{i+1}) are vertically or horizontally adjacent to each other.

Constraints

• 4 \leq H \times W \leq 10^6
• H and W are integers greater than or equal to 2.
• C_{i, j} is S, ., or #.
• There is exactly one (i, j) such that C_{i, j} = S.

Sample Input 1

4 4
....
#.#.
.S..
.##.

Sample Output 1

Yes

The path (3, 2) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow (3, 2) satisfies the conditions.

Sample Input 2

2 2
S.
.#

Sample Output 2

No

Sample Input 3

5 7
.#...#.
..#.#..
...S...
..#.#..
.#...#.

Sample Output 3

No

Problem Statement

Note: This problem has almost the same setting as Problem B. Only the parts in bold in the main text and constraints differ.

You are holding a ring with both hands. This ring consists of N\ (N \geq 3) parts numbered 1,2,\dots,N, where parts i and i+1 (1 \leq i \leq N-1) are adjacent, and parts 1 and N are also adjacent.

Initially, your left hand is holding part 1, and your right hand is holding part 2. In one operation, you can do the following:

• Move one of your hands to an adjacent part of the part it is currently holding. However, you can do this only if the other hand is not on the destination part.

The following figure shows the initial state and examples of operations that can and cannot be made from there. The number written on each part of the ring represents the part number, and the circles labeled L and R represent your left and right hands, respectively.

You need to follow Q instructions given to you in order. The i-th (1 \leq i \leq Q) instruction is represented by a character H_i and an integer T_i, meaning the following:

• Perform some number of operations (possibly zero) so that your left hand (if H_i is L) or your right hand (if H_i is R) is holding part T_i. Here, you may move the other hand not specified by H_i.

Under the settings and constraints of this problem, it can be proved that any instructions are achievable.

Find the minimum total number of operations required to follow all the instructions.

Constraints

• 3\leq N \leq 3000
• 1\leq Q \leq 3000
• H_i is L or R.
• 1 \leq T_i \leq N
• N, Q, and T_i are integers.

Sample Input 1

6 3
R 4
L 5
R 5

Sample Output 1

6

By performing the following operations, you can follow all Q instructions in order.

1. Move your right hand as part 2 \rightarrow 3 \rightarrow 4 to follow the first instruction.
2. Move your left hand as part 1 \rightarrow 6 \rightarrow 5 to follow the second instruction.
3. Move your left hand as part 5 \rightarrow 6, then move your right hand as part 4 \rightarrow 5 to follow the third instruction.

In this case, the total number of operations is 2+2+1+1=6, which is the minimum.

Sample Input 2

100 2
L 1
R 2

Sample Output 2

0

There are cases where you can follow the instructions without performing any operations.

Sample Input 3

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

Sample Output 3

58