一个拥有 $N$ 个顶点的异或图（XOR graph）定义如下。

• 该图包含 $N$ 个顶点，编号为 $0$ 至 $N-1$。
• 对于每个顶点 $i$，存在从顶点 $i$ 指向顶点 $i \oplus t$ 和顶点 $(i \oplus t) + 1$ 的有向边。
• 然而，如果目标顶点的编号超过 $N-1$，则该边不存在。

此处，$\oplus$ 表示按位异或运算。

给定顶点数 $N$、起点顶点 $x$、终点顶点 $y$ 以及一个非负整数 $t$，求从顶点 $x$ 出发到达顶点 $y$ 所需的最少边数。

输入格式

输入的第一行包含四个由空格隔开的整数 $N$，$x$，$y$ 和 $t$。（$2 \leq N \leq 10^{18}$；$0 \leq x, y < N$；$x \neq y$；$0 \leq t < 2^{20}$）

输出格式

输出从顶点 $x$ 移动到顶点 $y$ 所需的最少边数。如果不存在这样的路径，则输出 $-1$。

样例

输入样例 1

4 2 3 2

输出样例 1

2

输入样例 2

10 7 9 6

输出样例 2

-1

输入样例 3

165321961421 998244353 5029393147 98207

输出样例 3

8242633

说明