题目描述

斯塔斯的生日快到了，他决定举办一场盛大的聚会。他邀请了所有熟人。由于预计会有很多客人，聚会上还将安排一场大型表演。

所有客人都告诉了斯塔斯他们会在什么时候到达聚会，以及什么时候不得不离开。聚会持续 $N$ 分钟。斯塔斯知道，恰好有 $K$ 位客人能在聚会开始前到达。之后，在聚会的每一分钟，要么会有一位新客人到达，要么会有一位当前在场的客人离开。

经过努力，斯塔斯邀请到了他最喜欢的著名艺人演唱一首歌。舞台前有无限多把椅子，椅子编号为从 $1$ 开始的连续自然数。

问题是，艺人日程很紧，无法确定何时到达并开始表演。因此，斯塔斯需要在每一分钟都知道：如果艺人此刻到达，他要怎样快速安排当前所有客人入座，才能使客人的总不满值最小。

入座规则如下：

1. 斯塔斯先确定一个入座顺序；
2. 客人按照这个顺序一个一个选择座位；
3. 每位客人都有一个最喜欢的座位编号；
4. 当某位客人选择座位时，他会优先选择自己最喜欢的编号；如果该座位已被占用，他会选择后面第一个空座位；
5. 客人的不满值等于最终坐下的椅子编号减去他最喜欢的编号。

入座过程可以认为瞬间完成。表演只持续一瞬间，因此不需要考虑表演期间客人离开或到达。

斯塔斯想最小化当前所有客人的总不满值。请你对聚会的每一分钟计算这个最小值。

输入格式

第一行包含两个自然数 $N$ 和 $K$，表示聚会持续的分钟数，以及聚会开始前已经到达的客人数。

第二行包含 $K$ 个自然数，表示这些客人最喜欢的座位编号。

接下来 $N$ 行描述每一分钟的到达或离开事件。每行包含两个数 $T$ 和 $X$。

• 若 $T=1$，表示有一位新客人到达，其最喜欢的座位编号为 $X$；
• 若 $T=0$，表示有一位最喜欢座位编号为 $X$ 的客人离开。保证此时至少有一位这样的客人在场。

输入中的所有自然数均不超过 $5\cdot 10^4$，且 $T$ 只会取 0 或 1。

输出格式

在第一行输出 $N$ 个整数，第 $i$ 个数表示第 $i$ 分钟事件发生后，当前所有在场客人的最小总不满值。

样例输入

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

样例输出

4 1 1 3

样例解释

聚会开始前，有最喜欢座位编号为 $1,1,2$ 的三位客人。

第一分钟，来了一位最喜欢座位编号为 $2$ 的客人。现在共有四位客人。一个最优安排是：先让喜欢 $1$ 和 $2$ 的两位客人入座，他们都坐到自己喜欢的位置；然后让另一位喜欢 $1$ 的客人入座，由于 $1$ 和 $2$ 已被占用，他坐到 $3$ 号椅子，不满值为 $3-1=2$；最后让喜欢 $2$ 的客人坐到 $4$ 号椅子，不满值为 $4-2=2$。总不满值为 $4$。

第二分钟，一位喜欢 $1$ 的客人离开，场上只剩下喜欢 $1,2,2$ 的三位客人。

子任务

1. 15% 测试：所有数均不超过 $5$；
2. 35% 测试：没有客人离开，即所有 $T$ 均为 $1$。