Description

有一个长度为N的数组，现在对它有M次操作。
每次操作有2个选择:
询问数字x  第y次出现时在数组的下标是多少。
将下标为x的数字变为 y。

Input

第一行两个数字N，M（1<=N,M<=40000）
接下来给出数组a[N]，两个数字以空格间隔，1<=a[i]<=N
接下来M行，每行三个数字op,x,y(1<=x,y<=N)
若op等于1 则代表询问数字x  第y次出现时在数组的下标是多少。（若数组中x的个数小于y，则输出-1）
若op等于2 则代表将下标为x的数字变为 y。

Output

对于每次询问输出一个数字并换行。

Sample Input

3 3
2 3 2
1 2 2
2 2 2
1 2 2

Sample Output

3
2

HINT

Source

NBU OJ