Матрица размера \(n \times m\), состоящая только из цифр \(0\) или \(1\) считается красивой, если сумма в каждой подматрице размера \(2 \times 2\) ровно \(2\), т. е. каждый «квадрат» размера \(2 \times 2\) содержит ровно две цифры \(1\) и две цифры \(0\).
Вам задана матрица размера \(n \times m\). Изначально все ячейки матрицы пусты. Обозначим ячейку стоящую на пересечении \(x\)-й строки \(y\)-го столбца как \((x, y)\). Вам нужно обрабатывать запросы трех типов:
- \(x\) \(y\) \(-1\) — сделать ячейку \((x, y)\) пустой;
- \(x\) \(y\) \(0\) — записать цифру \(0\) в ячейку \((x, y)\), это перезапишет то, что там было;
- \(x\) \(y\) \(1\) — записать цифру \(1\) в ячейку \((x, y)\), это перезапишет то, что там было.
После каждого запроса выведите количество способов заполнить пустые ячейки матрицы так, чтобы матрица была красивой. Так как это значение может быть слишком велико, выведите его по модулю \(998244353\).
Выходные данные
После каждого запроса выведите число — количество способов заполнить пустые ячейки матрицы так, чтобы матрица была красивой по модулю \(998244353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 7
1 1 1
1 2 1
2 1 1
1 1 0
1 2 -1
2 1 -1
1 1 -1
|
3
1
0
1
2
3
6
|