E. GukiZ and GukiZianatime limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputProfessor GukiZ was playing with arrays again and accidentally discovered new function, which he called GukiZiana. For given array a, indexed with integers from 1 to n, and number y, GukiZiana(a, y) represents maximum value of j - i, such that aj = ai = y. If there is no y as an element in a, then GukiZiana(a, y) is equal to  - 1. GukiZ also prepared a problem for you. This time, you have two types of queries:   First type has form 1 l r x and asks you to increase values of all ai such that l ≤ i ≤ r by the non-negative integer x.  Second type has form 2 y and asks you to find value of GukiZiana(a, y). For each query of type 2, print the answer and make GukiZ happy!InputThe first line contains two integers n, q (1 ≤ n ≤ 5 * 105, 1 ≤ q ≤ 5 * 104), size of array a, and the number of queries. The second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 109), 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 ≤ 109), first type query.If line starts with 2, then th query looks like 2 y (1 ≤ y ≤ 109), second type query.OutputFor each query of type 2, print the value of GukiZiana(a, y), for y value for that query.ExamplesInput4 31 2 3 41 1 2 11 1 1 12 3Output2Input2 31 21 2 2 12 32 4Output0-1
Input4 31 2 3 41 1 2 11 1 1 12 3
Output2
['binary search', 'data structures', 'implementation', '*2500']