Description

Given an $n \times n$ matrix, you do not need to perform matrix multiplication. Instead, for each query, find the $k$-th smallest number in a subrectangle.

Input Format

The first line contains two integers, representing the matrix size $n$ and the number of queries $q$.

Lines $2$ through $(n + 1)$ each contain $n$ integers, representing the matrix. The $j$-th number on line $(i + 1)$ is the number in row $i$ and column $j$ of the matrix, denoted $a_{i, j}$.

Then $q$ lines follow, each containing five integers $x_1, y_1, x_2, y_2, k$, representing one query. For each query, find the $k$-th smallest number in the subrectangle with top-left corner $(x_1, y_1)$ and bottom-right corner $(x_2, y_2)$.

Output Format

For each query, output a single integer on its own line representing the answer.

2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3

1
3

Hint

Constraints and Conventions

• For $20\%$ of the testdata, it is guaranteed that $n \leq 100$, $q \leq 10^3$.
• For $40\%$ of the testdata, it is guaranteed that $n \leq 300$, $q \leq 10^4$.
• For $60\%$ of the testdata, it is guaranteed that $n \leq 400$, $q \leq 3 \times 10^4$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 500$, $1 \leq q \leq 6 \times 10^4$, $0 \leq a_{i, j} \leq 10^9$.

Translated by ChatGPT 5