Statement
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.
