Олимпиадный тренинг

Задача . D. Оптимальность изысканных произведений


As a tester, when my solution has a different output from the example during testing, I suspect the author first.
— Chris, a comment

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

  • Крису даны два массива \(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);
}
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число \(t\) (\(1 \leq t \leq 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(q\) (\(1 \leq n \leq 2\cdot 10^5\), \(1 \leq q \leq 2\cdot 10^5\)) — длина массива и количество операций.

Вторая строка каждого набора входных данных содержит \(n\) целых числа \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 5\cdot 10^8\)) — массив \(a\).

Третья строка каждого набора входных данных содержит \(n\) целых числа \(b_1, b_2, \ldots, b_n\) (\(1 \leq b_i \leq 5\cdot 10^8\)) — массив \(b\).

Затем следует \(q\) строк, каждая строка содержит два целых числа \(o\) и \(x\) (\(o \in \{1, 2\}\), \(1 \leq x \leq n\)), представляющие операцию.

Гарантируется, что и сумма \(n\), и сумма \(q\) по всем наборам входных данных не превосходят \(4\cdot 10^5\).

Выходные данные

Для каждого набора входных данных выведите на одной строке \(q + 1\) целых числа — ответы Криса по модулю \(998\,244\,353\).

Примечание

В первом наборе входных данных:

  • Перед внесением изменений Крис может переставить \(b\) в таком порядке: \([1, 2, 3]\), и тогда \(P = \prod\limits_{i=1}^n \min(a_i, b_i) = 1 \cdot 1 \cdot 2 = 2\). Можно доказать, что это максимально возможное значение. Например, если Крис переставит \(b = [2, 3, 1]\), то \(P\) будет равно \(1 \cdot 1 \cdot 1 = 1 < 2\), что не является оптимальным.
  • После первого изменения Крис может переставить \(b\) в таком порядке: \([1, 2, 3]\), и тогда \(P = 1 \cdot 1 \cdot 3 = 3\), что является максимально возможным значением.
  • После второго изменения Крис может переставить \(b\) в таком порядке: \([2, 2, 3]\), и тогда \(P = 1 \cdot 1 \cdot 3 = 3\), что является максимально возможным значением.
  • После третьего изменения Крис может переставить \(b\) в таком порядке: \([2, 2, 3]\), и тогда \(P = 6\), что является максимально возможным значением.
  • После четвертого изменения Крис может переставить \(b\) в таком порядке:\([2, 2, 4]\), и тогда \(P = 6\), что является максимально возможным значением.

Примеры
№Входные данныеВыходные данные
1
4
3 4
1 1 2
3 2 1
1 3
2 3
1 1
2 1
6 8
1 4 2 7 3 5
7 6 5 6 3 3
2 5
1 6
1 5
1 5
1 5
2 3
2 3
1 6
13 8
7 7 6 6 5 5 5 2 2 3 4 5 1
1 4 1 9 6 6 9 1 5 1 3 8 4
2 2
2 11
2 4
2 4
1 7
1 1
2 12
1 5
5 3
10000000 20000000 30000000 40000000 50000000
10000000 20000000 30000000 40000000 50000000
1 1
2 2
2 1
2 3 3 6 6
840 840 1008 1344 1680 2016 2016 2016 2352
2116800 2646000 3528000 3528000 3528000 4233600 4838400 4838400 4838400
205272023 205272023 205272023 264129429
Статистика успешных решений по компиляторам
 Кол-во
С++3