N. Just another array problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In addition to the number theory and string algorithms, Professor Sh. likes to work with arrays, not simple ones, but sorted by non-decreasing order of elements. Today Professor Sh. came up with a great problem and shares it with you. Initially, there is an array $$$a$$$ consisting of $$$N$$$ numbers, the elements of which are arranged in non-decreasing order. You can apply $$$2$$$ types of queries to this array:

  1. Shift the array cyclically to the left or right by $$$k$$$ positions.
  2. Check if there is a number $$$x$$$ in the array. If there is such a number, print its index in the array (possibly modified). If a number enters the array several times, you should print the index of its first occurrence in the array.

Since Professor Sh. knows how to work only with sorted arrays, he does not always know how to check whether there is a number $$$x$$$ in the array. Help Professor Sh. – write a program that will correctly respond to both types of queries.

Input

The first line contains the number $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – array length.

The second line contains $$$N$$$ numbers $$$a_i$$$ $$$(-10^{18} \le a_i \le 10^{18})$$$ – elements of the array $$$a$$$. It is guaranteed that initially the elements of the array are sorted by non-decreasing order.

The third line contains the number $$$Q$$$ $$$(1 \le Q \le 3 \cdot 10^5)$$$ – the number of queries.

The following $$$Q$$$ lines contain queries. The queries set like that:

  1. $$$s~k$$$ $$$(1 \le |k| \lt N)$$$ – shift the array cyclically by $$$k$$$ positions. If the number $$$k$$$ is negative, then the shift is carried out to the left, otherwise, the shift must be carried out to the right.
  2. $$$?~x$$$ – check if there is a number $$$x$$$ in the array.
Output

For each query "$$$?~x$$$" print a number in a separate line – index of $$$x$$$ item in the array. If there is no $$$x$$$ in the array, print "$$$-1$$$" in a separate line. It is assumed that the elements of the array are numbered from $$$1$$$.

Examples
Input
7
1 2 3 4 5 6 7
7
? 9
s 2
? 4
s -2
? 3
s -5
? 6
Output
-1
6
3
1
Input
7
1 1 2 2 3 3 4
7
? 9
s 2
? 4
s -1
? 2
s -5
? 1
Output
-1
2
4
4
Note

Consider the first example. Initially, the array is $$$a = [1, 2, 3, 4, 5, 6, 7]$$$.

  1. Since the number $$$9$$$ is larger than any element of the array $$$a$$$, we output $$$-1$$$.
  2. After query $$$s~2$$$ shift the array to the right by $$$2$$$ positions, it becomes equal to $$$[6, 7, 1, 2, 3, 4, 5]$$$.
  3. The number $$$4$$$ is at the position $$$6$$$, so we output $$$6$$$.
  4. After the query $$$s~-2$$$, the array will take the original form $$$[1, 2, 3, 4, 5, 6, 7]$$$
  5. The number $$$3$$$ is at the position $$$3$$$, so we output $$$3$$$
  6. After the query $$$s~-5$$$ , the array is shifted by $$$5$$$ positions to the left: $$$[6, 7, 1, 2, 3, 4, 5]$$$
  7. The number $$$6$$$ is at the position $$$1$$$, so we output $$$1$$$.