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;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, s, t;
    int q;
    cin >> n >> q >> s >> t;
    n /= 2; s--; t--;

    using P = pair<ll, ll>;
    VV<P> ok(q + 1);
    ok[q].push_back({t, t + 1});

    for (int ph = q - 1; ph >= 0; ph--) {
        for (auto p: ok[ph + 1]) {
            ll lw = p.first, up = p.second;
            assert(lw <= up);
            if (lw < n && up <= n) {
                ok[ph].push_back({2 * lw, 2 * up});
            } else if (n <= lw && n <= up) {
                ok[ph].push_back({2 * (lw - n), 2 * (up - n)});
            } else {
                ok[ph].push_back({2 * lw, 2 * n});
                ok[ph].push_back({0LL, 2 * (up - n)});
            }
        }
        sort(ok[ph].begin(), ok[ph].end());
        V<P> buf;
        for (auto p: ok[ph]) {
            if (!buf.empty() && p.first <= buf.back().second) {
                buf.back().second = max(buf.back().second, p.second);
                continue;
            }
            buf.push_back(p);
        }
        ok[ph] = buf;

/*        for (auto p: ok[ph]) {
            cout << "(" << p.first << " " << p.second << "), ";
        }
        cout << endl;*/
    }

    auto contain = [&](int ph, ll x) {
        for (auto p: ok[ph]) {
            if (p.first <= x && x < p.second) return true;
        }
        return false;
    };

    if (!contain(0, s)) {
        cout << -1 << endl;
        return 0;
    }

    V<int> ans;
    for (int i = 1; i <= q; i++) {
        int f = s % 2; s /= 2;
        if (contain(i, s)) {
            ans.push_back(f ^ 0);
        } else {
            s += n;
            assert(contain(i, s));
            ans.push_back(f ^ 1);
        }
    }

    for (int d: ans) {
        cout << d << "\n";
    }

    return 0;
}
