E. Not a Segment Tree
time limit per test
6 s
memory limit per test
512 MB
input
standard input
output
standard output

You are given two integer arrays $$$a(a_{0},a_{1},....,a_{n-1})$$$ containing $$$n$$$ elements, $$$b(b_{0},b_{1},....,b_{n-1})$$$ containing $$$n$$$ elements and an integer $$$k$$$.

You are allowed to do the following popular segment tree Operation on array $$$a$$$.

  1. Choose any value $$$l(0 \le l \le n-1)$$$.
  2. Let $$$sum$$$ = $$$(a_{(l-k)\%n}+a_{(l-k+1)\%n}+....+a_{l-1}+a_{l}+a_{l+1}+....+a_{(l+k-1)\%n}+a_{(l+k)\%n})$$$.
  3. Update $$$a_{l}$$$ = $$$sum$$$.

Find the minimum number of Operations required to change $$$a$$$ to $$$b$$$ or report if it is impossible to do.

Note that, $$$x\%y$$$ is the remainder when $$$y$$$ divides $$$x$$$. i.e., $$$(10\%4) = 2$$$, $$$(-5\%4) = 3$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of test case contains two integers $$$n,k$$$ ($$$1 \le n \le 2 \cdot 10^6$$$, $$$0 \le k \le ⌊\frac{n-1}{2}⌋$$$) — the length of the given arrays and an integer.

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^{12}$$$).

The third line of each test case contains $$$n$$$ space separated integers $$$b_{i}$$$ ($$$1 \le b_{i} \le 10^{12}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^6$$$.

Output

For each test case, print a single integer — the minimum number of Operations required to change $$$a$$$ to $$$b$$$ or $$$"-1"$$$(without quotes) if it is impossible to change.

Example
Input
3
4 1
1 4 3 2
17 14 25 2
6 2
1 1 1 1 1 1
1 49 5 29 9 13
5 2
1 2 3 9 11
2 4 6 18 22
Output
4
5
-1
Note

In the first test case,

  1. $$$a = (1, 4, 3, 2)$$$, by choosing $$$l = 2$$$ , $$$sum = 9$$$, so update $$$a_{2} = 9$$$, after this operation array will be $$$a = (1, 4, 9, 2)$$$.
  2. $$$a = (1, 4, 9, 2)$$$, by choosing $$$l = 1$$$ , $$$sum = 14$$$, so update $$$a_{1} = 14$$$, after this operation array will be $$$a = (1, 14, 9, 2)$$$.
  3. $$$a = (1, 14, 9, 2)$$$, by choosing $$$l = 2$$$ , $$$sum = 25$$$, so update $$$a_{2} = 25$$$, after this operation array will be $$$a = (1, 14, 25, 2)$$$.
  4. $$$a = (1, 14, 25, 2)$$$, by choosing $$$l = 0$$$ , $$$sum = 17$$$, so update $$$a_{0} = 17$$$, after this operation array will be $$$a = (17, 14, 25, 2)$$$, which is equal to $$$b$$$.

Hence, the total operations required are $$$4$$$.