Problem Statement

You are given a string S of length 3 consisting of uppercase English letters.

Determine whether it is possible to rearrange the characters in S to make it match the string ABC.

Constraints

• S is a string of length 3 consisting of uppercase English letters.

Sample Input 1

BAC

Sample Output 1

Yes

You can make S match ABC by swapping the first and second characters of S.

Sample Input 2

AAC

Sample Output 2

No

You cannot make S match ABC no matter how you rearrange the characters.

Sample Input 3

ABC

Sample Output 3

Yes

Sample Input 4

ARC

Sample Output 4

No

Problem Statement

There is a grid of 64 squares with 8 rows and 8 columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq8) and j-th column from the left (1\leq j\leq8).

Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence (S_1,S_2,S_3,\ldots,S_8) of 8 strings of length 8. Square (i,j) (1\leq i\leq8,1\leq j\leq8) is empty if the j-th character of S_i is ., and has a piece if it is #.

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy either of the following conditions:

• Placed on a square in row i
• Placed on a square in column j

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• Each S_i is a string of length 8 consisting of . and # (1\leq i\leq 8).

Sample Input 1

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

Sample Output 1

4

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece without it being captured on 4 squares: square (6,6), square (6,7), square (7,6), and square (7,7).

Sample Input 2

........
........
........
........
........
........
........
........

Sample Output 2

64

There may be no pieces on the grid.

Sample Input 3

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

Sample Output 3

4

Problem Statement

There is a grid of N^2 squares with N rows and N columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq N) and j-th column from the left (1\leq j\leq N).

Each square is either empty or has a piece placed on it. There are M pieces placed on the grid, and the k-th (1\leq k\leq M) piece is placed on square (a_k,b_k).

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy any of the following conditions:

• Placed on square (i+2,j+1)
• Placed on square (i+1,j+2)
• Placed on square (i-1,j+2)
• Placed on square (i-2,j+1)
• Placed on square (i-2,j-1)
• Placed on square (i-1,j-2)
• Placed on square (i+1,j-2)
• Placed on square (i+2,j-1)

Here, conditions involving non-existent squares are considered to never be satisfied.

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• 1\leq N\leq10^9
• 1\leq M\leq2\times10^5
• 1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
• (a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)
• All input values are integers.

Sample Input 1

8 6
1 4
2 1
3 8
4 5
5 2
8 3

Sample Output 1

38

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on the remaining 38 squares.

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999999999999997

Out of 10^{18} squares, only 3 squares cannot be used: squares (1,1), (2,3), and (3,2).

Note that the answer may be 2^{32} or greater.

Sample Input 3

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

Sample Output 3

338

Problem Statement

You are given two sequences of positive integers of length N, L=(L_1,L_2,\ldots,L_N) and R=(R_1,R_2,\ldots,R_N), and an integer M.

Find the number of pairs of integers (l,r) that satisfy both of the following conditions:

• 1\le l \le r \le M
• For every 1\le i\le N, the interval [l,r] does not completely contain the interval [L_i,R_i].

Constraints

• 1\le N,M\le 2\times 10^5
• 1\le L_i\le R_i\le M
• All input values are integers.

Sample Input 1

2 4
1 2
3 4

Sample Output 1

5

The five pairs (l,r)=(1,1),(2,2),(2,3),(3,3),(4,4) satisfy the conditions.

For example, (l,r)=(1,3) does not satisfy the conditions because the interval [1,3] completely contains the interval [1,2].

Sample Input 2

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

Sample Output 2

0

There may be cases where no pairs of integers satisfy the conditions.

Sample Input 3

6 20
8 12
14 20
11 13
5 19
4 11
1 6

Sample Output 3

102

Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

The following operation will be performed K times:

• For i=1,2,\ldots,N, simultaneously update P_i to P_{P_i}.

Print P after all operations.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq K\leq10^{18}
• 1\leq P_i\leq N\ (1\leq i\leq N)
• P_i\neq P_j\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

6 3
5 6 3 1 2 4

Sample Output 1

6 1 3 2 4 5

With each operation, P changes as follows:

• After the first operation, P is (2,4,3,5,6,1).
• After the second operation, P is (4,5,3,6,1,2).
• After the third operation, P is (6,1,3,2,4,5).

Thus, print 6 1 3 2 4 5.

Sample Input 2

5 1000000000000000000
1 2 3 4 5

Sample Output 2

1 2 3 4 5

Since P_i=i, P does not change no matter how many operations are performed.

Sample Input 3

29 51912426
7 24 8 23 6 1 4 19 11 18 20 9 17 28 22 27 15 2 12 26 10 13 14 25 5 29 3 21 16

Sample Output 3

18 23 16 24 21 10 2 27 19 7 12 8 13 5 15 26 17 4 3 9 1 22 25 14 28 11 29 6 20

Problem Statement

There is a grid of N^2 squares with N rows and N columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq N) and j-th column from the left (1\leq j\leq N).

Each square is either empty or has a piece placed on it. There are M pieces placed on the grid, and the k-th (1\leq k\leq M) piece is placed on square (a_k,b_k).

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy any of the following conditions:

• Placed in row i
• Placed in column j
• Placed on any square (a,b)\ (1\leq a\leq N,1\leq b\leq N) where i+j=a+b
• Placed on any square (a,b)\ (1\leq a\leq N,1\leq b\leq N) where i-j=a-b

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• 1\leq N\leq10^9
• 1\leq M\leq10^3
• 1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
• (a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)
• All input values are integers.

Sample Input 1

8 6
1 4
2 1
3 8
4 5
5 2
8 3

Sample Output 1

2

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on only two squares: squares (6,6) and (7,7).

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999997000000002

Out of 10^{18} squares, the squares that cannot be used are: squares in row 1, squares in column 1, and squares (1,1), (2,2), \ldots, (10^9,10^9), totaling 3\times10^9-2 squares.

Note that the answer may be 2^{32} or greater.

Sample Input 3

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

Sample Output 3

77

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N. Each string consists of lowercase English letters.

For each k=1,2,\ldots,N, solve the following problem.

Let T=S_k and consider performing the following two types of operations any number of times in any order:

• Pay a cost of 1 to delete the last character of T. This operation is possible when T is not empty.
• Pay a cost of 1 to add any lowercase English letter to the end of T.

Find the minimum total cost needed to make T either empty or match one of S_1,S_2,\ldots,S_{k-1}.

Constraints

• 1\le N\le 2\times 10^5
• Each S_i is a string of length at least 1 consisting of lowercase English letters.
• \displaystyle \sum_{i=1}^N |S_i|\le 2\times 10^5

Sample Input 1

3
snuke
snuki
snuuk

Sample Output 1

5
2
4

For k=1, you can make T empty by performing the delete operation five times.

For k=2, you can make T match S_1 by deleting the last character and then adding e to the end.

For k=3, you can make T match S_2 by deleting the last character twice, then adding k to the end, and finally adding i to the end.

Sample Input 2

3
abc
arc
agc

Sample Output 2

3
3
3

Sample Input 3

8
at
atatat
attat
aatatatt
attattat
ttatta
tta
tt

Sample Output 3

2
4
3
8
3
6
3
1