Enunț

R. a descoperit de curând tastatura DVORAK și s-a decis că poate scrie mult mai rapid și mai corect cod folosind această tastatură decât folosind tastatura QWERTY. Plictisindu-se, R. a creat, pentru a onora tastatura lui preferată, transformarea dvorak, care se realizează prin înlocuirea fiecărei litere dintr-un șir de caractere cu corespondența acesteia dintr-o permutare dată a alfabetului englez. De exemplu, cuvântul informatica poate să devină, printr-o transformare dvorak, cburpmaycja.

H., profitor din fire, a decis să intre pe calculatorul lui R. și să îi fure sursele valoroase de la problemele “rupere” pe care le-a rezolvat.

Dar R. şi-a securizat calculatorul cu o parolă (constând într-o succesiune de litere mici ale alfabetului englez). Din când în când, R. își modifică o parte din parolă efectuând următoarea operație: alege două poziții în parolă Si (capăt stânga) si Di (capăt dreapta) apoi aplică transformarea dvorak asupra secvenței formată din caracterele situate în parolă pe poziții din intervalul [Si, Di]. Această operație este de tipul 1 și este codificată prin: 1 Si Di.

Acum H. are nevoie de ajutorul vostru ca să afle parola şi să furați împreună toate sursele ca sa fiți primii la statistici pe Varena). Din când în când, el vă va da câte un sir de caractere nevid (SIR) și vă va întreba dacă acest șir se regăsește ca subsecvență în parola lui R. Această operație este de tipul 2 și este codificată prin: 2 SIR

Cerința

Cunoscându-se permutarea dată, parola lui R. precum și o succesiune de Q operații de tipul 1 sau 2, găsiți răspunsurile la întrebările toate lui H.

Date de intrare

Pe prima linie a fișierului dvorak.in se va afla numărul natural Q reprezentând numărul de operații din succesiunea dată.

Exemplu

dvorak.in

6
ifynmlbkpduogahqzsjxcervwt
olimpiadadeinformatica
1 1 6
2 info
2 olimpiada
1 8 15
1 9 14
2 olimpiadadeinformaticaecool5

dvorak.out

Da
Nu
Nu

Explicație

După prima operație, parola se transformă în hopgqpadadeinformatica
La a doua operație se răspunde cu Da.
La a treia operație se răspunde cu Nu.
După a patra operație, parola se transformă în hopgqpaninmpalhrmatica.
După a cincea operație, parola se transformă în hopgqpanpagqiohrmatica.
La a șasea operație se răspunde cu Nu.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("dvorak.in");
ofstream cout("dvorak.out");

bool verif(int i , char s[501] , char sir[501])
{
    for(int j = 0 ; j < strlen(s) && sir[i] ; ++j , ++i)
        if(s[j]!=sir[i])
            return 0;
    return 1;
}

bool inclus(char s[501] , char sir[501])
{
    if(strlen(s) > strlen(sir))
        return 0;
    bool ok = false;
    for(int i = 0 ; i <= strlen(sir)-strlen(s) ; ++i)
        if(verif(i , s , sir))
            ok=true;
    return ok;
}

int main()
{
    int q;
    cin >> q;
    char perm[27];
    cin >> perm;
    char sir[501];
    cin >> sir;
    char s[501];
    for(int i = 1 ; i <= q ; ++i)
    {
        int x;
        cin >> x;
        if(x==1)
        {
            int st , dr;
            cin >> st >> dr;
            for(int j = st - 1 ; j < dr ; ++j)
                sir[j] = perm[ sir[j] - 'a' ];
        }
        else
        {
            cin >> s;
            if(inclus(s , sir))
                cout << "Da" << '\n';
            else
                cout << "Nu" << '\n';
        }
    }
    return 0;
}