两个大小为 $$$n$$$ 的整数数组 $$$a$$$ 和 $$$b$$$ 是 互补 如果存在一个整数 $$$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]$$$ 不是互补的。
Cow the Nerd 认为每个人都对数学感兴趣,所以他给了 Cherry Bomb 两个整数数组 $$$a$$$ 和 $$$b$$$。已知 $$$a$$$ 和 $$$b$$$ 都包含 $$$n$$$ 非负 不大于 $$$k$$$ 的整数。
不幸的是,Cherry Bomb 丢失了 $$$b$$$ 中的一些元素。 $$$b$$$ 中丢失的元素用 $$$-1$$$ 表示。帮助 Cherry Bomb 计算可能的数组 $$$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$$$。
输出
精确输出一个整数,即 Cherry Bomb 可以填充 $$$b$$$ 中缺失元素的方式数,以使 $$$a$$$ 和 $$$b$$$ 互补。
示例
输入复制
73 101 3 2-1 -1 15 10 1 0 0 1-1 0 1 0 -15 10 1 0 0 1-1 1 -1 1 -15 101 3 2 5 4-1 -1 -1 -1 -15 41 3 2 1 31 -1 -1 1 -15 41 3 2 1 32 -1 -1 2 05 55 0 5 4 35 -1 -1 -1 -1
输出复制
1 0 0 7 0 1 0
注意
在第一个示例中,填充 $$$b$$$ 中缺失元素以使 $$$a$$$ 和 $$$b$$$ 互补的唯一方法是 $$$b = [2, 0, 1]$$$。
在第二个示例中,无法填充 $$$b$$$ 的缺失元素,使得 $$$a$$$ 和 $$$b$$$ 互补。
在第四个示例中,与 $$$a$$$ 互补的一些 $$$b$$$ 数组是:$$$[4, 2, 3, 0, 1], [7, 5, 6, 3, 4],$$$ 和 $$$[9, 7, 8, 5, 6]$$$。