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$ 。