两位玩家正在玩著名的 Nim 游戏。给定 $n$ 堆石子，其中第 $i$ 堆包含 $a_i$ 个石子。两位玩家轮流操作，每次可以从任意一堆中取走任意正整数个石子。游戏的目标是成为最后一个取走石子的人（即无法操作者输）。

显然，在双方都采取最优策略的情况下，游戏的结果是预先确定的。在本题中，你需要回答：如果输的一方试图让游戏尽可能多地进行（即最大化游戏的总步数），而赢的一方试图在不做出任何可能导致自己输掉游戏的步子的前提下，让游戏尽可能快地结束（即最小化游戏的总步数），游戏将会持续多少步。

你还需要输出先手（第一位玩家）在第一步的一种可能操作，该操作能够导致上述结果。

输入格式

第一行包含一个正整数 $n$（$1 \le n \le 10^5$）。

第二行包含 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^{12}$），表示每堆石子的数量。

输出格式

第一行输出一个正整数，表示在双方都采取上述最优策略下，游戏将持续的步数。

第二行输出先手的第一步操作，格式为 $i\ k$，其中 $i$ 是石子堆的索引（从 $1$ 开始），$k$ 是从第 $i$ 堆中取走的石子数量。如果有多种可能的操作都能导致上述最优结果，你可以输出其中任意一种。

样例

输入样例 1

2
1 3

输出样例 1

3
2 2

输入样例 2

2
2 2

输出样例 2

4
1 1