题目描述

哈希表又称散列表，是指任意的键值 key 都唯一对应到哈希表中的某个位置，只需要输入查找的键值，就可以快速地找到其对应的 value，类似 Python 里的字典。

给定哈希函数：

def hashing(key):
    return key % M

其中 $M$ 是一个固定的常数。

但可能多个键值可能对应哈希表的同一个位置，于是就有了拉链法。

拉链法是在每个存放数据的地方开一个链表，如果有多个键值索引到同一个地方，只用把他们都放到那个位置的链表里就行了。

查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其键值与查询的键值是否一致。

现在你要进行下面 $3$ 种操作

1. 往哈希表加入一个键值为 $k$,数值为 $v$ 的元素 如果哈希表的该位置已有元素，则加入该位置链表的开头；
2. 查询某个键值为 $k$ 的元素对应的数值 $v$；
3. 查询某个键值为 $k$ 的元素在链表中的位置。

输入格式

第一行两个正整数 $n,M$，分别表示表示操作次数和模数。

接下来 $n$ 行每行包括 $2$ 或 $3$ 个整数，表示一个操作。操作可以是一下四种之一：

• 1 k v 表示第一种操作；
• 2 k 表示第二种操作；
• 3 k 表示第三种操作；

输出包括若干行整数，为所有操作 $2$ 和操作 $3$ 的结果。

样例 #1

样例输入 #1

8 10
1 15 1
1 27 2
1 9 3
1 19 4
2 15
1 29 5
2 19
3 9

样例输出 #1

1
4
3

数据范围

对于 $100\%$ 的数据，保证 $1\le n \le 10^4,1 \le M \le 10^5,1\le k\le10^9$，保证键值互不相同。