Cross Coloring（逆向，map）

原文链接

There is a sheet of paper that can be represented with a grid of size n×mn×m: nn rows and mm columns of cells. All cells are colored in white initially.

qq operations have been applied to the sheet. The ii-th of them can be described as follows:

• xixi yiyi — choose one of kk non-white colors and color the entire row xixi and the entire column yiyi 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 qq operations is called a coloring. Two colorings are different if there exists at least one cell that is colored in different colors.

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

Input

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

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

The ii-th of the following qq lines contains a description of the ii-th operation — two integers xixi and yiyi (1≤xi≤n1≤xi≤n; 1≤yi≤m1≤yi≤m) — the row and the column the operation is applied to.

The sum of qq over all testcases doesn't exceed 2⋅1052⋅105.

Output

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

output

Copy

3
4s

颜色会被覆盖=》从后往前暴力

行把列都覆盖，或者列把行都覆盖，或者出现过，那么就没有必要继续

#include
using namespace std;
#define int long long
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")//
const int maxj=2e5+100,mod=998244353;
int r[maxj],c[maxj];
bool rr[maxj],cc[maxj];//bool速度快
void solve(){
    //因为颜色是覆盖的，所以逆向思考，后端染的色，会让它具备这种颜色，
    int n,m,k,q;
    cin>>n>>m>>k>>q;
    for(int i=1;i<=q;++i){
        cin>>r[i]>>c[i];
    }
    memset(rr,0,sizeof(rr));
    memset(cc,0,sizeof(cc));
    int numr=0,numc=0;
    int ans=1;
    for(int i=q;i>=1;--i){
        if(numr==n||numc==m||(rr[r[i]]&&cc[c[i]])){//行，或者列都被涂过，这个行列出现过
            continue;
        }
        if(!rr[r[i]]){
            rr[r[i]]=1;
            numr++;
        }
        if(!cc[c[i]]){
            cc[c[i]]=1;
            numc++;
        }
        ans=ans*k%mod;//每一个都对应k种颜色
    }cout<>t;
    while(t--)solve();
    return 0;
}