Sequence Rearrangement Operations

Given a sequence \( (a_{1}, a_{2}, \cdots, a_{n}) = (1, 2, \cdots, n) \), i.e., \( a_i = i \) for \( 1 \le i \le n \). You are to perform \( m \) operations on this sequence. Each operation is one of the following two types:

• Type 0: Sort the prefix \( (a_{1}, a_{2}, \cdots, a_{q}) \) in descending order, i.e., \( a_{1} \ge a_{2} \ge \cdots \ge a_{q} \).
• Type 1: Sort the suffix \( (a_{q}, a_{q+1}, \cdots, a_{n}) \) in ascending order, i.e., \( a_{q} \le a_{q+1} \le \cdots \le a_{n} \).

After performing all \( m \) operations sequentially, output the final sequence.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers \( n \) and \( m \) indicating the length of the sequence and the number of operations respectively.
2. Each of the next \( m \) lines contains two integers \( op \) and \( q \). Here, \( op \) represents the type of operation. If \( op = 0 \), sort the prefix \( (a_{1}, a_{2}, \cdots, a_{q}) \) in descending order; if \( op = 1 \), sort the suffix \( (a_{q}, a_{q+1}, \cdots, a_{n}) \) in ascending order.

Note: It is guaranteed that \( 1 \le q \le n \).

outputFormat

Output the final sequence after all operations. The elements should be printed in one line, separated by a space.

sample

5 2
0 3
1 4

3 2 1 4 5