题目描述

有 $k$ 堆糖果，第 $i$ 堆有 $n_i$ 颗糖果。两个孩子轮流从某一堆中取走至少一颗糖果（可以取完整堆），但不能跨堆取。取走最后一颗糖果的孩子获胜。

如果先手有必胜策略，请输出第一次应该如何取；如果先手必败，则输出 lose。

输入格式

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

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

输出格式

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

如果是先取必败，则输出 lose。

样例

3
3 6 9

4 3
3 6 5

4
15 22 19 10

lose

提示

对于全部数据，$k \le 500000$，$n_i \le 10^9$。