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 it's original position.

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

Input Format

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 Format

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

Sample Input 1

5 5
1 2 3 4 5
1 2 3
1 5 4
2 1
1 2 4
2 4

Sample Output 1

2
1

Sample Input 2

1 3
1
2 1
1 1 3
2 1

Sample Output 2

0
0

Constraints

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