给你一个从 $$$1$$$ 到 $$$n$$$ 的每个整数的排列$$$^{\text{*}}$$$ $$$p$$$。您还拥有一个大小为 $$$n$$$ 的二进制 $$$^{\text{†}}$$$ 字符串 $$$s$$$,其中 $$$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}$$$。
您还将获得一个大小为 $$$n$$$ 的二进制字符串 $$$x$$$。执行运算后,对于每个$$$1 \le i \le n$$$,如果$$$x_i = \mathtt{1}$$$,则$$$s_i = \mathtt{1}$$$。请注意,如果 $$$x_i = \mathtt{0}$$$,则 $$$s_i$$$ 可以有 任何 值。
找出任意序列 最多 $$$5$$$ 操作以满足上述条件,或者报告不可能这样做。请注意,您 不 必须尽量减少您进行的操作数量。
$$$^{\text{*}}$$$从$$$1$$$到$$$n$$$的每个整数的排列$$$p$$$是从$$$1$$$到$$$n$$$的元素序列,使得每个元素恰好出现一次。
$$$^{\text{†}}$$$大小为 $$$m$$$ 的字符串 $$$b$$$ 被视为二进制当且仅当 $$$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$$$ 个元素。
第三行包含一个大小为 $$$n$$$ 的二进制字符串 $$$x$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果不可能执行满足约束的操作,则输出 $$$-1$$$。
否则,输出一个整数$$$0 \le k \le 5$$$,操作次数。在接下来的 $$$k$$$ 行的第 $$$i$$$ 行上,输出两个整数 $$$1 \le l_i \le r_i \le n$$$,即执行的第 $$$i$$$ 操作的边界。如果有多个正确解,则输出任意一个。
示例
输入复制
631 2 301053 4 2 1 51111161 3 2 4 6 500110066 2 3 4 5 111011052 1 4 3 50000052 5 3 1 400100
输出复制
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}$$$。