Min-Plus Matrix Range Query

You are given a sequence of n matrices \(a_1,a_2,\dots,a_n\), where each \(a_i\) is a \(2\times2\) matrix with integer entries. You need to process m queries. In each query, you are given an interval \([l, r]\) and you must compute the product:

\[ \prod_{i=l}^r a_i = a_l \times a_{l+1} \times \cdots \times a_r, \]

where the multiplication \(\times\) is defined as the min-plus matrix product. Specifically, for two \(2\times2\) matrices \( A =\begin{pmatrix}a_{11}&a_{12}\\ a_{21}&a_{22}\end{pmatrix}, \quad B =\begin{pmatrix}b_{11}&b_{12}\\ b_{21}&b_{22}\end{pmatrix}, \) their min-plus product \(C = A \times B\) is given by \[ C_{ij}=\min_{k=1}^{2}(A_{ik}+B_{kj}), \quad 1\le i,j\le 2. \]

Note: This problem is intended primarily for correctness testing and comparison of imprecise efficiency. Please avoid overusing the judging resources.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of matrices and the number of queries respectively).

Then for each \(i=1,2,\dots,n\), there are two lines describing the matrix \(a_i\). The first line contains two integers representing the first row and the second line contains two integers representing the second row of the matrix.

Each of the next \(m\) lines contains two integers \(l\) and \(r\) (\(1\leq l\leq r\leq n\)), representing a query.

outputFormat

For each query, output the resulting \(2\times2\) matrix in two lines. The first line should contain the two integers of the first row, and the second line should contain the two integers of the second row.

sample

2 1
1 2
3 4
5 6
7 8
1 2

6 7
8 9