Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. GukiZ и GukiZiana
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Профессор GukiZ опять играет с массивами. Он случайно открыл новую функцию, которую назвалGukiZiana. Для данного массива a, проиндексированного целыми числами от 1 до n, и числа y, GukiZiana(a, y) определяется как максимальное возможное значение j - i, где числа j и i таковы, что aj = ai = y. Если же y не встречается в a как элемент, то GukiZiana(a, y) полагается равной  - 1. GukiZ также подготовил для вас задачу. На этот раз у вас есть два типа запросов:

  1. Запрос первого типа имеет вид 1 l r x, данный запрос означает, что все ai, такие, что l ≤ i ≤ r, должны быть увеличены на неотрицательное целое значение x.
  2. Запрос второго типа имеет вид 2 y, данный запрос означает, что надо определить значение GukiZiana(a, y).

Для каждого запроса типа 2 выведите ответ, и порадуйте этим GukiZ!

Входные данные

В первой строке записано два целых числа n, q (1 ≤ n ≤ 5·105, 1 ≤ q ≤ 5·104), размер массива a, и количество запросов.

Во второй строке записано n целых чисел a1, a2, ... an (1 ≤ ai ≤ 109), формирующих массив a.

Каждая из последующих q строк содержит либо четыре, либо два числа, как описано в условии задачи:

Если строка начинается с 1, то данный запрос выглядит следующим образом: 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109) и представляет собой запрос первого типа.

Если строка начинается с 2, то данный запрос выглядит следующим образом: 2 y (1 ≤ y ≤ 109), и представляет собой запрос второго типа.

Выходные данные

Для каждого запроса типа 2, выведите GukiZiana(a, y) для значения y из данного запроса.

Примеры
Входные данные
4 3
1 2 3 4
1 1 2 1
1 1 1 1
2 3
Выходные данные
2
Входные данные
2 3
1 2
1 2 2 1
2 3
2 4
Выходные данные
0
-1