题目描述

在一个充满竞争的冒险者公会里，小风是一位专注任务调度的管理者。他的任务列表每天都会被冒险者们频繁刷新。公会里有 $n$ 位冒险者，他们的编号从 $1$ 到 $n$。每当某位冒险者完成任务并提交成果时，小风会将他们放在任务列表的首位，以彰显他们的活跃度。

任务列表可以用一个大小为 $n$ 的排列 $p$ 来表示：

• $p_1$ 是最近完成任务的冒险者，
• $p_2$ 是第二最近完成任务的冒险者，依此类推。

起初，任务列表是冒险者的初始顺序 $[1, 2, \dots, n]$，代表每位冒险者初始的排序位置。

接着，小风一共处理了 $m$ 次任务提交，第 $j$ 次提交来自编号为 $a_j$ 的冒险者。每当某位冒险者完成任务时，任务列表会发生如下变化：

1. 这位冒险者 $a_j$ 会被移动到列表的第一位；
2. 位于第一位和冒险者 $a_j$ 当前位置之间的所有其他冒险者依次向后移动一位。

注意：

• 如果这位冒险者 $a_j$ 本来就在第一位，则任务列表保持不变。

例如：假设当前任务列表是 $p = [4,1,5,3,2]$：

1. 如果冒险者 $3$ 提交任务，列表变为 $[3,4,1,5,2]$；
2. 如果冒险者 $4$ 提交任务，列表不变，仍是 $[4,1,5,3,2]$；
3. 如果冒险者 $2$ 提交任务，列表变为 $[2,4,1,5,3]$。

现在，小风希望统计，每位冒险者在初始状态及任务提交后的所有变化中，曾经占据过的最靠前的位置和最靠后的位置。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \leq n, m \leq 3 \cdot 10^5$)， 表示冒险者数量和任务提交的次数。

第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$ ($1 \leq a_i \leq n$)，表示每次提交任务的冒险者编号。

输出格式

输出 $n$ 行，每行包含两个整数，分别表示某位冒险者在任务列表中的最靠前位置和最靠后位置。

样例

5 4
3 5 1 4

1 3
2 5
1 4
1 5
1 5

4 3
1 2 4

1 3
1 2
3 4
1 4

解释

对于样例1：

初始任务列表：$[1, 2, 3, 4, 5]$

处理任务提交的过程如下：

1. 冒险者 $3$ 提交任务后，列表变为：$[3, 1, 2, 4, 5]$
2. 冒险者 $5$ 提交任务后，列表变为：$[5, 3, 1, 2, 4]$
3. 冒险者 $1$ 提交任务后，列表变为：$[1, 5, 3, 2, 4]$
4. 冒险者 $4$ 提交任务后，列表变为：$[4, 1, 5, 3, 2]$

因此每位冒险者的最靠前位置和最靠后位置为：

• 冒险者 $1$: 最靠前 $1$, 最靠后 $3$
• 冒险者 $2$: 最靠前 $2$, 最靠后 $5$
• 冒险者 $3$: 最靠前 $1$, 最靠后 $4$
• 冒险者 $4$: 最靠前 $1$, 最靠后 $5$
• 冒险者 $5$: 最靠前 $1$, 最靠后 $5$