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$.


-----Input-----

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$.


-----Output-----

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


-----Examples-----

Input
2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2
Output
3
4


-----Note-----

None

Difficulty: MEDIUM_HARD
Tags: Mathematics

Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
import sys
from itertools import chain

def input():
	return sys.stdin.readline()[:-1]

def readline():
	return map(int, input().split())
MOD = 998244353

def solve():
	(n, m, k, q) = readline()
	last_in_row = dict()
	last_in_col = dict()
	for i in range(q):
		(x, y) = readline()
		last_in_row[x - 1] = i
		last_in_col[y - 1] = i
	lr = min(last_in_row.values()) if len(last_in_row) == n else 0
	lc = min(last_in_col.values()) if len(last_in_col) == m else 0
	start = max(lr, lc)
	is_valuable = [False] * q
	for i in chain(last_in_row.values(), last_in_col.values()):
		if i >= start:
			is_valuable[i] = True
	cnt = sum(is_valuable)
	print(pow(k, cnt, MOD))
t = int(input())
for __ in range(t):
	solve()


import sys
fin = sys.stdin
P = 998244353

def solve(n, m, k, q, o):
	cx = set()
	cy = set()
	unique_i = set()
	for (i, (x, y)) in enumerate(o[::-1]):
		if len(cx) == n or len(cy) == m:
			break
		if x not in cx or y not in cy:
			unique_i.add(i)
			cx.add(x)
			cy.add(y)
	return pow(k, len(unique_i), P)
t = int(fin.readline())
for test in range(t):
	(n, m, k, q) = list(map(int, fin.readline().split()))
	o = [tuple(map(int, fin.readline().split())) for _ in range(q)]
	print(solve(n, m, k, q, o))


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, m, k, q) = map(int, input().split())
	l = []
	rs = set()
	cs = set()
	for i in range(q):
		l.append([int(i) for i in input().split()])
	l.reverse()
	c = 0
	for [x, y] in l:
		if x not in rs or y not in cs:
			c = c + 1
			rs.add(x)
			cs.add(y)
		if len(rs) == n or len(cs) == m:
			break
	print(pow(k, c, 998244353))


import sys
input = sys.stdin.readline

def solve(n, m, k, q, arr):
	modulo = 998244353
	if n == 1 or m == 1:
		print(k % modulo)
		return
	dp = [0] * q
	dp[-1] = k
	(rSet, cSet) = (set(), set())
	rSet.add(arr[-1][0])
	cSet.add(arr[-1][1])
	for i in range(q - 2, -1, -1):
		(x, y) = arr[i]
		if x in rSet or y in cSet:
			if x not in rSet:
				if len(cSet) == m:
					dp[i] = dp[i + 1]
				else:
					dp[i] = dp[i + 1] * k % modulo
			elif y not in cSet:
				if len(rSet) == n:
					dp[i] = dp[i + 1]
				else:
					dp[i] = dp[i + 1] * k % modulo
			else:
				dp[i] = dp[i + 1]
		else:
			dp[i] = dp[i + 1] * k % modulo
		rSet.add(x)
		cSet.add(y)
	print(dp[0])
for _ in range(int(input())):
	(n, m, k, q) = map(int, input().split())
	arr = []
	for _ in range(q):
		(x, y) = map(int, input().split())
		arr.append([x - 1, y - 1])
	solve(n, m, k, q, arr)


def solve():
	t = int(input())
	for r in range(t):
		(n, m, k, q) = map(int, input().split())
		row = set()
		col = set()
		q_row = []
		q_col = []
		result = 1
		for i in range(q):
			s = input().split()
			q_row.append(int(s[0]))
			q_col.append(int(s[1]))
		for i in range(q - 1, -1, -1):
			f = 0
			if not q_row[i] in row:
				f = 1
				row.add(q_row[i])
			if not q_col[i] in col:
				f = 1
				col.add(q_col[i])
			if f == 1:
				result = result * k % 998244353
			if len(row) == n or len(col) == m:
				break
		print(result)
solve()


from enum import Enum, auto
import copy
import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		my_op = []
		(n, m, k, q) = map(int, input().split())
		for _ in range(q):
			my_op.append(list(map(int, input().split())))
		row_color = {}
		col_color = {}
		row_list = set()
		col_list = set()
		for (i, op) in enumerate(reversed(my_op)):
			if op[0] not in row_color:
				row_color[op[0]] = i
			if op[1] not in col_color:
				col_color[op[1]] = i
			row_list.add(op[0])
			col_list.add(op[1])
			if len(row_list) == n or len(col_list) == m:
				break
		num_colors = len(set(row_color.values()) | set(col_color.values()))
		res = 1
		for _ in range(num_colors):
			res = res * k
			res = res % 998244353
		print(res)
