Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2671
Cryptography

Time Limit: 5 Seconds      Memory Limit: 32768 KB

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

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

Help Georgie 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

InputOutput
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
0 2
0 0

0 2
0 1

0 1
0 0

2 1
1 2

Source: Andrew Stankevich's Contest #8
Submit    Status