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 <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

LL mod = 1000000007;

struct hoge{
  public:
  LL a, b, c, d;
  public:
  LL num;

public:
  hoge(LL a, LL b, LL c, LL d,LL num) : a(a), b(b), c(c), d(d),num(num) {}
};

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

  LL n, q, k, d;
  cin >> n >> q >> k >> d;

  k--;
  d--;

  vector<hoge> v;

  v.push_back(hoge(d, d, d, d, 1));

  FOR(i,1,q+1){
    hoge prev = v[i - 1];
    hoge nowhoge = hoge((prev.a * 2) % n, (prev.b * 2) % n, (prev.c * 2) % n, (prev.d * 2+1) % n, (prev.num * 2));

    if(nowhoge.d<nowhoge.a){
      nowhoge.d += n;
    }

    if (nowhoge.num >= n)
    {
      nowhoge.d += n;
      v.push_back(nowhoge);
      break;
    }
    v.push_back(nowhoge);
  }

  hoge last = v[v.size() - 1];

  LL now = k;

  if(last.num>=n){
    for (LL i = 0; i < q - v.size() + 1;++i)
    {
      if(now%2==0){
        cout << 0 << endl;
      }
      else
      {
        cout << 1 << endl;
      }
      now /= 2;
    }
  }

  REP(i,v.size()-1){
    hoge nowhoge = v[v.size() - i-1];
    hoge nexthoge = v[v.size() - i-2];

    bool flag = false;
    REP(j, 2)
    {
      //cout << nowhoge.a << " " << now << " " << nowhoge.d << endl;
      if (nowhoge.a <= now && now <= nowhoge.d)
      {

        bool a = now % 2 == 0;

        now = ((now - nowhoge.a) / 2 + nexthoge.a) % n;

        if(a ^ (now/(n/2)!=0))
        {
          cout << 0 << endl;
        }else{
          cout << 1 << endl;
        }

        flag = true;
        break;
      }
      now += n;
    }
    if(flag)
      continue;

    cout << -1 << endl;
    break;
  }
}

