P15556 [CCPC 2025 Harbin Site] Function Summation

Let the prime factorization of $n$ be: $$n=\prod\limits_{i=1}^k p_i^{\alpha_i},\ p_1

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 one line containing one integer, which is the XOR of the answers to all queries.

Translated by ChatGPT 5