[Solution] Cross Coloring solution codeforces

Cross Coloring solution codeforces – There is a sheet of paper that can be represented with a grid of size 𝑛×𝑚n×m — 𝑛n rows and 𝑚m columns of cells. All cells are colored in white initially.

𝑞q operations have been applied to the sheet. The 𝑖i-th of them can be described as follows:

  • 𝑥𝑖xi 𝑦𝑖yi — choose one of 𝑘k non-white colors and color the entire row 𝑥𝑖xi and the entire column 𝑦𝑖yi in it. The new color is applied to each cell, regardless of whether the cell was colored before the operation.

The sheet after applying all 𝑞q operations is called a coloring. Two colorings are different if there exists at least one cell that is colored in different colors.

Cross Coloring solution codeforces

How many different colorings are there? Print the number modulo 998244353998244353.

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of testcases.

The first line of the testcase contains four integers 𝑛,𝑚,𝑘n,m,k and 𝑞q (1𝑛,𝑚,𝑘,𝑞21051≤n,m,k,q≤2⋅105) — the size of the sheet, the number of non-white colors and the number of operations.

The 𝑖i-th of the following 𝑞q lines contains a description of the 𝑖i-th operation — two integers 𝑥𝑖xi and 𝑦𝑖yi (1𝑥𝑖𝑛1≤xi≤n1𝑦𝑖𝑚1≤yi≤m) — the row and the column the operation is applied to.

The sum of 𝑞q over all testcases doesn’t exceed 21052⋅105.

Cross Coloring solution codeforces

For each testcase, print a single integer — the number of different colorings modulo 998244353998244353.

Example

input

Copy
2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2

Cross Coloring solution codeforces

3
4

Leave a Comment