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;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)

typedef long long ll;
typedef pair<ll,ll> P;

ll n, q, k ,d;
vector<set<P>> s(61);
void build(ll target) {
	//cout << "dfs " << target << endl;
	s[0].insert(MP(target, target + 1));
	REP(i, 60){
		for(auto it = s[i].begin();it != s[i].end();){
			P p= *it;
			it++;
			while(it != s[i].end() && it -> FI <= p.SE){
				p.SE = max(p.SE, it -> SE);
				it++;
			}
			{
				ll l=p.first,r=min(p.second,n/2)-1;
				if(l <= r)s[i+1].insert(P(2*(l%(n/2)),2*(r%(n/2))+2));
			}
			{
				ll l=max(p.first,n/2),r=min(p.second,n)-1;
				if(l <= r)s[i+1].insert(P(2*(l%(n/2)),2*(r%(n/2))+2));
			}
		}
	}
}

int main(){

	cin >> n >> q >> k >> d;
	d--;k--;
	build(d);
	//cout << "out build" << endl;
	vector<int> ans;

	for(int i = q;i > 0;i--){
		//cout << "k " << k << endl;
		if(i > 60){
			if(k % 2)ans.PB(1);
			else ans.PB(0);
			k /= 2;
		}
		else {
			bool ok = false;
			ll a = (k / 2);
			ll b = (k / 2) + n / 2;
			//cout << "ab " << a << " " << b << endl;
			for(auto it = s[i-1].begin();it != s[i-1].end();it++){
				if(it -> FI <= a && a < it -> SE){
					if(k%2)ans.PB(1);
					else ans.PB(0);
					k = a;
					ok = true;
					break;
				}
				if(it -> FI <= b && b < it -> SE){
					if(k%2)ans.PB(0);
					else ans.PB(1);
					k = b;
					ok = true;
					break;
				}
			}
			if(!ok){
				cout << -1 << endl;
				return 0;
			}
		}
	}

	REP(i,q)cout << ans[i] << endl;


	return 0;
}

