Island Tour

문제

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 $nn$ attractions, conveniently numbered from $11$ to $nn$ 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 $ii$ visits the attractions in the order $ii$, $i+1i+1$, $\dots \backslash ldots$, $nn$, $11$, $\dots \backslash ldots$, $i-1i-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.

입력

The input consists of:

• One line with an integer $nn$ ($1\le n\le 4001\; \backslash le\; n\; \backslash le\; 400$), the number of tourist attractions.
• One line with $nn$ integers $d_1,\dots ,d_{n}d\_1,\backslash ldots,d\_n$ ($1\le d_i\le {10}^{6}1\; \backslash le\; d\_i\; \backslash le\; 10^6$ for each $ii$), where $d_{i}d\_i$ is the travel time in minutes from tourist attraction $ii$ to $i+1i+1$ (or to $11$ when $i=ni\; =\; n$).
• For each of Tijmen, Annemarie and Imme:
  • One line with $nn$ integers $t_1,\dots ,t_{n}t\_\{1\},\; \backslash ldots,\; t\_\{n\}$ ($1\le t_i\le {10}^{6}1\; \backslash le\; t\_\{i\}\; \backslash le\; 10^6$ for each $ii$), where $t_{i}t\_i$ is the time in minutes that the given person is going to spend at attraction $ii$.

출력

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.