Футбол у Потоколяндії

Execution time limit is 2 seconds

Runtime memory usage limit is 256 megabytes

Збірна команда Потоколяндії з футболу складається з $n$ футболістів, пронумерованих цілими числами від $0$ до $n - 1$ . Для кожного гравця відоме його вміння грати у футбол (у Потоколяндії ця характеристика завжди є цілим числом). Вміння гравця з номером $i$ рівне $a_{i}$ .

Головний тренер Козак Вус часто проводить різні тренування. Під час тренування вміння гравців можуть змінюватись. Але оскільки Козак не дуже досвідчений тренер, він завжди тренує лише пару футболістів, чия різниця номерів рівна $1$ . При цьому обов'язково, щоб сума вмінь гравців які тренуватимуться після тренування, залишалась такою самою, як і до тренування. Наприклад, якщо тренуватимуться гравці з номерами $x$ та $x + 1$ та до вміння гравця з номером $x$ буде додано деяке число $k$ то від вміння гравця з номером $x + 1$ буде віднято $k$ .

Згідно з новим регламентом заміни під час матчу заборонені та футболісти, які братимуть участь у матчі, мають мати послідовні номери. Іншими словами, номери футболістів що братимуть участь у матчі, можна буде описати парою цілих чисел $(l, r)$ , що означатиме, що братимуть участь у матчі лише футболісти з номерами $l, l + 1, \dots, r$ .

Козак Вус вважає, що перемогти збірну Сішляндії у фіналі чемпіонату України можна лише у випадку, якщо сума вмінь гравців що братимуть участь у матчі буде рівною $w$ .

У певному матчі чемпіонату лише гравці з номерами $a_{i}, a_{i} + 1, \dots, b_{i}$ згодні грати в матчі.

Тепер Козак просить Вас допомогти йому знаходити команду, яка має шанси на перемогу у матчі проти збірної Сішляндії, якщо відбуваються тренування та не всі гравці згодні грати в певному матчі.

Input

Перший рядок містить чотири цілих числа $n$ , $m$ , $w$ , $g ro u p$ ( $1 \leq n, m \leq 1 0^{5}, ∣ w ∣ \leq 1 0^{9}$ ) — кількість членів збірної команди Потоколяндії з футболу, кількість подій (сума кількостей тренувань та запитів знаходження команди, що має шанси на перемогу), значення $w$ та номер блока відповідно.

Другий рядок містить $n$ цілих чисел $a_{0}, a_{1}, ..., a_{n - 1}$ $(∣ a_{i} ∣ \leq 1 0^{9})$ — значення вмінь футболістів.

Кожний з наступних $m$ рядків описує подію і має один з наступних форматів:

«1 p k» $(0 \leq p < n - 1, ∣ k ∣ \leq 2 \cdot 1 0^{9})$ — мінімальний з номерів гравців, що братимуть участь у тренуванні, та значення, що додасться до вміння гравця з номером $p$ та відніметься від вміння гравця з номером $p + 1$ .
«2 a b» ( $0 \leq a \leq b < n$ ) — параметри, що означають, що в даний момент грати проти збірної Сішляндії погоджуються футболісти з номерами $a_{i}, a_{i} + 1, \dots, b_{i}$ .

Гарантується, що в будь-який момент часу для усіх $i$ виконується $∣ a_{i} ∣ \leq 1 0^{9}$ та що буде принаймні одна подія другого типу.

Interaction

Зверніть увагу, що це інтерактивна задача і вам потрібно відповідати на всі запити онлайн.

Не забувайте виводити символ кінця рядка та використовувати операцію flush після кожного вивода.

Output

Для кожної події другого типу виведіть пару чисел $(l, r)$ , яка визначатиме гравців команди, яка має шанси на перемогу проти збірної Сішляндії, або $- 1$ , якщо таку команду неможливо утворити за відповідних умов.

Examples

Input #1

Answer #1

Note

Пояснення до прикладу:

Значення елементів масиву $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]$ ;