Let's deal with an array, the most important data structure of computer science. You will be given some operations to do. There will be three types of operations:

Type 1: Insert a number at the end of the array.

Type 2: Delete the last number of the array, where the last number means the latest number which has been inserted.

Type 3: You will get a number and two indices i & j where i<=j. Now you will have to answer how many time the number appears in the array starting from i to j.

You may assume that initially the array is empty.

Input

Each file contains one test case. The first line is an integer Q(1<=Q<=200000), the number of operations. Each of the next Q lines contains an opeation. The operations will appear as the formats below:

1 x , where 1<=x<=200000, which means you have to insert number x at the end of the array.

0 , For this operation, you have to delete the last number of the array

2 x i j , Here, you have to find how many times x appers in the array from i to j. Here x will always be present in the array and 1<=i<=j<=length the array.

Output

For deletion, if the array is already empty, then output a string "invalid" (without quote),otherwise you don't need to print anything for deleting numbers. For the operation type of 2, you have to output an integer, how many times x appears in the array from i to j inclusive.

Example

Input:

7
1 10
1 20
2 20 1 2
0
2 10 1 1
0
0 

Output:
1
1
invalid