main()


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	(n, m, k, q) = M()
	queries = []
	for i in range(q):
		(x, y) = M()
		queries.append([x, y])
	r = set()
	c = set()
	cnt = 0
	for (x, y) in reversed(queries):
		if x in r and y in c or len(r) == n or len(c) == m:
			continue
		r.add(x)
		c.add(y)
		cnt += 1
	print(pow(k, cnt, mod2))


for _ in range(int(input())):
	(n, m, k, q) = map(int, input().split())
	o = [tuple(list(map(int, input().split()))) for i in range(q)][::-1]
	xy = [set(), set()]
	ans = 1
	for (x, y) in o:
		if len(xy[0]) < n and len(xy[1]) < m and (not (x in xy[0] and y in xy[1])):
			ans *= k
			ans %= 998244353
			xy[0].add(x)
			xy[1].add(y)
	print(ans)


for _ in range(int(input())):
	(n, m, k, q) = [int(x) for x in input().split()]
	l = []
	for i in range(q):
		(x, y) = [int(t) for t in input().split()]
		l.append([x, y])
	modting = 998244353
	rowscolored = set()
	columnscolored = set()
	l = l[::-1]
	kcnt = 0
	for i in l:
		if i[0] not in rowscolored or i[1] not in columnscolored:
			kcnt += 1
		columnscolored.add(i[1])
		rowscolored.add(i[0])
		if len(rowscolored) == n or len(columnscolored) == m:
			break
	print(pow(k, kcnt, modting) % modting)


ux = []
uy = []

def solve():
	(n, m, k, q) = list(map(int, input().split(' ')))
	mod = 998244353
	while len(ux) < n + 1:
		ux.append(False)
	while len(uy) < m + 1:
		uy.append(False)
	queries = []
	for i in range(q):
		(x, y) = map(int, input().split(' '))
		queries.append((x, y))
	cr = 0
	cc = 0
	res = 1
	for i in range(q - 1, -1, -1):
		(xi, yi) = queries[i]
		f = False
		if cr == n or cc == m:
			continue
		if ux[xi] == 0:
			ux[xi] = True
			cr += 1
			f = True
		if uy[yi] == 0:
			uy[yi] = True
			cc += 1
			f = True
		if f:
			res = res * k % mod
	for i in range(q):
		(xi, yi) = queries[i]
		ux[xi] = False
		uy[yi] = False
	print(res)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, m, k, q) = map(int, input().split())
	queries = []
	for _ in range(q):
		queries.append(tuple(map(int, input().split())))
	ligneColored = set()
	colColored = set()
	numberOfWay = 1
	while queries:
		currentQ = queries.pop()
		if len(ligneColored) == m or len(colColored) == n:
			break
		elif currentQ[0] in colColored and currentQ[1] in ligneColored:
			continue
		else:
			numberOfWay *= k
			numberOfWay = numberOfWay % 998244353
			colColored.add(currentQ[0])
			ligneColored.add(currentQ[1])
	print(numberOfWay)


t = int(input())
for tc in range(t):
	(n, m, k, q) = map(int, input().split())
	moves = []
	for ops in range(q):
		moves.append([int(fdsjk) for fdsjk in input().split()])
	modting = 998244353
	kcnt = 0
	moves.reverse()
	rowscolored = set()
	columnscolored = set()
	for i in moves:
		if i[0] not in rowscolored or i[1] not in columnscolored:
			kcnt += 1
		if i[0] not in rowscolored:
			rowscolored.add(i[0])
		if i[1] not in columnscolored:
			columnscolored.add(i[1])
		if len(rowscolored) == n or len(columnscolored) == m:
			break
	print(pow(k, kcnt, modting) % modting)


