Cryptography#5662
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 2 \times 2 matrix. Georgie has a sequence of matrices A_1, A_2, \ldots, A_n. As a step of his algorithm he must take some segment A_i, A_{i+1}, \ldots, A_j of the sequence and multiply some vector by a product P_{i,j} = A_i \times A_{i+1} \times \ldots \times A_j of the segment. He must do it for various segments. Help Georgie to determine the products he needs.
The first line contains (1 \leq r \leq 10000), (1 \leq n \leq 30000) and (1 \leq m \leq 30000). Next blocks of two lines, containing two integer numbers ranging from to r - 1 each, describe matrices. Blocks are separated with blank lines. They are followed by pairs of integer numbers ranging from to each that describe segments, products for which are to be calculated.
Print blocks containing two lines each. Each line should contain two integer numbers ranging from to r - 1 and define the corresponding product matrix.
Separate blocks with an empty line.
Example 1