/*
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;:,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,r@S2:,,,:s&5,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:r9@S2s;;s9@&:,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:::::;2@SSSi23HX2;,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:siSisi3@5SS555225;:,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;@@@iSh@55555S5529:,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:r5@5Si5iSS555S52;:,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::i@&SS55S252S553;,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::s@@S5SSi55522S5r,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:r5BX252A3@@5SS52;:,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;s5XS:,,,,,,,,,,,,,,,,,,,,,:r3hS255is5&@52552;,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;SXsrrrr:,,,,,,,,::,,,,,,,,,,:r92SiSSSssX@2SSSS9:,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;5sr;2@@@;,,,,,::si2h;:,,,,,,,:rX&5S5S525XH@iSSiir::,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:i5r;;Xsr;;::::;sXXrssih:::::::::s@Xi5isiS2iSsiiSiSrrsi;,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;5s;;rXisssssss5Grrrrrrsirrriiis;rr@@Sissssi3@SsSii95h@ii,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;2s;r;s23Gsr;;r9;;ii;rrr93G&issis9sri5@@@@rr3H@iiiiiiXSi5:,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;5X;;srM2r;rr;;:r@H@;rsss@rssrsissiisrsSh@iii5@&siSiiSi53:,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;sS3Brr;;r;r@@s;;;;rGHS;rsrrsX@@Xssrr3GG92&@issri@@SssssiH:,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:rS9r;;rrr;;;i252&2;;;;SG@;r;rs3SS2&@rsirrrs2#9rsr;;;s@@#@@;:,,,,,
,,,,,,,,,,,::;rrr;:,,,,,,,,,,,,,,,,,,,,,,,,:sXr;r;S@S;r;;5irrSGirr;;hHs;rrr2iss2BSrrssirr@rsi;:::::::::,,,,,,,
,,,,,,,,::r535SiiS2i:,,,,,,,,,,,,,,,,,,,,,:rXr;;;@5XGSr;;rir;r2@;;;;iG@;;rr;2ii2HXrrS@rrr;rrr::,,,,,,,,,,,,,,,
,,,,,,,:r55S25iiiSSiM;:,,,,,,,::;;;;::,,,:;S9rrr2SsiX@;;;rXr;rShi:::rXAs;;;;r3Xh#ir;52@9;sis::,,,,,,,,,,,,,,,,
,,,,,:;i3225@@9&GS55i@:,,,,,:;i29Sssi5;::;sXs;r;&srrihr:;;;irri9@;::rSX@;r;;rrS2r;;Xr;;rrr::,,,,,,,,,,,,,,,,,,
,,,,:;S5522@5ii2A2iSS@;:,,:;S3srrsrri5Xsri2&rrrr5s;;r2@:;;:Xss5GS;:;5ss2@;;;;;;r;;&;::::,,,,,,,,,,,,,,,,,,,,,,
,,,,;i2225@5r;rS35SS@s::::r2Sssss&@@@5iXG&5;rrr;;5r;;SG;;:;;3X&#::::s;;;i@s;r;r;3r;:,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,:s32X5X@s;:::r@@@;::::r2SssrS@hBsrrrsr;;5@;;;;iSrsSh9;;::;r;::::s;::::;r@@@s;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,;522259@r::,:::::,,,:;S3issr@52hrrrr;r;XGHr;:;;XX59H;:r;;rr;:;Gr::,,,,,,::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,:rhXX2XGM;::,,,,,,,,,:s2iisii5ss5Xssrsr;r33M;;::r;Xi;;::;;;95ir;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,:s3XXX29@;:,,,,,,,,,,:sGsisr5Sr;;rs2Gsrrr@i5@;;rr;;::i@;;;:sr;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,;iXX3X23@r:,,,,,,,,,,;s9isssS5r:::;r5Arr;AsrsXis;;:;#2Gi:::;;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,:i333X2X@r::,,,,,,,,,:i3sssrrhr;:::rSG;;r@r;:;rs#@Sr;;rArX@;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,:sXX3322Mi;:,,,,,,,,,:s9sssrr25;:::r5&;r;i;::::::::::::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,:s3XXX2X9@r::,,,,,,,,:r2rrrsrr&5srrS95sr2r::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,:r&333XX2@i;::,,,,,,,:;i2rrsrrs3hX3&&rrrs;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,;S3XXXX32@s::,,,,,,,::s3srrrsirsiSs;;r@;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,:shX2XXXXX3r::,,,,,::ri3Bsssisrrrrrri5;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,;SX222225X9ir;::;;;s5hhssissssrsri@r::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,:r&2X2XSiiS@95iii5X&hrsrs@SS@3A@s;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,:r92525iSS5S2BBBXiisss5@r;:::::::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,:;H32255SiiSiSiiisss@r;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,::s925S5iSs5SiirS@r;:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,:;rAXSs5SsiX@s;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,:::;;rr;;;::,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,:,:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
*/

