Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sofdor Ali Is in Love

By Labib666 · 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.

Discussion

Statistics


82% Solution Ratio

WildVegemiteEarliest, Feb '16

moshiur_cse15Fastest, 53086.1s

Labib666Lightest, 1.8 MB

rafy13Shortest, 359B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.