Bear_2 退休后经营了一家超市，共有 n 件商品，编号为 1,2,……,n ，编号为 i 的商品价格为 Pi。
他最多能记住 m 件商品的价格，现在有两种操作能更改它的记忆：
1.当有人买商品 X 时，他会从大脑中搜寻商品 X 的信息，当他大脑中存有商品 X 的信息时，他会告诉顾客商品 X 的价格，并且加深对商品 X 的印象，这是一个有效询问。如果他大脑中没有商品 X 的信息，他会告诉顾客 "-1" 表示他不知道这个的价格，这是一个无效询问
2.当商品 X 价格改变时，他会在大脑中添加商品 X 的信息，如果原本就存有商品 X 的信息那么他就加深对商品 X 的印象。不然就在大脑中添加商品 X 的信息，如果原本就存有 m 件商品的信息，那么他会遗忘掉最久没有被提及(有效询问也算被提及)的商品。
例如，Bear_2 最多记住 3 件商品信息，按顺序添加了商品 1,2,3,4 ，那么在添加第 4 件商品的时候，他会遗忘 1 商品的信息。
又例如，Bear_2 最多记住3 件商品信息，按顺序添加商品 1,2,3 的信息后，顾客询问了 1 商品的价格，那么再添加商品 4 时，Bear_2会遗忘商品 2 的信息。
假设一开始Bear_2 脑子里什么都没有，请你帮 Bear_2 对每次顾客的询问做出回应。
输入描述:
第一行输入两个正整数 n,m (1<=n,m<=1000000) 分别表示商品的数量和 Bear_2 最多记住商品的数量
第二行输入一个正整数 Q(1<=Q<=1000000) 表示有 Q 次操作
之后的 Q 行，每行先输入一个正整数 op(1<=op<=2)
当 op 等于 1 时，输入一个正整数 X ，表示顾客询问商品 X 的信息
当 op 等于 2 时，输入两个正整数 X,P 表示商品 X 的价格变为 P
输出描述:
对于每个操作1，在一行内输出一个正整数表示对顾客的回应。
示例1
输入
复制
5 3
10
1 1
2 1 1
1 1
2 2 2
2 3 3
2 4 4
1 1
1 2
2 1 5
1 3
说明
第一次操作询问商品 1 的价格，Bear_2 此时脑袋空空如也，所以回应 -1
第二次操作添加商品 1 的信息，存储此信息后 Bear_2 大脑中存有 1 条信息
第三次操作询问商品 1 的信息，Bear_2 此时存有商品 1 的信息，所以回应 1
第四次操作添加商品 2 的信息，存储此信息后 Bear_2 大脑中存有 2 条信息
第五次操作添加商品 3 的信息，存储此信息后 Bear_2 大脑中存有 3 条信息
第六次操作添加商品 4 的信息，已存有 3 条信息，所以先删除最久没有被提及的商品 1 的信息，然后存储商品 4 的信息，存储此信息后 Bear_2 大脑中存有 3 条信息
第七次操作询问商品 1 的信息，Bear_2 在上次操作中已忘记商品 1 的信息，所以回应 -1
第八次操作询问商品 2 的信息，Bear_2 此时存有商品 2 的信息，所以回应 2
第九次操作添加商品 1 的信息，已存有 3 条信息，所以先删除最久没有被提及的商品 3 的信息，然后存储商品 1 的信息，存储此信息后 Bear_2 大脑中存有 3 条信息
第十次操作询问商品 3 的信息，Bear_2 在上次操作中已忘记商品 3 的信息，所以回应 -1