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 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.
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.
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.
Source: Andrew Stankevich's Contest #8