Today, you need to solve a problem on a Puzzled Grid game. "In a grid of $n \times n$ size, where each cell has a positive integer, two players compete in several rounds.

Each round starts by both players putting a rock in a random location of the grid. Then, the two players must connect the two rocks with a line that passes through the grid cells (e.g: from a grid cell the line can can expand either horizontally or vertically and never out the grid). Since there may be a lot of ways to connect the two stones, we are only interested in those lines that minimizes the highest cell in their path (e.g: the cell with the highest number should be as small as possible).

You need to find and print this minimized maximum. Can you do it?

Input:

First line contains two integers n and Q, where n is the grid size and Q is the number of rounds of the game. Next n lines contain each n integer denoting the grid cell numbers. Then, next Q lines contain each 4 integers $x1, y1, x2, y2$ denoting the first and second stone locations -- the indexes are 0 based and the origin is the top leftmost cell.

Output:

Print Q lines, each denoting the answer for each round.

Constraints:

• $2 \le n \le 500$.
• Grid cell numbers are less than or equal $10^6$.
• At the start of each round the stones are in different locations.
• $1 \le Q \le 10^5$.