#P17816. [ONTAK 2023]TAB

[ONTAK 2023]TAB

题目描述

有 nn 座工厂,第 ii 座工厂的权值为 aia_i。你维护一个由不超过 nn 的质数组成的集合 SS,初始为空。

每次操作给出一个质数 pp:如果 p∉Sp\notin S,就将它加入;否则将它删除。

每次操作后,求所有不被 SS 中任何质数整除的下标 ii 对应的 aia_i 之和。一个下标即使被多个已选质数整除,也只被覆盖一次。

输入格式

第一行两个整数 n,qn,q。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。第三行 qq 个质数,依次表示操作。

输出格式

输出 qq 行,每行一个整数,表示对应操作后的答案。

数据范围

1≤n≤1061\le n\le10^6,1≤q≤200001\le q\le20000,1≤ai≤10001\le a_i\le1000。每个操作数都是 [2,n][2,n] 内的质数,因此合法输入必然有 n≥2n\ge2。

样例

6 5
1 2 4 8 16 32
3 2 3 2 5
27
17
21
63
47