Description

Given $k$ and $k$ integers $n_1, n_2, \cdots, n_k$, there are $k$ piles of matchsticks, where the $i$-th pile contains $n_i$ sticks. You will then play a matchstick-taking game against the computer. The rules are as follows: on each turn, you may take any positive number of matchsticks from exactly one pile, possibly taking the entire pile, but you may not take from multiple piles in a single move, and you may not pass.

Whoever takes the last matchstick wins.

For example: $k = 2$, $n_1 = n_2 = 2$. Let A denote you, and P denote the computer. If A moves first:

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

If A moves second:

• 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$, and A moves second:

• P: $(1, 2, 3) \rightarrow (0, 2, 3)$.
• A: $(0, 2, 3) \rightarrow (0, 2, 2)$.
• A has reduced the game to the $(2, 2)$ case; no matter how P moves, A will surely win.

Write a program that, given the initial state, determines whether the first player has a forced win or a forced loss. If the first player has a forced win, output how to make the first move. If the first player has a forced 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 the first player has a forced win, output two integers $a, b$ on the first line, meaning that on the first move you take $a$ matchsticks from pile $b$. The second line should be the state after the first move.

If there are multiple valid answers, output the lexicographically smallest answer by the pair $\langle b, a \rangle$ (that is, with the smallest $b$, and under that, the smallest $a$).

If the first player has a forced loss, output lose.

3
3 6 9

4 3
3 6 5

4
15 22 19 10

lose

Hint

Constraints

For all testdata, $k \le 500000$, $n_i \le 10^9$.

Translated by ChatGPT 5