本题没有可用的提交语言。

John likes to perform operations on arrays. He imagines a sequence of N numbers and then sorts it.

On this sorted sequence John applies M operations:

1 x - Remove the element at the index x (if x is smaller or equal to the size of the array, otherwise skip the operation)

2 x - Remove one integer with value x from the array (if there is such an integer in the array)

3 x - Remove all the integers with value x from the array (if there is/are such integer/s in the array)

4 x - Add integer x into the array

After he performs each operation, John sorts the array. Your task is to print the size of the sorted array after John performs M operations.

Input

The first line of the input contains two positive integers N(1<=N<=1000000) and M(1<=M<=1000000), the size of the array and number of operations to perform. 

The second line contains N integers not exceeding 10^18 by their absolute values.

The following M lines contain 2 numbers F(1<=F<=4) and X, the type of operation and value/index X.

Output

If the array is empty after all queries, print 0.

Otherwise, print the size of the array in one line.

O0.

Example

Input:
6 5
2 3 4 5 6 6
4 6
1 1
3 6
4 3278
2 3278

Output:
3