UOJ Logo

NOI.AC

1S 256MB

#60. ball

统计

ball

题目描述

数轴上有 $n$ 个球,每个球直径为 $1$,第 $i$ 个球的左端点为 $p_i$(即占据了数轴上 $[p_i,p_i+1]$)。在 $P$ 位置有一堵墙。

有 $q$ 个操作,每次要么以 $x$ 位置为左端点放一个新球(如果有了就不管),要么把最左边的球往右推。一个球碰到另一个的时候,旧球停下来,新球继续滚。球碰到墙的时候就停下来。

最后你需要输出所有球的位置。

输入格式

第一行三个整数 $n, q, P$ 。

第二行一共 $n$ 个整数,表示 $p_i$ 。

接下来一共 $q$ 行,描述一个操作,其中第一个数 $ty$ 表示数据类型。若 $ty=1$ 则表示为第一类操作,后接一个参数 $x$ ;若 $ty=2$ 则表示为第二类参数,后面没有参数。

输出格式

一行若干个数,从小到大输出最终每个球的位置。

样例

输入

5 3 10
1 8 3 7 2
2
1 4
2

输出

1 3 5 6 8 9

数据范围

$n, q \leq 2*10^5, P \leq 10^9$ 。

Subtask1 ($30\%$) : $n, q \leq 1000$ 。

Subtask2 ($20\%$) :只有第二类操作。

Subtask3 ($20\%$) : $P \leq 5*10^5$ 。

Subtask4 ($30\%$) :无特殊限制。

时间限制: $1s$ 。

空间现在: $256MB$ 。