B. Сига та Кимата
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$. У вас также есть бинарная$$$^{\text{†}}$$$ строка $$$s$$$ длины $$$n$$$, где $$$s_i = \mathtt{0}$$$ для всех $$$1 \le i \le n$$$. Вы можете выполнить следующую операцию не более чем $$$5$$$ раз:

  • Выберите любые два целых числа $$$l$$$ и $$$r$$$ такие, что $$$1 \le l \le r \le n$$$. Затем, для каждого $$$i$$$, такого что $$$l \lt i \lt r$$$ и одновременно выполняются условия $$$\min(p_l, p_r) \lt p_i \lt \max(p_l, p_r)$$$, сделайте $$$s_i$$$ равным $$$\mathtt{1}$$$.

Вам также дана бинарная строка $$$x$$$ длины $$$n$$$. После выполнения операций для каждого $$$1 \le i \le n$$$ должно выполняться, что если $$$x_i = \mathtt{1}$$$, то $$$s_i = \mathtt{1}$$$. Обратите внимание, что если $$$x_i = \mathtt{0}$$$, то $$$s_i$$$ может иметь любое значение.

Определите любую последовательность из не более чем $$$5$$$ операций, такую что указанное условие выполнено, или сообщите, что это невозможно. Обратите внимание, что вам не нужно минимизировать количество выполняемых операций.

$$$^{\text{∗}}$$$Перестановка $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$ — это последовательность элементов от $$$1$$$ до $$$n$$$, в которой каждый элемент встречается ровно один раз.

$$$^{\text{†}}$$$Строка $$$b$$$ длины $$$m$$$ называется бинарной, если и только если $$$b_i = \mathtt{0}$$$ или $$$b_i = \mathtt{1}$$$ для всех $$$1 \le i \le m$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — длину массива.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, элементы $$$p$$$ попарно различны), где $$$p_i$$$ — это $$$i$$$-й элемент перестановки.

Третья строка содержит одну бинарную строку $$$x$$$ длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных, если невозможно выполнить операции так, чтобы условие было выполнено, выведите $$$-1$$$.

В противном случае выведите целое число $$$0 \le k \le 5$$$ — количество операций. В $$$i$$$-й из следующих $$$k$$$ строк выведите два целых числа $$$1 \le l_i \le r_i \le n$$$ — границы $$$i$$$-й выполненной операции. Если существует несколько правильных решений, выведите любое из них.

Пример
Входные данные
6
3
1 2 3
010
5
3 4 2 1 5
11111
6
1 3 2 4 6 5
001100
6
6 2 3 4 5 1
110110
5
2 1 4 3 5
00000
5
2 5 3 1 4
00100
Выходные данные
1
1 3
-1
2
1 5
2 6
-1
0
1
2 4
Примечание

В первом наборе входных данных $$$p = [1, 2, 3]$$$ и $$$x = \mathtt{010}$$$. Мы можем выполнить одну операцию с $$$l = 1$$$ и $$$r = 3$$$. В результате $$$s_2$$$ становится равным $$$\mathtt{1}$$$, так как $$$l \lt 2 \lt r$$$, и одновременно выполняются условия $$$\min(p_l, p_r) \lt p_2 = 2 \lt \max(p_l, p_r)$$$. В результате, $$$s = \mathtt{010}$$$.

Во втором наборе входных данных можно показать, что не существует корректной последовательности из не более чем $$$5$$$ операций, поэтому мы выводим $$$-1$$$.

В третьем наборе входных данных $$$p = [1, 3, 2, 4, 6, 5]$$$ и $$$x = \mathtt{001100}$$$. После выполнения операции для $$$l = 1$$$ и $$$r = 5$$$ получается $$$s = \mathtt{011100}$$$. Если мы также выполним операцию для $$$l = 2$$$ и $$$r = 6$$$, $$$s$$$ останется прежним. Строка $$$s = \mathtt{011100}$$$ является допустимой, потому что для каждой позиции, где $$$x$$$ имеет $$$\mathtt{1}$$$, $$$s$$$ также имеет $$$\mathtt{1}$$$ на этой позиции.