#1338. 跑跑龟

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zxyoi

题目描述

众所周知,只有乌龟才会比谁更活得久。但是在桌游《跑跑龟》里,跑得远的乌龟才是冠军。

小可想让游戏更加刺激,因此他正在设计一款《超级跑跑龟》,但是需要一套系统来辅助计算乌龟的位置。

游戏的棋子由编号 [1,...,n][1,...,n] 的乌龟组成。游戏的棋盘由编号 [0,...,m][0,...,m] 的位置组成,其中 00 号位置为起点。一开始所有的棋子都在起点,且1号棋子位于最下方,第i+1i+1号棋子在第ii号棋子上方(1i<n1 \leq i < n)。

接下来会发生mm次操作,第ii次操作,编号为xx的乌龟会携带其上的所有棋子移动到ii号位置上。

当全部的 mm 次操作结束后,输出每个棋子所在的位置编号。

输入格式

第一行三个整数 n,m (1n,m5×105)n, m\ (1 \le n,m \le 5\times 10^5) 用空格隔开,代表棋子个数和棋盘长度。

接下来 mm 行,每一行一个整数 x (1xn)x\ (1 \le x \le n) 用空格隔开,代表一次操作。

输出格式

输出 nn 个整数,用空格隔开,表示每个棋子所在的位置编号。

样例

样例输入一

5 5
3
4
1
2
4

样例输入二

3 4 1 5 5