Jittery Jumps
/

## Medium-Hard

Problem
Editorial
Analytics

The country virtualBit is organized as an N x N grid. The cells are numbered from 1 to N, from south to north, and from west to east. Each cell in the grid represents one of its cities. The transportation system in virtualBit is pretty crazy and inconvenient. From a cell (i, j), there are four routes:

route-0 - North route that leads to (min(N, i + Di,j), j)

route-1 - East route that leads to (i, min(N, j + Di,j))

route-2 - South route that leads to (max(1, i - Di,j), j)

route-3 - West route that leads to (i, max(1, j - Di,j))

The government of virtualBit wants to improve the transportation system. To achieve this task, they need the answer to M queries. In each query, a person starts from some cell in the grid and takes S steps. Initially the person has a non-negative number F. In each step, he takes the F%4 route from the current cell. After taking a route from cell (i, j) the number F changes as F = F * Bi,j +Ci,j

Given starting cell (Ti,Tj), and non-negative numbers F and S, you need to answer where the person will end up.

Note that even if a person stays in the same cell after a jump, we count it as a step. See test case 3 of sample input.

Input:

The first line contains N.

Each of the next N lines contain N numbers. The jth number of ith next line is Di,j.

Each of the next N lines contain N numbers. The jth number of ith next line is Bi,j.

Each of the next N lines contain N numbers. The jth number of ith next line is Ci,j.

The next line contains M , the number of queries.

Each of the next M lines contain (Ti,Tj) the coordinates of the starting cell, F and S.

Output:

For each query, print two numbers that are the coordinates of the cell where the person will end up, given the initial conditions.

Constraints:

1 <= N <= 500

0 <= S <= 1018

1 <= M <= 105

0 <= Di,j <= 500

0 <= Bi,j, Ci,j <= 105

1 <= Ti, Tj <= N

0 <= F <= 105

SAMPLE INPUT
2
1 2
2 0
1 0
1 1
1 1
3 1
4
1 2 5 1
1 1 12 2
2 1 3 2
2 2 123 100
SAMPLE OUTPUT
1 2
2 2
1 1
2 2
Explanation

In query 3 we start at (2,1). In step 1 we stay at (2,1) itself, and the value of F changes to 6. And in step 2, we jump to (1,1)

In query 4, no matter how many steps we take, we'll always stay at (2,2) as D 2,2 is 0

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...