Background

Description

有 n 个正整数 x1~xn，初始时状态均为未选。
有 m 个操作，每个操作给定一个编号 i，将 xi 的选取状态取反。每次操作后，你需要求出选取的数中有多少个互质的无序数对。

Format

Input

第一行两个整数 n,m。第二行 n 个整数 x1~xn。接下来 m 行每行一个整数。

Output

m 行，每行一个整数表示答案。

Sample

Input

4 5 
1 2 3 4 
1 
2 
3 
4 
1 

Output

0
1
3
5
2

Limitation

对于 20%的数据，n,m<=1000。
对于另外 30%的数据，xi<=100。
对于 100%的数据，n,m<=200000，xi<=500000，1<=i<=n。
2s, 128000KiB for each test case.

Hint

Source

CDQZ TEST