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 Ki 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 Ki.
Output:
Print the answers for all queries.
Constraints:
1 ≤ N, Q ≤ 106
0 ≤ Ki < N
Let's take a look at all circular shifts in left direction of string "pussycat":
0: "pussycat"
1: "ussycatp"
2: "ssycatpu"
3: "sycatpus"
4: "ycatpuss"
5: "catpussy"
6: "atpussyc"
7: "tpussyca"
We need exactly i operations to get i-th shift.
And now let's sort them lexicographically:
6: "atpussyc"
5: "catpussy"
0: "pussycat"
2: "ssycatpu"
3: "sycatpus"
7: "tpussyca"
1: "ussycatp"
4: "ycatpuss"
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor