An XOR graph with $N$ vertices is defined as follows.

• The graph has $N$ vertices numbered from $0$ to $N-1$.
• For each vertex $i$, there are directed edges from vertex $i$ to vertex $i \oplus t$ and vertex $(i \oplus t) + 1$.
• However, if the destination vertex exceeds $N-1$, the edge does not exist.

Here, $\oplus$ denotes the bitwise XOR operation.

Given the number of vertices $N$, the starting vertex $x$, the destination vertex $y$, and a non-negative integer $t$, find the minimum number of edges needed to move from vertex $x$ to vertex $y$.

Input

The first line of input contains four space-separated integers $N$, $x$, $y$, and $t$. ($2 \leq N \leq 10^{18}$; $0 \leq x, y < N$; $x \neq y$; $0 \leq t < 2^{20}$)

Output

Print the minimum number of edges needed to move from vertex $x$ to vertex $y$. If no such path exists, print $-1$ instead.

Examples

Input 1

4 2 3 2

Output 1

2

Input 2

10 7 9 6

Output 2

-1

Input 3

165321961421 998244353 5029393147 98207

Output 3

8242633

Note