Mars Space Stations Circular Tour

Byteazar has landed on one of the Mars space stations. All of the space stations are located on a circle. Each station provides a certain amount of fuel. Traveling uses fuel: 1 liter of fuel is required to cover 1 meter, i.e. traveling a distance of \(d\) meters costs \(d\) liters of fuel.

When Byteazar arrives at a station, he collects all the fuel available there (his fuel tank has unlimited capacity). However, if at any point his fuel becomes negative before reaching the next station, the journey fails.

Byteazar can choose to travel in either clockwise or anticlockwise direction. He wishes to select a space station for landing such that starting there and traveling in one of the two directions he can visit every station exactly once and return to the starting station without ever running out of fuel.

The fuel consumed to travel between two consecutive stations (in clockwise order) is given by a distance \(d_i\) (in meters) starting from station \(i\) to station \(i+1\) (with station \(n+1\) interpreted as station 1). For anticlockwise travel, the cost from station \(i\) to station \(i-1\) is \(d_{i-1}\) (with station 0 interpreted as station \(n\)).

Your task is to determine the smallest index (1-indexed) of a station from which Byteazar can complete the full circle using either clockwise or anticlockwise direction. If both directions are possible from that station, you may output either. If no such station exists, output -1.

Input Format: The first line contains an integer \(n\) indicating the number of space stations. The second line contains \(n\) integers \(f_1, f_2, \ldots, f_n\), where \(f_i\) is the amount of fuel available at the \(i\)th station. The third line contains \(n\) integers \(d_1, d_2, \ldots, d_n\), where \(d_i\) is the distance from station \(i\) to station \(i+1\) (with station \(n+1\) being station 1).

Output Format: If a valid starting station exists, output two space‐separated items: the station index (1-indexed) and the chosen direction (either clockwise or anticlockwise). If no valid starting point exists, output -1.

inputFormat

The first line contains a single integer \(n\) (the number of space stations).

The second line contains \(n\) space-separated integers \(f_1, f_2, \ldots, f_n\) representing the fuel available at each station.

The third line contains \(n\) space-separated integers \(d_1, d_2, \ldots, d_n\) representing the distance in meters required to travel from station \(i\) to station \(i+1\) (with station \(n+1\) being station 1).

It is guaranteed that \(n \ge 3\).

outputFormat

If a valid starting station exists, output a single line with two space-separated items: the 1-indexed station number and the travel direction (clockwise or anticlockwise). If there is no solution, output a single line containing -1.

sample

3
4 6 7
6 5 3

1 anticlockwise