BSSPC '21 S2 - Hacker Soup

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Soup has infiltrated Lakshy's top secret lab! Inside this lab are the secrets on how to survive the IB program. However, to get in Soup would need to bypass a sophisticated security lock. The security lock is an N by N matrix of cells. Soup has gained intel that the value of cell at (i, j) (that is, the i^{th} row and j^{th} column) would be (i-1) \times N  + j by default. To pass the lock, Soup will need to answer Q queries, the k^{th} asking for the value of a particular cell (y_k, x_k). Unfortunately, Soup was also informed that the numbers on the grid have been scrambled in K successive rotation operations! In the k^{th} operation, Lakshy rotates the square with top left corner (t_k, l_k) and bottom right corner (b_k, r_k) by 90 degrees clockwise. Overwhelmed by the difficulty, Soup cannot unlock the security lock, so he has come to you, his trusty accomplice, to help him!

Constraints

For all subtasks:

1 \le N \le 10^9

1 \le K, Q \le 5 \times 10^3

1 \le t_k \le b_k \le N

1 \le l_k \le r_k \le N

b_k - t_k = r_k - l_k

1 \le y_k, x_k \le N

Subtask 1 [20%]

1 \le N \le 500

1 \le K \le 100

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains three integers, N, K, Q.

The next K lines each contain four integers, t_k, l_k, b_k, r_k.

The next Q lines each contain two integers, y_k, x_k.

Output Specification

For each of the Q queries, output on a separate line the value of cell (y_k, x_k).

Sample Input

3 2 2
1 1 3 3
2 2 3 3
3 2
1 2

Sample Output

3
4

Explanation

Before any rotations, the matrix looks like this:

1 2 3
4 5 6
7 8 9

After the first rotation, the matrix looks like this:

7 4 1
8 5 2
9 6 3

After the second rotation, the matrix looks like this:

7 4 1
8 6 5
9 3 2

Thus the cell at (3, 2) is 3 and the cell at (1, 2) is 4.


Comments

There are no comments at the moment.