Nếu bạn đã từng nghe đến các loại tiền mã hóa như Bitcoin hay Ethereum, thì bạn chắc chắn không muốn bỏ lỡ VNOICoin — một đồng coin đặc biệt trong hệ sinh thái VNOI. Điểm đặc biệt của VNOICoin nằm ở cách "đào coin": thay vì sử dụng sức mạnh tính toán để giải các bài toán mã hóa, người tham gia sẽ phải tham gia vào việc tìm ra các dãy hoán vị vui vẻ.

Mỗi khi tạo một khối giao dịch mới, hệ thống VNOICoin sẽ sinh ra một số nguyên dương ~n~, một dãy hoán vị ~b = [b_1, b_2, \dots, b_n]~ của các số từ ~1~ đến ~n~, và một số nguyên tố ~k~.

Một hoán vị ~p = [p_1, p_2, \dots, p_n]~ được gọi là hoán vị vui vẻ tương ứng với ~(b, k)~ nếu ~p~ thỏa mãn điều kiện sau:

Ví dụ, với ~b = [1, 2, 3]~ và ~k = 3~, ta có tất cả ~6~ hoán vị của ~p~. Các hoán vị sau đây không phải là hoán vị vui vẻ tương ứng với ~(b, k)~:

• ~[1, 3, 2]~, do ~k \cdot p_2 = 3 \cdot 3 = 9~ không chia hết cho ~b_2 = 2~;

• ~[2, 1, 3]~, do ~k \cdot p_2 = 3 \cdot 1 = 3~ không chia hết cho ~b_2 = 2~;

• ~[2, 3, 1]~, do ~k \cdot p_2 = 3 \cdot 3 = 9~ không chia hết cho ~b_2 = 2~;

• ~[3, 1, 2]~, do ~k \cdot p_2 = 3 \cdot 1 = 3~ không chia hết cho ~b_2 = 2~;

Hoán vị ~[1, 2, 3]~ và ~[3, 2, 1]~ là hai hoán vị vui vẻ.

Lợi nhuận thu được từ hoán vị vui vẻ ~p~ là số lượng hoán vị vui vẻ ~q~ tương ứng với ~(b, k)~ mà có thứ tự từ điển nhỏ hơn ~p~ ~^*~.

Với ví dụ trên (~b = [1, 2, 3]~, ~k = 3~):

• Hoán vị vui vẻ ~[1, 2, 3]~ có lợi nhuận thu được là ~0~, do không có hoán vị vui vẻ khác có thứ tự từ điển nhỏ hơn;

• Hoán vị vui vẻ ~[3, 2, 1]~ có lợi nhuận thu được là ~1~, do có duy nhất hoán vị vui vẻ ~[1, 2, 3]~ với thứ tự từ điển nhỏ hơn.

Long — một người đam mê tiền mã hóa — đã tìm được một hoán vị vui vẻ ~p~ tương ứng với ~(b, k)~ đã cho. Tuy nhiên, do hệ thống VNOICoin bị tấn công, nhà phát triển đã triển khai cơ chế bảo mật mới với ~q~ lần cập nhật: Mỗi lần cập nhật sẽ bao gồm việc hoán đổi hai vị trí ~x~ và ~y~ trong cả hai dãy ~p~ và ~b~, tức là đổi chỗ ~p_x~ với ~p_y~ và đồng thời đổi chỗ ~b_x~ với ~b_y~.

Long muốn biết rằng chiến thuật "đào coin" của mình có hiệu quả hay không. Hãy giúp Long xác định nhanh lợi nhuận ban đầu của dãy, cũng như lợi nhuận sau mỗi lần cập nhật. Do giá trị của lợi nhuận có thể rất lớn, hãy in lợi nhuận modulo ~10^9 + 7~.

~^*~Với hai hoán vị ~p~ và ~q~ khác nhau cùng có độ dài ~n~, ta nói ~q~ nhỏ hơn ~p~ theo thứ tự từ điển nếu ~q_i < p_i~, với ~i~ là vị trí đầu tiên mà ~p_i \neq q_i~.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \leq t \leq 10^4~) – số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa hai số nguyên dương ~n, k, q~ (~2 \le k \le n \leq 10^5~, ~0 \le q \le 10^5~) – độ dài của dãy hoán vị, số nguyên tố ~k~ được tạo ra và số lần thay đổi của dãy.

Dòng thứ hai chứa ~n~ số nguyên dương ~b_i~ (~1 \leq b_i \leq n~) – dãy hoán vị mà VNOICoin tạo ra trong khối giao dịch.

Dòng thứ ba chứa ~n~ số nguyên dương ~p_i~ (~1 \leq p_i \leq n~) – dãy hoán vị vui vẻ mà Long tìm được. Dữ liệu đảm bảo rằng dãy này là một hoán vị vui vẻ tương ứng với ~(b, k)~.

Dòng thứ ~i~ trong ~q~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên dương ~x, y~ (~1 \le x, y \le n~, ~x \neq y~), là dữ liệu cho sự điều chỉnh của dãy. Lưu ý rằng các truy vấn là không độc lập với nhau, tức là truy vấn ~i~ sẽ ảnh hưởng tới các truy vấn sau.

Đảm bảo rằng:

• Tổng của ~n~ qua các test case không vượt quá ~10^5~,

• Tổng của ~q~ qua các test case không vượt quá ~10^5~.

Output

Với mỗi test case, hãy in ra ~q + 1~ số nguyên. Số thứ ~i~ trong đó là giá trị lợi nhuận của dãy ~p~ sau khi ~i - 1~ truy vấn đầu tiên đã được áp dụng theo thứ tự cho bởi 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

Ở test case đầu tiên, với ~k = 3~,

• Ban đầu, ~b = [3, 2, 4, 1, 5, 6]~ và ~p = [1, 2, 4, 3, 5, 6]~. ~p~ ở đây cũng là hoán vị vui vẻ tương ứng với ~b~ có thứ tự từ điển nhỏ nhất, nên lợi nhuận của Long là ~0~.

• Sau truy vấn ~1~, ~b = [\underline{1}, 2, 4, \underline{3}, 5, 6]~ và ~p = [\underline{3}, 2, 4, \underline{1}, 5, 6]~. Tồn tại ~2~ hoán vị vui vẻ bé hơn ~p~ theo thứ tự từ điển là ~[1, 2, 4, 3, 5, 6]~ và ~[1, 6, 4, 3, 5, 2]~, nên lợi nhuận của Long là ~2~.

• Sau truy vấn ~2~, ~b = [\underline{4}, 2, \underline{1}, 3, 5, 6]~ và ~p = [\underline{4}, 2, \underline{3}, 1, 5, 6]~. Tồn tại ~1~ hoán vị vui vẻ bé hơn ~p~ theo thứ tự từ điển là ~[4, 2, 1, 3, 5, 6]~, nên lợi nhuận của Long là ~1~.

• Sau truy vấn ~3~, ~b = [4, \underline{6}, 1, 3, 5, \underline{2}]~ và ~p = [4, \underline{6}, 3, 1, 5, \underline{2}]~. Tồn tại ~3~ hoán vị vui vẻ bé hơn ~p~ theo thứ tự từ điển là ~[4, 2, 1, 3, 5, 6]~, ~[4, 2, 3, 1, 5, 6]~ và ~[4, 6, 1, 3, 5, 2]~, nên lợi nhuận của Long là ~3~.