给你一个 $$$n$$$ 非负整数数组 $$$[a_1, a_2, \dots, a_n]$$$。
你的任务是将其切成三个非空部分:前缀、中间部分和后缀。形式上,您需要选择两个整数 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l \lt r \lt n$$$,并获得三个部分:
- 索引 $$$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$$$ 都不同,或者所有数字 $$$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 \le l \lt r \lt n$$$),则输出这两个整数(如果有多个合适的对,则可以输出其中任何一个)。否则,输出两个等于$$$0$$$的整数。
示例
输入复制
461 2 3 4 5 641 3 3 732 1 057 2 6 2 4
输出复制
3 5 0 0 1 2 2 4
注意
考虑以下声明中的示例:
- 在第一个示例中,数组被分割为 $$$[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$$$。