The key idea is that there are only $26$ alphabets in the string. Let $\Sigma$ denote the set of alphabets, i.e., $|\Sigma| = 26$. Assume that you have a data structure that for every pair of $L$ and $R$, computes the number of occurrences of any alphabet in $[L,R]$ efficiently. Using those numbers, you can easily check in $O(|\Sigma|)$ time if the substring from $L$ to $R$ forms a palindrome or not; this part is easy I leave the details to you. After finding the palindrome, you need to update the data structure without changing the original string; this part is complex, which I will explain in more detail.
Data Structure: Maintain an Interval tree (or segment tree) for each alphabet. A leaf in the tree corresponds to an interval $[s,t]$, such that the alphabet appears contiguously in the string $S$ from positions $s$ to $t$. For example: Suppose the string $S$ is $baaaedaabbbzz$ and the alphabet is $a$. Then the leaves of the segment tree of alphabet $a$ will be: $[2,4], [7,8]$ since $a$ appears in the string from positions $2$ to $4$, and it also appears in the string from positions $7$ to $8$. Similarly, for $b$, the leaves of its segment tree would be $[1,1], [9,11]$.
The segment trees for all the alphabets can be constructed in $O(|S| \log |S|)$ time. If you are not familiar with segment trees, you will need to study it by yourself.
Query: For a given query $[L,R]$, you can find the number of occurrences of any alphabet between positions $L$ and $R$ using the corresponding segment tree of the alphabet. This takes $O(\log |S|)$ time for each alphabet. Now, you can easily check if the sub-string makes a palindrome or not.
Updating the Data Structure: Now, you do not need to output/print the palindrome; you just need to find the interval in which an alphabet occurs in the palindrome (the lexicographically smallest one). This can be done in $O(|\Sigma|)$ time; it is easy, I leave the details to you. There will be at most two intervals for each alphabet in the palindrome. Update the segment trees of each alphabet by adding these new intervals. Adding these two intervals takes $O(\log |S|)$ time. However, you also need to remove some old intervals that overlap with these new intervals. It also takes $O(\log |S|)$ time: Why? Think in terms of amortized analysis.
Lastly, after performing all the queries, you can reconstruct the final string using the segment trees.
Overall running time is $O((|S|+|\Sigma|) \cdot \log |S|) \approx 10^7$.