Криптографія#5662
Молодий криптоаналітик Джордж планує зламати новий шифр, створений його другом Ендрю. Для цього йому потрібно виконати кілька лінійних перетворень у кільці Z_r = Z / rZ.
Кожне лінійне перетворення задається 2 \times 2 матрицею. Джордж має послідовність матриць A_1, A_2, \ldots, A_n. На кожному кроці алгоритму він повинен вибрати певний відрізок A_i, A_{i+1}, \ldots, A_j цієї послідовності та перемножити вектор на добуток P_{i,j} = A_i \times A_{i+1} \times \ldots \times A_j. Цю операцію він має виконати для різних відрізків. Допоможіть Джорджу знайти необхідні добутки.
Перший рядок містить значення (1 \leq r \leq 10000), (1 \leq n \leq 30000) і (1 \leq m \leq 30000).
Наступні блоків по два рядки містять по два цілі числа в діапазоні від до r - 1, що задають матриці. Блоки відокремлені один від одного порожніми рядками.
Далі йдуть пар цілих чисел у діапазоні від до , кожна з яких визначає відрізок, добуток на якому потрібно обчислити.
Виведіть блоків, кожен з яких містить по два рядки. Кожен рядок містить по два цілі числа в діапазоні від до r - 1, утворюючи таким чином матрицю добутку.
Блоки розділяйте порожнім рядком.
Приклад 1