Ecrade 有一个整数 $$$x$$$。有两种操作。
- 将 $$$x$$$ 替换为 $$$\left\lfloor \dfrac{x}{2}\right\rfloor$$$,其中 $$$\left\lfloor \dfrac{x}{2}\right\rfloor$$$ 是最大整数 $$$\le \dfrac{x}{2}$$$。
- 将 $$$x$$$ 替换为 $$$\left\lceil \dfrac{x}{2}\right\rceil$$$,其中 $$$\left\lceil \dfrac{x}{2}\right\rceil$$$ 是最小整数 $$$\ge \dfrac{x}{2}$$$。
Ecrade 将以任意顺序执行 $$$n$$$ 第一次操作和 $$$m$$$ 第二次操作。他想知道 $$$n+m$$$ 运算后 $$$x$$$ 的最小和最大可能值。不过,好像有点困难,所以请帮助他!
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含三个整数 $$$x$$$、$$$n$$$ 和 $$$m$$$ ($$$0 \le x, n, m \le 10^9$$$)。
输出
对于每个测试用例,在一行中打印两个整数,表示 $$$n + m$$$ 操作后 $$$x$$$ 的最小和最大可能值。
示例
输入复制
512 1 212 1 112 0 012 1000000000 1000000000706636307 0 3
输出复制
1 2 3 3 12 12 0 0 88329539 88329539
注意
为简单起见,我们将第一个操作称为 $$$\text{OPER 1}$$$,将第二个操作称为 $$$\text{OPER 2}$$$。
在第一个测试用例中:
- 如果我们执行 $$$12 \xrightarrow{\text{OPER 2}} 6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 1}} 1$$$,我们可以获得最小可能值 $$$1$$$。
- 如果我们执行 $$$12 \xrightarrow{\text{OPER 2}} 6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 2}} 2$$$,我们可以获得最大可能值 $$$2$$$。