
ZOJ Problem Set  2671
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×2 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. InputThere 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. Separate blocks with an empty line. Sample
Source: Andrew Stankevich's Contest #8 