P1527 [CTT] Matrix Multiplication

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.

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)$.

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

#### 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