Вам дан двудольный граф, состоящий из $$$n_1$$$ вершин в первой доле и $$$n_2$$$ вершин во второй доле и $$$m$$$ ребер, пронумерованных от $$$1$$$ до $$$m$$$. Вы должны раскрасить каждые ребро в один из двух цветов, красный и синий. Необходимо минимизировать следующее значение: $$$\sum \limits_{v \in V} |r(v) - b(v)|$$$, где $$$V$$$ — множество вершин графа, $$$r(v)$$$ — число красных ребер, инцидентных $$$v$$$, и $$$b(v)$$$ — число синих ребер, инцидентных $$$v$$$.

Звучит классически и просто, не так ли? Ну, вы должны обработать $$$q$$$ запросов следующего формата:

• $$$1$$$ $$$v_1$$$ $$$v_2$$$ — добавить новое ребро, соединяющее вершину $$$v_1$$$ первой доли с вершиной $$$v_2$$$ второй доли. Это ребро получает новый индекс следующим образом: первое добавленное ребро получает индекс $$$m + 1$$$, второе — $$$m + 2$$$ и так далее. После добавления ребра вы должны вывести хэш текущей оптимальной раскраски (если существует несколько оптимальных раскрасок, выведите хэш любой из них). На самом деле этот хэш не будет проверен, вы можете вывести любое число в качестве ответа на этот запрос, но вас могут попросить предоставить раскраску с этим хэшем;
• $$$2$$$ — выведите оптимальную раскраску графа с тем же хэшем, который вы вывели при обработке предыдущего запроса. Запрос этого типа будет задан только после запроса типа $$$1$$$, и будет не более $$$10$$$ запросов этого типа. Если существует несколько оптимальных раскрасок, соответствующих этому хэшу, выведите любую из них.

Обратите внимание, что если ребро было красным или синим в какой-то раскраске, оно может изменить свой цвет в следующих раскрасках.

Хэш раскраски вычисляется следующим образом: пусть $$$R$$$ — множество индексов красных ребер, тогда хэш равен $$$(\sum \limits_{i \in R} 2^i) \bmod 998244353$$$.

Обратите внимание, что вы должны решить эту задачу в режиме online. Это означает, что вы не можете считать все входные данные сразу. Вы можете считать каждый запрос только после вывода ответа на последний запрос. Используйте функции fflush в C++ и BufferedWriter.flush в Java после каждого вывода в вашей программе.