#P18713. Efficient Summation

Efficient Summation

Efficient Summation

对于正整数 yy,将其质因数分解写为

$$y=\prod_{j=1}^{k}p_j^{\alpha_j},\qquad p_1<p_2<\cdots<p_k.$$

给定一个长度为 mm、元素两两不同的序列 rr,定义

f(y)=∏i=1m(priαri).f(y)=\prod_{i=1}^{m}(p_{r_i}\alpha_{r_i}).

如果 ri>kr_i>k,对应的因子 priαrip_{r_i}\alpha_{r_i} 视为 11。特别地,f(1)=1f(1)=1。这里的排名针对不同质因子按质数值递增排列后的顺序;某个质因子的指数会乘在该质数上。

给定上界 nn,有 qq 次查询。每次给出正整数 xx,查询答案为

$$g(x)=\left(\sum_{i=1}^{\lfloor n/x\rfloor}f(ix)\right)\bmod 2^{32}.$$

为了减少输出量,只需输出全部查询答案的按位异或。输入中的 xx 以质因数分解形式给出。

输入格式

第一行包含三个整数 n,m,qn,m,q,满足 1≤n≤7×1081\le n\le7\times10^8、1≤m≤251\le m\le25、1≤q≤5×1051\le q\le5\times10^5。

第二行包含 mm 个两两不同的整数 r1,…,rmr_1,\ldots,r_m,满足 1≤ri≤251\le r_i\le25。不保证 rr 有序。

接下来 qq 行分别描述一次查询。每行首先给出一个整数 LL,随后给出 2L2L 个整数 P1,A1,…,PL,ALP_1,A_1,\ldots,P_L,A_L,表示

x=∏j=1LPjAj.x=\prod_{j=1}^{L}P_j^{A_j}.

PjP_j 是两两不同的质数,Aj≥1A_j\ge1,保证 1≤x≤n1\le x\le n。L=0L=0 时表示 x=1x=1。

保证 P1<⋯<PLP_1<\cdots<P_L。

输出格式

输出一行一个整数,表示全部 g(x)g(x) 的按位异或,范围为 00 到 232−12^{32}-1。先对每次查询的和取模,再异或。

原样例

10 2 5
2 3
0
1 5 1
1 2 1
1 7 1
2 2 1 3 1
31