题目描述

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

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

注意：链表的第一个位置是从前往后的第1个位置，最后一个位置是从前往后的第 n 个位置（n 为链表当前长度）。从后往前计数时，链表末尾的位置为 1，倒数第二个位置为 2，以此类推。

输入格式

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

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

输出格式

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

样例

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

1
2
-1

样例解释

样例1中：

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

7
1 0 1
1 1 2
1 2 3
2 2
2 1
2 4
1 1 4

1
2
-1

样例解释

样例2中：

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

数据范围

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

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