Sofdor Ali Is in Love

Limits 1s, 512 MB

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,

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?)

Input

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 ).

Constraints:

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.

Output

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 )

Sample

InputOutput
3 3 26 2
1 2 3
1
5
3
5

Explanation

The sample represents the example discussed in the statement.