题目描述

令 $n$ 的素因子分解结果为：

$$n=\prod\limits_{i=1}^k p_i^{\alpha_i},\ p_1<p_2<\cdots<p_k$$

现给出一个长为 $m$ 的，不包含重复元素的序列 $r$，定义 $f(n)$ 为：

$$f(n)=\prod\limits_{i=1}^m p_{r_i}\times \alpha_{r_i}$$

如果 $r_i>k$，我们认为此时 $p_{r_i}\times \alpha_{r_i}=1$。

给定 $q$ 次查询，每次给出一个 $x$，多次查询 $\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}f(ix)\bmod 2^{32}$ 的值。

为了减少输出量，请输出所有答案的异或和。特别地，我们将以质因数分解的形式给出 $x$。

输入格式

输入第一行包含三个整数 $n,m,q$ ($1 \le n \le 7 \times 10^8, 1 \le m \le 25, 1 \le q \le 5 \times 10^5$)，分别表示查询上界的参数，序列 $r$ 的长度，以及询问的数量。

输入第二行包含 $m$ 个整数 $r_1,r_2,\ldots,r_m$ ($1 \le r_i \le 25$, $r_i$ 互不相同)。

接下来 $q$ 行，第 $i$ 行会先输入一个整数 $L$ 表示 $x$ 的质因子分解项数。接下来输入 $2L$ 个整数 $P_1,A_1,P_2,A_2,\ldots,P_L,A_L$ ($P_i$ 为质数且互不相同)，表示 $x=\prod\limits_{i=1}^{L} P_{i}^{A_i}$，保证 $1 \le x \le n，A_i\ge 1$。

特殊地，若 $L=0$，则表示 $x=1$。

输出格式

输出一行包含一个整数，表示所有询问答案的异或和。

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

31