Given $n$ matrices $A_1,A_2,…,A_n$ of size $2×2$. You need to calculate the product of the matrices $A_i,A_{i+1},…,A_j$ for several queries. All calculations are performed modulo $r$.

The first line of the input file contains integers $r\ (1≤r≤10,000),\ n\ (1≤n≤200,000),\ m\ (1≤m≤200,000)$. 

The following $n$ blocks are two lines each containing two integers, the matrix descriptions. 

Then follow $m$ pairs of integers from $1$ to $n$, requests for a product on a segment.

Print $m$ blocks of two lines, two integers in each: products on segments. Separate blocks with an empty string. All calculations are performed modulo $r$.