A. Разрежь массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив из $$$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$$$.

Пример
Входные данные
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
Примечание

Рассмотрим примеры из условия:

  • в первом примере массив разрезается на части $$$[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$$$.