K-th Smallest Number in a Subrectangle

You are given an n × n matrix. You need to process multiple queries. In each query, you are given a subrectangle of the matrix, specified by its top‐left corner (r₁, c₁) and bottom‐right corner (r₂, c₂), and an integer k. Your task is to output the k-th smallest number in that subrectangle. Note that the indices are 1-based.

Mathematical Formula:

If the subrectangle elements are represented as an array A, after sorting we obtain A_sorted. You need to return A_sorted[k-1].

inputFormat

The first line contains an integer n representing the size of the matrix.

The next n lines each contain n space-separated integers representing the matrix.

The following line contains an integer q representing the number of queries.

Each of the next q lines contains five integers: r1, c1, r2, c2, k, where (r1, c1) and (r2, c2) define the top-left and bottom-right corners of the subrectangle (1-indexed), and k denotes the order of the smallest number to find in that subrectangle.

outputFormat

For each query, output the k-th smallest number in the specified subrectangle on a new line.

sample

3
1 5 9
2 6 10
3 7 11
2
1 1 2 2 3
2 2 3 3 2

5
7