C - Except and Min Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から N の番号がついた N 個のボールが袋に入っています。ボール i には整数 A_i が書かれています。
Q 個のクエリを処理してください。
クエリでは長さ K の数列 B_1, B_2, \dots, B_{K} が与えられるので以下の一連の操作を行ってください。ここで、B_i は全て 1 以上 N 以下で、かつ相異なります。

  • まず、ボール B_1, ボール B_2, \dots, ボール B_K を全て袋から取り出す。
  • そして、現在の袋に入っているボールに書かれた整数の最小値を出力する。(この時、袋は空でないことが制約から保証されている。)
  • その後、取り出した K 個のボールを全て袋に戻す。

制約

  • 6 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq K \leq 5
  • 1 \leq B_1 \lt B_2 \lt \dots \lt B_K \leq N
  • 全てのクエリに対する K の総和は 4 \times 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

クエリは以下の形式で与えられる。

K
B_1 B_2 \dots B_K

出力

Q 行出力せよ。i 行目には i 番目のクエリの答えを出力せよ。

入力例 1

6 6
3 2 5 9 1 2
2
4 5
5
1 2 3 4 6
3
2 5 6
4
1 2 5 6
1
5
3
1 2 3

出力例 1

2
1
3
5
2
1

例えば 1 番目のクエリでは、ボール 4 とボール 5 を袋から取り出します。この時、袋には以下の 4 個のボールが残っています：

  • 3 が書き込まれたボール 1
  • 2 が書き込まれたボール 2
  • 5 が書き込まれたボール 3
  • 2 が書き込まれたボール 6

よってこの時の袋に入っているボールに書かれた整数の最小値は 2 です。

Score : 300 points

Problem Statement

A bag contains N balls numbered 1 to N. Ball i has the integer A_i written on it.
Process Q queries.
For each query, a sequence B_1, B_2, \dots, B_{K} of length K is given, and you should perform the following sequence of operations. Here, all B_i are between 1 and N inclusive and are distinct.

  • First, remove balls B_1, B_2, \dots, B_K from the bag.
  • Then, output the minimum value among the integers written on the balls currently in the bag. (It is guaranteed by the constraints that the bag is not empty at this point.)
  • Afterwards, return all K removed balls to the bag.

Constraints

  • 6 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq K \leq 5
  • 1 \leq B_1 \lt B_2 \lt \dots \lt B_K \leq N
  • The sum of K over all queries is at most 4 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i-th query.

N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format.

K
B_1 B_2 \dots B_K

Output

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

Sample Input 1

6 6
3 2 5 9 1 2
2
4 5
5
1 2 3 4 6
3
2 5 6
4
1 2 5 6
1
5
3
1 2 3

Sample Output 1

2
1
3
5
2
1

For example, in the first query, balls 4 and 5 are removed from the bag. At this point, the following four balls remain in the bag:

  • Ball 1 with 3 written on it
  • Ball 2 with 2 written on it
  • Ball 3 with 5 written on it
  • Ball 6 with 2 written on it

Thus, the minimum value among the integers written on the balls in the bag is 2.