CF1644D Cross Coloring

有一张纸，可以用一个 $n \times m$ 的网格表示：共有 $n$ 行 $m$ 列的格子。所有格子初始都是白色的。 对这张纸进行了 $q$ 次操作。第 $i$ 次操作如下： - $x_i$ $y_i$ —— 选择 $k$ 种非白色中的一种颜色，将第 $x_i$ 行和第 $y_i$ 列的所有格子都涂成这种颜色。无论该格子之前是否被涂色，都会被新颜色覆盖。 所有 $q$ 次操作完成后得到一种“涂色方案”。如果存在至少一个格子在两种方案中颜色不同，则认为这两种方案不同。 一共有多少种不同的涂色方案？请输出方案数对 $998\,244\,353$ 取模的结果。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含四个整数 $n, m, k, q$（$1 \le n, m, k, q \le 2 \cdot 10^5$），分别表示纸张的大小、非白色的颜色数和操作数。 接下来的 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n$；$1 \le y_i \le m$），表示第 $i$ 次操作作用的行和列。 所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$。

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

由 ChatGPT 4.1 翻译