题意：给你一个固定长度的LRU数组，每次有两种操作
0号操作：若查询的字符串已加入到数组中，就把它取出来，原有值保持不变，压入数组末尾。否则直接加入到末尾，值为输入的v。
1号操作：先得出输入的字符串在数组中的下标k，查询下标为（k+v）的数组元素的值，若k或（k+v）不存在都输出Invalid。

读懂题意后就可以开始模拟啦！
时间限制比较死，加了快读才过的。 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <utility>
#include <set>
#include <bitset>
#include <random>

#define mst(a,b) memset(a,b,sizeof(a))
#define scd(x) scanf("%d", &x)
#define scdd(x,y) scanf("%d%d", &x, &y)
#define scddd(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define eb emplace_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = 2*acos(0.0);
const double eps = 1e-6;
const ll mod = 1e9+7;
const int N = 2e5 + 10;
const int M = 1000 + 10;

namespace IO {
    const int maxn=14096;
    char buf[maxn], t[50];
    int bn=maxn, bi=maxn;
    int read(char* s) {
        while (bn) {
            for (; bi<bn && buf[bi]<=' '; bi++);
            if (bi<bn) break;
            bn=fread(buf, 1, maxn, stdin);
            bi=0;
        }
        int sn=0;
        while (bn) {
            for (; bi<bn && buf[bi]>' '; bi++) s[sn++]=buf[bi];
            if (bi<bn) break;
            bn=fread(buf, 1, maxn, stdin);
            bi=0;
        }
        s[sn]=0;
        return sn;
    }
    bool read(int& x) {
        if (!read(t)) return 0;
        x=atoi(t);
        return 1;
    }
}

struct node{
    string s;
    int v;
    node(string s, int v):s(s), v(v){}
};

unordered_map <string, list<node>::iterator> mp;
list <node> lst;
char str[50];

void solve(){
    int T;
    IO::read(T);
    while(T--){
        mp.clear(); lst.clear();
        int q, m;
        IO::read(q); IO::read(m);
        while(q--){
            int op, v;
            string s;
            IO::read(op); IO::read(str); IO::read(v);
            s = string(str);
            if(op == 0){
                if(mp.find(s)!=mp.end()){
                    auto it = mp[s];
                    v = it->v;
                    lst.erase(it);
                }
                lst.eb(node(s, v));
                mp[s] = prev(lst.end());
                printf("%d\n", v);
                if(lst.size() > m){
                    mp.erase((lst.begin())->s);
                    lst.pop_front();
                }
            }
            else{
                if(mp.find(s)==mp.end()) puts("Invalid");
                else{
                    auto it = mp[s];
                    if(v==-1){
                        if(it==lst.begin()) puts("Invalid");
                        else{
                            it = prev(it);
                            printf("%d\n", it->v);
                        }
                    }
                    else if(v==1){
                        if(next(it)==lst.end()) puts("Invalid");
                        else{
                            it = next(it);
                            printf("%d\n", it->v);
                        }
                    }
                    else printf("%d\n", it->v);
                }
            }
        }
    }
}

int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
    //freopen("ans.txt","w",stdout);
#endif
    //std::ios::sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);

    solve();  return 0;
}