C. Черри Бомб
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два целых массива $$$a$$$ и $$$b$$$ размером $$$n$$$ являются дополняющими, если существует целое число $$$x$$$, такое что $$$a_i + b_i = x$$$ для всех $$$1 \le i \le n$$$. Например, массивы $$$a = [2, 1, 4]$$$ и $$$b = [3, 4, 1]$$$ являются дополняющими, поскольку $$$a_i + b_i = 5$$$ для всех $$$1 \le i \le 3$$$. Однако массивы $$$a = [1, 3]$$$ и $$$b = [2, 1]$$$ не являются дополняющими.

Коровка Нерд считает, что всем интересна математика, поэтому она дала Черри Бомб два массива целых чисел $$$a$$$ и $$$b$$$. Известно, что $$$a$$$ и $$$b$$$ оба содержат $$$n$$$ неотрицательных целых чисел, не превосходящих $$$k$$$.

К сожалению, Черри Бомб потеряла некоторые элементы в $$$b$$$. Потерянные элементы в $$$b$$$ обозначены как $$$-1$$$. Помогите Черри Бомб подсчитать количество возможных массивов $$$b$$$, таких что:

  • $$$a$$$ и $$$b$$$ являются дополняющими.
  • Все потерянные элементы заменены неотрицательным целым числом не более $$$k$$$.
Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$) — размер массивов и максимальное возможное значение их элементов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ ($$$0 \le a_i \le k$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, ..., b_n$$$ ($$$-1 \le b_i \le k$$$). Если $$$b_i = -1$$$, то этот элемент отсутствует.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Выведите ровно одно целое число, количество способов, которыми Черри Бомб может заполнить отсутствующие элементы из $$$b$$$, так что $$$a$$$ и $$$b$$$ являются дополняющими.

Пример
Входные данные
7
3 10
1 3 2
-1 -1 1
5 1
0 1 0 0 1
-1 0 1 0 -1
5 1
0 1 0 0 1
-1 1 -1 1 -1
5 10
1 3 2 5 4
-1 -1 -1 -1 -1
5 4
1 3 2 1 3
1 -1 -1 1 -1
5 4
1 3 2 1 3
2 -1 -1 2 0
5 5
5 0 5 4 3
5 -1 -1 -1 -1
Выходные данные
1
0
0
7
0
1
0
Примечание

В первом примере единственный способ заполнить отсутствующие элементы в $$$b$$$, чтобы $$$a$$$ и $$$b$$$ были дополняющими, это если $$$b = [2, 0, 1]$$$.

Во втором примере нет способа заполнить отсутствующие элементы в $$$b$$$, чтобы $$$a$$$ и $$$b$$$ были дополняющими.

В четвертом примере некоторые массивы $$$b$$$, которые являются дополняющими к $$$a$$$: $$$[4, 2, 3, 0, 1], [7, 5, 6, 3, 4],$$$ и $$$[9, 7, 8, 5, 6]$$$.