Matrix Chain Product Query over Finite Field

You are given a sequence of n invertible k × k matrices over the finite field \(\mathbb{F}_p\) with \(p = 1145141\). The matrices are non-singular, i.e. their determinants are nonzero modulo \(p\). You are also given q queries. In each query, you are provided with two integers \(l\) and \(r\) (1-indexed), and you must compute the matrix product

[ A = \prod_{i=l}^{r} a_i \quad (\text{matrix multiplication is performed modulo } p) ]

where \(a_i\) is the \(i\)th matrix in the sequence. Output the resulting matrix for each query.

inputFormat

The first line contains three integers \(n\), \(k\), and \(q\) -- the number of matrices, the dimension of each square matrix, and the number of queries respectively.

The following \(n \times k\) lines describe the \(n\) matrices. For each matrix, there are \(k\) lines, and each line contains \(k\) space-separated integers representing the entries of the matrix (all operations are performed modulo \(1145141\)).

The next \(q\) lines each contain two integers \(l\) and \(r\) (1-indexed) representing a query.

outputFormat

For each query, output the resulting k × k matrix. Each matrix should be printed in \(k\) lines, with each line containing \(k\) space-separated integers.

sample

2 2 1
1 0
0 1
1 2
3 4
1 2

1 2
3 4