6745: 伙伴
[Creator : ]
Description
有 $n$ 名士兵参加了一场激烈的战斗。
每个士兵身边有两个伙伴，第 $i$ 号士兵的左侧伙伴编号为 $i-1$，右侧伙伴的编号为和 $i+1$。$1$ 号士兵没有左侧伙伴，$n$ 号士兵没有右侧伙伴。
在战斗过程中，陆续牺牲了 $m$ 名士兵。一旦一名士兵牺牲了，存活的士兵就会相互接近，形成新的伙伴关系。
给定士兵们牺牲的顺序及编号，请你输出当每个士兵牺牲时，新构成伙伴关系的两个士兵的编号。
每个士兵身边有两个伙伴，第 $i$ 号士兵的左侧伙伴编号为 $i-1$，右侧伙伴的编号为和 $i+1$。$1$ 号士兵没有左侧伙伴，$n$ 号士兵没有右侧伙伴。
在战斗过程中，陆续牺牲了 $m$ 名士兵。一旦一名士兵牺牲了，存活的士兵就会相互接近，形成新的伙伴关系。
给定士兵们牺牲的顺序及编号，请你输出当每个士兵牺牲时，新构成伙伴关系的两个士兵的编号。
Input
第一行：两个正整数表示 $n$ 和 $m$。
第二行到第 $m+1$ 行：在第 $i+1$ 行，有一个正整数 $s_i$，表示第 $i$ 个牺牲的士兵编号。
第二行到第 $m+1$ 行：在第 $i+1$ 行，有一个正整数 $s_i$，表示第 $i$ 个牺牲的士兵编号。
Output
共 $m$ 行：每行两个整数，第 $i$ 行表示当 $s_i$ 牺牲时，左右伙伴的编号，如果某侧没有伙伴，输出一个 *。
Constraints
对于 $30\%$ 的数据，$1\leq n\leq 10,000$；
对于 $60\%$ 的数据，$1\leq n\leq 100,000$；
对于 $100\%$ 的数据，$1\leq n\leq 1,000,000,\ 1\leq m<n$。
对于 $60\%$ 的数据，$1\leq n\leq 100,000$；
对于 $100\%$ 的数据，$1\leq n\leq 1,000,000,\ 1\leq m<n$。
Sample 1 Input
5 3
3
2
1
Sample 1 Output
2 4
1 4
* 4