题目描述

在白板上写着若干个正整数。两名玩家轮流操作，每次当前玩家选择白板上的一个数 $X$，擦掉它，并写上 $X$ 的一个真因数。真因数必须严格小于 $X$。当白板上所有数都等于 $1$ 时，就再也没有合法操作。

游戏有两种规则：

• 普通规则（normal play）：无法操作的玩家输；
• 反常规则（misère play）：无法操作的玩家赢。

现在白板上已经有 $B$ 个数，所有初始数都位于区间 $[lo,hi]$。在游戏开始前，你必须再向白板上加入恰好一个整数 $X$，其中 $lo\le X\le hi$，允许与已有数字重复。加入之后由 Shawn 先手。双方都会采取最优策略。

请分别计算在普通规则和反常规则下，有多少种不同的 $X$ 可以保证你最终获胜。

输入格式

第一行包含三个整数：

B lo hi

其中：

• $0\le B\le50$；
• $1\le lo\le hi\le10^{12}$；
• $hi-lo\le10^5$。

若 $B>0$，第二行包含 $B$ 个整数，表示白板上原有的数字。每个数字都位于 $[lo,hi]$。若 $B=0$，第二行可以省略。

输出格式

为了与提供的真实测试数据格式保持一致，输出采用原 TopCoder int[] 返回值的序列化形式。

第一行固定输出：

2

第二行输出两个整数：

normal misere

其中 normal 表示普通规则下可使你获胜的 $X$ 的数量，misere 表示反常规则下的数量。

样例 1

输入

0 1 12

输出

2
1 5

样例 2

输入

5 12 12
12 12 12 12 12

输出

2
1 1

样例 3

输入

5 10 30
12 16 29 24 28

输出

2
6 6

样例 4

输入

3 1 12
1 1 1

输出

2
1 5

本题原题来自 TopCoder SRM 845 Div1 Hard。这里已经按照提取出的真实数据格式改写为标准输入输出题。