Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

• S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

• a
• y
• ay
• ya
• yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54

Problem Statement

There are N rectangular sheets spread out on a coordinate plane.

Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.

Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.

Constraints

• 2\leq N\leq 100
• 0\leq A_i<B_i\leq 100
• 0\leq C_i<D_i\leq 100
• All input values are integers.

Sample Input 1

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

Sample Output 1

20

The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.

Sample Input 2

2
0 100 0 100
0 100 0 100

Sample Output 2

10000

Note that different sheets may cover the same region.

Sample Input 3

3
0 1 0 1
0 3 0 5
5 10 0 10

Sample Output 3

65

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

Constraints

• 2 \leq N \leq 100
• 1 \leq P_i \leq N \, (1 \leq i \leq N)
• P_i \neq P_j \, (i \neq j)
• (P_1, \dots, P_N) \neq (1, \dots, N)
• All values in the input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

• (1, 2, 3)
• (1, 3, 2)
• (2, 1, 3)
• (2, 3, 1)
• (3, 1, 2)
• (3, 2, 1)

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

• For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
• For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

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

• Choose an arbitrary row of A and remove it.
• Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

• 1 \leq H_2 \leq H_1 \leq 10
• 1 \leq W_2 \leq W_1 \leq 10
• 1 \leq A_{i, j} \leq 10^9
• 1 \leq B_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.

Sample Input 2

3 3
1 1 1
1 1 1
1 1 1
1 1
2

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.

Problem Statement

There are N+2 cells arranged in a row. Let cell i denote the i-th cell from the left.

There is one stone placed in each of the cells from cell 1 to cell N.
For each 1 \leq i \leq N, the stone in cell i is white if S_i is W, and black if S_i is B.
Cells N+1 and N+2 are empty.

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

• Choose a pair of adjacent cells that both contain stones, and move these two stones to the empty two cells while preserving their order.
  More precisely, choose an integer x such that 1 \leq x \leq N+1 and both cells x and x+1 contain stones. Let k and k+1 be the empty two cells. Move the stones from cells x and x+1 to cells k and k+1, respectively.

Determine if it is possible to achieve the following state, and if so, find the minimum number of operations required:

• Each of the cells from cell 1 to cell N contains one stone, and for each 1 \leq i \leq N, the stone in cell i is white if T_i is W, and black if T_i is B.

Constraints

• 2 \leq N \leq 14
• N is an integer.
• Each of S and T is a string of length N consisting of B and W.

Sample Input 1

6
BWBWBW
WWWBBB

Sample Output 1

4

Using . to represent an empty cell, the desired state can be achieved in four operations as follows, which is the minimum:

• BWBWBW..
• BW..BWBW
• BWWBB..W
• ..WBBBWW
• WWWBBB..

Sample Input 2

6
BBBBBB
WWWWWW

Sample Output 2

-1

Sample Input 3

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

Sample Output 3

7