Problem E
Island Tour

Iceland by Irena Jackson, CC0 Public Domain

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.

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

4
1 1 1 1
1 1 1 1
10 3 2 1
4 2 5 1

impossible