Limits 2s, 256 MB

Bob is the owner of a shop named "Color Maker". He has 256 types of watercolor in his shop. The types are numbered from 0 to 255. Bob stores the watercolors in small boxes. One box contains only one type of watercolor and there can be more than one box containing the same type of watercolor. Bob keeps the boxes on a shelf side by side. As he has a limited supply of watercolors, he sells the boxes of watercolors with a condition applied.

Bob arranges another set of sample boxes containing watercolors and keeps them on another shelf side by side. He does not sell these sample boxes.

After that, Bob numbers the boxes. Let the number of boxes on the first shelf is NN and the number of the sample boxes is MM. Then Bob numbers the boxes on the first shelf from 1 to NN and the sample boxes from 1 to MM.

When Alice wants to buy watercolors in this shop, Bob asks her to choose a box. If she chooses the kk-th box, Bob finds out a position jj in the sample boxes and the number of boxes pp such that:

Bk=SjB_k = S_j, Bk+1=Sj+1B_{k+1} = S_{j+1}, Bk+2=Sj+2B_{k+2} = S_{j+2}, ..., Bk+p1=Sj+p1B_{k+p-1} = S_{j+p-1}, where BiB_i represents the ii-th box on the first shelf, SiS_i represents the ii-th box of the sample boxes and k1k ≥ 1, k+p1Nk+p-1 ≤ N, j1j ≥ 1 and j+p1Mj+p-1 ≤ M. Bob then sells pp boxes to Alice.

Surprisingly, Bob notices that there can be multiple ways and multiple values of pp possible. Alice demands that among the ways, he has to choose the way in which the value of pp is maximized and has to sell pp boxes. Since calculating the maximum possible value of p is tough for Alice, she asks you to calculate this on behalf of her.

Input

The first line of the input contains two integers NN (1N1061 ≤ N ≤ 10^6), MM (1M1031 ≤ M ≤ 10^3) - the number of boxes on the first shelf and the number of the sample boxes.

The second line contains NN space-separated integers. the ii-th integer represents the type of the watercolor ii-th box contains.

The third line contains MM space-separated integers. the ii-th integer represents the type of the watercolor ii-th sample box contains.

The next line contains an integer QQ (1Q1061 ≤ Q ≤ 10^6), the number of the queries. In each of the next QQ lines, there will be an integer kk (1kN1 ≤ k ≤ N), the position of the box Alice chooses.

Other Constraints:

  • 0Types of Watercolor2550 ≤ \text{Types of Watercolor} ≤ 255

Output

For each query, print in this format in a single line (without quotes): "Query x: y", where xx is the number of the query and yy is the maximum possible value of pp described in the statement.

Sample

InputOutput
6 5
14 25 90 14 81 12
14 14 81 12 0
3
5
2
4
Query 1: 2
Query 2: 0
Query 3: 3

In the third Query, Alice chooses the 4th4^{th} box. So, k=4k = 4. To maximize the value of pp, the best way is to select the position 2 in the sample boxes. So, j=2j = 2. Thus, B4=S2B_4 = S_2, B5=S3B_5 = S_3, B6=S4B_6 = S_4. Here, B4=14B_4 = 14, B5=81B_5 = 81, B6=12B_6 = 12 and S2=14S_2 = 14, S3=81S_3 = 81, S4=12S_4 = 12. As 3 boxes are matched in this way, the value of pp is 3 here and its the maximum among other ways. BB represents the boxes on the first shelf, SS represents the sample boxes.


Submit

Login to submit.

Statistics

79% Solution Ratio
tmwilliamlin168Earliest, Jan '20
TurinhstuFastest, 0.2s
mahbubcsejuLightest, 27 MB
borisalShortest, 1501B
Toph uses cookies. By continuing you agree to our Cookie Policy.