Ada the Ladybug is cultivating vegetables. She has a long furrow full of different kinds of it and she wants to know the number of unique vegetables on a segment of the furrow. As the cultivation is a dynamic process, a kind (on a single position) might become another kind during this process.

Given furrow and a few updates, can you answer questions asking about number of unique kinds of vegetable on a segment?

Input

The first line contains 1 ≤ N, Q ≤ 2*10⁵ , length of furrow and number of queries.

Next line contains N integers 0 ≤ A_i ≤ 2*10⁵, the kind of i^th vegetable

Each of following Q lines contains one of the following kinds of query:

1 I V: The vegetable on index 0 ≤ I < N, will be changed to kind 0 ≤ A ≤ 2*10⁵

2 L R: 0 ≤ L ≤ R < N , the index of left/right bound of segment for which you want to know the number of unique kinds.

Output

For each query of second kind, print the number of unique kinds of vegetable.

Example Input

8 8
1 2 3 3 1 2 3 3
2 1 3
2 0 3 
2 0 7
1 3 4
1 7 0
2 1 3
2 0 3 
2 0 7

Example Output

1
2
0
3
4
2