You are given an array \(a_1,\ a_2,\ \dots ,\ a_N\) consisting of \(N\) elements. You are given \(Q\) queries. Each query is of the following types:

The format of the first type of query is \(1\ L\ R\ x\). You must increase the values of all elements in range \(L\) to \(R\) (both inclusive) by integer \(x\).
The format of the second type of query is \(2\ L\ R\ y\). You must multiply the values of all elements in range \(L\) to \(R\) (both inclusive) by the integer \(y\).
The format of the third type of query is \(3\ z\). You are required to find the maximum distance between elements that are equal to \(z\) in the array. If the element is not present in the array, print -1.

Input format

The first line contains an integer \(N\).
The next line contains \(N\) integers \(a_1,\ a_2,\ \dots ,\ a_N\) denoting the elements of the array.
The next line contains \(Q\) denoting the number of queries.
The next Q lines contain one of the 3 queries mentioned above.

Output format

For every query of Type 3, print an integer denoting the maximum distance \(j-i+1\) where \(1 ≤ i,\ j ≤ n\).

Note: The query of type 3 is present at least once in the problem.

Constraints

\(1 \le N \le 400000\\ 1 ≤ a_i ≤ 10^9\\ 1\le L,\ R \le N\\ 1\le Q \le 10000\\ 1 \le x,\ y,\ z\le 1000000000\)

Note: No \(a_i\) exceeds \(10^{18}\) after updates.