GukiZ and GukiZiana

Description:

Input:

The first line contains two integers n, q (1 ≤ n ≤ 5 * 10⁵, 1 ≤ q ≤ 5 * 10⁴), size of array a, and the number of queries.

The second line contains n integers a₁, a₂, ... a_n (1 ≤ a_i ≤ 10⁹), forming an array a.

Each of next q lines contain either four or two numbers, as described in statement:

If line starts with 1, then the query looks like 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 10⁹), first type query.

If line starts with 2, then th query looks like 2 y (1 ≤ y ≤ 10⁹), second type query.

Output:

For each query of type 2, print the value of GukiZiana(a, y), for y value for that query.

Sample Input:

4 3
1 2 3 4
1 1 2 1
1 1 1 1
2 3

Sample Output:

2

Sample Input:

2 3
1 2
1 2 2 1
2 3
2 4

Sample Output:

0
-1