题目描述

题目译自 Ukrainian Olympiads in Informatics 2017 Stage 4 Day2 T4. День Народження

斯塔斯（Stas）的生日快到了，为此他决定举办一场盛大的派对。当然，斯塔斯向他所有的熟人都发了邀请函。预计会有大量客人到场，因此计划了一场盛大的表演。

所有客人都已告知斯塔斯他们何时会到达派对，以及何时必须离开。在分析了这些信息后，斯塔斯制定了一份客人到达和离开的时间表，因为他希望一切都能完美进行，并做好充分的准备。 派对将持续 $N$ 分钟。斯塔斯知道，在派对开始前，正好有 $K$ 位客人能到场。之后，在整个派对期间，每一分钟要么会有一位新客人到达，要么会有一位在场的客人离开。

经过巨大的努力，斯塔斯成功地让他最喜爱的著名艺人同意来演唱一首歌。为此，派对上将搭建一个巨大的舞台，舞台前将摆放无限数量的椅子，从 $1$ 开始连续编号。

不幸的是，有一个问题。这位著名艺人的日程非常紧张，他不确定自己究竟何时能来表演。因此，斯塔斯决定先用其他娱乐活动招待客人，当艺人到达并准备好开始时，再迅速地将所有客人安排到舞台前准备好的椅子上就座。

安排座位的方式如下：

首先，斯塔斯确定安排就座的顺序。客人们将按照这位英雄确定的顺序逐一就座。

然而，斯塔斯的每位朋友都有自己的怪癖。例如，每个人都有自己喜欢的数字。因此，当某人选择坐哪张椅子时，他会尝试选择带有自己喜欢号码的椅子。如果那个座位已经被占了，这位客人会感到不满，但还是会决定坐在紧挨着它的下一张椅子上。如果那张椅子也被占了，客人会更加不满，但会继续寻找下一个空位。可以认为这个过程是瞬间完成的。最终，客人对斯塔斯的总不满值可以用他实际坐下的椅子编号与他心仪的椅子编号之差来表示。斯塔斯是个很棒的朋友，所以他知道他每个熟人喜欢的数字。

艺人的表演只持续一瞬间，所以斯塔斯不必担心在表演期间会有人需要离开，或者有新客人到来需要安排座位。 当然，斯塔斯希望最小化客人的总不满值。

斯塔斯需要为派对的每一分钟计算出，如果要安排当前所有在场客人就座，所产生的最小总不满值是多少。对他来说，这是一项相当困难的任务，因此他请求您的帮助。

输入格式

输入文件的第一行包含两个自然数 $N$ 和 $K$，表示派对的持续时间（分钟）以及在派对开始前到达的客人数量。

下一行包含 $K$ 个用空格分隔的自然数，表示在派对开始前到场的客人喜欢的数字。

接下来的 $N$ 行是客人的到达-离开时间表。每行包含两个数字，$T$ 和 $X$。如果 $T$ 等于 $1$，表示在相应分钟会有一位新客人到来，其喜欢的数字是 $X$。否则，一位喜欢数字为 $X$ 的客人将不得不离开派对；保证在这种情况下，派对上至少有一位喜爱数字为 $X$ 的客人在场。

输入文件中的所有自然数均不超过 $5 \cdot 10^4$。$T$ 的值为 $0$ 或 $1$。

输出格式

在输出文件的第一行，输出 $N$ 个用空格分隔的数字，表示每一分钟安排所有在场客人就座后的最小总不满值。

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

4 1 1 3

在派对开始前，喜欢数字为 $1$、$1$ 和 $2$ 的客人到场了。派对开始，在第一分钟，又来了一位喜欢数字 2 的客人。现在有四位客人。一种最优的座位安排可能是这样的：

首先，我们邀请喜欢数字 $1$ 和 $2$ 的朋友就座。他们依次顺利地坐到 $1$ 号和 $2$ 号椅子上，没有对斯塔斯产生不满。接着，我们邀请喜欢数字 $1$ 的客人就座。由于 $1$ 号和 $2$ 号椅子已被占用，他坐到第 $3$ 号椅子上，对斯塔斯的不满值为 $3 - 1 = 2$。最后，喜欢数字 $2$ 的客人坐下，他坐到第 $4$ 号位置，不满值为 $4 - 2 = 2$。所有客人的总不满值等于 $4$。

在第二分钟，一位喜欢数字 $1$ 的客人离开派对，只剩下喜欢数字 $1$、$2$、$2$ 的人。

数据范围与提示

• 对于 $15\%$ 的数据，所有自然数不超过 $5$。
• 对于 $35\%$ 的数据，没有客人离开派对（所有的 $T$ 都等于 $1$）。