Problem

There is a bundle of $ n $ cards, with $ i $ written on the $ i $ th card from the bottom. Shuffle this bundle as defined below $ q $ times.


* When looking at the bundle from below, consider a bundle $ x $ made by stacking odd-numbered cards on top, and a bundle $ y $ made by stacking even-numbered cards on top. Then do whatever you like out of the following $ 2 $.
* Operation $ 0 $: Put the bundle $ y $ on the bundle $ x $ to make a bundle of $ 1 $.
* Operation $ 1 $: Put the bundle $ x $ on the bundle $ y $ to make a bundle of $ 1 $.



For example, if you consider shuffling $ 1 $ times for a bundle of $ 6 $ cards (123456 from the bottom), the bundle you get when you perform the operation $ 0 $ is ~~ 246135 ~~ from the bottom. 135246, the bundle obtained by performing the operation $ 1 $ is ~~ 135246 ~~ 246135 from the bottom. (Corrected at 14:52)

After $ q $ shuffle, I want the card with $ k $ to be $ d $ th from the bottom of the bunch.
If possible, print $ q $ of shuffle operations in sequence, and if not, print $ -1 $.

Constraints

The input satisfies the following conditions.

* $ 2 \ le n \ le 10 ^ {15} $
* $ 1 \ le q \ le 10 ^ 6 $
* $ 1 \ le k, d \ le n $
* $ n $ is even

Input

The input is given in the following format.


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


Output

If it is possible to shuffle the conditions, output the shuffle operation on the $ q $ line.

If not possible, output $ -1 $.

Examples

Input

4 2 1 1


Output

0
0


Input

4 2 3 1


Output

0
1


Input

4 1 1 4


Output

-1


Input

7834164883628 15 2189823423122 5771212644938


Output

0
1
1
1
1
1
0
1
0
1
0
0
0
0
0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll under[1000500];
ll over[1000500];
ll n, q, k, d;

void query(int now) {
    ll delta = (over[now+1] - under[now+1] + 1 + n) % n;
    if(delta * 2 >= n || delta == 0) {
        under[now] = 1;
        over[now] = n;
        return;
    }
    ll after = under[now+1];
    if(after > n / 2) after - n / 2;
    ll new_under = ((after-1) * 2 + 1) % n;
    under[now] = new_under;
    over[now] = (new_under + delta * 2 - 1 + n) % n;
    return;
}

bool isin(ll under, ll over, ll val) {
    if(under <= over) {
        if(((under <= val) && (val <= over))) {
            //cout << -1 << endl;
            return true;
        }
    } else {
        if(((val >= under) || (val <= over))) {
            //cout << -1 << endl;
            return true;
        }
    }
    //cerr << "FAILED " << under << " " << over << " " << val << endl;
    return false;
}

ll one(ll now) {
    if(now % 2 == 0) {
        return now / 2;
    }
    return n / 2 + (now + 1) / 2;
}

ll zero(ll now) {
    if(now % 2 == 0) {
        return n / 2 + now / 2;
    }
    return (now + 1) / 2;
}

int main() {
    cin >> n >> q >> k >> d;
    over[q] = d;
    under[q] = d;
    for(int i = q - 1; i >= 0; i--) {
        query(i);
    }
    for(int i = 0; i <= q; i++) {
        //cout << under[i] << " " << over[i] << endl;
    }
    /*
    if(under[0] < over[0]) {
        if(!((under[0] <= k) && (k <= over[0]))) {
            //cout << -1 << endl;
            return 0;
        }
    } else {
        if(!((k >= under[0]) || (k <= over[0]))) {
            //cout << -1 << endl;
            return 0;
        }
    }
    */
    if(!isin(under[0], over[0], k)) {
        cout << -1 << endl;
        return 0;
    }
    vector<int> ans;
    ll now = k;
    for(int i = 1; i <= q; i++) {
        ll NEW = zero(now);
        //cout << i << " NEWNUMBER : " << NEW << endl;
        if(isin(under[i], over[i], NEW)) {
            ans.push_back(0);
            now = NEW;
            //cout << "0 " << now << endl;
            continue;
        }
        NEW = one(now);
        ans.push_back(1);
        now = NEW;
        //cout << "1 " << now << endl;
    }
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
    return 0;
}
