甘蔗原来有多长

难度：T2（本地估计）

【知识点：逆向递推】【知识点：整数除法】【知识点：范围计数】

前置知识：循环、整数除法、最小值与最大值、long long。

题目描述

第 $1$ 天，一根甘蔗的长度为某个正整数 $a$。从第 $2$ 天起，猴子每天把剩余长度变成前一天的一半；有小数时舍去小数部分。例如，长度 $9$ 和 $8$ 经过一次变化，都会变成 $4$。

现在只记得两件事：

• 到第 $n$ 天时，甘蔗的长度恰好为 $x$。
• 第 $1$ 天的长度 $a$ 在 $L$ 到 $R$ 之间，包含两端。

请找出符合这两条记录的初始长度有多少种，以及其中最小的长度。

第 $1$ 天是初始状态，不发生变化，因此到第 $n$ 天一共发生 $n-1$ 次变化。若中途长度变为 $0$，以后仍为 $0$；本题不在长度达到 $1$ 时提前停止。

输入格式

一行四个整数 $n,x,L,R$，用空格分隔。

输出格式

一行两个整数，依次为可能的初始长度数量、最小的初始长度，中间用一个空格分隔。

如果没有符合记录的初始长度，输出 0 -1。

样例输入 1

3 2 7 12

样例输出 1

4 8

样例说明

这 $4$ 个初始长度都符合记录。区间中的 $7$ 最后变为 $1$，$12$ 最后变为 $3$，均不符合。

样例输入 2

3 2 1 7

样例输出 2

0 -1

样例输入 3

1 5 3 8

样例输出 3

1 5

数据范围

$1\le n\le30$，$1\le x\le10^9$，$1\le L\le R\le10^{18}$。

所有答案和推算中需要的整数都能用 long long 保存。长度范围很大，不能逐个尝试 $L$ 到 $R$ 中的所有整数。