P1247 Matchstick Game

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`.

The first line contains a positive integer $k$. The second line contains $k$ integers $n_1, n_2, \cdots, n_k$.

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`.

### Constraints For all testdata, $k \le 500000$, $n_i \le 10^9$. Translated by ChatGPT 5