Lexicographical Sequence Sorting

You are given m sequences, each of length n, consisting of nonnegative integers. The first sequence is given as \(a_{1,1}, a_{1,2}, \ldots, a_{1,n}\). For each \(i\) from 2 to \(m\), you are provided with two integers \(p_i\) and \(x_i\) representing the following update:

• For every index \(1 \leq j \leq n\) with \(j \neq p_i\), we have \(a_{i,j} = a_{i-1,j}\).
• \(a_{i,p_i} = x_i\).

After constructing these \(m\) sequences, sort them in lexicographical order; that is, sequence \(A\) precedes sequence \(B\) if there exists an index \(j\) such that \(A_1 = B_1, A_2 = B_2, \ldots, A_{j-1} = B_{j-1}\) and \(A_j < B_j\). If two sequences are identical, the sequence with the smaller original index comes first. Output the original indices of the sequences in the sorted order.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) (\(1 \leq n, m \leq 10^5\), for instance).

The second line contains \(n\) space-separated nonnegative integers representing the first sequence: \(a_{1,1}, a_{1,2}, \ldots, a_{1,n}\).

Each of the next \(m-1\) lines contains two integers \(p_i\) and \(x_i\) (for \(2 \leq i \leq m\)), meaning that the \(i\)th sequence is identical to the \((i-1)\)th sequence except that the \(p_i\)th element is replaced by \(x_i\). Note that indices are 1-indexed.

outputFormat

Output a single line containing \(m\) integers — the indices of the sequences in sorted order according to the lexicographical order (with the original sequence index used as a tie-breaker).

sample

3 3
1 2 3
2 1
1 4

2 1 3