D. Раскраска крестиками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представьте лист бумаги — сетку размера $$$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$$$) — размер листа, количество небелых цветов и количество операций.

В $$$i$$$-й из следующих $$$q$$$ строк записана $$$i$$$-я операция — два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$) — строка и столбец, к которым применяется операция.

Сумма $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — количество различных раскрасок по модулю $$$998\,244\,353$$$.

Пример
Входные данные
2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2
Выходные данные
3
4