无额外样例。

问题描述

有一种计算机程序设计语言，和 C++ 语言非常相似，不同的是，该语言中有一种动态数据类型，命名为 dint。该类型仍然是整型，只是它所占用的空间是动态分配的。当接收到一个特定的整数 BASE 时，dint 类型的变量会分配 BASE 个比特位。

现在有如下程序段：

long long BASE, cnt=0;
cin>>BASE;
dint st,ed,delta;
cin>>st>>ed>>delta;
for(dint i=st; i!=ed; i+=delta)
{
  cnt++;
}
cout<<cnt;

现在输入 BASE, st，ed，delta，问该程序会输出什么？如果没有输出，则你需要输出 -1

多组数据。

输入

若干行，每行表示一组数据，包含 4 个整数：BASE, st, ed, delta

最后一行一个 0 表示输入结束。

输出

每组数据的答案占一行

样例输入

4 1 2 3
3 0 1 2
32 1234567890 987654321 233333333
0

样例输出

11
-1
1867899747

数据范围

100% 的数据：1 ≤ BASE ≤ 32， 0 ≤ st, ed, delta < 2^BASE