Sofdor Ali Is in Love

Labib666 DRMCSC Programming Contes...
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,

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

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.

Submit

Login to submit.

Statistics

83% Solution Ratio
WildVegemiteEarliest, Feb '16
Yasir_ArafatFastest, 0.0s
Labib666Lightest, 1.8 MB
rafy13Shortest, 359B
Toph uses cookies. By continuing you agree to our Cookie Policy.