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