Ranch CCTV
Time limit2sMemory limit256 MB
For each query, sheep in a grid shift one cell per day in a fixed direction for K days; report the XOR of the daily maximum over the CCTV rectangle.
- Level
Hard8 of 10
- Topics
- Prefix sum, Matrix, Math, Implementation
- Solved
- No attempts yet
Problem
Junho keeps a rectangular ranch in a hidden space at Hanyang University, with N rows and M columns of sheep, N×M sheep in total. When Junho is worn out from a mountain of work, he heals by watching the sheep at the ranch, so he treasures the time he spends watching them. But Junho is a very busy person, and he often had to leave for other regions on business trips for several days, and each time he could not have time to watch the sheep. In the end, wanting to watch the sheep even from far away, Junho installed a single-use CCTV in the ranch that can be used for one business trip only.
This CCTV is quite unusual: a rectangle R rows below and C columns to the right of the installation point is its shooting range, and once a day it takes a photo of the largest sheep within the shooting range and sends it. Junho's sheep also have an unusual habit that shows only when Junho is away. Because the sheep feel anxious when Junho is absent, from the day after Junho leaves until he returns, all sheep choose one of up, down, left, right and move one cell each day in the same direction. However, since the ranch is very large, the sheep never reach the boundary of the ranch and become unable to move. Of course, even when the sheep move, the CCTV stays fixed in place and does not move.
Junho wondered whether the CCTV would work normally in this environment, and asked you to write a program that verifies whether this CCTV works properly. Given the information needed for verification, write a program that outputs the size of the sheep the CCTV must send each day. However, since there are too many sheep to output all the results, output the XOR of all results for each business trip Junho makes to another region.
Input
The first line gives the integers N, M (1 ≤ N, M ≤ 500), the number of rows and columns of the sheep Junho keeps.
The next N lines give information about the sizes of the sheep. Each line contains M integers Aij (1 ≤ Aij ≤ 100,000, 1 ≤ i ≤ N, 1 ≤ j ≤ M), the size of a sheep.
The third line gives a positive integer Q (1 ≤ Q ≤ 50,000), the number of times Junho goes on a business trip to another region.
The next Q lines give, for each business trip, information about the single-use CCTV installed and the movement of the sheep. Each line contains integers X, Y (1 ≤ X ≤ N, 1 ≤ Y ≤ M) for the CCTV installation position, integers R, C (1 ≤ R ≤ N, 1 ≤ C ≤ M) for the shooting range, an integer K (1 ≤ K ≤ max(N, M)) for the number of days Junho is away, and an integer D (1 ≤ D ≤ 4) for the direction the sheep move during the period. The directions up, down, left, right correspond to 1, 2, 3, 4 respectively.
No case is given in which an empty space appears within the shooting range of the CCTV.
Output
Over Q lines, for each business trip Junho makes, output the XOR of the K integers obtained as the sizes of the sheep the CCTV must send each day during the K days.