Хотя Ирис иногда ставит задачу, решение которой неверно, она по-прежнему настаивает на создании задач с помощью своего воображения; в конце концов, все мы упрямы... И, как всегда, Ирис поставила перед собой задачу, которую она решила неправильно, и Крис должен её спасать! Но в этот раз вы будете играть роль Криса:

• Крису даны два массива $$$a$$$ и $$$b$$$, оба состоящие из $$$n$$$ целых чисел.
• Ирис интересуется наибольшим возможным значением $$$P = \prod\limits_{i=1}^n \min(a_i, b_i)$$$ после произвольной перестановки $$$b$$$. Обратите внимание, что она хочет только узнать максимальное значение $$$P$$$, элементы самого массива $$$b$$$ не переставляются.
• Будет внесено $$$q$$$ изменений. Каждое изменение может быть обозначено двумя целыми числами $$$o$$$ и $$$x$$$ (значение $$$o$$$ может быть $$$1$$$ или $$$2$$$, $$$1 \leq x \leq n$$$). Если $$$o = 1$$$, то Ирис увеличивает $$$a_x$$$ на $$$1$$$; в противном случае она увеличивает $$$b_x$$$ на $$$1$$$.
• Ирис спрашивает у Криса максимальное значение $$$P$$$ суммарно $$$q + 1$$$ раз: один раз перед изменениями, затем после каждого изменения.
• Поскольку $$$P$$$ может быть очень большим, Крису нужно только вычислить его по модулю $$$998\,244\,353$$$.

Крис вскоре справился с этой задачей, но он так устал, что заснул. Помимо благодарности Крису, теперь ваша очередь написать программу для вычисления ответов по заданным входным данным.

Обратите внимание: поскольку входные и выходные данные большие, вам, возможно, потребуется оптимизировать их для решения данной задачи.

Например, в C++ достаточно использовать следующие строки в начале функции main():

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
}