CF1644D.Cross Coloring

There is a sheet of paper that can be represented with a grid of size $n \times 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:

• $x_i$ $y_i$ — choose one of $k$ non-white colors and color the entire row $x_i$ and the entire column $y_i$ 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.

How many different colorings are there? Print the number modulo $998\,244\,353$.

有一张可以表示为 $n \times m$ 网格的纸：共 $n$ 行、$m$ 列的单元格。初始时所有单元格均为白色。

对该纸张共执行了 $q$ 次操作。第 $i$ 次操作可描述如下：

• $x_i$ $y_i$ — 从 $k$ 种非白色颜色中任选一种，并将整行 $x_i$ 和整列 $y_i$ 均染成该颜色。新颜色会覆盖每个单元格，无论该单元格在本次操作前是否已被染色。

执行完全部 $q$ 次操作后的纸张称为一种染色方案。若存在至少一个单元格在两种染色方案中被染成不同颜色，则称这两种染色方案不同。

问：共有多少种不同的染色方案？请输出结果对 $998\,244\,353$ 取模的值。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of the testcase contains four integers $n, m, k$ and $q$ ($1 \le n, m, k, q \le 2 \cdot 10^5$) — 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 $x_i$ and $y_i$ ($1 \le x_i \le n$; $1 \le y_i \le m$) — the row and the column the operation is applied to.

The sum of $q$ over all testcases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含四个整数 $n, m, k$ 和 $q$（$1 \le n, m, k, q \le 2 \cdot 10^5$）——纸张的尺寸、非白色颜色种类数以及操作次数。

接下来的 $q$ 行中，第 $i$ 行描述第 $i$ 个操作——两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n$；$1 \le y_i \le m$）——表示该操作作用于第 $x_i$ 行、第 $y_i$ 列。

所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$。

For each testcase, print a single integer — the number of different colorings modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——不同染色方案的数量对 $998\,244\,353$ 取模的结果。