Problem I: Shuffle 2

Problem

$n$枚のカードからなる束があり、下から$i$番目のカードには$i$が書かれている。この束に対して、以下のように定義されるシャッフルを$q$回行う。

• 束を下から見たとき、奇数番目のカードを上に重ねていって作られる束$x$、偶数番目のカードを上に重ねていって作られる束$y$を考える。その後以下の$2$つのうち、好きな操作を行う。
• 操作 $0$： 束$x$の上に束$y$をのせて$1$つの束にする。
• 操作 $1$： 束$y$の上に束$x$をのせて$1$つの束にする。

例えば、$6$枚のカードからなる束(下から123456)に対して$1$回のシャッフルを行うことを考えたとき、操作$0$を行った場合に得られる束は下から246135、操作$1$を行った場合に得られる束は下から135246である。

$q$回のシャッフルの後、$k$の書かれたカードが束の下から$d$番目にあるようにしたい。
可能であるなら$q$回のシャッフルの操作を順番に出力し、不可能ならば$-1$を出力せよ。

Input

入力は以下の形式で与えられる。

$n$ $q$ $k$ $d$

Constraints

入力は以下の条件を満たす。

• $2 \le n \le 10^{15}$
• $1 \le q \le 10^6$
• $1 \le k,d \le n$
• $n$は偶数

Output

条件を満たすシャッフルが可能なら$q$行にシャッフルの操作を出力せよ。

不可能なら$-1$を出力せよ。

Sample Input 1

4 2 1 1

Sample Output 1

0
0

Sample Input 2

4 2 3 1

Sample Output 2

0
1

Sample Input 3

4 1 1 4

Sample Output 3

-1

Sample Input 4

7834164883628 15 2189823423122 5771212644938

Sample Output 4

0
1
1
1
1
1
0
1
0
1
0
0
0
0
0

Note

Link

 

---