TAIDADA

Interview

Time limit1sMemory limit1024 MB

Summary

Pick N distinct integers from 1 to M so that no two of them XOR to K, or report -1 when that is impossible.

Level: Medium4 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

The Monthly Hyangyuhoe continues in 2025 as well.

Construct a sequence $A$ of $N$ distinct integers, each between $1$ and $M$ inclusive, that satisfies the following condition.

$A_i \oplus A_j \neq K$ $(1 \le i < j \le N)$

$\oplus$ is the bitwise XOR operation.

Input

The first line contains the length $N$ of the sequence $A$ , and the positive integers $M$ and $K$ , separated by spaces. $(1 \le N \le 200\,000;$ $1 \le M, K \le 10^9)$

Output

If a sequence $A$ can be constructed, print its $N$ elements separated by spaces on one line. Otherwise, print -1.

If several sequences satisfy the condition, print any of them.

Examples2

Example 1
Input
```
3 5 2
```
Expected output
```
2 3 4
```
Example 2
Input
```
2 1 1
```
Expected output
```
-1
```