CF2106C Cherry Bomb

Two integer arrays $ a $ and $ b $ of size $ n $ are complementary if there exists an integer $ x $ such that $ a_i + b_i = x $ over all $ 1 \le i \le n $ . For example, the arrays $ a = [2, 1, 4] $ and $ b = [3, 4, 1] $ are complementary, since $ a_i + b_i = 5 $ over all $ 1 \le i \le 3 $ . However, the arrays $ a = [1, 3] $ and $ b = [2, 1] $ are not complementary. Cow the Nerd thinks everybody is interested in math, so he gave Cherry Bomb two integer arrays $ a $ and $ b $ . It is known that $ a $ and $ b $ both contain $ n $ non-negative integers not greater than $ k $ . Unfortunately, Cherry Bomb has lost some elements in $ b $ . Lost elements in $ b $ are denoted with $ -1 $ . Help Cherry Bomb count the number of possible arrays $ b $ such that: - $ a $ and $ b $ are complementary. - All lost elements are replaced with non-negative integers no more than $ k $ .

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 0 \le k \le 10^9 $ ) — the size of the arrays and the maximum possible value of their elements. The second line contains $ n $ integers $ a_1, a_2, ..., a_n $ ( $ 0 \le a_i \le k $ ). The third line contains $ n $ integers $ b_1, b_2, ..., b_n $ ( $ -1 \le b_i \le k $ ). If $ b_i = -1 $ , then this element is missing. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

Output exactly one integer, the number of ways Cherry Bomb can fill in the missing elements from $ b $ such that $ a $ and $ b $ are complementary.

In the first example, the only way to fill in the missing elements in $ b $ such that $ a $ and $ b $ are complementary is if $ b = [2, 0, 1] $ . In the second example, there is no way to fill in the missing elements of $ b $ such that $ a $ and $ b $ are complementary. In the fourth example, some $ b $ arrays that are complementary to $ a $ are: $ [4, 2, 3, 0, 1], [7, 5, 6, 3, 4], $ and $ [9, 7, 8, 5, 6] $ .