该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

石宇浩学长负责管理实验室的 n 类器材，第 i 类器材最初有 a[i] 件。一天内会依次发生 m 次借还操作：

• B i x：申请借走第 i 类器材 x 件。若库存不少于 x，则借出成功并扣除库存；否则本次申请失败，库存不变。
• R i x：归还第 i 类器材 x 件，库存增加 x。

请输出一天结束后每类器材的库存，并统计失败的借用申请数量。

输入格式

第一行输入两个整数 n m。

第二行输入 n 个整数 a[1], a[2], ..., a[n]。

接下来 m 行，每行输入一个字符 op 和两个整数 i x，表示一次操作。

输出格式

第一行输出 n 个整数，表示所有器材的最终库存。

第二行输出一个整数，表示失败的借用申请数量。

样例

3 5
5 2 8
B 1 3
B 2 4
R 2 5
B 2 6
B 3 8

2 1 0
1

数据范围与限制

• 1 <= n, m <= 100000；
• 0 <= a[i] <= 10^9；
• 1 <= i <= n，1 <= x <= 10^9；
• 最终库存不超过 10^18；
• 时间限制：1 秒；
• 空间限制：64 MiB。