Consider the prime factorization of a positive integer $n$: $$n = \prod_{i=1}^{k} p_i^{\alpha_i}, \text{ where } p_1 < p_2 < \dots < p_k$$

Given a sequence $r$ of length $m$, where all elements in $r$ are distinct, define $f(n)$ as follows: $$f(n) = \prod_{i=1}^{m} (p_{r_i} \times \alpha_{r_i})$$ If $r_i > k$, we consider $p_{r_i} \times \alpha_{r_i} = 1$.

There are $q$ queries. For each query, given $x$, calculate the result of: $$\left( \sum_{i=1}^{\lfloor n/x \rfloor} f(ix) \right) \pmod{2^{32}}$$

To reduce the output size, output the XOR sum of all answers. Specifically, $x$ is given in the form of its prime factorization.

Input

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 for the queries, the length of sequence $r$, and the number of queries, respectively.

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

The next $q$ lines each describe a query. The $i$-th line starts with an integer $L$, representing the number of terms in the prime factorization of $x$. This is followed by $2L$ integers $P_1, A_1, P_2, A_2, \dots, P_L, A_L$ ($P_i$ are distinct primes), representing $x = \prod_{i=1}^{L} P_i^{A_i}$, with the guarantee that $1 \le x \le n$ and $A_i \ge 1$. Specifically, if $L = 0$, it means $x = 1$.

Output

Output a single line containing an integer, representing the XOR sum of all query answers.

Examples

Input 1

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

Output 1

31