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

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.

82% Solution Ratio

WildVegemiteEarliest,

moshiur_cse15Fastest, 53086.1s

Labib666Lightest, 1.8 MB

rafy13Shortest, 359B

Login to submit

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