Черепаха Алиса в настоящее время разрабатывает коробку для печенья с предсказаниями, и она хотела бы включить в нее теорию Лоушу.
Коробку можно рассматривать как таблицу размера \(n \times m\) (\(n, m \ge 5\)), где строки нумеруются \(1, 2, \dots, n\), а столбцы нумеруются \(1, 2, \dots, m\). Каждая клетка может быть либо пустой, либо содержать одно печенье с предсказанием одной из следующих форм: круг или квадрат. Клетка на пересечении \(a\)-й строки \(b\)-го столбца обозначается как \((a, b)\).
Изначально вся таблица пуста. Затем Алиса выполняет \(q\) операций с коробкой для печенья. \(i\)-я операция (\(1 \le i \le q\)) выполняется следующим образом: указывается в настоящее время пустая клетка \((r_i,c_i)\) и форма (круг или квадрат), затем ставится печенье с предсказанием указанной формы в клетку \((r_i,c_i)\). Обратите внимание, что после \(i\)-й операции клетка \((r_i,c_i)\) больше не является пустой.
Перед всеми операциями и после каждой из \(q\) операций Алиса задается вопросом, сколько существует способов разместить печенья с предсказанием во всех оставшихся пустых клетках, так чтобы было удовлетворено следующее требование:
Не существует трёх последовательных клеток с печеньем одинаковой формы в одной строке, одном столбце или на одной диагонали. Формально:
- Не существует \((i,j)\), удовлетворяющих \(1 \le i \le n, 1 \le j \le m-2\), таких, что в клетках \((i,j), (i,j+1), (i,j+2)\) есть печенье одинаковой формы.
- Не существует \((i,j)\), удовлетворяющих \(1 \le i \le n-2, 1 \le j \le m\), таких, что в клетках \((i,j), (i+1,j), (i+2,j)\) есть печенье одинаковой формы.
- Не существует \((i,j)\), удовлетворяющих \(1 \le i \le n-2, 1 \le j \le m-2\), таких, что в клетках \((i,j), (i+1,j+1), (i+2,j+2)\) есть печенье одинаковой формы.
- Не существует \((i,j)\), удовлетворяющих \(1 \le i \le n-2, 1 \le j \le m-2\), таких, что в клетках \((i,j+2), (i+1,j+1), (i+2,j)\) есть печенье одинаковой формы.
Все ответы должны быть выведены по модулю \(998\,244\,353\). Также обратите внимание, что после некоторых операций требование уже может не быть удовлетворено с уже размещенными печеньями, в этом случае, вы должны выводить \(0\).
Выходные данные
Для каждого набора входных данных выведите \(q+1\) строк. Первая строка вывода должна содержать ответ до операций, \(i\)-я строка (\(2 \le i \le q+1\)) должна содержать ответ после первых \(i-1\) операций. Все ответы должны быть взяты по модулю \(998\,244\,353\).
Примечание
Во втором примере, после размещения печенья в форме круга в клетках \((1,1)\), \((1,2)\) и \((1,3)\), Требование уже не удовлетворено. Поэтому вы должны вывести \(0\).