I. Infinite Arrays
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A subarray of an array $$$B$$$ is a contiguous sequence of elements taken from $$$B$$$. For example, if $$$B=[3,1,4,1,5]$$$, then $$$[3,1,4]$$$, $$$[4,1]$$$, the empty array $$$[\ ]$$$ and the whole array $$$B$$$ are subarrays of $$$B$$$ (among others), while $$$[3,4,5]$$$ and $$$[1,3]$$$ are not subarrays of $$$B$$$.

We also define $$$C^m$$$ as the array obtained by the concatenation of $$$m$$$ copies of the array $$$C$$$. For example, if $$$C=[3,2]$$$ then $$$C^1=[3,2]$$$, $$$C^2=[3,2,3,2]$$$ and $$$C^{\infty}=[\ldots,3,2,3,2,3,2,\ldots]$$$.

In this problem you are given an array $$$P$$$ containing no repeated numbers, and you have to process a sequence of events that occur in order. The events can be of three types:

  • Delete: a number present in $$$P$$$ must be deleted. For example, if $$$P=[2,3,4]$$$ and the number $$$3$$$ has to be deleted, once the event is processed $$$P$$$ will become $$$[2,4]$$$.
  • Insert: a number not present in $$$P$$$ must be inserted into $$$P$$$ before some other number present in $$$P$$$. For example, if $$$P=[4,3,2,1]$$$ and the number $$$9$$$ must be inserted before the number $$$1$$$, once the event is processed $$$P$$$ will become $$$[4,3,2,9,1]$$$.
  • Query: the length of the longest common subarray between $$$P^\infty$$$ and $$$A^\infty$$$ must be computed, where $$$A$$$ is an array given in the query. For example, if $$$P=[1,2,3,4]$$$ and $$$A=[3,2]$$$, then the longest common subarray between $$$P^\infty$$$ and $$$A^\infty$$$ is $$$[2,3]$$$, so the answer to the query is $$$2$$$.

Are you ready for this challenge?

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 5 \cdot 10^5$$$) indicating the initial length of $$$P$$$.

The second line contains $$$N$$$ different integers $$${P_1}, {P_2}, \ldots, {P_N}$$$ ($$$1 \leq P_i \leq 10^6$$$ for $$${i}={1}, {2}, \ldots, {N}$$$).

The third line contains an integer $$$E$$$ ($$$1 \leq E \leq 5 \cdot 10^5$$$) representing the number of events that need to be processed.

Each of the next $$$E$$$ lines describes an event, in the order they must be processed. The content of the line depends on the event, as follows:

  • Delete: the line contains the character '-' (minus sign) and an integer $$$X$$$ ($$$1 \leq X \leq 10^6$$$, and $$$X \in P$$$), denoting that $$$X$$$ must be deleted from $$$P$$$. It is guaranteed that after the removal $$$P$$$ does not become empty.
  • Insert: the line contains the character '+' (plus sign) and two integers $$$Y$$$ and $$$Z$$$ ($$$1 \leq Y, Z \leq 10^6$$$, $$$Y \notin P$$$, and $$$Z \in P$$$), denoting that $$$Y$$$ must be inserted into $$$P$$$ immediately to the left of $$$Z$$$.
  • Query: the line contains the character '?' (question mark), a positive integer $$$K$$$, and $$$K$$$ integers $$${A_1}, {A_2}, \ldots, {A_K}$$$ ($$$1 \leq A_i \leq 10^6$$$ for $$${i}={1}, {2}, \ldots, {K}$$$), indicating that the length of the longest common subarray between $$$P^{\infty}$$$ and $$$A^{\infty}$$$ must be computed. It is guaranteed that the input contains at least one query, and the sum of $$$K$$$ across all the queries is at most $$$10^6$$$.
Output

Output a line for each query, with an integer indicating the length of the longest common subarray between $$$P^\infty$$$ and $$$A^\infty$$$, or the character '*' (asterisk) if the length of the longest common subarray is larger than $$$10^{18}$$$.

Examples
Input
4
1 2 3 4
10
? 2 3 2
? 3 99 99 99
- 1
- 4
? 2 3 3
? 3 4 1 4
+ 64 3
+ 1 2
? 4 1 2 64 3
? 4 1 3 64 2
Output
2
0
1
0
*
1
Input
1
217
1
? 1 314
Output
0