Constructing a Sequence with Top‐Group Constraints

You are given a positive integer sequence \(a\) of length \(n\) where each \(a_i\) is in the range \(1\) to \(10^9\). In addition, you are given the values of \(s\) elements in the sequence (their positions and values are fixed) and \(m\) constraints. Each constraint is described by four numbers: \(l, r, k\) and then \(k\) positive integers \(x_1, x_2, \ldots, x_k\). This means that in the segment \(a_l, a_{l+1}, \ldots, a_r\) one can partition the elements into two groups: a top group consisting of exactly \(k\) numbers whose multiset is exactly \(\{x_1,x_2,\ldots,x_k\}\) (in any order), and a bottom group consisting of the remaining \(r-l+1-k\) numbers. Moreover, every number in the top group must be strictly greater than every number in the bottom group. (Note that if \(r-l+1-k > 0\) then automatically \(\min\{x_1,\ldots,x_k\}>1\) must hold.)

Your task is to construct any sequence \(a_1, a_2, \ldots, a_n\) fulfilling all the fixed values and all the \(m\) constraints, or determine that no such sequence exists. If there are multiple solutions, you can print any one.

Note: It is allowed that different constraints overlap. An element that is not fixed can be assigned an arbitrary value, but once assigned it cannot be changed. You must choose the assignments so that in every constraint the elements can be partitioned as described.

inputFormat

The first line contains three integers \(n, m, s\) (the length of the sequence, the number of constraints, and the number of fixed positions).

The next \(s\) lines each contain two integers \(p\) and \(v\), meaning that the element at position \(p\) is fixed to value \(v\) (1-indexed).

Then \(m\) lines follow. Each constraint is given in one line in the following format:

l r k x1 x2 ... xk

Here, \(l, r\) define the segment (1-indexed), \(k\) is the number of top elements in that segment, and \(x_1, x_2, \ldots, x_k\) is the multiset of the top numbers for that segment.

outputFormat

If a valid sequence exists, print \(n\) space‐separated integers representing the sequence \(a_1, a_2, \ldots, a_n\). Otherwise, print -1.

sample

5 1 2
1 5
3 3
1 5 2 5 4

5 4 3 1 1