Mislove 有一个包含 $$$n$$$ 正整数的数组 $$$a_1$$$、$$$a_2$$$、$$$\cdots$$$、$$$a_n$$$,但他已经丢失了。他只记得以下事实:
- 数组中不同数字的个数不小于$$$l$$$且不大于$$$r$$$;
- 对于每个数组的元素 $$$a_i$$$,$$$a_i = 1$$$ 或 $$$a_i$$$ 是偶数,并且数组中有一个数字 $$$\dfrac{a_i}{2}$$$。
例如,如果 $$$n=5$$$、$$$l=2$$$、$$$r=3$$$ 则数组可以是 $$$[1,2,2,4,4]$$$ 或 $$$[1,1,1,1,2]$$$;但它不可能是 $$$[1,2,2,4,8]$$$ 因为这个数组包含 $$$4$$$ 不同的数字;它不可能是 $$$[1,2,2,3,3]$$$,因为 $$$3$$$ 是奇数并且不等于 $$$1$$$;它不可能是 $$$[1,1,2,2,16]$$$,因为数组中有一个数字 $$$16$$$,但没有数字 $$$\frac{16}{2} = 8$$$。
根据这些事实,他要求你计算数组中所有元素的最小和最大可能和。
输入
唯一的输入行包含三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \leq n \leq 1\,000$$$, $$$1 \leq l \leq r \leq \min(n, 20)$$$) - 数组的大小、数组中不同元素的最小数量和最大数量。
输出
输出两个数字——数组中所有元素的最小和最大可能总和。
示例
输入 #1
4 2 2
输出 #1
5 7
输入 #2
5 1 5
输出 #2
5 31
注意
在第一个示例中,数组可以是以下之一:$$$[1,1,1,2]$$$、$$$[1,1,2,2]$$$ 或 $$$[1,2,2,2]$$$。在第一种情况下达到最小总和,在最后一种情况下达到最大总和。
在第二个示例中,在数组 $$$[1,1,1,1,1]$$$ 处达到最小和,在数组 $$$[1,2,4,8,16]$$$ 处达到最大和。