Palindrome Game

Alice and Bob are playing a game. Alice gives Bob a string S. Then, she asks him Q queries. The positions in the string are labelled as 1, 2, 3, ..., |S| (|S| denotes the length of S). Each query is of the form [l, r]. Bob has to form a palindromic string using some of the characters at positions that lie in the range [l, r]. More formally, he can pick characters at position i such that l ≤ i ≤ r