Представьте лист бумаги — сетку размера \(n \times m\): \(n\) строк и \(m\) столбцов с ячейками. Все ячейки изначально белые.
К листу применили \(q\) операций. \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач