Wakana Sakai wants to finish a song that she and her mother never completed. She has found an incomplete melody and wants to compose it into a beautiful and harmonious piece of music.

A melody of length $n$ consists of $k$ different notes, meaning each note $a_1, \dots, a_n$ is an integer from $1$ to $k$. The $k$ notes form an equal temperament, and the transition between two adjacent notes $a_i, a_{i+1}$ forms a progression of size $(a_{i+1} - a_i) \pmod k$.

Wakana has a harmony table $h_0, \dots, h_{k-1}$ for these progressions, where $h_i$ is the harmony value of a progression of size $i$.

She believes that in a melody, when a progression of the same size appears repeatedly, its harmony is additive in terms of powers. That is, if a melody contains $c_i$ progressions of size $i$, their total harmony is $h_i^{c_i}$. Specifically, she assumes $0^0 = 1$.

She believes that the harmony of different sizes of progressions in a melody is simply additive, meaning the harmony of the entire melody is $\sum_{i=0}^{k-1} h_i^{c_i}$.

Now she has found the incomplete melody, in which $m$ notes are already determined, namely $a_{x_i} = y_i$. Wakana wants you to calculate the sum of the harmonies of all $k^{n-m}$ possible melodies if she can choose the remaining $n-m$ notes arbitrarily. Since the answer can be very large, you only need to help her find the value modulo $20120923$.

Input

The input contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^5$), representing the number of test cases.

For each test case, the first line contains three integers: the melody length $n$ ($1 \le n \le 10^9$), the number of determined notes $m$ ($0 \le m \le 10^6$), and the number of note types $k$ ($1 \le k \le 10^6$).

The next line contains an array of length $k$, representing $h_0, \dots, h_{k-1}$ in order. It is guaranteed that $0 \le h_i < 20120923$.

The next $m$ lines each contain two integers $x_i, y_i$, representing $a_{x_i} = y_i$. It is guaranteed that $1 \le x_i \le n$, $1 \le y_i \le k$, and all $x_i$ are distinct.

It is guaranteed that $\sum k \le 10^6$ and $\sum mk \le 10^6$.

Output

Output $T$ lines, each containing an integer representing the result modulo $20120923$.

Examples

Input 1

3
7 0 3
0 1 2
13 3 7
1 2 2 2 0 1 0
2 1
10 7
7 5
1000000000 10 12
203213032110
10
10 1
100 2
1000 3
10000 4
100000 5
1000000 6
10000000 7
100000000 8
1000000000 9

Output 1

14667
3100924
13878903

Note

For the second test case, one possible complete melody is: $[5, 1, 1, 2, 3, 5, 5, 6, 1, 7, 1, 2, 3]$, where $c_0 = 2, c_1 = 6, c_2 = 2, c_3 = 1, c_4 = c_5 = 0, c_6 = 1$. Therefore, its harmony is $1^2 + 2^6 + 2^2 + 2^1 + 0^0 + 1^0 + 0^1 = 73$.