当前没有测试数据。

题目描述

ZYB has finished his computer course recently. He is very interested in the LRU algorithm for cache management.

To simplify the problem, assume that a block contains a name (which is a string) and a set of data (which is a number). ZYB wants to implement the LRU algorithm with an array.

His array can hold at most $\ M$ elements at any time. In the beginning, the array is empty. In each operation, the CPU may access a block $\ s$. ZYB will search for it in his array by brute force. If this block is present in his array (which means he can find a block with the same name), he takes it out of the array and puts it back at the end of the array. Otherwise, he simply adds it to the end of the array. If at any time, the size of the array exceeds the capacity, he will remove the first block in his array (the block at the front of the array).

Seems boring? Well, sometimes ZYB may ask the data of a block in, before or after a certain block. Could you help him to write a program to achieve his goal?

输入格式

There are multiple cases. The first line of the input contains a single positive integer $\ T$, indicating the number of cases.

For each case, the first line of the input contains two integers $\ Q$ and $M\ (1 \leq Q, \ M \leq 500000)$), denoting the number of operations and the capacity of the array. The following $\ Q$ lines each contain an integer $opt \ (0 \le opt \le 1)$, a string $s \ (1 \leq |s| \leq 10)$ and an integer $\ v$, separated by single spaces, describing an operation.

If $\ opt = 0$, then $\ |v| < 10$, and the operation is that the CPU wants to access a block. If this access misses (which means you can't find a block in the array with the name $\ s$), add a block at the end of the array with the name $\ s$ and the data $\ v$, and the result of the operation is $\ v$. If this access hits, the result of the operation is the data of the block you found (ignore $\ v$ in this case). Don't forget to move that block to the end of the array.

If $\ opt = 1$, then $\ v$ will be $\ -1,0$ or $\ 1$ , and the operation is that you should answer ZYB's question. Let $\ k$ be the index of the block with the name $\ s$ in the array. Then the result of this operation is the data of the block with the index $\ k+v$ in the array. If such block doesn't exist, please output ``Invalid'' (without quotation marks) instead.

Note that ZYB's questions (operations of type $\ 1$) don't count as access and don't cause the array to be updated.

It is guaranteed that the sum of $\ Q$ over all cases does not exceed $\ 1000000$, and that $\ s$ only contains digits (i.e. '0' - '9').

输出格式

For each case, print the result of each operation in a line as defined in the input section of the statement.

样例

样例输入 1

1
8 3
0 0101010 1
0 0101011 2
1 0101010 1
0 1100000 3
0 0101011 -1
0 1111111 4
1 0101011 -1
1 0101010 0

样例输出 1

1
2
2
3
2
4
3
Invalid