## DMOPC '17 Contest 5 P6 - Bridges

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem type

You are the leader of an island nation. Your nation consists of islands conveniently labelled . Each island has inhabitants. Currently, the only way of travelling between any two islands is by sea. You have created plans to build bridges labelled to connect your nation. Specifically, bridge will connect islands and for all . Now all that's left is to build these bridges and the people of your nation will rejoice!

The bridges will be built one at a time. Once each bridge is built, an opening ceremony will be held for that bridge. The bridge will be allowed for public use once the opening ceremony ends. At the opening ceremony for bridge , all inhabitants who can currently reach island by land (including already-built bridges) will gather on one side of the bridge and all inhabitants who can currently reach island by land (including already-built bridges) will gather on the other. This ceremony will generate a unity value which is the product of the number of inhabitants on each side.

This process doesn't seem very interesting, so you decide to play a game with one of your advisors to make things more fun. Your advisor has chosen an order to build the bridges. They have determined the unity values which will result from this order. Your task is to find an order to build the bridges which obtains the same array of unity values.

However, your advisor believes that simply giving you their array of unity values will make it too easy. Instead, you are allowed to ask them up to questions. You will give your advisor an order to build the bridges - a permutation of . Say that is the unity value of bridge from the advisor's construction order and is the unity value of bridge from your construction order. Your advisor will only tell you . Note that and are not the unity values of the bridge in the construction order. They are the unity values of bridge , once it has been constructed.

#### Input Specification

The first line will contain two space-separated integers and .
The next line will contain space-separated integers. The of these will be , the number of inhabitants on island .

#### Interaction

This is an interactive problem. After reading the initial two lines of input, your program can make queries.
Each query must be a single line containing space-separated integers. These integers must be a permutation of indicating the order which the bridges should be built. The first integer will indicate the index of the first bridge built, and so on.
After printing and flushing, a new line with a single integer will appear as input. It will be the value as described in the problem statement.
You cannot make more than queries. Also, you do not need to use all queries.

Your program will be deemed correct if the value is ever for your queries. The judge will halt interaction once it has printed .

Note: To flush, you can use fflush(stdout); in C++, or System.out.flush(); in Java, or import sys; sys.stdout.flush() in Python 2/3. For other languages, search in its documentation.

#### Sample Interaction

>>> denotes your output. You should not print this out in your actual program.

5 10
1 2 3 2 1
>>> 1 2 3 4
12
>>> 1 2 4 3
24
>>> 1 3 2 4
0

#### Explanation for Sample

The advisor's order is 3 1 2 4. Then .
The first query gives the following unity values: .
The second query gives the following unity values: .
The third query gives the following unity values: .