Криптографія

Молодий криптоаналітик Джордж планує зламати новий шифр, створений його другом Ендрю. Для цього йому потрібно виконати кілька лінійних перетворень у кільці (Z_r = Z/rZ).

Кожне лінійне перетворення задається (2 $\times$ 2) матрицею. Джордж має послідовність матриць (A_1, A_2, ..., A_n). На кожному кроці алгоритму він повинен вибрати певний відрізок (A_i, A_i+1, ..., A_j) цієї послідовності та перемножити вектор на добуток (P_i,j = A_i $\times$ A_i+1 $\times$ ...$\times$ A_j). Цю операцію він має виконати для (m) різних відрізків. Допоможіть Джорджу знайти необхідні добутки.

Вхідні дані

Перший рядок містить значення (r) ((1 $\le$ r $\le$ 10000)), (n) ((1 $\le$ n $\le$ 30000)) і (m) ((1 $\le$ m $\le$ 30000)). Наступні (n) блоків по дві рядки містять по два цілі числа в діапазоні від (0) до (r - 1), що задають матриці. Блоки відокремлені один від одного порожніми рядками. Далі йдуть (m) пар цілих чисел у діапазоні від (1) до (n), кожна з яких визначає відрізок, добуток на якому потрібно обчислити.

Вихідні дані

Виведіть (m) блоків, кожен з яких містить по дві рядки. Кожна рядок містить по два цілі числа в діапазоні від (0) до (r - 1), утворюючи таким чином матрицю добутку.

Блоки розділяйте порожнім рядком.

Приклади