← 返回题目列表

Codeforces · 1198/B

B. 福利国家

中文机器翻译题面 查看原题

有一个国家,有 $$$n$$$ 公民。他们中的第 $$$i$$$ 最初拥有 $$$a_{i}$$$ 钱。政府严格控制公民的财富。每当公民购物或赚钱时,他们必须向社会服务机构发送一张收据,注明他们目前拥有的金额。

有时政府会向穷人发放补助:所有钱严格少于 $$$x$$$ 的公民都会得到相应的补助,这样在发放后他们就拥有了 $$$x$$$ 的钱。在这种情况下,公民不会发送收据。

您知道每个公民的初始财富以及所有事件的日志:收入和支出。在所有事件发生后恢复每个公民拥有的金钱数量。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — 公民人数。

下一行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_{i} \le 10^{9}$$$) — 公民的初始余额。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^{5}$$$) — 事件数。

接下来的 $$$q$$$ 行中的每一行都包含一个事件。这些事件按时间顺序给出。

每个事件被描述为 1 p x ($$$1 \le p \le n$$$, $$$0 \le x \le 10^{9}$$$) 或 2 x ($$$0 \le x \le 10^{9}$$$)。在第一种情况下,我们收到一张收据,表明第 $$$p$$$ 人的余额等于 $$$x$$$。在第二种情况下,我们得到参数 $$$x$$$ 的收益。

输出

打印 $$$n$$$ 整数 — 所有事件后所有公民的余额。

示例

输入 #1

4
1 2 3 4
3
2 3
1 2 2
2 1

输出 #1

3 2 3 4

输入 #2

5
3 50 2 1 10
3
1 2 0
2 8
1 3 20

输出 #2

8 8 20 8 10

注意

在第一个示例中,余额变化如下: 1 2 3 4 $$$\rightarrow$$$ 3 3 3 4 $$$\rightarrow$$$ 3 2 3 4 $$$\rightarrow$$$ 3 2 3 4

在第二个示例中,余额变化如下: 3 50 2 1 10 $$$\rightarrow$$$ 3 0 2 1 10 $$$\rightarrow$$$ 8 8 8 8 10 $$$\rightarrow$$$ 8 8 20 8 10