Siga ta Kymata

题目描述

你将会得到一个由 $1$ 到 $n$ 的所有整数构成的一个排列* $p$。你还拥有一个长度为 $n$ 的二进制^† 字符串 $s$，初始时对于所有 $1\leqslant i\leqslant n$，均有 $s_{i}=0$。你最多可以进行 $5$ 次如下操作：

• 选择任意两个整数 $l$ 和 $r$，满足 $1\leqslant l\leqslant r\leqslant n$。然后，对于每一个满足 $l<i<r$ 且同时满足 $\min(p_{l},p_{r})<p_{i}<\max(p_{l},p_{r})$ 的 $i$，你将把 $s_{i}$ 设置为 $1$。

你还会得到一个长度为 $n$ 的二进制字符串 $x$。在执行所有操作之后，对于每个 $1\leqslant i\leqslant n$，必须满足：如果 $x_{i}=1$，那么 $s_{i}=1$。请注意，如果 $x_{i}=0$，则 $s_{i}$ 可以为任意值。

找出一组最多 $5$ 次的操作序列，使得上述条件得到满足；或者报告说这是不可能做到的。注意，你不需要最小化操作次数。

$^{\ast}$ 一个由 $1$ 到 $n$ 的所有整数构成的排列 $p$ 是指一个包含 $1$ 到 $n$ 的序列，其中每个元素恰好出现一次。

$^{\dagger}$ 一个长度为 $m$ 的字符串 $b$ 被认为是二进制的，当且仅当对于所有 $1\leqslant i\leqslant m$，$b_{i}=0$ 或 $b_{i}=1$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t(1\leqslant t\leqslant 10^{4})$。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n(3\leqslant n\leqslant 2\cdot 10^{5})$ —— 数组的大小。

第二行包含恰好 $n$ 个整数 $p_{1},p_{2},...,p_{n}(1\leqslant p_{i}\leqslant n$，$p$ 中的元素互不相同) —— 其中 $p_{i}$ 是排列的第 $i$ 个元素。

第三行包含一个长度为 $n$ 的二进制字符串 $x$。

保证所有测试用例的 $n$ 的总和不超过 $2\cdot 10^{5}$。

输出格式

对于每个测试用例，如果无法通过操作满足约束条件，则输出 $-1$。

否则，输出一个整数 $0\leqslant k\leqslant 5$，表示操作次数。在接下来的 $k$ 行中，第 $i$ 行输出两个整数 $1\leqslant l_{i}\leqslant r_{i}\leqslant 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 = 010$。我们可以执行一次操作，选择 $l=1$ 和 $r=3$。操作后，我们将 $s_2$ 设置为 $1$，因为同时满足 $l<2<r$ 和 $\min(p_1,p_3) < p_2=2 < \max(p_1,p_3)$。结果，$s=010$。

在第二个示例中，可以证明不存在最多 $5$ 次操作的正确序列，因此我们输出 $-1$。

在第三个示例中，$p = [1,3,2,4,6,5]$，$x = 001100$。执行一次操作，选择 $l=1$ 和 $r=5$ 后，得到 $s=011100$。如果我们再执行一次操作，选择 $l=2$ 和 $r=6$，$s$ 将保持不变。字符串 $s=011100$ 是有效的，因为在 $x$ 为 $1$ 的每个位置上，$s$ 在该位置上的值也是 $1$。

数据范围

见题面。