Monocarp 有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。他决定选择两个整数 $$$l$$$ 和 $$$r$$$,使得 $$$1 \le l \le r \le n$$$,然后对子数组 $$$a[l..r]$$$ 进行排序(子数组 $$$a[l..r]$$$ 是数组 $$$a$$$ 中包含元素 $$$a_l、a_{l+1}、a_{l+2} 的部分, \dots, a_{r-1}, a_r$$$) 按非降序排列。对子数组进行排序后,Monocarp 获得了一个新数组,我们将其表示为 $$$a'$$$。
例如,如果 $$$a = [6, 7, 3, 4, 4, 6, 5]$$$,并且 Monocarp 选择了 $$$l = 2, r = 5$$$,则 $$$a' = [6, 3, 4, 4, 7, 6, 5]$$$。
给定数组 $$$a$$$ 和 $$$a'$$$。找出 Monocarp 可以选择的整数 $$$l$$$ 和 $$$r$$$。如果有多对值 $$$(l, r)$$$,找到对应于最长子数组的一对。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由三行组成:
- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$);
- 第三行包含 $$$n$$$ 整数 $$$a'_1, a'_2, \dots, a'_n$$$ ($$$1 \le a'_i \le n$$$)。
输入的附加限制:
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$;
- 通过对$$$a$$$的一个子数组进行排序可以获得数组$$$a'$$$;
- $$$a' \ne a$$$ (这两个数组至少存在一个位置不同)。
输出
对于每个测试用例,打印两个整数 - $$$l$$$ 和 $$$r$$$ 的值 ($$$1 \le l \le r \le n$$$)。如果有多个答案,则打印对应于最长子数组的值。如果仍有多个答案,请打印其中任何一个。
示例
输入 #1
3 7 6 7 3 4 4 6 5 6 3 4 4 7 6 5 3 1 2 1 1 1 2 3 2 2 1 2 1 2
输出 #1
2 5 1 3 2 3