← 返回题目列表

Codeforces · 547/C

C. 迈克和泡沫

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

迈克是 Rico 酒吧的调酒师。在 Rico's,他们将啤酒杯放在一个特殊的架子上。 Rico's 有 n 种啤酒,编号从 1 到 n。第 i 种啤酒上有 ai 毫升的泡沫。

Maxim 是 Mike 的老板。今天他告诉 Mike 执行 q 查询。最初架子是空的。在每个请求中,Maxim 都会给他一个数字 x。如果编号 x 的啤酒已经在货架上,那么迈克应该将其从货架上移走,否则他应该将其放入货架上。

每次查询后,Mike 应该告诉他货架的分数。熊是极客。因此,他们认为货架的分数是货架上眼镜的对数 (i, j),使得 i < j 且 $$\gcd(a_i, a_j) = 1$$,其中 $$\gcd(a,b)$$ 是数字 a 和 b 的最大公约数。

迈克累了。所以他请求你帮助他执行这些请求。

输入

第一行输入包含数字n和q(1≤n,q≤2×105),不同种类啤酒的数量和查询次数。

下一行包含 n 个空格分隔的整数,a1, a2, ... , an (1 ≤ ai ≤ 5 × 105),即每种啤酒顶部泡沫的高度。

接下来的 q 行包含查询。每个查询由一个整数 x (1 ≤ x ≤ n) 组成,它是应在货架上添加或删除的啤酒的索引。

输出

对于每个查询,在一行中打印该查询的答案。

示例

输入 #1

5 6
1 2 3 4 6
1
2
3
4
5
1

输出 #1

0
1
3
5
6
2