取火柴游戏

题目描述

输入 $k$ 及 $k$ 个整数 $n_1,n_2,\cdots,n_k$,表示有 $k$ 堆火柴棒,第 $i$ 堆火柴棒的根数为 $n_i$;接着便是你和计算机取火柴棒的对弈游戏。取的规则如下:每次可以从一堆中取走若干根火柴,也可以一堆全部取走,但不允许跨堆取,也不允许不取。 谁取走最后一根火柴为胜利者。 例如:$k=2$,$n_1=n_2=2$,A 代表你,P 代表计算机,若决定 A 先取: - A:$(2,2) \rightarrow (1,2)$,即从第一堆中取一根。 - P:$(1,2) \rightarrow (1,1)$,即从第二堆中取一根。 - A:$(1,1) \rightarrow (1,0)$。 - P:$(1,0) \rightarrow (0,0)$。P 胜利。 如果决定 $A$ 后取: - P:$(2,2) \rightarrow (2,0)$。 - A:$(2,0) \rightarrow (0,0)$。A 胜利。 又如 $k=3$,$n_1=1$,$n_2=2$,$n_3=3$,$A$ 决定后取: - P:$(1,2,3) \rightarrow (0,2,3)$。 - A:$(0,2,3) \rightarrow (0,2,2)$。 - A 已将游戏归结为 $(2,2)$ 的情况,不管 P 如何取 A 都必胜。 编一个程序,在给出初始状态之后,判断是先取必胜还是先取必败,如果是先取必胜,请输出第一次该如何取。如果是先取必败,则输出 `lose`。

输入输出格式

输入格式


第一行,一个正整数 $k$。 第二行,$k$ 个整数 $n_1,n_2,\cdots,n_k$。

输出格式


如果是先取必胜,请在第一行输出两个整数 $a,b$,表示第一次从第 $b$ 堆取出 $a$ 个。第二行为第一次取火柴后的状态。如果有多种答案,则输出 $\lang b,a\rang$ 字典序最小的答案( 即 $b$ 最小的前提下,使 $a$ 最小)。 如果是先取必败,则输出 `lose`。

输入输出样例

输入样例 #1

3
3 6 9

输出样例 #1

4 3
3 6 5

输入样例 #2

4
15 22 19 10

输出样例 #2

lose

说明

### 数据范围及约定 对于全部数据,$k \le 500000$,$n_i \le 10^9$。