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 people, labeled 1 to N. Person i has an integer A_i.

Among the people who satisfy the condition "None of the other N-1 people has the same integer as themselves," find the one with the greatest integer, and print that person's label.

If no person satisfies the condition, report that fact instead.

Constraints

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

Sample Input 1

9
2 9 9 7 9 2 4 5 8

Sample Output 1

9

Those who satisfy the condition are the persons labeled 4, 7, 8, and 9.
Their integers are 7, 4, 5, and 8, respectively, and the person with the largest integer is the person labeled 9.
Thus, the answer is 9.

Sample Input 2

4
1000000000 1000000000 998244353 998244353

Sample Output 2

-1

If no person satisfies the condition, print -1.

Problem Statement

There are N products labeled 1 to N flowing on a conveyor belt. A Keyence printer is attached to the conveyor belt, and product i enters the range of the printer T_i microseconds from now and leaves it D_i microseconds later.

The Keyence printer can instantly print on one product within the range of the printer (in particular, it is possible to print at the moment the product enters or leaves the range of the printer). However, after printing once, it requires a charge time of 1 microseconds before it can print again. What is the maximum number of products the printer can print on when the product and timing for the printer to print are chosen optimally?

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq T_i,D_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5
1 1
1 1
2 1
1 2
1 4

Sample Output 1

4

Below, we will simply call the moment t microseconds from now time t.

For example, you can print on four products as follows:

• Time 1 : Products 1,2,4,5 enter the range of the printer. Print on product 4.
• Time 2 : Product 3 enters the range of the printer, and products 1,2 leave the range of the printer. Print on product 1.
• Time 3 : Products 3,4 leave the range of the printer. Print on product 3.
• Time 4.5 : Print on product 5.
• Time 5 : Product 5 leaves the range of the printer.

It is impossible to print on all five products, so the answer is 4.

Sample Input 2

2
1 1
1000000000000000000 1000000000000000000

Sample Output 2

2

Sample Input 3

10
4 1
1 2
1 4
3 2
5 1
5 1
4 1
2 1
4 1
2 4

Sample Output 3

6

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of the grid.
Each square of the grid is holed or not. There are exactly N holed squares: (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N).

When the triple of positive integers (i, j, n) satisfies the following condition, the square region whose top-left corner is (i, j) and whose bottom-right corner is (i + n - 1, j + n - 1) is called a holeless square.

• i + n - 1 \leq H.
• j + n - 1 \leq W.
• For every pair of non-negative integers (k, l) such that 0 \leq k \leq n - 1, 0 \leq l \leq n - 1, square (i + k, j + l) is not holed.

How many holeless squares are in the grid?

Constraints

• 1 \leq H, W \leq 3000
• 0 \leq N \leq \min(H \times W, 10^5)
• 1 \leq a_i \leq H
• 1 \leq b_i \leq W
• All (a_i, b_i) are pairwise different.
• All input values are integers.

Sample Input 1

2 3 1
2 3

Sample Output 1

6

There are six holeless squares, listed below. For the first five, n = 1, and the top-left and bottom-right corners are the same square.

• The square region whose top-left and bottom-right corners are (1, 1).
• The square region whose top-left and bottom-right corners are (1, 2).
• The square region whose top-left and bottom-right corners are (1, 3).
• The square region whose top-left and bottom-right corners are (2, 1).
• The square region whose top-left and bottom-right corners are (2, 2).
• The square region whose top-left corner is (1, 1) and whose bottom-right corner is (2, 2).

Sample Input 2

3 2 6
1 1
1 2
2 1
2 2
3 1
3 2

Sample Output 2

0

There may be no holeless square.

Sample Input 3

1 1 0

Sample Output 3

1

The whole grid may be a holeless square.

Sample Input 4

3000 3000 0

Sample Output 4

9004500500