#include <fstream>
#include <vector>
#include <string>
using namespace std;

struct Map {
    string key;
    string value;
    Map *next = NULL;
    Map *previos = NULL;
};

int MY(string s)
{
    int t = 0;
    for (int i = 0; i < s.size(); i++)
    {
        t *= 48;
        t += s[i];
        t %= 1000000;
    }
    return t;
}
int main()
{
    ifstream cin("linkedmap.in");
    ofstream cout("linkedmap.out");
    string s, s1, s2;
    vector <vector<Map>> a(1000000);
    int t;
    bool flag;
    Map *previos = NULL;
    while (cin >> s)
    {
        if (s[0] == 'p'&& s.size() == 3)
        {
            cin >> s1 >> s2;
            t = MY(s1);
            flag = false;

            for (int i = 0; i < a[t].size(); i++)
            {
                if (a[t][i].key == s1)
                {
                    flag = true;
                    a[t][i].value = s2;
                }
            }

            if (flag == false)
            {
                if (a[t].size() == 0)
                    a[t].reserve(100);
                Map x;
                x.key = s1;
                x.value = s2;
                x.next = NULL;
                x.previos = previos;
                a[t].push_back(x);
                if (previos != NULL)
                    previos->next = &a[t][a[t].size() - 1];
                previos = &a[t][a[t].size() - 1];

            }
        }

        if (s[0] == 'd')
        {
            cin >> s1;
            t = MY(s1);
            for (int i = 0; i < a[t].size(); i++)
            {
                if (a[t][i].key == s1)
                {
                    if (a[t][i].next == NULL)
                        previos = a[t][i].previos;
                    else
                        a[t][i].next->previos = a[t][i].previos;
                    if (a[t][i].previos != NULL)
                        a[t][i].previos->next = a[t][i].next;
                    a[t][i].value = "";
                    a[t][i].next = NULL;
                    a[t][i].previos = NULL;
                    a[t][i].key = "";
                    break;
                }
            }

        }

        if (s[0] == 'g')
        {
            cin >> s1;
            t = MY(s1);
            flag = false;
            for (int i = 0; i < a[t].size(); i++)
            {
                if (s1 == a[t][i].key)
                {
                    cout << a[t][i].value << endl;
                    flag = true;
                }
            }
            if (flag == false) cout << "none\n";
        }

        if (s[0] == 'p'&&s.size() == 4)
        {
            cin >> s1;
            t = MY(s1);
            flag = false;
            for (int i = 0; i < a[t].size(); i++)
            {
                if (s1 == a[t][i].key)
                {
                    if (a[t][i].previos != NULL) {
                        cout << a[t][i].previos->value << endl;
                        flag = true;
                    }
                }
            }
            if (flag == false) cout << "none\n";
        }

        if (s[0] == 'n')
        {
            cin >> s1;
            t = MY(s1);
            flag = false;
            for (int i = 0; i < a[t].size(); i++)
            {
                if (s1 == a[t][i].key)
                {
                    if (a[t][i].next != NULL) {
                        cout << a[t][i].next->value << endl;
                        flag = true;
                    }
                }
            }
            if (flag == false) cout << "none\n";
        }
    }
    return 0;
}