Equal-Sum Partition - Repovive Premier Round 6 | Repovive

16A. Equal-Sum Partition

500 pts2s256 MB

You are given two arrays $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ of positive integers.

You want to partition each array into the same number $k$ of non-empty contiguous subarrays. The partition points in the two arrays do not have to be at the same positions.

For every $1 \le i \le k$ , the sum of the elements in the $i$ -th subarray of the first array must be equal to the sum of the elements in the $i$ -th subarray of the second array.

Find the maximum possible value of $k$ . If no such partition exists, output $-1$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i, b_i \le 10^4$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

1
5
5

Case 2

3
1 2 3
1 2 4

Case 3

4
1 2 1 2
2 1 2 1

Case 4

5
2 2 2 2 2
1 3 1 3 2

Case 5

6
3 1 4 1 5 9
2 2 4 6 3 6

Explanation

Case 1

The only possible partition consists of the whole array, whose sum is $5$ in both arrays.

Case 2

The total sums are $6$ and $7$ , so no valid partition exists.

Case 3

One optimal partition has segment sums $3$ and $3$ in both arrays.

Case 4

The arrays can be partitioned into three corresponding parts with sums $4$ , $4$ , and $2$ .

Case 5

The arrays can be partitioned into four corresponding parts with sums $4$ , $4$ , $6$ , and $9$ .

Output

Case 1

Case 2

-1

Case 3

Case 4

Case 5

You are given two arrays $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ of positive integers.

You want to partition each array into the same number $k$ of non-empty contiguous subarrays. The partition points in the two arrays do not have to be at the same positions.

For every $1 \le i \le k$ , the sum of the elements in the $i$ -th subarray of the first array must be equal to the sum of the elements in the $i$ -th subarray of the second array.

Find the maximum possible value of $k$ . If no such partition exists, output $-1$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i, b_i \le 10^4$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

The only possible partition consists of the whole array, whose sum is $5$ in both arrays.

The total sums are $6$ and $7$ , so no valid partition exists.

One optimal partition has segment sums $3$ and $3$ in both arrays.

The arrays can be partitioned into three corresponding parts with sums $4$ , $4$ , and $2$ .

The arrays can be partitioned into four corresponding parts with sums $4$ , $4$ , $6$ , and $9$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

16A. Equal-Sum Partition

Constraints

Input

Output

Samples

16A. Equal-Sum Partition

Constraints

Input

Output

Samples