Xima has N balls arranged together in a line, the i-th (1 ≤ i ≤ N) ball has a value of A_i.

Tzaph asks Q queries to Xima. There are two types of queries:

• 1 i k: The value of the i-th ball is changed into k. In other words, A_i = k. Take note that A_i and k could have a same value. In this case, Xima shouldn't do anything.
• 2 i: Tzaph removes the i-th ball out from the line. Print the number of pairs (x, y) such that the x-th and the y-th ball is in the line,  x < y, and A_x = A_y. After this query, Tzaph returns the i-th ball back to the line in its original position.

However, Tzaph asks too many queries and Xima has too many balls. Xima asks you to help him answer all of Tzaph's queries. Help him out!

Input

The first line contains two integers N and Q.

The second line consists of N integers, where the i-th integer represents A_i.

The next Q lines represents the queries with format explained in the description.

Output

For every second type of query, print the answer required.

Constraints

1 ≤ N, Q, A_i, k ≤ 10⁵

Examples

Input 1:
5 5
1 2 3 4 5
1 2 3
1 5 4
2 1
1 2 4
2 4

Output 1:
2
1

Input 2:
1 3
1
2 1
1 1 3
2 1

Output 2:
0
0