#描述#
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. <BR>
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. <BR>
Help LCS to determine the products he needs.

#格式#
##输入格式##
There are several test cases in the input. The first line of each case contains r (1 &lt= r &lt= 10,000), n (1 &lt= n &lt= 30,000) and m (1 &lt= m &lt= 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.

##输出格式##
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.

#样例1#
##样例输入1##

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

##样例输出1##

0 2
0 0

0 2
0 1

0 1
0 0

2 1
1 2

#限制#
2000ms
32768KB

#提示#

#来源#
ycc