E - A += v Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

整数 N,M と各要素が 1 以上 M 以下である長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

この整数列 A に対して以下の操作を 10^{100} 回行います。

  • 1 以上 M 以下の整数のうち A における出現回数が最も少ないものを v とする。ただし、そのような v が複数存在する場合はその中で値が最小のものとする。そして、A の末尾に v を追加する。

Q 個のクエリが与えられます。 i 番目のクエリでは整数 X_i が与えられるので、操作を 10^{100} 回行った後の A_{X_i} の値を求めてください。

制約

  • 1\le N,M\le 5\times 10^5
  • 1\le A_i \le M
  • 1\le Q\le 2\times 10^5
  • 1\le X_i \le 10^{18}
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \ldots A_N
Q
X_1
X_2
\vdots
X_Q

出力

Q 行出力せよ。

i 行目には、i 番目のクエリに対する答えを出力せよ。

入力例 1

3 3
1 1 2
8
1
2
3
4
5
6
7
8

出力例 1

1
1
2
3
2
3
1
2

はじめ A=(1,1,2) です。各操作で A は以下のように変化します。

  • 1 回目：A に含まれる 1,2,3 の個数はそれぞれ 2,1,0 であるため、v=3 とする。v を A の末尾に追加し、A=(1,1,2,3) となる。
  • 2 回目：A に含まれる 1,2,3 の個数はそれぞれ 2,1,1 であるため、v=2 とする。v を A の末尾に追加し、A=(1,1,2,3,2) となる。
  • 3 回目：A に含まれる 1,2,3 の個数はそれぞれ 2,2,1 であるため、v=3 とする。v を A の末尾に追加し、A=(1,1,2,3,2,3) となる。
  • \vdots

操作を 10^{100} 回行った後の A は A=(1,1,2,3,2,3,1,2,\ldots) となります。

入力例 2

7 30
20 26 3 14 4 4 9
10
31
9
21
23
97
99
30
79
57
3

出力例 2

30
2
18
21
7
9
29
19
27
3

Score : 475 points

Problem Statement

You are given integers N, M and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N where each element is between 1 and M, inclusive.

The following operation is performed 10^{100} times on this integer sequence A:

  • Let v be the integer between 1 and M, inclusive, with the fewest occurrences in A. If there are multiple such v, take the smallest among them. Then, append v to the end of A.

You are given Q queries. The i-th query gives an integer X_i, so find the value of A_{X_i} after performing the operation 10^{100} times.

Constraints

  • 1\le N,M\le 5\times 10^5
  • 1\le A_i \le M
  • 1\le Q\le 2\times 10^5
  • 1\le X_i \le 10^{18}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N
Q
X_1
X_2
\vdots
X_Q

Output

Output Q lines.

The i-th line should contain the answer to the i-th query.

Sample Input 1

3 3
1 1 2
8
1
2
3
4
5
6
7
8

Sample Output 1

1
1
2
3
2
3
1
2

Initially, A=(1,1,2). With each operation, A changes as follows:

  • First operation: The counts of 1, 2, 3 in A are 2, 1, 0 respectively, so v=3. Append v to the end of A, giving A=(1,1,2,3).
  • Second operation: The counts of 1, 2, 3 in A are 2, 1, 1 respectively, so v=2. Append v to the end of A, giving A=(1,1,2,3,2).
  • Third operation: The counts of 1, 2, 3 in A are 2, 2, 1 respectively, so v=3. Append v to the end of A, giving A=(1,1,2,3,2,3).
  • \vdots

After performing the operation 10^{100} times, A becomes A=(1,1,2,3,2,3,1,2,\ldots).

Sample Input 2

7 30
20 26 3 14 4 4 9
10
31
9
21
23
97
99
30
79
57
3

Sample Output 2

30
2
18
21
7
9
29
19
27
3