题目内容

Tk 有一个长度为 $n$ 的数组 ${a_1,a_2,…,a_n}$ ，其中每个元素 $a_i$ 等于 $-1$ 或 $1$ 。

你需要与 Tk 进行 $m$ 轮游戏，每轮游戏相互独立，（即数组的改变并不会影响其他轮次）；

$S=\sum^r_{i=l}a_i$

随后将区间 $[l,r]$ 从数组中删除，剩余元素按原顺序拼接；你的任务是，在新的数组中找到一个区间 $[l_1,r_1]$ 满足

区间长度与被删除的区间相同，即 $r_1-l_1=r-l$ 。

且 $\sum^{r_1}_{i=l_1}a_i>S$ ；

如果存在多个满足条件的区间，可以输出任意一个；如果不存在，则输出 $- 1$ 。

输入描述

每个测试文件均包含多组测试数据:

除此之外，保证单个测试文件的 $\sum n$ 、 $\sum m$ 及所有被删除区间长度之和均不超过 $10^5$ ;

接下来对于每组测试数据:

第一行输入两个整数 $n$ 和 $m(1≤n,m≤10^5)$ ，分别表示数组长度和游戏轮次；

第二行输入 $n$ 个数组 $a_1,a_2,…,a_n(a_i∈$ { $-1,1$ } $)$ ，表示初始的数组。

此后 $m$ 行，每行输入两个整数 $l$ 和 $r(1≤l≤r≤n)$ ,表示 $Tk$ 选择的删除区间。

对于每组测试数据，输出 $m$ 行，每行对应一轮游戏的答案。

如果无解，输出 $-1$ 。

否则，输出两个整数 $l_1$ 和 $r_1(1≤l_1≤r_1≤n-(r-l+1))$ 表示你选取的区间。

输入

1
5 2
-1 1 1 -1 1
3 4
1 3

输出

2 3
-1

说明

第一轮游戏 $S= 0$ ,删除后数组变为{ $-1,1,1$ }区间 $[2,3]$ 满足答案。

第二轮游戏删除后数组变为{ $- 1,1$ }长度小于 $3$ 一定无解。