题目描述

波托科兰迪亚足球国家队由 $n$ 名足球运动员组成，编号为 $0$ 到 $n-1$。对于每名球员，已知他的足球能力值。在波托科兰迪亚，能力值总是一个整数。编号为 $i$ 的球员的能力值为 $a_i$。

主教练哥萨克·乌斯经常组织各种训练。训练过程中，球员的能力值可能发生变化。不过，由于乌斯并不是很有经验的教练，他每次只训练一对编号相差为 $1$ 的球员。同时要求训练前后，这两名球员的能力值之和保持不变。

例如，如果训练编号为 $x$ 和 $x+1$ 的两名球员，并且给编号为 $x$ 的球员的能力值增加某个整数 $k$，那么编号为 $x+1$ 的球员的能力值就会减少 $k$。

根据新的规定，比赛中禁止换人，并且参加比赛的球员编号必须连续。换句话说，参加比赛的球员可以用一对整数 $(l,r)$ 表示，表示只有编号为

$$l,l+1,\ldots,r$$

的球员参加比赛。

乌斯认为，只有当参加比赛的球员能力值之和等于 $w$ 时，才有可能在乌克兰锦标赛决赛中击败西什兰迪亚国家队。

在某场比赛中，只有编号为 $a_i,a_i+1,\ldots,b_i$ 的球员愿意参加比赛。

现在，在训练不断发生、并且每场比赛中愿意参赛的球员范围不同的情况下，乌斯请求你帮助他找到一支有机会取胜的队伍。

交互说明

本题为交互式题目。你的程序需要按顺序读入评测器发送的信息，并在每次查询后立即输出答案。

程序开始时，评测器会发送：

n m w group

其中：

• $1\le n,m\le 10^5$；
• $|w|\le 10^9$；
• $group$ 表示测试点所属的子任务编号。

随后评测器会发送一行，共 $n$ 个整数：

a_0 a_1 ... a_{n-1}

表示所有球员初始的能力值，满足 $|a_i|\le 10^9$。

接下来共有 $m$ 个事件。每个事件的格式为以下两种之一。

训练事件

1 p k

表示训练编号为 $p$ 和 $p+1$ 的两名球员，其中：

• $0\le p<n-1$；
• $|k|\le 2\cdot 10^9$。

训练后：

$$a_p\leftarrow a_p+k,$$ $$a_{p+1}\leftarrow a_{p+1}-k.$$

查询事件

2 a b

其中 $0\le a\le b<n$。表示当前只有编号为

$$a,a+1,\ldots,b$$

的球员愿意参加比赛。

对于每个查询事件，你需要立即输出一个答案。

输出格式

对于每个第二类事件，你需要输出以下两种形式之一：

• 输出两个整数 l r，表示选择编号为 $l,l+1,\ldots,r$ 的球员参加比赛；
• 输出 -1，表示在当前条件下无法组成满足要求的队伍。

若输出 l r，必须满足：

$$a\le l\le r\le b,$$

且当前时刻：

$$a_l+a_{l+1}+\cdots+a_r=w.$$

每次输出后，都必须输出换行并刷新输出缓冲区。例如在 C++ 中可以使用：

cout << l << ' ' << r << endl;

或：

cout << -1 << endl;

其中 endl 会自动刷新输出缓冲区。也可以使用 \n 后手动 flush。

保证任意时刻所有 $i$ 均满足 $|a_i|\le 10^9$，并且至少存在一个第二类事件。

样例交互

下面给出一种可能的交互过程。注意，本题答案可能不唯一。

输入

14 9 3 0
1 2 -1 5 0 3 5 -2 -2 4 1 4 6 0
2 0 1
2 0 13
1 5 7
2 4 8
1 10 -2
2 6 11
2 0 5
1 1 -1
2 0 9

输出

0 1
8 10
-1
9 10
0 1
-1

样例解释

数组 $a$ 的变化如下：

第 $1$ 次训练后：

$$[1, 2, -1, 5, 0, 10, -2, -2, -2, 4, 1, 4, 6, 0]$$

第 $2$ 次训练后：

$$[1, 2, -1, 5, 0, 10, -2, -2, -2, 4, -1, 6, 6, 0]$$

第 $3$ 次训练后：

$$[1, 1, 0, 5, 0, 10, -2, -2, -2, 4, -1, 6, 6, 0]$$

评分方式

原题的子任务评分方式如下图所示：

Hint

本题原时限为2s,但OJ上测评要加上交互程序的运行时间，因而时限放宽到4s--8s