Cryptography
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 Z_r = Z/rZ.
Each linear transformation is defined by 2x2 matrix. Georgie has a sequence of matrices A_1, A_2, ..., A_n. As a step of his algorithm he must take some segment A_i, A_{i+1}, ..., A_j of the sequence and multiply some vector by a product P_{i,j} = A_i×A_{i+1}×...×A_j of the segment. He must do it for m various segments. Help Georgie to determine the products he needs.
Input
The first line contains r (1 ≤ r ≤ 10000), n (1 ≤ n ≤ 30000) and m (1 ≤ m ≤ 30000). 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.
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.
Separate blocks with an empty line.