Báo cáo

Mỗi tháng, giám đốc Blake nhận được một bản báo cáo gồm $n$ số nguyên. Trước khi đến tay Blake, bản báo cáo lần lượt đi qua $m$ người quản lý. Người quản lý thứ $i$ thực hiện đúng một thao tác: sắp xếp $r_i$ phần tử đầu tiên của dãy theo thứ tự không giảm (nếu $t_i=1$) hoặc không tăng (nếu $t_i=2$), rồi chuyển bản báo cáo cho người tiếp theo (hoặc cho Blake nếu $i=m$).

Cho dãy ban đầu $a_1,a_2,\dots ,a_n$ và mô tả thao tác của từng người quản lý, hãy xác định bản báo cáo cuối cùng mà Blake nhận được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số phần tử của báo cáo và số người quản lý.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: dãy ban đầu.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $t_i$ và $r_i$: người quản lý thứ $i$ sắp xếp $r_i$ phần tử đầu theo thứ tự không giảm ($t_i=1$) hoặc không tăng ($t_i=2$).

Dữ liệu ra

In ra $n$ số nguyên: bản báo cáo cuối cùng sau khi qua tay cả $m$ người quản lý.

Ràng buộc

• $1\le n,m\le 200000$
• $|a_i|\le {10}^9$
• $t_i\in \{1,2\}$, $1\le r_i\le n$

Ví dụ