You are given a ~2~-dimensional array of integers of size ~N \times N~. We will call this array ~arr~. You are then required to answer multiple queries for the minimum integer in a given submatrix.

Formally, given ~4~ integers ~a, b, c, d~, determine ~\min \{arr[i][j] \mid a \le i \le b, c \le j \le d\}~.

Implementation Details

You should implement the following functions:

void init(std::vector<std::vector<int>> arr);

• ~arr~: a ~2~-dimensional array of size ~N \times N~.

int query(int a, int b, int c, int d);

• ~a~: the lower bound on the first dimension of the submatrix.
• ~b~: the upper bound on the first dimension of the submatrix.
• ~c~: the lower bound on the second dimension of the submatrix.
• ~d~: the upper bound on the second dimension of the submatrix.
• This function should return the minimum integer in the submatrix formed by ~a, b, c, d~.

It is guaranteed that init will be called exactly once, and that this call will be made before any calls to query.

Constraints

For all subtasks:

~1 \le N \le 1000~
~1 \le arr[i][j] \le 10^9~ for ~0 \le i, j \le N-1~
~0 \le a \le b \le N-1~ for all calls to query
~0 \le c \le d \le N-1~ for all calls to query

Disclaimer: ~arr[i][j], a, b, c, d~ were generated randomly.
Your answer will be considered correct if the bitwise ~xor~ of the answers to all the queries matches the expected result.

Subtask 1 [10%]

query will be called at most ~1\,000~ times.

Subtask 2 [20%]

query will be called at most ~100\,000~ times.

Subtask 3 [30%]

query will be called at most ~1\,000\,000~ times.

Subtask 4 [40%]

query will be called at most ~10\,000\,000~ times.

Sample Interaction

Please note that the sample will not appear in any of the test cases.