Mô phỏng Messenger

Polycarp có $n$ người bạn, được đánh số từ $1$ đến $n$. Danh sách trò chuyện gần đây của anh ta là một hoán vị $p$ của $1,2,\dots ,n$: $p_1$ là người bạn vừa nhắn tin gần nhất, $p_2$ là người thứ hai gần nhất, và cứ thế tiếp tục.

Ban đầu danh sách có dạng $p=[1,2,\dots ,n]$.

Sau đó Polycarp nhận $m$ tin nhắn. Tin nhắn thứ $j$ đến từ người bạn $a_j$. Khi đó người bạn $a_j$ được chuyển lên đầu danh sách, còn tất cả những người đang đứng từ đầu danh sách đến vị trí hiện tại của $a_j$ đều bị dịch xuống một bậc. Nếu $a_j$ đã ở ngay đầu danh sách thì không có gì thay đổi.

Ví dụ, nếu danh sách là $p=[4,1,5,3,2]$:

• nhận tin từ người $3$, danh sách thành $[3,4,1,5,2]$;
• nhận tin từ người $4$, danh sách không đổi $[4,1,5,3,2]$;
• nhận tin từ người $2$, danh sách thành $[2,4,1,5,3]$.

Với mỗi người bạn, hãy xét tất cả các vị trí mà người đó từng đứng: ở trạng thái ban đầu và sau mỗi tin nhắn. Với mỗi người bạn, tìm vị trí nhỏ nhất và vị trí lớn nhất mà người đó từng đứng.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số người bạn và số tin nhắn.
• Dòng thứ hai chứa $m$ số nguyên $a_1,a_2,\dots ,a_m$ — người gửi của các tin nhắn.

Dữ liệu ra

In ra $n$ dòng. Dòng thứ $i$ chứa hai số nguyên: vị trí nhỏ nhất và vị trí lớn nhất mà người bạn $i$ từng đứng (tính cả trạng thái ban đầu và sau mỗi tin nhắn).

Ràng buộc

• $1\le n,m\le 3·{10}^5$
• $1\le a_i\le n$

Ví dụ