One day, Xiao Xu's friend invited him to eat pudding, so Xiao Xu happily went to his friend's house. Wow! So many colorful puddings! The friend said, "Let's play a game before we start eating." He arranged the puddings in a row and continued, "I can change all puddings of a certain color to another color, and at certain moments, I will ask you how many color segments there are in total. For example, four puddings with colors 1, 2, 2, 1 have a total of 3 color segments."

Input

The first line contains two integers $n$ and $m$, representing the number of puddings and the number of operations, respectively, separated by a space. The second line contains $n$ integers $A_1, A_2, \cdots, A_n$ separated by spaces, where $A_i(1 \le i \le n)$ represents the color of the $i$-th pudding. The following $m$ lines describe the $m$ operations. For each operation, if the first number is $1$, it means the friend wants to change colors; this is followed by two integers $x$ and $y$ ($x$ may equal $y$), meaning that after the operation, all puddings with color $x$ are changed to color $y$. If the first number is $2$, it means the friend wants to ask how many color segments there are currently, and you should output an integer as the answer. The input data guarantees $0 < n, m < 100\,001$ and $0 < A_i, x, y < 1\,000\,000$.

Output

The number of lines in the output corresponds to the number of type 2 operations (i.e., queries about the number of color segments). For each query, output the number of color segments at that time on a new line.

Examples

Input 1

4 3
1 2 2 1
2
1 2 1
2

Output 1

3
1