题目描述

给定两个长度为 $n$ 的整数序列 $a_0,a_1,…,a_{n−1}$ 和 $b_0,b_1,…,b_{n−1}$，序列是循环的（即下标模 $n$）。

你可以执行以下操作任意多次（包括零次）：

• 选择一个下标 $i$（$0≤i≤n−1$）和一个整数 $x$（可以为负）。
• 将 $a_i$ 增加 $x$，将 $a_{i+1}$ $mod$ $n$ 增加 $-2x$，将 $a_{i+2}$ $mod$ $n$ 增加 $x$。

每次操作的代价为 $|x|$，即 $x$ 的绝对值。

你的目标是经过一系列操作后，使得对于所有 $i$ 都有 $a_i = b_i$。

你需要计算达成目标的最小总代价，如果无法达成则输出 $-1$。

输入格式

本题输入包含多组测试数据。

第一行包含一个整数 $T$，表示测试组数。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示序列的长度。
• 第二行包含 $n$ 个整数 $a_0…a_{n−1}$。
• 第三行包含 $n$ 个整数 $b_0…b_{n−1}$。

本题读入量较大，请选择较快速的方式读入。

输出格式

对于每组测试数据，输出一行一个整数，表示最小总代价或无法达成。

5
1
0
0
2
1 0
0 1
3
1 2 3
2 3 4
4
0 0 0 0
1 -2 1 0
5
0 0 0 0 0
1 -1 -1 1 0

0
-1
-1
1
2

样例解释

无

数据规模与约定

下发文件

下发文件对应子任务 $3,4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^2,2 \leq n \leq 10^5,1 \leq \sum n \leq 10^6,-5000 \leq a_i,b_i \leq 5000$。