Hide

Problem F
Island Tour

/problems/islandtour/file/statement/en/img-0001.jpg
Iceland by Irena Jackson, CC0 Public Domain
Tijmen, Annemarie and Imme are visiting Iceland, a beautiful island country located in the middle of the Atlantic Ocean. To see as much of the island as possible, they would like to visit all of the tourist attractions on the Ring Road; the main road that runs around the circular perimeter of the island. There are $n$ attractions, conveniently numbered from $1$ to $n$ in the order they appear along the road.

Unfortunately, current distancing measures only allow one visitor at a time at any given attraction, so they have decided to split up. Each person will start at a different attraction, visiting the remaining attractions in circular order around the Ring Road, i.e. a person starting their tour at attraction $i$ visits the attractions in the order $i$, $i+1$, $\ldots $, $n$, $1$, $\ldots $, $i-1$.

They know how long it takes to travel from one attraction to the next and how much time each person is going to spend at each attraction. They will each start their tour at the same time and—due to their impatience—will follow their plan without any waiting. Help Tijmen, Annemarie and Imme decide where each person should start their tour such that there never comes a time where more than one person is located at the same attraction. A person may enter an attraction at the same moment another person leaves the attraction, and when a person is finished visiting their last attraction they will immediately leave the attraction and return to their hotel.

Input

The input consists of:

  • One line with an integer $n$ ($1 \le n \le 400$), the number of tourist attractions.

  • One line with $n$ integers $d_1,\ldots ,d_ n$ ($1 \le d_ i \le 10^6$ for each $i$), where $d_ i$ is the travel time in minutes from tourist attraction $i$ to $i+1$ (or to $1$ when $i = n$).

  • For each of Tijmen, Annemarie and Imme:

    • One line with $n$ integers $t_{1}, \ldots , t_{n}$ ($1 \le t_{i} \le 10^6$ for each $i$), where $t_ i$ is the time in minutes that the given person is going to spend at attraction $i$.

Output

If there is a valid assignment, output one line with three integers, the starting attraction for each person. Otherwise, output “impossible”. If there are multiple valid solutions, you may output any one of them.

Sample Input 1 Sample Output 1
6
1 1 1 1 1 1
2 1 3 2 3 1
8 7 4 9 7 2
7 6 2 9 2 1
1 5 6
Sample Input 2 Sample Output 2
4
1 1 1 1
1 1 1 1
10 3 2 1
4 2 5 1
impossible

Please log in to submit a solution to this problem

Log in