Moorhsum和Slime是好朋友。

在侥幸取得省选名额后，Moorhsum开始整天乱浪。为了让他练练手，Slime给他出了这样一道题：

给定一个序列，支持：

1. 将区间$[l,r]$中的每个数加上$x$

2. 询问一个数$x$在区间$[l,r]$中第一次出现的位置

作为普及二等选手，Moorhsum并不会做。于是他向你求助，你能帮帮他么？

输入格式

第一行两个数 $n$，$q$ 代表序列长度和操作次数

接下来 $n$ 个数 $a_1$ ~ $a_n$ 代表数列的初始值

随后 $q$ 行，每行四个数 $tp$,$l$,$r$,$x$

若 $tp$ 为$1$ 代表把$a_l$ ~ $a_r$统一加上$x$

若 $tp$ 为$2$ 代表询问$[l,r]$中，$x$的第一次出现位置

输出格式

对于每次询问，输出一行表示答案。

若$x$未在$[l,r]$中出现过 输出$-1$

样例一

input

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

output

-1
-1
3
-1
-1

explanation

样例二

input

10 10
6 6 1 4 8 2 5 3 5 6 
2 5 7 8
2 8 8 3
2 6 7 5
2 7 10 5
1 6 8 4
2 9 10 4
2 3 7 8
2 5 9 5
2 2 8 9
2 8 8 9

output

5
8
7
7
-1
5
9
7
-1

样例三

限制与约定

对于$50\texttt{%}$的数据 $n, q \leq 5000$

另有$10\texttt{%}$的数据无修改操作

另有$20\texttt{%}$的数据修改操作的 $l$，$r$ 相等

对于$100\texttt{%}$的数据 $n, q \leq 100000$

保证任何时刻

$-10^9 \leq a_i \leq 10^9$

$-10^9 \leq x \leq 10^9$

$1 \leq l \leq r \leq n$

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载