题目内容

你有一个长度为 $n$ 的整数序列，其中的每个元素要么是 $1$，要么是 $-1$。现在需要依次处理 $m$ 个操作。

对于每个操作，给定一个区间 $[l, r]$，先计算该区间内所有元素的和，记为 $X$。然后将这个区间从序列中移除，剩下的元素按原顺序拼接成一个新的序列（新序列的长度为 $n - (r-l+1)$）。

你的任务是，在新序列中另选一个长度等于 $r-l+1$ 的区间，使得该区间内元素之和严格大于 $X$。如果存在这样的区间，输出任意一个可行区间的左右端点（新序列中的下标，从 $1$ 开始编号）；如果不存在，输出 $-1$。

请注意，每个操作是独立的：每次操作前，序列都会恢复到最初的 $n$ 个元素。

约束条件：

• $1 \le n, m \le 10^5$。
• 序列中的元素仅为 $-1$ 或 $1$。
• 所有测试数据中，$\sum n$、$\sum m$ 以及所有被移除区间的长度之和均不超过 $10^5$。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据的组数。保证所有测试数据的 $\sum n$、$\sum m$ 及所有被移除区间的长度之和均不超过 $10^5$。

对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $m$，分别表示序列的长度和操作的数量。
• 第二行包含 $n$ 个整数，每个整数为 $-1$ 或 $1$，表示初始序列。
• 接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示一次操作中被移除的区间。

输出描述

对于每组测试数据的 $m$ 个操作，输出 $m$ 行，每行对应一个操作的答案。

如果无解，输出 $-1$；否则输出两个整数 $l_1$ 和 $r_1$，表示你选择的新区间在新序列中的起始和结束位置（$1 \le l_1 \le r_1 \le n-(r-l+1)$）。

样例1

输入

5 1
1 1 1 1 1
2 4

输出

-1

说明

序列长度为 5，元素全为 1。 操作区间为 $[2, 4]$，其长度 $k = 3$，区间和 $X = 3$。 移除该区间后，剩余序列的长度为 $n - k = 2$。 由于 $2 < 3$，无法在新序列中选出一个长度为 $3$ 的区间，因此无解，输出 -1。

样例2

输入

8 3
1 1 1 -1 -1 1 1 1
3 6
1 2
2 5

输出

1 4
-1
1 4

说明

第一组操作：区间 $[3,6]$，长度 $k=4$，和 $X = 1 + (-1) + (-1) + 1 = 0$。 移除后新序列由原下标 $1,2,7,8$ 组成，值均为 $1$，即 $[1,1,1,1]$，长度为 $4$。 选择整个新序列（区间 $[1,4]$），和为 $4$，严格大于 $X = 0$，因此输出 1 4。

第二组操作：区间 $[1,2]$，长度 $k=2$，和 $X = 2$。 剩余元素为原下标 $3..8$，值 $[1,-1,-1,1,1,1]$。所有长度为 $2$ 的子区间和最大为 $2$，无法严格大于 $X$，故输出 -1。

第三组操作：区间 $[2,5]$，长度 $k=4$，和 $X = 1 + (-1) + (-1) + 1 = 0$。 新序列由原下标 $1,6,7,8$ 组成（全为 $1$），即 $[1,1,1,1]$。区间 $[1,4]$ 和为 $4 > 0$，输出 1 4。

样例3

输入

4 2
-1 -1 -1 -1
1 2
2 4

输出

-1
-1

说明

序列全为 $-1$，任何区间的和均为负数。 第一个操作 $[1,2]$：$k=2$，$X=-2$；剩余序列长 $2$，区间和也为 $-2$，无法严格大于 $X$，无解。 第二个操作 $[2,4]$：$k=3$，剩余序列长度 $1 < 3$，无法选出长度为 $3$ 的区间，无解。 因此两行均输出 -1。