题目描述

波托科兰迪亚国家足球队由 $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$) —— 分别表示波托科兰迪亚国家足球队的队员数量、事件数量（训练次数与寻找有获胜机会球队的查询次数之和）、$w$ 的值以及数据组编号。

第二行包含 $n$ 个整数 $a_0, a_1, ..., a_{n-1}$ $(|a_i| \le 10^9)$ —— 足球运动员的技艺值。

接下来的 $m$ 行描述事件，格式为以下两种之一：

• $1\ p\ k$ $(0 \le p < n-1, |k| \le 2 \cdot 10^9)$ —— 表示参与训练的球员中编号较小者，以及将加到编号 $p$ 球员技艺值上并从编号 $p+1$ 球员技艺值中减去的值。
• $2\ a\ b$ ($0 \le a \le b < n$) —— 表示当前同意与西什兰迪亚队比赛的球员编号为 $a_i, a_i+1, \ldots, b_i$。

保证在任何时刻，对于所有 $i$ 都有 $|a_i| \leq 10^9$，并且至少有一个类型 2 的事件。

输出格式

对于每个类型 2 的事件，输出一对数字 $(l, r)$，用于定义有机会战胜西什兰迪亚队的球员阵容，如果无法在相应条件下形成这样的球队，则输出 $-1$。

请注意，这是一个交互式问题，您需要在线回答所有查询。

不要忘记在每次输出后输出换行符并使用 flush 操作。

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, 2, -1, 5, 0, 10, -2, -2, -2, 4, 1, 4, 6, 0]$；

第二次训练后 —— $[1, 2, -1, 5, 0, 10, -2, -2, -2, 4, -1, 6, 6, 0]$；

第三次训练后 —— $[1, 1, 0, 5, 0, 10, -2, -2, -2, 4, -1, 6, 6, 0]$。

$$\begin{array}{|c|c|c|c|} \hline \rule{0pt}{1.5em} \textbf{子任务编号} & \textbf{n, m} & \textbf{额外限制} & \textbf{分值} \\ \hline \rule{0pt}{1.5em} 1 & 1 \le n, m \le 100 & - & 12 \\ \hline \rule{0pt}{1.5em} 2 & 1 \le n, m \le 5000 & - & 13 \\ \hline \rule{0pt}{1.5em} 3 & 1 \le n, m \le 10^5 & 在任何时刻，所有\ a_i \ 非负，总共不超过\ 500\ 个第二类事件 & 11 \\ \hline \rule{0pt}{1.5em} 4 & 1 \le n, m \le 10^5 & 不进行任何训练 & 15 \\ \hline \rule{0pt}{1.5em} 5 & 1 \le n, m \le 10^5 & 在任何时刻，所有\ a_i \ 等于\ 0\ 或\ 1\ & 12 \\ \hline \rule{0pt}{1.5em} 6 & 1 \le n, m \le 10^5 & w = 0 & 13 \\ \hline \rule{0pt}{1.5em} 7 & 1 \le n, m \le 10^5 & - & 24 \\ \hline \end{array}$$