Problem Description

Given an integer \( k \) and \( k \) integers \( n_1, n_2, \cdots, n_k \), representing \( k \) piles of matchsticks where the \( i \)-th pile contains \( n_i \) matchsticks, you will play a game of taking matchsticks against the computer. The rules for taking matchsticks are as follows: each turn, you can take any number of matchsticks from one pile, or take the entire pile, but you cannot take matchsticks from multiple piles or skip your turn.

The winner is the one who takes the last matchstick.

For example: \( k = 2 \), \( n_1 = n_2 = 2 \), where A represents you and P represents the computer. If A decides to take first:

• A: \( (2,2) \rightarrow (1,2) \), taking one from the first pile.
• P: \( (1,2) \rightarrow (1,1) \), taking one from the second pile.
• A: \( (1,1) \rightarrow (1,0) \).
• P: \( (1,0) \rightarrow (0,0) \). P wins.

If A decides to take last:

• P: \( (2,2) \rightarrow (2,0) \).
• A: \( (2,0) \rightarrow (0,0) \). A wins.

Another example: \( k = 3 \), \( n_1 = 1 \), \( n_2 = 2 \), \( n_3 = 3 \), where A decides to take last:

• P: \( (1,2,3) \rightarrow (0,2,3) \).
• A: \( (0,2,3) \rightarrow (0,2,2) \).
• A has reduced the game to the state \( (2,2) \), ensuring a win regardless of P's move.

Write a program that, given the initial state, determines whether taking the first move is a guaranteed win or a guaranteed loss. If it is a guaranteed win, output the first move to take. If it is a guaranteed loss, output lose.

Input Format

The first line contains a positive integer \( k \).

The second line contains \( k \) integers \( n_1, n_2, \cdots, n_k \).

Output Format

If taking the first move is a guaranteed win, output two integers \( a, b \) on the first line, indicating that the first move is to take \( a \) matchsticks from the \( b \)-th pile. The second line should describe the state after the first move. If there are multiple correct answers, output the one with the smallest lexicographical order \( (b, a) \) (i.e., smallest \( b \) and then smallest \( a \)).

If taking the first move is a guaranteed loss, output lose.

Sample Input and Output

Sample Input #1

3
3 6 9

Sample Output #1

4 3
3 6 5

Sample Input #2

4
15 22 19 10

Sample Output #2

lose

Notes

Data Range and Constraints

For all data, \( k \leq 500000 \), \( n_i \leq 10^9 \).

见题面 Input 部分

见题面 Output 部分