E - For Fun

Time limit: 8 s
Memory limit: 64 MiB
Languages: C, C++, Java, Pascal, ... (details)

Fito ha escrito el siguiente código:

string fun(char S[], int Q, int A[], int B[]) {
    for (int i = 0; i < Q; i++)
        sort(S + A[i], S + B[i]);
    return (
string)S;
}

Fito quiere saber lo que retorna su función. La función $\text{sort}(S + A[i], S + B[i])$ ordena los elementos desde $A[i]$ hasta $B[i] – 1$ inclusive.

Input

Línea 1: $S$  $(2 \leq |S| \leq 10^5)$, $S$ contiene solo caracteres del alfabeto inglés y en minúscula $(\texttt{a}, \texttt{b}, ..., \texttt{z})$.
Línea 2: $Q$ $(0 \leq Q \leq 10^5)$.
Línea 3 ... Q + 2Dos enteros $A_i$ y $B_i$ $(0 \leq A[i] \lt B[i] \leq |S|)$.

Output

La salida contiene $\text{fun}(S, Q, A, B)$.

Sample test(s)

Input
abcbdbabbdnfbgai 5 15 16 0 4 4 7 11 14 5 9
Output
abbcabbbddnbfgai