题目描述

输入 $k$ 及 $k$ 个整数 $n_1，n_2，…，n_k$，表示有 $k$ 堆火柴棒，第 $i$ 堆火柴棒的根数为 $n_i$；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。

谁取走最后一根火柴为胜利者。

例如：$k＝2，n_1＝n_2＝2$， $A$ 代表你，$P$ 代表计算机，若决定 $A$ 先取：

A：(2,2)→(1,2) {从一堆中取一根}

P：(1,2)→(1,1) {从另一堆中取一根}

A：(1,1)→(1,0)

P：(1,0)→ (0,0) {P胜利}

如果决定 $A$ 后取：

P：(2,2)→(2,0)

A：(2,0)→ 0,0) {A胜利}

又如 $k＝3，n1=1，n2＝2，n3＝3$，$A$ 决定后取：

P：(1,2,3)→(0,2,3)

A：(0,2,3)→(0,2,2)

$A$ 已将游戏归结为 (2,2) 的情况，不管 $P$ 如何取 $A$ 都必胜。

编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出“lose”。

输入格式

第一行，一个正整数 $k$。

第二行，$k$ 个整数 $n_1，n_2，…，n_k$。

输出格式

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

样例

输入#1

3
3 6 9

输出#1

4 3
3 6 5

解释#1

第一次从 3 堆中取出 4 个出来必胜

输入#2

4
15 22 19 10

输出#2

lose

解释#2

先取必败

数据范围/约定

时间空间限制：1s, 256MB.

$k \leq 500000, n_i \leq 10^9$

题目来源

课课通 P9-6-5