훈련 프로그램 II

유명 FC온라인 클럽 "ACE"는 곧 있을 eSports 대회 예선을 대비하여 실력 향상을 위해 훈련 프로그램을 운영하고 있다. 클럽에는 $N$ 명의 선수가 있으며, 각 선수는 다양한 실력을 갖추고 있다. 다가올 예선에 대비하여, 선수들은 2인 1조 훈련팀을 구성하려고 한다. 각 선수는 정확히 두 개의 훈련팀에 참여해야 하며, 같은 두 선수로 이루어진 훈련팀이 두 번 등장해서는 안 된다.

실력이 $a$인 선수와 실력이 $b$인 선수 두 명이 훈련팀을 이루면, 해당 팀의 실력 불균형은 $|a-b|$이다. 실력 차이가 큰 팀은 서로 소통하고 전략을 공유하는 데 어려움을 겪을 수 있기 때문에, 모든 팀의 실력 불균형 총합을 최소화하는 것이 훈련 효율을 높이는 데 중요하다.

이 훈련 프로그램은 $Q$ 번 진행되는데, 회차마다 외부에서 초청 선수가 참여하여 진행한다. 선수 $N$ 명의 실력이 주어졌을 때, 초청된 선수의 실력까지 고려하여 훈련팀을 구성하고 모든 팀의 실력 불균형 총합을 최소화하는 프로그램을 작성하라.

입력 형식

첫 줄에 선수의 수를 나타내는 정수 $N$과 훈련 프로그램의 횟수를 나타내는 정수 $Q$가 공백으로 구분되어 주어진다. ($2 \le N \le 100\,000;$ $1 \le Q \le 100\,000$)

그다음 줄에 각 선수의 실력을 나타내는 $N$ 개의 정수가 공백으로 구분되어 주어진다. 이때, 주어지는 실력은 $1$ 이상 $1\,000\,000\,000$ 이하이다.

이어지는 $Q$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 훈련 프로그램에 초청된 선수의 정보를 나타내는 정수 $k$와 $k$ 개의 정수가 공백으로 구분되어 주어진다. 이는 $i$ 번째 훈련 프로그램에서 $k$ 명의 선수가 초청됨을 의미하며, 주어지는 $k$ 개의 정수는 초청된 선수의 실력을 나타낸다. 이때, $k$는 $1$ 이상 $2$ 이하이며, 주어지는 실력은 $1$ 이상 $1\,000\,000\,000$ 이하이다.

출력 형식

$Q$ 개의 줄에 걸쳐 정답을 출력한다. 출력의 $i$ 번째 줄에 $i$ 번째 훈련 프로그램에서 모든 팀의 실력 불균형 총합의 최솟값을 출력한다.

예제 1

6 2
7 7 8 5 4 5
1 9
1 5

6
4

예제 2

8 4
9 8 8 4 6 1 2 2
2 1 9
1 3
1 1
2 8 6

12
10
12
8

예제 설명

입력 예제 1에서, 총 $6$명의 선수가 있으며, 선수의 실력은 각각 $7, 7, 8, 5, 4, 5$이다.

첫 번째 훈련 프로그램에서 실력이 $9$인 선수가 초청된다. 이 경우, 다음과 같이 훈련팀을 구성하면 모든 팀의 실력 불균형 총합이 $6$이 되며, 이보다 실력 불균형의 총합이 더 낮은 경우는 없다.

• 첫 번째 선수와 두 번째 선수가 훈련팀을 이루어 실력 불균형 $0$이 된다.
• 첫 번째 선수와 세 번째 선수가 훈련팀을 이루어 실력 불균형 $1$이 된다.
• 세 번째 선수와 초청 선수가 훈련팀을 이루어 실력 불균형 $1$이 된다.
• 두 번째 선수와 초청 선수가 훈련팀을 이루어 실력 불균형 $2$가 된다.
• 네 번째 선수와 다섯 번째 선수가 훈련팀을 이루어 실력 불균형 $1$이 된다.
• 네 번째 선수와 여섯 번째 선수가 훈련팀을 이루어 실력 불균형 $0$이 된다.
• 다섯 번째 선수와 여섯 번째 선수가 훈련팀을 이루어 실력 불균형 $1$이 된다.

두 번째 훈련 프로그램에서 실력이 $5$인 선수가 초청된다. 이 경우, 다음과 같이 훈련팀을 구성하면 모든 팀의 실력 불균형 총합이 $4$가 되며, 이보다 실력 불균형의 총합이 더 낮은 경우는 없다.

• 첫 번째 선수와 두 번째 선수가 훈련팀을 이루어 실력 불균형 $0$이 된다.
• 첫 번째 선수와 세 번째 선수가 훈련팀을 이루어 실력 불균형 $1$이 된다.
• 두 번째 선수와 세 번째 선수가 훈련팀을 이루어 실력 불균형 $1$이 된다.
• 네 번째 선수와 초청 선수가 훈련팀을 이루어 실력 불균형 $0$이 된다.
• 다섯 번째 선수와 초청 선수가 훈련팀을 이루어 실력 불균형 $1$이 된다.
• 다섯 번째 선수와 여섯 번째 선수가 훈련팀을 이루어 실력 불균형 $1$이 된다.
• 네 번째 선수와 여섯 번째 선수가 훈련팀을 이루어 실력 불균형 $0$이 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설