If you have ever heard of cryptocurrencies like Bitcoin or Ethereum, then you definitely don't want to miss VNOICoin — a special coin in the VNOI ecosystem. The special feature of VNOICoin lies in its "mining" method: instead of using computational power to solve cryptographic puzzles, participants must find a fun permutation.

Each time a new transaction block is created, the VNOICoin system generates a positive integer ~n~, a permutation ~b = [b_1, b_2, \dots, b_n]~ of the numbers from ~1~ to ~n~, and a prime number ~k~.

A permutation ~p = [p_1, p_2, \dots, p_n]~ is called a fun permutation corresponding to ~(b, k)~ if ~p~ satisfies the following condition:

For example, with ~b = [1, 2, 3]~ and ~k = 3~, there are ~6~ possible permutations of ~p~. The following permutations are not fun permutations corresponding to ~(b, k)~:

• ~[1, 3, 2]~, because ~k \cdot p_2 = 3 \cdot 3 = 9~ is not divisible by ~b_2 = 2~;

• ~[2, 1, 3]~, because ~k \cdot p_2 = 3 \cdot 1 = 3~ is not divisible by ~b_2 = 2~;

• ~[2, 3, 1]~, because ~k \cdot p_2 = 3 \cdot 3 = 9~ is not divisible by ~b_2 = 2~;

• ~[3, 1, 2]~, because ~k \cdot p_2 = 3 \cdot 1 = 3~ is not divisible by ~b_2 = 2~;

The permutations ~[1, 2, 3]~ and ~[3, 2, 1]~ are two fun permutations.

The profit obtained from a fun permutation ~p~ is the number of fun permutations ~q~ corresponding to ~(b, k)~ that are lexicographically smaller than ~p~ ~^*~.

With the above example (~b = [1, 2, 3]~, ~k = 3~):

• The fun permutation ~[1, 2, 3]~ has a profit of ~0~, since there is no other fun permutation that is lexicographically smaller;

• The fun permutation ~[3, 2, 1]~ has a profit of ~1~, since there is only one fun permutation ~[1, 2, 3]~ that is lexicographically smaller.

Long — a cryptocurrency enthusiast — has found a fun permutation ~p~ corresponding to the given ~(b, k)~. However, due to a security breach, the VNOICoin developers have implemented a new security mechanism with ~q~ updates: Each update consists of swapping two positions ~x~ and ~y~ in both sequences ~p~ and ~b~, i.e., swap ~p_x~ with ~p_y~ and simultaneously swap ~b_x~ with ~b_y~.

Long wants to know whether his "mining" strategy is effective. Help Long quickly determine the initial profit of the sequence, as well as the profit after each update. Since the profit value can be very large, print the profit modulo ~10^9 + 7~.

~^*~Given two different permutations ~p~ and ~q~ of length ~n~, we say ~q~ is lexicographically smaller than ~p~ if ~q_i < p_i~, where ~i~ is the first position such that ~p_i \neq q_i~.

Input

Each test consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \leq t \leq 10^4~) – the number of test cases. The description of each test case is as follows.

The first line contains three positive integers ~n, k, q~ (~2 \le k \le n \leq 10^5~, ~0 \le q \le 10^5~) – the length of the permutation, the prime number ~k~ generated, and the number of updates.

The second line contains ~n~ positive integers ~b_i~ (~1 \leq b_i \leq n~) – the permutation generated by VNOICoin in the transaction block.

The third line contains ~n~ positive integers ~p_i~ (~1 \leq p_i \leq n~) – the fun permutation found by Long. The data guarantees that this sequence is a fun permutation corresponding to ~(b, k)~.

The ~i~-th line of the next ~q~ lines contains ~2~ positive integers ~x, y~ (~1 \le x, y \le n~, ~x \neq y~), representing the update to the sequences. Note that the queries are not independent, i.e., query ~i~ affects subsequent queries.

It is guaranteed that:

• The sum of ~n~ over all test cases does not exceed ~10^5~,

• The sum of ~q~ over all test cases does not exceed ~10^5~.

Output

For each test case, print ~q + 1~ integers. The ~i~-th number is the profit value of the sequence ~p~ after the first ~i - 1~ queries have been applied in the order given in the input, modulo ~10^9 + 7~.

Scoring

Sample Input 1

2
6 3 3
3 2 4 1 5 6
1 2 4 3 5 6
1 4
1 3
2 6
8 2 4
8 7 2 4 5 1 3 6
4 7 1 8 5 2 3 6
1 4
2 5
1 5
6 8

Sample Output 1

0 2 1 3
2 12 12 2 3

Notes

In the first test case, with ~k = 3~,

• Initially, ~b = [3, 2, 4, 1, 5, 6]~ and ~p = [1, 2, 4, 3, 5, 6]~. Here, ~p~ is also the lexicographically smallest fun permutation corresponding to ~b~, so Long's profit is ~0~.

• After query ~1~, ~b = [\underline{1}, 2, 4, \underline{3}, 5, 6]~ and ~p = [\underline{3}, 2, 4, \underline{1}, 5, 6]~. There are ~2~ fun permutations lexicographically smaller than ~p~: ~[1, 2, 4, 3, 5, 6]~ and ~[1, 6, 4, 3, 5, 2]~, so Long's profit is ~2~.

• After query ~2~, ~b = [\underline{4}, 2, \underline{1}, 3, 5, 6]~ and ~p = [\underline{4}, 2, \underline{3}, 1, 5, 6]~. There is ~1~ fun permutation lexicographically smaller than ~p~: ~[4, 2, 1, 3, 5, 6]~, so Long's profit is ~1~.

• After query ~3~, ~b = [4, \underline{6}, 1, 3, 5, \underline{2}]~ and ~p = [4, \underline{6}, 3, 1, 5, \underline{2}]~. There are ~3~ fun permutations lexicographically smaller than ~p~: ~[4, 2, 1, 3, 5, 6]~, ~[4, 2, 3, 1, 5, 6]~, and ~[4, 6, 1, 3, 5, 2]~, so Long's profit is ~3~.