题目描述

我们称两个长度均为 $n$ 的整数数组 $a$ 和 $b$ 是互补的，当且仅当存在一个整数 $x$，使得对于所有 $1 \le i \le n$，$a_i+b_i=x$。例如数组 $a=[2,1,4]$ 和 $b=[3,4,1]$ 是互补的，因为对于所有 $1 \le i \le 3$，$a_i+b_i$ 都等于 $5$。而数组 $a=[1,3]$ 和 $b=[2,1]$ 则不是互补的。

Cow the Nerd 觉得任何人都对数学感兴趣，所以他给了 Cherry Bomb 两个长度均为 $n$ 的整数数组 $a$ 和 $b$，其中元素均为非负整数且不大于 $k$。

但是 Cherry Bomb 不小心弄丢了 $b$ 中的一些数，这些数以 $-1$ 表示。请求出满足以下要求的可能的 $b$ 数组的数量：

• 数组 $a$ 和数组 $b$ 互补。
• $b$ 中的元素均为非负整数且不大于 $k$。

输入格式

输入的第一行是测试数据的组数 $t$（$1 \le t \le {10}^4$），以下有 $t$ 组测试数据。

对于每组测试数据，第一行是两个正整数 $n,k$（$1 \le n \le 2\times {10}^5,\ 0 \le k \le {10}^9,\ 1 \le \sum n \le 2\times {10}^5$）。

第二行是 $n$ 个小于等于 $k$ 的非负整数，表示 $a$ 数组。

第三行是 $n$ 个整数，每个整数要么是小于等于 $k$ 的非负整数，要么是 $-1$，表示 $b$ 数组，其中 $-1$ 是未知的数。

输出格式

对于每组数据，输出一行一个非负整数，表示满足条件的 $b$ 数组的数量。

说明/提示

对于第一组数据，由 $a_3=2$ 且 $b_3=1$，可以求出 $x=3$，从而唯一满足条件的 $b$ 数组为 $[2,0,1]$。

对于第二组数据，$a_2+b_2=1$，$a_4+b_4=0$，所以不可能做到 $a$ 数组与 $b$ 数组互补。

对于第四组数据，以下是所有满足条件的 $b$ 数组：

• $[4,2,3,0,1]$
• $[5,3,4,1,2]$
• $[6,4,5,2,3]$
• $[7,5,6,3,4]$
• $[8,6,7,4,5]$
• $[9,7,8,5,6]$
• $[10,8,9,6,7]$

共有 $7$ 种可能，因此输出 $7$。

样例

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