Cho dãy $(a_1,a_2,\dots,a_n)=(1,2,\dots,n)$ , tức $a_i=i$ .

Lan sẽ thực hiện $m$ lần thao tác trên dãy này, mỗi lần có thể là:

• sắp xếp $a_1,a_2,\dots,a_{q_i}$ theo thứ tự giảm dần;

• hoặc sắp xếp $a_{q_i},a_{q_i+1},\dots,a_n$ theo thứ tự tăng dần.

Hãy tìm dãy thu được sau khi hoàn thành các thao tác.

Dữ liệu vào

Dòng đầu tiên của đầu vào chứa hai số nguyên $n,m$ , lần lượt là độ dài dãy và số lần thao tác.

$m$ dòng tiếp theo mô tả các thao tác trên dãy, trong đó dòng thứ $i$ chứa hai số nguyên $p_i,q_i$ :

• $p_i=0$ : sắp xếp $q_i$ số đầu tiên theo thứ tự giảm dần;

• $p_i=1$ : sắp xếp từ số thứ $q_i$ đến cuối dãy theo thứ tự tăng dần.

Dữ liệu ra

In ra một dòng chứa $n$ số nguyên, các số liền kề cách nhau đúng một dấu cách.

Ví dụ

Input

3 3
0 3
1 2
0 2

Output

3 1 2

Ghi chú

Giải thích mẫu

Dãy ban đầu là $(1,2,3)$ .

Sau bước 1 là $(3,2,1)$ .

Sau bước 2 là $(3,1,2)$ .

Sau bước 3 dãy không đổi, vì hai số đầu đã theo thứ tự giảm dần.

Quy mô test và ràng buộc

• Với 30% số test: $n,m\le 1000$ ;

• Với 60% số test: $n,m\le 5000$ ;

• Với tất cả các test: $1\le n,m\le 100000$ , $0\le p_i\le 1$ , $1\le q_i\le n$ .