Against all the odds, Sofdor Ali has fallen in love. He wishes to gift the girl the sweetest of substrings from a given string.
The initial string S has some special properties. The length of this string is M. The letters used to create this string are from a special new language Sofdor Ali invented that has L letters in its alphabet. Also, the M letters used to compose the string are distinct.
Now Sofdor Ali concatenates N instances of the initial string to get a new string T. He is running some experiments on T to find the sweetest substring. He needs your help to solve a small problem. Given an integer K, what is the length of the K-th suffix in the lexicographically sorted list of suffixes of T? He has Q such queries. You are so happy for him that you have agreed to help!
Notice that,
A suffix of a string A = a1a2...an is a string B = aiai+1...an-1an such that 1<=i<=n.
A prefix of a string A = a1a2...an is a string B = a1a2...ai-1ai such that 1<=i<=n.
A string A is lexicographically smaller than another string B if, either A is a prefix of B and |A| != |B|, or for some integer i (1<=i<=|A|), Aj=Bj for all j < i and Ai < Bi. Here, |A| is the length of the string A.
For example, Let S="abc" and N=3. So the new string is T="abcabcabc". If K=1, your answer should be 3 because "abc" is the lexicographically smallest suffix of T. If K=5, the answer will be 5. (Why?)
The first line of the input will contain four integers M, N, L, Q - length of the string S, number of times S will be concatenated to form T, number of letters in the alphabet of the special language and number of Sofdor Ali's queries respectively.
The next line will contain M space separated integers. ith of these integers, Ai, represents the position of the letter Si in the alphabet.
The following Q lines will contain one integer each: K ( explained in the statement above ).
1 <= M <= 105, M <= L
1 <= N <= 105
1 <= L <= 109
1 <= Q <= 105
1 <= Ai <= L, all the Ai will be distinct
1 <= K <= N.M
For 20% of the cases, N.M will not exceed 103.
For 40% of the cases, N.M will not exceed 106.
For each query, print one integer in a separate line: the length of the K-th suffix in the lexicographically sorted list of suffixes of T. ( See the sample to get a better idea about input/output )
Input | Output |
---|---|
3 3 26 2 1 2 3 1 5 | 3 5 |
The sample represents the example discussed in the statement.