Pussycat Sonya has a string S of length N. And she's asked Q queries of form: What is the minimal number of circular shifts in left direction of string S she needs to perform to get lexicographically smallest string, if she can do K_i such shifts at most?

Input:
The first line of input contains one integer N - the length of the string S.
The second line contains string S.
The third line contains one integer Q - the number of queries.
Each of the next Q lines contains one integer K_i.

Output:
Print the answers for all queries.

Constraints:
1 ≤ N, Q ≤ 10⁶
0 ≤ K_i < N