Красный/синий забор

У каждого друга есть требование. Друг $i$ хочет видеть ровно $c_i$ красных досок. Мы называем друга $i$ счастливым, если Фирдавс удовлетворяет его требованию.

Счастье Фирдавса зависит непосредственно от его друзей. От каждого счастливого друга он получает определенное количество счастья. Более формально, счастье Фирдавса - это сумма $e_i$ по всем счастливым друзьям $i$. Фирдавс в свою очередь будет стараться покрасить свой забор так, чтобы максимизировать свое счастье.

Фирдавс сейчас думает о различных сценариях. Он не знает, сколько у него баков каждого цвета. Пусть $F(R, B)$ - ответ на вопрос: Если бы у Фирдавса было $R$ баков красного цвета и $B$ баков синего цвета, какое максимальное счастье он мог бы иметь?

Подумав некоторое время, он решил выяснить, какова будет общая сумма его счастья во всех возможных сценариях? То есть, для всех $R, B$ таких, что $0 \leq R, B \leq N, N \leq R + B$. Поскольку ответ может быть огромным, его интересует только остаток от деления на $998244353$. Более формально, найдите следующую сумму:

$\sum_{R = 0}^{N} \sum_{B=N-R}^{N} F(R, B)\mod 998244353$

Формат Ввода

• Первая строка содержит одно целое число $T$, количество тестов. -Затем, для каждого теста: -Первая строка содержит два целых числа, разделенных пробелом, $N, M$. -Вторая строка содержит $M$ целых чисел, разделенных пробелом, $p_1, p_2, \ldots, p_M \ (1 \leq p_i \leq N)$. -Третья строка содержит $M$ целых чисел, разделенных пробелом, $c_1, c_2, \ldots, c_M \ (0 \leq c_i \leq p_i)$. -Четвертая строка содержит $M$ целых чисел, разделенных пробелом, $e_1, e_2, \ldots, e_M \ (0 \leq e_i \leq 10^9)$.

Ограничения

Пусть $S_N, S_M$ - общая сумма $N, M$ во всех тестах соответственно.

• $1 \leq T \leq 10^3$
• $1 \leq N \leq 10^9$
• $1 \leq S_M \leq 2 \cdot 10^5$

Формат Вывода

Для каждого теста выведите одну строку, содержащую одно целое число - ответ.

Система оценки