题目描述

给定一个包含 $n$ 个非负整数的数组 $[a_1, a_2, \dots, a_n]$。

你需要将其切分为三个非空部分：前缀、中间部分和后缀。具体来说，你需要选择两个整数 $l$ 和 $r$，满足 $1 \le l < r < n$，得到三部分：

• 前缀部分包含第 $1$ 个到第 $l$ 个元素（即 $[a_1, a_2, \dots, a_l]$）；
• 中间部分包含第 $l+1$ 个到第 $r$ 个元素（即 $[a_{l+1}, a_{l+2}, \dots, a_r]$）；
• 后缀部分包含第 $r+1$ 个到第 $n$ 个元素（即 $[a_{r+1}, a_{r+2}, \dots, a_n]$）。

令 $s_1, s_2, s_3$ 分别表示上述三部分元素和对 $3$ 取模的余数，即：

• $s_1 = (\sum\limits_{i=1}^{l} a_i) \bmod 3$；
• $s_2 = (\sum\limits_{i=l+1}^{r} a_i) \bmod 3$；
• $s_3 = (\sum\limits_{i=r+1}^{n} a_i) \bmod 3$。

你的任务是找到一组 $l$ 和 $r$，使得 $s_1, s_2, s_3$ 要么全都不同，要么全都相等。

输入格式

第一行为一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

每个测试用例包含两行：

• 第一行一个整数 $n$（$3 \le n \le 40$）；
• 第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 40$）。

输出格式

对于每个测试用例，如果存在一组合适的整数 $l$ 和 $r$（$1 \leq l < r < n$），输出这两个数（如果有多组解，输出任意一组即可）。如果不存在合适的切割方法，则输出两个 $0$。

说明/提示

参考样例中的说明：

• 在第一个样例中，数组被分为 $[1, 2, 3]$、$[4, 5]$、$[6]$，$s_1 = s_2 = s_3 = 0$；
• 在第二个样例中，没有满足条件的切割方法；
• 在第三个样例中，数组被分为 $[2]$、$[1]$、$[0]$，$s_1 = 2$，$s_2 = 1$，$s_3 = 0$；
• 在第四个样例中，数组被分为 $[7, 2]$、$[6, 2]$、$[4]$，$s_1 = 0$，$s_2 = 2$，$s_3 = 1$。

由 ChatGPT 5 翻译

样例

4
6
1 2 3 4 5 6
4
1 3 3 7
3
2 1 0
5
7 2 6 2 4

3 5
0 0
1 2
2 4