2296: 伙伴

Memory Limit:128 MB Time Limit:1.000 S
Creator:
Submit:5 Solved:2

Description

有 n 名士兵参加了一场激烈的战斗。每个士兵身边有两个伙伴,第 ii号士兵的左侧伙伴编号为 i-1右侧伙伴的编号为和 i+111 号士兵没有左侧伙伴nn号士兵没有右侧伙伴

在战斗过程中,陆续牺牲了 m 名士兵。一旦一名士兵牺牲了,存活的士兵就会相互接近,形成新的伙伴关系。给定士兵们牺牲的顺序及编号,请你输出当每个士兵牺牲时,新构成伙伴关系的两个士兵的编号。

Input

第一行:两个正整数表示 n 和 m
第二行到第 m+1行:在第 i+1行,有一个正整数 s_i,表示第 i个牺牲的士兵编号。

Output

共 m 行:每行两个整数,第 i行表示当 s_i牺牲时,左右伙伴的编号,如果某侧没有伙伴,输出一个 *

Sample Input

5 3
3
2
1

Sample Output

2 4
1 4
* 4