← 返回题目列表

Codeforces · 2182/C

C. 雪人的制作

中文机器翻译题面 查看原题

为了营造真正的节日气氛,圣诞老人的帮手们开设了一家生产雪人的工厂!

每个雪人都由三个雪球组成——头部、躯干和腿。为了使雪人保持稳定,形成腿部的球必须严格大于形成躯干的球;反过来,形成躯干的球必须严格大于形成头部的球。形式上,如果我们将头部、躯干和腿的尺寸分别表示为$$$a、b、c$$$,则当且仅当$$$a \lt b \lt c$$$ 时,雪人才是稳定的。

在雪人生产工厂,有三个传送带,每个传送带包含$$$n$$$个雪球。第一个传送带包含尺寸为 $$$a_1, a_2, \dots, a_n$$$ 的球;第二个包含尺寸为 $$$b_1, b_2, \dots, b_n$$$ 的球;第三个包含尺寸为 $$$c_1、c_2、\dots、c_n$$$ 的球。输送机是循环式的;换句话说,在编号为$$$n$$$的元素之后,又跟着编号为$$$1$$$的元素,我们可以认为编号为$$$i$$$的球和编号为$$$i+n$$$的球(以及编号为$$$i+2n$$$、$$$i+3n$$$的球等)是同一个球。

要生产雪人,需要指定三个参数 $$$i, j, k$$$ ($$$1 \le i, j, k \le n$$$),表示从每个传送带上的哪些球开始生产。之后,雪人将由球组装而成,如下所示:

  • 第一个雪人的头部尺寸为$$$a_i$$$,躯干尺寸为$$$b_j$$$,腿尺寸为$$$c_k$$$;
  • 第二个雪人的头部尺寸为$$$a_{i+1}$$$,躯干尺寸为$$$b_{j+1}$$$,腿尺寸为$$$c_{k+1}$$$;
  • 等等;
  • 第$$$n$$$(最后一个)雪人的头部尺寸为$$$a_{i+n-1}$$$,躯干尺寸为$$$b_{j+n-1}$$$,腿尺寸为$$$c_{k+n-1}$$$。

参数 $$$i、j、k$$$ 的选择必须确保所有 $$$n$$$ 雪人都是稳定的。您的任务是计算合适的参数组合的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

每个测试用例由四行组成:

  • 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$);
  • 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 3n$$$);
  • 第三行包含$$$n$$$整数$$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 3n$$$);
  • 第四行包含$$$n$$$整数$$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 3n$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出一个整数 - 所有 $$$n$$$ 雪人都稳定的参数 $$$i, j, k$$$ 的组合数量。

示例

输入
复制

4
2
1 2
3 4
5 4
3
1 1 1
2 2 2
3 3 3
4
1 2 1 2
3 3 2 2
5 5 5 5
5
1 4 2 3 5
6 4 5 7 6
7 5 8 10 10

输出
复制

4
27
0
10

注意

在第一个示例中,合适的参数集 $$$i, j, k$$$ 如下:

  • $$$i = 1, j = 1, k = 2$$$:那么雪人将是 $$$(1, 3, 4)$$$ 和 $$$(2, 4, 5)$$$;
  • $$$i = 1, j = 2, k = 1$$$: 那么雪人将是 $$$(1, 4, 5)$$$ 和 $$$(2, 3, 4)$$$;
  • $$$i = 2, j = 1, k = 2$$$:那么雪人将是 $$$(2, 3, 4)$$$ 和 $$$(1, 4, 5)$$$;
  • $$$i = 2, j = 2, k = 1$$$:那么雪人将是 $$$(2, 4, 5)$$$ 和 $$$(1, 3, 4)$$$。

在第二个示例中,所有参数组合都是合适的。

在第三个例子中,对于任何参数组合,都会产生一个头部尺寸为$$$2$$$、躯干尺寸为$$$2$$$的雪人,这是不稳定的。