시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 16 2 2 66.667%

문제

준호는 한양대학교의 숨겨진 공간에 직사각형 모양의 목장을 만들어 NM열을 이루는 양 N×M 마리를 키우고 있다. 준호는 산더미 같은 할 일에 지칠 땐 목장에서 양들을 보며 힐링하기 때문에 양들을 지켜보는 시간을 매우 소중하게 생각한다. 그러나 준호는 매우 바쁜 사람이기 때문에 며칠동안 다른 지역에 출장 가야하는 일이 매우 많았고, 그 때마다 양을 지켜보는 시간을 가질 수 없었다. 결국 준호는 멀리서나마 양을 지켜보고 싶은 마음에 한번의 출장동안만 사용할 수 있는 일회용 CCTV를 목장에 설치하게 되었다.

이 CCTV는 굉장히 특이한데, 설치지점으로부터 아래로 R행, 오른쪽으로 C열의 직사각형이 촬영 범위로, 하루에 한번씩 촬영범위 안에서 가장 크기가 큰 양의 사진을 찍어 전송하는 기능만을 제공한다. 또한 준호의 양들도 준호가 없을 때만 보이는 특이한 습성이 있다. 양들은 준호가 없으면 불안함을 느끼기 때문에, 준호가 떠난 다음날부터 준호가 돌아올 때까지 모든 양들이 상하좌우 중 한 방향을 골라서 매일매일 하루에 한 칸씩 같은 방향으로 움직인다. 단, 목장은 크기가 매우 크기 때문에 양들이 목장의 경계까지 이동하여 움직이지 못하는 경우는 발생하지 않는다. 물론 양들이 움직여도 CCTV는 제자리에 고정되어 움직이지 않는다.

준호는 이러한 환경에서도 CCTV가 정상적으로 작동하는지 의문이 생겼고 당신에게 이 CCTV가 제대로 작동하는지 검증하는 프로그램을 작성해달라고 부탁했다. 검증에 필요한 정보들이 주어졌을 때, CCTV가 매일 전송해야 하는 양의 크기를 출력하는 프로그램을 작성하자. 단, 모든 결과를 출력하기에는 양이 많으니 준호가 한번 다른 지역에 갈 때마다 그 때의 모든 결과를 XOR한 결과를 출력하도록 한다.

입력

첫째 줄에는 준호가 기르고 있는 양의 행과 열을 나타내는 정수 N, M (1 ≤ N, M ≤ 500) 이 주어진다.

다음 N개의 줄에 걸쳐 양들의 크기에 대한 정보가 주어진다. 각 줄에는 양의 크기를 나타내는 정수 Aij (1 ≤ Aij ≤ 100,000, 1 ≤ i ≤ N, 1 ≤ j ≤ M) M개가 주어진다. 

셋째 줄에는 준호가 다른 지역에 출장 가는 횟수를 나타내는 양의 정수 Q (1 ≤ Q ≤ 50,000) 가 주어진다.

다음 Q개의 줄에 걸쳐 각 출장에 대해 설치한 일회용 CCTV와 양들의 이동에 관한 정보가 주어진다. 각 줄은 CCTV의 설치 위치를 나타내는 정수 X, Y (1 ≤ X ≤ N, 1 ≤ Y ≤ M), 촬영범위를 나타내는 정수 R, C (1 ≤ R ≤ N, 1 ≤ C ≤ M), 준호가 다른 지역에 가 있는 일자를 나타내는 정수 K (1 ≤ K ≤ max(N, M)), 기간 동안 양들이 움직이는 방향을 나타내는 정수 D (1 ≤ D ≤ 4) 가 주어진다. 방향은 각각 상하좌우가 1, 2, 3, 4에 대응한다.

CCTV의 촬영범위 안에 빈 공간이 생기는 경우는 주어지지 않는다.

출력

Q개의 줄에 걸쳐, 각각 준호가 출장을 가 있는 K일 동안 매일 CCTV가 전송해야 하는 양의 크기를 구하여 얻은 정수 K개를 XOR한 값을 출력한다.

예제 입력 1

5 5
2 6 12 2 11
20 9 10 6 10
8 18 4 18 15
10 14 11 10 3
17 11 15 13 16
2
2 2 2 2 2 4
1 1 1 2 5 1

예제 출력 1

6
31

첫번째 검증에서 CCTV는 (2,2)에 설치되어 아래로 2행, 오른쪽으로 2열의 직사각형이 촬영범위이고 2일동안 사용되었다. 첫째날에는 양이 움직이지 않으므로 (2,2), (2,3), (3,2), (3,3)이 촬영범위이고, 여기에서 가장 크기가 큰 양은 (3,2)의 18이다. 둘째날에는 모든 양이 우측으로 한 칸 이동했기 때문에 촬영범위는 (2,1), (2,2), (3,1), (3,2)가 된다. 이 촬영범위 안에서 가장 크기가 큰 양은 (2,1)의 20이다. 따라서 첫번째 검증의 정답은 18과 20의 XOR인 6이다.