405255: GYM101858 G Gift Swords
Description
Asuna wants give a gift to Kirito. She want to buy swords, but she doesn't know which yet.
Since Kirito is a dual-wielder (meaning than he can use two swords at the same time), Asuna will buy a pair of swords to him, but dual-wielders have to use compatible swords.
Each sword can be identified as one positive integer $$$id$$$ ($$$id > 0$$$). Two swords are compatible if they do not have any characteristic in common. The characteristics of a sword are all positive integers $$$c$$$ ($$$c > 1$$$) which $$$id = k \times c$$$, for some integer $$$k > 0$$$.
For example, the sword with $$$id = 15$$$ has two characteristics: $$$3$$$ and $$$5$$$.
The sword shop have $$$n$$$ swords in total. As times passes, swords go out of stock and back to stock. Asuna wants to know, for each event, how many pairs of swords she can gift Kirito.
InputThe first line of input contains two integers, $$$n$$$ and $$$t$$$ ($$$1 \le n, t \le 2 \times 10^5$$$) — the number of swords the shop sells and how many events will happen.
The next line contains $$$n$$$ space-separated integers, $$$id_i$$$ ($$$1 \le id_i \le 5 \times 10^5$$$) — the identification of each sword. Swords does not necessarily have distinct identifications.
The next $$$t$$$ lines contains, each, one integer, $$$x$$$ ($$$1 \le x \le n$$$) — the $$$x$$$-th sword came out of stock or back to stock. If the $$$x$$$-th sword was in stock then it came out of stock, otherwise it came back to stock.
Initially no swords are in stock.
OutputFor each event print how many pairs of swords Asuna can gift Kirito.
ExamplesInput5 6Output
1 2 3 4 6
1
2
3
4
5
1
0Input
1
3
5
6
2
3 5Output
1 2 4
1
2
3
2
1
0
1
2
1
0