题目描述

给定一个初始为空的单链表，你需要对它进行两种操作：

1. 1 x y - 在链表中插入一个值为 y 的节点。如果 x = 0，则在链表头部插入 y；否则，在第一个值为 x 的节点后面插入 y。如果 x ≠ 0 且链表中不存在值为 x 的节点，则不进行插入操作。
2. 2 x - 查询链表中第一个值为 x 的节点，输出该节点从前往后的位置（即从链表头部开始计数的位置），如果链表中不存在值为 x 的节点，则输出 -1

注意：链表的第一个位置是从前往后的第1个位置，最后一个位置是从前往后的第 n 个位置（n 为链表当前长度）。

输入格式

第一行一个正整数 n，表示操作序列的长度。

接下来的 n 行，每行一个操作。如果第一个数字是 1，则后面跟着两个整数 x, y，表示插入操作；如果第一个数字是 2，则后面跟着一个整数 x，表示查询操作。

输出格式

对于每个查询操作，输出一行一个整数，表示查询结果。

样例

5
1 0 1
1 0 2
1 0 3
2 2
2 4

2
-1

样例解释

样例1中：

• 在头部插入1：链表为 [1]
• 在头部插入2：链表为 [2, 1]
• 在头部插入3：链表为 [3, 2, 1]
• 查询2：第一个2从前往后是第2个位置，输出2
• 查询4：链表中不存在4，输出-1

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

2
1
-1

样例解释

样例2中：

• 在头部插入1：链表为 [1]
• 在1后面插入2：链表为 [1, 2]
• 在2后面插入3：链表为 [1, 2, 3]
• 查询2：第一个2从前往后是第2个位置，输出2
• 查询1：第一个1从前往后是第1个位置，输出1
• 查询4：链表中不存在4，输出-1

数据范围

子任务	分值	数据范围	特殊性质
1	30	$1 \le n \le 10^3$, $1 \le x,y \le 10^6$	无
2		$1 \le n \le 10^4$, $1 \le x,y \le 10^6$
3	40	$1 \le n \le 5 \times 10^4$, $1 \le x,y \le 10^6$

保证至少有一个查询操作（即至少有一个操作类型为 2）。