There are ~N~ ~(1 \le N \le 100\,000)~ bells arranged in a line, labelled ~1~ to ~N~. The ~i^\text{th}~ bell has a frequency of ~f_i~ Hz ~(1 \le f_i \le 10^8)~. There are ~Q~ ~(1 \le Q \le 50\,000)~ operations to perform.

There are two types of operations:

• 1 i f Replace the ~i^{th}~ bell with one with a frequency of ~f~ Hz.
• 2 l r Output the number of distinct frequencies between the ~l^\text{th}~ and ~r^\text{th}~ bell (inclusive).

There will be at most ~1000~ distinct frequencies at a time.

Fast input may be required.

Constraints

For 10% of the points, ~1 \le N \le 100, 1 \le Q \le 100~.

For 90% of the points, ~1 \le N \le 100\,000, 1 \le Q \le 50\,000~.

Input Specification

The first line contains two space separated integers, ~N~ ~Q~, respectively the number of bells and the number of queries.

The next line contains ~N~ space separated integers, the frequency of the bells.

The next ~Q~ lines each contain a query in the format described above.

Output Specification

Output a single integer on its own line for each type 2 query.

Sample Input 1

6 3
1 2 1 4 4 2
2 1 6
1 2 1
2 1 3

Sample Output 1

3
1

Sample Output 1 Explanation

In the beginning, there are only 3 distinct frequencies which the bells have, 1 Hz, 2 Hz, and 4 Hz. After switching the second bell with one with a frequency of 1 Hz. There is only one distinct frequency among the first 3 bells.