Description

LCS is planning to break the new cipher invented by his friends. To do this, he must make some linear transformations over the ring Zr = Z/rZ.

Each linear transformation is defined by 2×2 matrix. LCS has a sequence of matrices A1 , A2 ,..., An . As a step of his algorithm he must take some segment Ai , A(i+1) , ..., Aj of the sequence and multiply some vector by a product Pi,j=Ai × A(i+1) × ... × Aj of the segment. He must do it for m various segments.

Help LCS to determine the products he needs.

Input

There are several test cases in the input. The first line of each case contains r (1 <= r <= 10,000), n (1 <= n <= 30,000) and m (1 <= m <= 30,000). Next n blocks of two lines, containing two integer numbers ranging from 0 to r - 1 each, describe matrices. Blocks are separated with blank lines. They are followed by m pairs of integer numbers ranging from 1 to n each that describe segments, products for which are to be calculated. There is an empty line between cases.

Output

Print m blocks containing two lines each. Each line should contain two integer numbers ranging from 0 to r - 1 and define the corresponding product matrix. There should be an empty line between cases. Separate blocks with an empty line.

Sample

Input

3 4 4
0 1
0 0

2 1
1 2

0 0
0 2

1 0
0 2

1 4
2 3
1 3
2 2

Output

0 2
0 0

0 2
0 1

0 1
0 0

2 1
1 2

Source: ycc