Prefix and Suffix

alamkhan Intra AUST Programming Co...
Limits 2s, 256 MB

Initially, you are given an empty array AA. You have to perform the following queries.

11 PP - Add an integer PP at the beginning of the array.

22 QQ - Add an integer QQ at the end of the array.

33 XX YY - How many times does the subarray of length (YX+1)(Y-X+1) consisting of XXth index to YYth index exist in the whole array. For example, if there is an array A[2,2,2,3,4,5,2,2]A[2,2,2,3,4,5,2,2] and subarray of length 22 from index 22 to index 33 is[2,2][2,2] then this subarray exist 33 times in the main array.

44 XX YY - Is the subarray [X.Y][X….Y] is same as the reverse of that subarray? That means, Is A[X,X+1,,Y1,Y]A[X,X+1,,Y-1,Y] is the same as A[Y,Y1,..,X1,X]A[Y,Y-1,..,X-1,X]? Print Yes“Yes” or No“No” based on your answer. For example, if there is an array A[2,2,2,3,4,5,2,2]A[2,2,2,3,4,5,2,2] then subarray of index 11 to 33 is same as the reverse of that subarray, while subarray of index 33to 55 and 11to 66 is not.

Input

First line of input consists of the number of queries N(1<=N<=5105)N(1<=N<=5*10^5). Then next NN lines have the queries described above. The Maximum length of the array does not exceed 51055*10^5.

0<=P,Q<=1090<=P,Q<=10^9

1<=X<=Y<=1<=X<=Y<= length of the array at current moment

Output

For each query of types 3 and 4 print the query result. See sample output for more details.

Sample

InputOutput
6
1 4
2 4
3 1 2
2 4
4 1 3
3 1 2
1
Yes
2

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.