def power(a, n, m):
	if n == 0:
		return 1
	if n == 1:
		return a % m
	if n % 2 == 0:
		return power(a, n // 2, m) ** 2 % m
	else:
		return power(a, n // 2, m) * power(a, n - n // 2, m) % m
for some_random_name in range(int(input())):
	(n, m, k, q) = map(int, input().split())
	a = []
	for i in range(q):
		(l, b) = map(int, input().split())
		a.append([l, b])
	a.reverse()
	x = set()
	y = set()
	pos = 0
	for i in range(q):
		(l, r) = (a[i][0], a[i][1])
		if len(x) >= n or len(y) >= m:
			break
		if l in x and r in y:
			continue
		pos += 1
		x.add(l)
		y.add(r)
	print(pow(k, pos, 998244353))


class Solver1644D:

	def __init__(self):
		self.mod = 998244353
		(self.n, self.m, self.k, self.q) = list(map(int, input().split(' ')))
		self.inp = []
		for i in range(self.q):
			(x, y) = list(map(int, input().split(' ')))
			self.inp.append([x, y])

	def solve(self):
		seen_x = {}
		seen_y = {}
		output = 1
		for i in range(self.q - 1, -1, -1):
			if len(seen_x) != self.n and len(seen_y) != self.m and (seen_x.get(self.inp[i][0]) == None or seen_y.get(self.inp[i][1]) == None):
				output = output * self.k % self.mod
				seen_x[self.inp[i][0]] = 1
				seen_y[self.inp[i][1]] = 1
		return output
t = int(input())
while t:
	t -= 1
	cur = Solver1644D()
	print(cur.solve())


def solve(n, m, s, k):
	if m == 1 or n == 1:
		print(k)
		return
	s.reverse()
	x = dict()
	y = dict()
	count = 0
	for item in s:
		r = item[0]
		c = item[1]
		if r not in x or c not in y:
			if r not in x:
				x.__setitem__(r, '')
			if c not in y:
				y.__setitem__(c, '')
			count += 1
			if len(x) == n or len(y) == m:
				break
	ans = 1
	for i in range(0, count):
		ans = ans * k % 998244353
	print(ans)
	return
test = int(input())
for te in range(0, test):
	(n, m, k, q) = list(map(int, input().split()))
	s = []
	for pi in range(0, q):
		s.append(list(map(int, input().split())))
	solve(n, m, s, k)


mod = 998244353
t = int(input())
for _ in range(t):
	(n, m, k, q) = map(int, input().split())
	rd = {}
	cd = {}
	rs = set()
	cs = set()
	res = 1
	rc = []
	for i in range(q):
		(r, c) = map(int, input().split())
		rc.append([r, c])
		rd[r] = rd.get(r, 0) + 1
		cd[c] = cd.get(c, 0) + 1
		rs.add(r)
		cs.add(c)
	for (r, c) in rc:
		if rd[r] > 1 and cd[c] > 1 or (rd[r] > 1 and len(rs) == n) or (cd[c] > 1 and len(cs) == m):
			pass
		else:
			res *= k
			res %= mod
		rd[r] -= 1
		if rd[r] == 0:
			rs.remove(r)
		cd[c] -= 1
		if cd[c] == 0:
			cs.remove(c)
	print(res)


from re import T
t = int(input())
ans = []
for i in range(t):
	(n, m, k, q) = tuple(map(int, input().split()))
	arr = []
	for i in range(q):
		arr.append(tuple(map(int, input().split())))
	(r, c) = (set(), set())
	cnt = 0
	for i in range(q - 1, -1, -1):
		(ri, ci) = (arr[i][0], arr[i][1])
		(rc, cc) = (False, False)
		if len(c) == m or ri in r:
			rc = True
		if len(r) == n or ci in c:
			cc = True
		if cc and rc:
			continue
		cnt += 1
		r.add(ri)
		c.add(ci)
	ans.append(k ** cnt % 998244353)
for i in ans:
	print(i)


for _ in range(int(input())):
	(n, m, t, q) = map(int, input().split())
	s = {}
	a = []
	for i in range(q):
		(r, c) = map(int, input().split())
		if f'r{r}' not in s:
			s[f'r{r}'] = len(a)
			a.append([f'r{r}', True, i])
		else:
			a[s[f'r{r}']][1] = False
			s[f'r{r}'] = len(a)
			a.append([f'r{r}', True, i])
		if f'c{c}' not in s:
			s[f'c{c}'] = len(a)
			a.append([f'c{c}', True, i])
		else:
			a[s[f'c{c}']][1] = False
			s[f'c{c}'] = len(a)
			a.append([f'c{c}', True, i])
	colors = set()
	r_count = 0
	c_count = 0
	for (ty, valid, color) in reversed(a):
		if valid:
			if ty[0] == 'r':
				if c_count == m:
					break
				else:
					colors.add(color)
					r_count += 1
			elif r_count == n:
				break
			else:
				colors.add(color)
				c_count += 1
	print(pow(t, len(colors), 998244353))


for _ in range(int(input())):
	(n, m, k, q) = map(int, input().split())
	color = []
	x = set()
	y = set()
	for i in range(q):
		color.append(list(map(int, input().split())))
	cnt = 0
	t1 = t2 = 0
	for i in range(q - 1, -1, -1):
		(xi, yi) = color[i]
		if t1 < n and t2 < m:
			if xi not in x and yi in y:
				cnt += 1
				x.add(xi)
				t1 += 1
			elif yi not in y and xi in x:
				cnt += 1
				y.add(yi)
				t2 += 1
			elif xi not in x and yi not in y:
				cnt += 1
				x.add(xi)
				y.add(yi)
				t1 += 1
				t2 += 1
		else:
			break
	M = 998244353
	print(k ** cnt % M)