SOLVE

LATER

Jittery Jumps

/

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 + **D _{i,j}**), j)

route-1 - East route that leads to (i, min(**N**, j + **D _{i,j}**))

route-2 - South route that leads to (max(1, i - **D _{i,j}**), j)

route-3 - West route that leads to (i, max(1, j - **D _{i,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** * **B _{i,j}** +

Given starting cell (**T _{i},T_{j}**), and non-negative numbers

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 **D _{i,j}**.

Each of the next **N** lines contain **N** numbers. The jth number of ith next line is **B _{i,j}**.

Each of the next **N** lines contain **N** numbers. The jth number of ith next line is **C _{i,j}**.

The next line contains **M** , the number of queries.

Each of the next **M** lines contain (**T _{i},T_{j}**) the coordinates of the starting cell,

**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** <= 10^{18}

1 <= **M** <= 10^{5}

0 <= **D _{i,j}** <= 500

0 <= **B _{i,j}**,

1 <= **T _{i}**,

0 <= **F** <= 10^{5}

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

Initializing Code Editor...