switchLetters

#include <bits/stdc++.h>

using namespace std;

ifstream fin("switchletters.in");
ofstream fout("switchletters.out");

const int m = 1 << 17;

string s;
char aint[4*m+5][27];
char alfabet[] = "abcdefghijklmnopqrstuvwxyz";
string ans;

struct queries {
    int st, dr;
    char t, tl;
}quer[m+5];

struct events {
    int t, ind, tip;
}event[2*m+5];

bool comp(events a, events b) {
    if(a.t != b.t) {
        return a.t < b.t;
    } else {
        if(a.tip > b.tip) {
            return true;
        } else {
            return false;
        }
    }
}

void build(int nod, int st, int dr) {
    strcpy(aint[nod], alfabet);
    if(st == dr) {
        return;
    }
    int mid = (st + dr) / 2;
    build(2*nod, st, mid);
    build(2*nod+1, mid+1, dr);
}

void compose(char *a, char *b, char *rez) {
    for(int i = 0; i < 26; i++) {
        rez[i] = b[a[i]-'a'];
    }
}

void sw(int nod, int st, int dr, int pos, char c1, char c2) {
    if(st == dr) {
        strcpy(aint[nod], alfabet);
        aint[nod][c1-'a'] = c2;
        return;
    }
    int mid = (st + dr) / 2;
    if(pos <= mid) {
        sw(2*nod, st, mid, pos, c1, c2);
    } else {
        sw(2*nod+1, mid+1, dr, pos, c1, c2);
    }
    compose(aint[2*nod], aint[2*nod+1], aint[nod]);
}

int main() {
    fin >> s;
    int q; fin >> q;
    build(1, 1, q);
    for(int i = 1; i <= q; i++) {
        fin >> quer[i].st >> quer[i].dr;
        fin >> quer[i].t >> quer[i].tl;
        event[2*i-1].ind = i;
        event[2*i-1].t = quer[i].st;
        event[2*i-1].tip = 1;
        event[2*i].ind = i;
        event[2*i].t = quer[i].dr+1;
        event[2*i+1].tip = -1;
    }
    sort(event+1, event+2*q+1, comp);
    for(int i = 0, j = 1; i < s.size(); i++) {
        while(j <= 2*q && event[j].t <= i) {
            if(event[j].tip == 1) {
                string abc = alfabet;
                abc[quer[event[j].ind].t-'a'] = quer[event[j].ind].tl;
                sw(1, 1, q, event[j].ind, quer[event[j].ind].t, quer[event[j].ind].tl);
            } else {
                sw(1, 1, q, event[j].ind, 'a', 'a');
            }
            j++;
        }
        ans += aint[1][s[i]-'a'];
    }
    fout << ans;
    return 0;
}