集合加和查询

题目描述

有一个长度为 $N$ 的整数数列 $A=(A_1,A_2,\ldots,A_N)$,所有元素初始均为 $0$。还有一个集合 $S$,初始为空。

请按顺序执行以下 $Q$ 个查询。处理完所有 $Q$ 个查询后,求出数列 $A$ 的每个元素的值。第 $i$ 个查询的格式如下:

给定整数 $x_i$。如果 $x_i$ 在 $S$ 中,则将 $x_i$ 从 $S$ 中移除;否则,将 $x_i$ 插入 $S$。然后,对于每个满足 $j\in S$ 的 $j=1,2,\ldots,N$,将 $|S|$ 加到 $A_j$。

这里,$|S|$ 表示集合 $S$ 中元素的个数。例如,若 $S=\lbrace 3,4,7\rbrace$,则 $|S|=3$。

输入格式

输入按以下格式从标准输入给出:

$N$ $Q$
$x_1$ $x_2$ $\ldots$ $x_Q$

输出格式

以如下格式输出处理完所有查询后的数列 $A$:

$A_1$ $A_2$ $\ldots$ $A_N$

样例

3 4
1 3 3 2

6 2 2

在第一个查询中,将 $1$ 插入 $S$,$S=\lbrace 1\rbrace$。然后,将 $|S|=1$ 加到 $A_1$。数列变为 $A=(1,0,0)$。

在第二个查询中,将 $3$ 插入 $S$,$S=\lbrace 1,3\rbrace$。然后,将 $|S|=2$ 加到 $A_1$ 和 $A_3$。数列变为 $A=(3,0,2)$。

在第三个查询中,将 $3$ 从 $S$ 中移除,$S=\lbrace 1\rbrace$。然后,将 $|S|=1$ 加到 $A_1$。数列变为 $A=(4,0,2)$。

在第四个查询中,将 $2$ 插入 $S$,$S=\lbrace 1,2\rbrace$。然后,将 $|S|=2$ 加到 $A_1$ 和 $A_2$。数列变为 $A=(6,2,2)$。

最终,数列变为 $A=(6,2,2)$。

4 6
1 2 3 2 4 2

15 9 12 7

数据范围

• $1 \leq N,Q \leq 2 \times 10^5$
• $1 \leq x_i \leq N$
• 所有输入值均为整数。