Constructing a Monotonic Sequence with Prefix MEX Constraints

You are given an integer n and k constraints. You are to construct a non‐decreasing sequence A of length n (possibly empty) consisting of nonnegative integers such that if we define its prefix MEX sequence B by

\(B[i]=\mathrm{MEX}\{A_1,A_2,\dots,A_i\}\),

then for every given constraint expressed as a pair (x, y) the number x appears exactly y times among the entries of B.

Recall that for a sequence \(X\) of finitely many nonnegative integers, the MEX is the smallest nonnegative integer that does not occur in \(X\); for example, \(\mathrm{MEX}\{1,2,3\}=0\) and \(\mathrm{MEX}\{0,1,2,4\}=3\).

Important: There are two possible constructions for A:

• Case 1: When A does not contain 0. In this case, for every prefix the MEX is 0. Hence B is an all-zero sequence and the only valid constraint is (0, n).
• Case 2: When A contains 0. In a non-decreasing A the first element must be 0. Then, the prefix MEX sequence B will be constructed in "blocks". In particular, if we introduce 0 at index 1 then B[1]=1. Later when we first introduce 1 in A at some position, B will jump to 2 and so on. Thus, if we decide to introduce exactly the numbers \(0,1,2,\dots, M-1\) in A then B will consist of consecutive constant segments with values 1, 2, …, M (the last block being the final MEX value). Suppose the lengths of these blocks are \(L_1,L_2,\dots,L_M\). Then we have:</p>

  \(B[1]\) appears \(L_1\) times, \(B[2]\) appears \(L_2\) times, …, and \(B[M]\) appears \(L_M\) times, with \(L_i\ge 1\) for every block and \(\sum_{i=1}^{M}L_i=n\).

  For every input constraint (x, y) with x >= 1, we need the corresponding block (with value x) to have length exactly y. For any block with no constraint, you may assign a length of at least 1 arbitrarily. If there is extra length remaining, it can be added to any unconstrained block (or to the last block if all blocks are constrained) as long as the total length remains n.

  If no valid sequence A exists, then output -1.

  You do not need to optimize any other property of A besides satisfying the constraints.

  inputFormat

  The first line contains two integers n and k (where n is the required length of the sequence A and k is the number of constraints).

  Each of the next k lines contains two integers x and y indicating that the number x must appear exactly y times in the prefix MEX sequence B of A.

  Note: It is guaranteed that there are more than 2 test cases.

  outputFormat

  If there exists a valid non-decreasing sequence A satisfying the conditions, output n space-separated nonnegative integers in one line representing A. Otherwise, output -1.

  sample

  5 1
  0 5
  

  1 1 1 1 1