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