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 the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

• 1 \leq a \lt b \leq H
• 1 \leq c \lt d \leq W
• There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

• 2 \leq H, W \leq 500
• S_{i,j} is # or ..

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

Problem Statement

You are given a sequence of N numbers: A=(A_1,\ldots,A_N).

Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.

Constraints

• 2 \leq N \leq 2\times 10^5
• -10^9 \leq A_i \leq 10^9
• -10^9 \leq X \leq 10^9
• All values in the input are integers.

Sample Input 1

6 5
3 1 4 1 5 9

Sample Output 1

Yes

We have A_6-A_3=9-4=5.

Sample Input 2

6 -4
-2 -7 -1 -8 -2 -8

Sample Output 2

No

There is no pair (i,j) such that A_i-A_j=-4.

Sample Input 3

2 0
141421356 17320508

Sample Output 3

Yes

We have A_1-A_1=0.

Problem Statement

Takahashi has N balls. Each ball has an integer not less than 2 written on it. He will insert them in a cylinder one by one. The integer written on the i-th ball is a_i.

The balls are made of special material. When k balls with k (k \geq 2) written on them line up in a row, all these k balls will disappear.

For each i (1 \leq i \leq N), find the number of balls after inserting the i-th ball.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq a_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

5
3 2 3 2 2

Sample Output 1

1
2
3
4
3

The content of the cylinder changes as follows.

• After inserting the 1-st ball, the cylinder contains the ball with 3.
• After inserting the 2-nd ball, the cylinder contains 3, 2 from bottom to top.
• After inserting the 3-rd ball, the cylinder contains 3, 2, 3 from bottom to top.
• After inserting the 4-th ball, the cylinder contains 3, 2, 3, 2 from bottom to top.
• After inserting the 5-th ball, the cylinder momentarily has 3, 2, 3, 2, 2 from bottom to top. The two consecutive balls with 2 disappear, and the cylinder eventually contains 3, 2, 3 from bottom to top.

Sample Input 2

10
2 3 2 3 3 3 2 3 3 2

Sample Output 2

1
2
3
4
5
3
2
3
1
0

Problem Statement

We have an N \times N chessboard. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of this board.
The board is described by N strings S_i.
The j-th character of the string S_i, S_{i,j}, means the following.

• If S_{i,j}= ., the square (i, j) is empty.
• If S_{i,j}= #, the square (i, j) is occupied by a white pawn, which cannot be moved or removed.

We have put a white bishop on the square (A_x, A_y).
Find the minimum number of moves needed to move this bishop from (A_x, A_y) to (B_x, B_y) according to the rules of chess (see Notes).
If it cannot be moved to (B_x, B_y), report -1 instead.

Notes

A white bishop on the square (i, j) can go to the following positions in one move.

• For each positive integer d, it can go to (i+d,j+d) if all of the conditions are satisfied.

  • The square (i+d,j+d) exists in the board.
  • For every positive integer l \le d, (i+l,j+l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i+d,j-d) if all of the conditions are satisfied.

  • The square (i+d,j-d) exists in the board.
  • For every positive integer l \le d, (i+l,j-l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i-d,j+d) if all of the conditions are satisfied.

  • The square (i-d,j+d) exists in the board.
  • For every positive integer l \le d, (i-l,j+l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i-d,j-d) if all of the conditions are satisfied.

  • The square (i-d,j-d) exists in the board.
  • For every positive integer l \le d, (i-l,j-l) is not occupied by a white pawn.

Constraints

• 2 \le N \le 1500
• 1 \le A_x,A_y \le N
• 1 \le B_x,B_y \le N
• (A_x,A_y) \neq (B_x,B_y)
• S_i is a string of length N consisting of . and #.
• S_{A_x,A_y}= .
• S_{B_x,B_y}= .

Sample Input 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

Sample Output 1

3

We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.

• (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)

Sample Input 2

4
3 2
4 2
....
....
....
....

Sample Output 2

-1

There is no way to move the bishop from (3,2) to (4,2).

Sample Input 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

Sample Output 3

9

Problem Statement

There are N points labeled 1, 2, \dots, N on the xy-plane. Point i is located at coordinates (X_i, Y_i).
You can perform the following operation between 0 and K times, inclusive.

• First, choose one of the N points. Let k be the selected point, and assume it is currently at (x, y).
• Next, choose and execute one of the following four actions:
  • Move point k along the x-axis by +1. The coordinates of point k become (x+1, y).
  • Move point k along the x-axis by -1. The coordinates of point k become (x-1, y).
  • Move point k along the y-axis by +1. The coordinates of point k become (x, y+1).
  • Move point k along the y-axis by -1. The coordinates of point k become (x, y-1).
• It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates.

After all your operations, draw one square that includes all the N points inside or on the circumference, with each side parallel to the x- or y-axis.
Find the minimum possible value for the length of a side of this square. This value can be shown to be an integer since all points are always on lattice points.

In particular, if all points can be made to exist at the same coordinates, the answer is considered to be 0.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 0 \le K \le 4 \times 10^{14}
• 0 \le X_i, Y_i \le 10^9

Sample Input 1

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

Sample Output 1

3

The figure below illustrates this case with the horizontal x-axis and the vertical y-axis.

For example, after performing four moves following the arrows in the figure, you can include all points inside or on the circumference of the square shown in the figure with a side length of 3, and this can be shown to be the minimum value.

Sample Input 2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0

All points already exist at the same coordinates from the beginning.
For example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is 0.

Sample Input 3

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

Sample Output 3

484373824