Gnomes

The country of Dadorlandtiria has \(n\) gnomes, numbered from \(0\) to \(n-1\). One day the evil Dr. Dilyor kidnapped the gnomes, brought them to Dr. Dilyor Evil Inc., and gave them a difficult assignment.

The gnomes stand in a circle. Dr. Dilyor comes and puts a colored hat on each gnome's head. The hat color can be any number from \(0\) to \(k-1\). No gnome can see the color of the hat on their own head, but they can see the hat colors of the other \(n-1\) gnomes.

After everyone has been given a hat, all gnomes simultaneously say an integer between \(0\) and \(h-1\) (they do not all have to say the same number). Afterwards, all gnomes must say the color of their own hat.

Before Dr. Dilyor starts putting on the hats, the gnomes may confer among themselves and devise a plan. Once the hat-placing has started, no planning is possible.

If all gnomes correctly name the color of their hat, Dr. Dilyor releases them. If anyone makes a mistake, all of them remain in prison forever. Help the gnomes.

Implementation details

You should implement the following procedures:

void init(int n, int k, int h)

• \(n\): the total number of gnomes.
• \(k\): the total number of hat colors.
• \(h\): the maximum number a gnome may say.
• The procedure returns nothing.

int say_number(int id, int[] a)

• \(id\): the gnome's number.
• \(a\): an array of length \(n-1\) – the hat colors of all gnomes except gnome \(id\).
• The procedure should return the number that gnome \(id\) should say.

int answer(int id, int[] a, int[] c)

• \(id\): the gnome's number.
• \(a\): an array of length \(n-1\) – the hat colors of all gnomes except gnome \(id\).
• \(c\): an array of length \(n\), where \(c[i]\) is the number said by gnome \(i\).
• The procedure should return the hat color of gnome \(id\).

Each test contains several independent scenarios. If a test has \(t\) scenarios, the above programs are used three times in the following way:

In the first part, the init procedure is called once (\(n\), \(k\) and \(h\) are the same in all scenarios). Then the say_number procedure is called exactly \(t \cdot n\) times (\(n\) times for each scenario, i.e. once per gnome). The returned results are stored in the system.

The second program is restarted. The init procedure is called once. Then the answer procedure is called exactly \(t \cdot n\) times. In each call, an arbitrary scenario may be chosen.

In general, when the code is restarted all variables are cleared – data stored in static or global variables after the first part cannot be used in the second part.

Example

Suppose \(n = 5\), \(k = 12\) and \(h = 100\). Let the gnomes' hat numbers be \(p = [4, 11, 7, 0, 2]\). Then the following sequence of calls occurs:

init(5, 12, 100)

This call tells you the values of \(n\) and \(k\).

Then suppose the following calls are made:

say_number(0, [11, 7, 0, 2])
say_number(1, [4, 7, 0, 2])
say_number(2, [4, 11, 0, 2])
say_number(3, [4, 11, 7, 2])
say_number(4, [4, 11, 7, 0])

Suppose these calls return the numbers \(6\), \(2\), \(7\), \(5\) and \(10\) respectively.

Then the following calls are made (in any order):

answer(0, [11, 7, 0, 2], [6, 2, 7, 5, 10])
answer(1, [4, 7, 0, 2],  [6, 2, 7, 5, 10])
answer(2, [4, 11, 0, 2], [6, 2, 7, 5, 10])
answer(3, [4, 11, 7, 2], [6, 2, 7, 5, 10])
answer(4, [4, 11, 7, 0], [6, 2, 7, 5, 10])

The answer procedures should return \(4\), \(11\), \(7\), \(0\), \(2\) respectively.

Constraints

• \(1 \le t \le 100\)
• \(2 \le n \le 20\)
• \(2 \le k \le 500\,000\)
• \(2 \le h \le 500\,000\)
• \(0 \le p[i] \le k - 1\), for all \(0 \le i \le n - 1\)

Subtasks

1. (5 points) \(n = k = h\), all \(p[i]\) values are distinct.
2. (5 points) \(k = h\).
3. (20 points) \(h = 20\) and for every hat there is another hat of the same color.
4. (70 points) \(n = 20\), \(k = 500\,000\), \(h = 10\).

Additionally, partial score is available in subtask 4. Let \(m\) be the maximum among the numbers returned by the say_number function across all tests. Then you score:

Condition	Points
\(10 \le m\)	\(0\)
\(5 \le m < 10\)	\(15\)
\(2 \le m < 5\)	\(60 - 10 \cdot m\)
\(m < 2\)	\(70\)

Sample grader

Feed the sample grader the input in the following format:

• line 1: \(n \; k \; h \; t\)

For each of the next \(t\) scenarios, provide:

• \(p[0] \; p[1] \; \ldots \; p[n - 1]\)

Then the sample grader prints the answers in the following format:

• line 1: \(m\)

In the next \(t\) lines, the answer for each scenario (\(r\) – the returned array):

• \(r[0] \; r[1] \; \ldots \; r[n - 1]\)

Additionally, the calls made to the init, say_number, answer procedures and their results are written by the grader to log.txt.