Молодой криптоаналитик Джордж планирует взломать новый шифр, изобретенный его другом Эндрю. Для этого он должен совершить несколько линейных преобразований над кольцом \textbf{Z_r} = \textbf{Z/rZ}. Каждое линейное преобразование определяется \textbf{2}x\textbf{2} матрицей. У Джорджа имеется последовательность матриц \textbf{A_1}, \textbf{A_2}, ..., \textbf{A_n}. За шаг алгоритма он должен взять некоторый отрезок \textbf{A_i}, \textbf{A_\{i+1\}}, ..., \textbf{A_j} этой последовательности и перемножить некоторый вектор на произведение \textbf{P_\{i,j\}} = \textbf{A_i}×\textbf{A_\{i+1\}}×\textbf{...}×\textbf{A_j}. Такую операцию он должен проделать для \textbf{m }различных отрезков. Помогите Джорджу найти необходимые произведения. \InputFile Первая строка содержит значения \textbf{r }(\textbf{1 }≤ \textbf{r }≤ \textbf{10000}), \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{30000}) и \textbf{m }(\textbf{1 }≤ \textbf{m }≤ \textbf{30000}). Следующие \textbf{n }блоков по две строки содержат по два целых числа в промежутке от \textbf{0 }до \textbf{r - 1}, задавая матрицы. Блоки отделены друг от друга пустыми строками. Далее следуют \textbf{m} пар целых чисел в промежутке от \textbf{1 }до \textbf{n}, каждая из которых характеризует отрезок, произведение на котором следует вычислить. \OutputFile Вывести \textbf{m }блоков, каждый из которых содержит по две строки. Каждая строка содержит по два целых числа в промежутке от \textbf{0 }до \textbf{r - 1}, формируя таким образом матрицу произведения. Блоки разделять пустой строкой.