Notes

For the rankings by score, see here: https://yukicoder.me/problems/no/5004/score

This problem is the Day 1 problem of Advent Calendar Contest 2021.
The difficulty level is one assigned for the Advent Calendar Contest. You can earn points in the contest as long as you produce a valid output.

Since this is a score-based problem, you cannot make another submission for 5 minutes after your last submission.

The rules (as intended by the writer) on discussing this problem during the contest are as follows.

• Discussion and consultation are allowed on matters not directly related to solutions (such as how to run local tests).
• Volunteers may create and publish visualizers, among other things.
• Furthermore, you are allowed to directly discuss your own solution and to share your code.
• However, if someone else improves their solution as a result, the resulting score belongs to the person who submitted the improved code.

Problem Statement

This is an interactive problem.

You are a server engineer for an online game.
Your task is to write a program that assigns appearing players to rooms so that players of as similar skill as possible share a room, and so that this is done as quickly as possible.

First, $2$ integers $T,R$ are given in the following format.

$T$ $R$

$N$ $S_1$ $S_2$ $\dots$ $S_N$

$M$
$U_1$ $V_1$
$U_2$ $V_2$
$\dots$
$U_M$ $V_M$

Scoring

Among the players in a room, let $S_M$ be the skill value of the player with the largest skill value, and $S_m$ be the skill value of the player with the smallest skill value.
Also, define $E$ as follows.
$E=\sum_{i,j}$ ( $y-x$, if $i$ appeared at tick $x$ and $(i,j)$ came to be in the same room at tick $y$ )
Here, $\sum_{i,j}$ denotes the sum over all pairs $(i,j)$ $(i \neq j)$ of distinct players in the same room.
The value of each room is then defined as follows.

• If the room has $1$ person, the value of the room is $0$
• If the room has $2$ people, the value of the room is $\max(1 \times (200-(S_M-S_m)^2) - E,0)$
• If the room has $3$ people, the value of the room is $\max(3 \times (200-(S_M-S_m)^2) - E,0)$
• If the room has $4$ people, the value of the room is $\max(6 \times (200-(S_M-S_m)^2) - E,0)$

Input Generation

• The number of test cases used for scoring is $100$
• $T=3600$ is fixed
• $R=4$ is fixed
• The sum of $N$ is fixed at $5400$
• For all $S_i$, $0 \le S_i \le 100$

Distributed Materials

Get the distributed materials (zip) here.
The same content is also available from GitHub.
You may use these materials in your solutions, and you may redistribute translations of them into other languages.
Notes on local testing:
In this problem, scoring is performed by giving the contents of the input file as is to your code, step by step, through interaction.
Therefore, no interaction with a judge is needed for local testing.
Implement your code so that it receives the appropriate information at the appropriate time, run it to generate an output file, and give that file to the scoring program to get the scoring result.

Sample

6 4
1 5
2 4 7
2 50 4
3 4 4 4
2 0 51
2 100 100

0
2
1 2
2 3
0
4
8 7
7 6
6 5
5 8
0
2
4 10
9 11