Matrix Reconstruction from Row and Column Sums with Constraints

Given an integer \(n\), you have \(n^2\) unknown integers \(a_1,a_2,\dots,a_{n^2}\) arranged in an \(n\times n\) matrix. The unknowns satisfy two sets of equations:

Row equations: For \(i=1,\dots,n\): \[ \sum_{j=1}^{n} a_{(i-1)n+j} = A_i. \]

Column equations: For \(i=1,\dots,n\): \[ \sum_{j=1}^{n} a_{i+(j-1)n} = B_i. \]

In addition, there are \(m\) constraints of the form \(a_{p_i}=q_i\). Each \(a_i\) must be an integer in the range \([-2^{63},2^{63})\). It is guaranteed that the input equations and constraints are consistent with the ranges.

Your task is to find any valid solution that satisfies all the equations and constraints. If no solution exists, output No Solution. Otherwise, output OK in the first line and then a valid solution as a sequence of \(n^2\) integers in row-major order.

Note: The row equations and column equations are not independent (in fact, \(\sum_{i=1}^n A_i=\sum_{i=1}^n B_i\) is required for a valid solution).

inputFormat

The input consists of several lines:

1. An integer \(n\) indicating the size of the matrix.
2. A line with \(n\) integers: \(A_1, A_2, \dots, A_n\), representing the row sums.
3. A line with \(n\) integers: \(B_1, B_2, \dots, B_n\), representing the column sums.
4. An integer \(m\) indicating the number of constraints.
5. Then \(m\) lines follow, each containing two integers \(p_i\) and \(q_i\) which mean that \(a_{p_i}=q_i\). The unknowns are numbered from 1 to \(n^2\) in row-major order.

outputFormat

If no solution exists output No Solution (without quotes). Otherwise, print OK in the first line followed by a line containing \(n^2\) space‐separated integers representing a valid solution in row-major order.

sample

2
3 7
4 6
0

OK
0 3 4 3