Problem Description

Let the prime factorization of $n$ be:

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

Now you are given a sequence $r$ of length $m$ with no repeated elements. Define $f(n)$ as:

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

If $r_i>k$, we treat $p_{r_i}\times \alpha_{r_i}=1$.

You are given $q$ queries. In each query, an $x$ is given, and you need to compute the value of

$$\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}f(ix)\bmod 2^{32}$$

for multiple queries.

To reduce output size, please output the XOR of all query answers. In particular, $x$ will be given in the form of its prime factorization.

Input Format

The first line contains three integers $n,m,q$ ($1 \le n \le 7 \times 10^8, 1 \le m \le 25, 1 \le q \le 5 \times 10^5$), representing the upper bound parameter, the length of the sequence $r$, and the number of queries.

The second line contains $m$ integers $r_1,r_2,\ldots,r_m$ ($1 \le r_i \le 25$, and all $r_i$ are distinct).

The next $q$ lines describe the queries. In the $i$-th line, an integer $L$ is given first, indicating the number of prime factorization terms of $x$. Then $2L$ integers $P_1,A_1,P_2,A_2,\ldots,P_L,A_L$ are given ($P_i$ are primes and are pairwise distinct), meaning

$$x=\prod\limits_{i=1}^{L} P_{i}^{A_i}$$

It is guaranteed that $1 \le x \le n$ and $A_i\ge 1$.

In particular, if $L=0$, then $x=1$.

Output Format

Output one line containing one integer, which is the XOR of the answers to all queries.

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

31

Hint

Translated by ChatGPT 5