For killkth : Say you have the suffix tree of the string. Here each node represents a set of substrings. And all the substrings that a node represents occur equal number of times, which is the number of leaves under it in the tree (synonymously, the number of suffixes each substring is a part of). It is worth noting that, all of these substrings occur consecutively in your hidden string. This can be computed for each node.
Now maintain, for each node, the \sum(length of substrings that are lexicographically lesser than the smallest string for that node). This is, basically \sum(length of substrings of already encountered nodes * number of leaves it’s an ancestor of).
Note that, nodes are being traversed in a depth first manner, and one node is encountered before an other if substrings of one are lexicographically lesser than that of the other.
Say you are traversing the nodes in the order P_1, P_2, ..
You have a number X_i(increasing with i), and F_i(frequency of each substring of that node) for each node P_i. X_i tells you the position of the last character corresponding to the largest string in P_{i-1} in the hidden string. So if you have a query K, you can find the node P_i corresponding this query, where X_i is the smallest value > K, do this by a simple binary search.
You have the node. Now you find which substring the (K - X_i)^{th}(-X_i because, X_i characters have already been discovered before this node). Substrings corresponding to a node P_i are of the form S_1, S_2, S_3 .. S_w, where |S_1| = L, |S_2| = L+1, .. |S_w| = L+w-1 = R. Each occurring F_i times. Here you need to find smallest i where F_i * \sum_{j = L}^{L+i-1}j > K - X_i. This calls for another binary search. So you have the substring. You can do some math and get the position of the character in the substring as well. You have the substring and the position of the desired character in the substring.
Suffix Tree - VisuAlgo (try repeating characters for better understanding)