Question

A person has invented a machine that

outputs the most frequently occurring

characters in a string that lie in the

range $L,R.$ The machine accepts a

series of characters and asks the user

to input two numbers, $L$ and $R.$ The

machine outputs the characters for all

the pairs of $L,R$ values the user

provides.

Write an algorithm to help person find

the output for all the inputs they

provide.

Input

The first line of the input consists of a

string $-$ strS$,$ representing the series of

characters that are fed to the machine

initially.

The second line consists of two space$-$

separated integers $-$ numPairand

valPair, representing the number of

pairs provided by the user $(S$ and

number of values in each pair

always$),$ respectively.

The next $P$ lines consist of $N$ space$-$

separated integers $-$ vall and valR,

representing the values of the lower

and upper range for the pairs $L,R,$

respectively.

Output

Print a string consisting of $P$

characters representing the most

frequently occurring characters for all

the pairs of inputs the person

provides. If more than one character

in a particular input has the same

frequency, print the character that is

least in the lexicographic order.