#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  printf("%d\n", n >= 31 ? m : m % (1 << n));
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> p(n), deg(n);
  for (int i = 1; i < n; i++) {
    cin >> p[i];
    p[i]--;
    deg[p[i]]++;
  }
  vector<int> sons_leaves(n);
  for (int i = 0; i < n; i++) {
    if (deg[i] == 0) {
      sons_leaves[p[i]]++;
    }
  }
  for (int i = 0; i < n; i++) {
    if (deg[i] > 0 && sons_leaves[i] < 3) {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
  return 0;
}

n = int(input())
p = [int(input()) - 1 for _ in range(n - 1)]
leafs = list(filter(lambda x: not x in p, range(n)))
lp = [x for i, x in enumerate(p) if i + 1 in leafs]
x = min(lp.count(k) for k in p)
print("Yes" if x >= 3 else "No")

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, L;
  scanf("%d %d", &n, &L);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &c[i]);
  }
  for (int i = 0; i < n - 1; i++) {
    c[i + 1] = min(c[i + 1], 2 * c[i]);
  }
  long long ans = (long long) 4e18;
  long long sum = 0;
  for (int i = n - 1; i >= 0; i--) {
    int need = L / (1 << i);
    sum += (long long) need * c[i];
    L -= need << i;
    ans = min(ans, sum + (L > 0) * c[i]);
  }
  cout << ans << endl;
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, T;
  scanf("%d %d", &n, &T);
  vector<int> a(n), t(n);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a[i], &t[i]);
  }
  vector<int> res;
  int low = 0, high = n;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    vector< pair<int,int> > e;
    for (int i = 0; i < n; i++) {
      if (a[i] >= mid) {
        e.emplace_back(t[i], i);
      }
    }
    sort(e.begin(), e.end());
    bool ok = false;
    if ((int) e.size() >= mid) {
      int sum = 0;
      for (int i = 0; i < mid; i++) {
        sum += e[i].first;
      }
      if (sum <= T) {
        ok = true;
        res.resize(mid);
        for (int i = 0; i < mid; i++) {
          res[i] = e[i].second;
        }
      }
    }
    if (ok) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  int sz = (int) res.size();
  printf("%d\n%d\n", sz, sz);
  for (int i = 0; i < sz; i++) {
    if (i > 0) {
      putchar(' ');
    }
    printf("%d", res[i] + 1);
  }
  printf("\n");
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, T;
  scanf("%d %d", &n, &T);
  vector< vector< pair<int, int> > > at(n + 1);
  for (int i = 0; i < n; i++) {
    int foo, bar;
    scanf("%d %d", &foo, &bar);
    at[foo].emplace_back(bar, i);
  }
  vector<int> res;
  set< pair<int, int> > s;
  int sum = 0;
  for (int k = n; k > 0; k--) {
    for (auto &p : at[k]) {
      sum += p.first;
      s.emplace(p);
    }
    while ((int) s.size() > k) {
      sum -= (--s.end())->first;
      s.erase(--s.end());
    }
    if ((int) s.size() == k && sum <= T) {
      for (auto &p : s) {
        res.push_back(p.second);
      }
      break;
    }
  }
  int sz = (int) res.size();
  printf("%d\n%d\n", sz, sz);
  for (int i = 0; i < sz; i++) {
    if (i > 0) {
      putchar(' ');
    }
    printf("%d", res[i] + 1);
  }
  printf("\n");
  return 0;
}

#include <iostream>
#include <set>
#include <vector>
#include <string>

using namespace std;

bool ls(const string& a, const string& b) {
	if (a.length() == b.length()) return a < b;
	return a.length() < b.length();
}

struct Expression {
	int p, t;
	string e;

	Expression(string _e, int t_, int _p) : e(_e), t(t_), p(_p) {}

	bool operator < (const Expression& ex) const {
		if (ex.e == e) {
			if (t != ex.t) {
				return t < ex.t;
			}
			return p < ex.p;
		}
		return ls(e, ex.e);
	}
};

set<Expression> q;

const int FULL = 0xff;
const vector<int> B = {1, 2, 4, 8, 16, 32, 64, 128};
const int X_TABLE = B[4] + B[5] + B[6] + B[7];
const int Y_TABLE = B[2] + B[3] + B[6] + B[7];
const int Z_TABLE = B[1] + B[3] + B[5] + B[7];

string dp[1 << 8][3];

void add(int pr, const string& s, int mask) {
	if (dp[mask][pr].empty() || ls(s, dp[mask][pr])) {
		dp[mask][pr] = s;
		Expression e(s, mask, pr);
		q.insert(e);
	}
}

int main() {
	add(2, "x", X_TABLE);
	add(2, "y", Y_TABLE);
	add(2, "z", Z_TABLE);
	while (!q.empty()) {
		auto e = *q.begin();
		q.erase(q.begin());

		if (e.p == 2) {
			add(2, "!" + e.e, ~e.t & FULL);
			add(1, e.e, e.t);
		}

		if (e.p == 1) {
			for (int mask = 0; mask < FULL; ++mask) {
				if (!dp[mask][2].empty()) {
					add(1, dp[mask][2] + "&" + e.e, mask & e.t);
					add(1, e.e + "&" + dp[mask][2], mask & e.t);
				}
			}
			add(2, "(" + e.e + ")", e.t);
			add(0, e.e, e.t);
		}

		if (e.p == 0) {
			for (int mask = 0; mask < FULL; ++mask) {
				for (int pr = 1; pr <= 2; ++pr) {
					if (!dp[mask][pr].empty()) {
						add(0, dp[mask][pr] + "|" + e.e, mask | e.t);
						add(0, e.e + "|" + dp[mask][pr], mask | e.t);
					}
				}
			}
			add(2, "(" + e.e + ")", e.t);
		}
	}

	
	int n;
	cin >> n;
	while (n--) {
		string s;
		cin >> s;
		int mask = 0;
		for (int i = 0; i < 8; ++i) {
			if (s[i] == '1') {
				mask |= (1 << i);
			}
		}

		cout << dp[mask][0] << endl;
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

string res[256][3];
bool changed;

void update(string &a, string &b) {
  if (a == "" || (b.length() < a.length() || (b.length() == a.length() && b < a))) {
    changed = true;
    a = b;
  }
}

int main() {
  res[(1 << 4) + (1 << 5) + (1 << 6) + (1 << 7)][0] = "x";
  res[(1 << 2) + (1 << 3) + (1 << 6) + (1 << 7)][0] = "y";
  res[(1 << 1) + (1 << 3) + (1 << 5) + (1 << 7)][0] = "z";
  changed = true;
  while (changed) {
    changed = false;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 3; j++) {
        if (res[i][j] == "") {
          continue;
        }
        { // op == 0
          string s = res[i][j];
          if (j > 0) {
            s = "(" + s + ")";
          }
          s = "!" + s;
          update(res[i ^ 255][0], s);
        }
        for (int ii = 0; ii < 256; ii++) {
          for (int jj = 0; jj < 3; jj++) {
            if (res[ii][jj] == "") {
              continue;
            }
            for (int op = 1; op <= 2; op++) {
              string s = res[i][j];
              if (j > op) {
                s = "(" + s + ")";
              }
              string t = res[ii][jj];
              if (jj > op) {
                t = "(" + t + ")";
              }
              string w = s + (op == 1 ? '&' : '|') + t;
              update(res[op == 1 ? (i & ii) : (i | ii)][op], w);
            }
          }
        }
      }
    }
  }
  int tt;
  cin >> tt;
  while (tt--) {
    string z;
    cin >> z;
    int mask = 0;
    for (int i = 0; i < 8; i++) {
      mask |= (z[i] - '0') << i;
    }
    string best = "";
    for (int j = 0; j < 3; j++) {
      update(best, res[mask][j]);
    }
    cout << best << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

int main() {
  int n, P, Q;
  cin >> n >> P >> Q;
  int p = mul(P, inv(Q));
  vector< vector<int> > p_win(n + 1, vector<int>(n + 1, 0));
  p_win[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      add(p_win[i + 1][j], mul(p_win[i][j], power(p, j)));
      add(p_win[i + 1][j + 1], mul(p_win[i][j], power((1 - p + md) % md, i - j)));
    }
  }
  vector<int> p_strong(n + 1);
  for (int i = 1; i <= n; i++) {
    p_strong[i] = 1;
    for (int j = 1; j < i; j++) {
      sub(p_strong[i], mul(p_strong[j], p_win[i][j]));
    }
  }
  vector<int> res(n + 1);
  res[1] = 0;
  for (int i = 2; i <= n; i++) {
    res[i] = 0;
    for (int j = 1; j < i; j++) {
      int coeff = mul(p_strong[j], p_win[i][j]);
      int games = (res[j] + res[i - j]) % md;
      add(games, j * (j - 1) / 2 + j * (i - j));
      add(res[i], mul(coeff, games));
    }
    add(res[i], mul(i * (i - 1) / 2, p_strong[i]));
    res[i] = mul(res[i], inv((1 - p_strong[i] + md) % md));
  }
  cout << res[n] << endl;
  return 0;
}

def dlog(x, n):
  bigMod = 5 ** n
  ans = [None, 0, 1, 3, 2][x % 5]
  val = 2 ** ans % bigMod
  mod, phi = 5, 4
  phiVal = 2 ** phi % bigMod
  for i in range(2, n + 1):
    nextMod = mod * 5
    while val % nextMod != x % nextMod:
      val = val * phiVal % bigMod
      ans += phi
    phi *= 5
    phiVal = (phiVal *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod)
    mod = nextMod
  return ans

def main():
  inp = input()
  n = len(inp)
  a = int(inp)
  for m in range(n + 1):
    l = a * 10 ** m
    x, mod = l, 2 ** (n + m)
    if x % mod != 0:
      x += mod - x % mod
    if x % 5 == 0:
      x += mod
    if x < l + 10 ** m:
      assert x % mod == 0 and x % 5 != 0
      x = x // mod
      mod = 5 ** (n + m)
      print(n + m + dlog(x % mod, n + m))
      return
  assert False

if __name__ == '__main__':
  cnt = int(input())
  for i in range(cnt):
    main()

#include <bits/stdc++.h>

using namespace std;

inline long long mul(long long a, long long b, long long md) {
  long long res = 0;
  while (b > 0) {
    if (b & 1) {
      res += a; if (res >= md) res -= md;
    }
    a += a; if (a >= md) a -= md;
    b >>= 1;
  }
  return res;
}

inline long long power(long long a, long long b, long long md) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a, md);
    }
    a = mul(a, a, md);
    b >>= 1;
  }
  return res;
}

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    long long a;
    cin >> a;
    int n = (int) to_string(a).length();
    for (int m = 0; ; m++) {
      long long b = (-a) & ((1LL << (n + m)) - 1);
      if ((a + b) % 5 == 0) {
        b += (1LL << (n + m));
      }
      if ((b == 0 && m == 0) || (int) to_string(b).length() <= m) {
        long long c = (a + b) >> (n + m);
        long long t = vector<long long>{-1, 0, 1, 3, 2}[c % 5];
        long long p5 = 5;
        for (int i = 1; i < n + m; i++) {
          while (power(2, t, p5 * 5) != c % (p5 * 5)) {
            t += p5 / 5 * 4;
          }
          p5 *= 5;
        }
        t += n + m;
        cout << t << endl;
        break;
      }
      a *= 10;
    }
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

const int N = 77;

int C[N][N];

typedef vector<int> poly;

poly integrate(poly a) {
  poly b = {0};
  for (int i = 0; i < (int) a.size(); i++) {
    b.push_back(mul(a[i], inv(i + 1)));
  }
  return b;
}

void sub(poly &a, poly b) {
  while (a.size() < b.size()) {
    a.push_back(0);
  }
  for (int i = 0; i < (int) b.size(); i++) {
    sub(a[i], b[i]);
  }
}

poly plug(poly a, int delta) {
  // a(x + delta)
  poly b(a.size(), 0);
  for (int i = 0; i < (int) a.size(); i++) {
    for (int j = 0; j <= i; j++) {
      add(b[j], mul(a[i], mul(C[i][j], power(delta, i - j))));
    }
  }
  return b;
}

int eval(poly a, int x) {
  int res = 0;
  for (int i = (int) a.size() - 1; i >= 0; i--) {
    res = mul(res, x);
    add(res, a[i]);
  }
  return res;
}

const int COEFF = 1000000;

int main() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      C[i][j] = (j == 0 ? 1 : (i == 0 ? 0 : (C[i - 1][j] + C[i - 1][j - 1]) % md));
    }
  }
  int n;
  cin >> n;
  vector<int> x(n), fracs;
  for (int i = 0; i < n; i++) {
    double foo;
    cin >> foo;
    x[i] = (int) (foo * COEFF + 0.5);
    fracs.push_back(x[i] % COEFF);
  }
  fracs.push_back(0);
  sort(fracs.begin(), fracs.end());
  fracs.resize(unique(fracs.begin(), fracs.end()) - fracs.begin());
  int cnt = (int) fracs.size();
  vector<int> point(n * cnt + 1);
  for (int i = 0; i <= n * cnt; i++) {
    point[i] = mul(i / cnt * COEFF + fracs[i % cnt], inv(COEFF));
  }
  vector<int> cut(n);
  for (int i = 0; i < n; i++) {
    cut[i] = (int) (find(point.begin(), point.end(), mul(x[i], inv(COEFF))) - point.begin());
  }
  vector<poly> a(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    a[i] = {i < min(cnt, cut[0]) ? 1 : 0};
  }
  for (int id = 1; id < n; id++) {
    for (int i = 0; i < n * cnt; i++) {
      a[i] = integrate(a[i]);
    }
    for (int i = n * cnt - 1; i >= 0; i--) {
      sub(a[i][0], eval(a[i], point[i]));
      for (int j = i - 1; j >= i - cnt && j >= 0; j--) {
        add(a[i][0], eval(a[j], point[j + 1]));
        if (j > i - cnt) {
          sub(a[i][0], eval(a[j], point[j]));
        } else {
          sub(a[i], plug(a[i - cnt], md - 1));
        }
      }
    }
    for (int i = cut[id]; i < n * cnt; i++) {
      a[i] = {0};
    }
  }
  int ans = 0;
  for (int i = 0; i < n * cnt; i++) {
    poly b = integrate(a[i]);
    add(ans, eval(b, point[i + 1]));
    sub(ans, eval(b, point[i]));
  }
  printf("%d\n", ans);
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  return power(a, md - 2);
}

typedef vector<int> poly;

poly integrate(poly a) {
  poly b = {0};
  for (int i = 0; i < (int) a.size(); i++) {
    b.push_back(mul(a[i], inv(i + 1)));
  }
  return b;
}

void sub(poly &a, poly b) {
  while (a.size() < b.size()) {
    a.push_back(0);
  }
  for (int i = 0; i < (int) b.size(); i++) {
    sub(a[i], b[i]);
  }
}

int eval(poly a, int x) {
  int res = 0;
  for (int i = (int) a.size() - 1; i >= 0; i--) {
    res = mul(res, x);
    add(res, a[i]);
  }
  return res;
}

const int COEFF = 1000000;

int main() {
  int n;
  cin >> n;
  vector<int> x(n), fracs;
  for (int i = 0; i < n; i++) {
    double foo;
    cin >> foo;
    x[i] = (int) (foo * COEFF + 0.5);
    fracs.push_back(x[i] % COEFF);
  }
  fracs.push_back(0);
  sort(fracs.begin(), fracs.end());
  fracs.resize(unique(fracs.begin(), fracs.end()) - fracs.begin());
  int cnt = (int) fracs.size();
  vector<int> point(n * cnt + 1);
  for (int i = 0; i <= n * cnt; i++) {
    point[i] = i / cnt * COEFF + fracs[i % cnt];
  }
  vector<int> cut(n);
  for (int i = 0; i < n; i++) {
    cut[i] = (int) (find(point.begin(), point.end(), x[i]) - point.begin());
  }
  vector<int> sz(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    sz[i] = mul((point[i + 1] - point[i] + md) % md, inv(COEFF));
  }
  vector<poly> a(n * cnt);
  vector<int> sum(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    a[i] = i < min(cnt, cut[0]) ? vector<int>{0, 1} : vector<int>{0};
    sum[i] = a[i].size() == 1 ? 0 : sz[i];
  }
  for (int id = 1; id < n; id++) {
    for (int i = n * cnt - 1; i >= 0; i--) {
      if (i >= cut[id]) {
        a[i] = {0};
        sum[i] = 0;
      } else {
        for (int j = i - 1; j >= i - cnt && j >= 0; j--) {
          add(a[i][0], sum[j]);
        }
        if (i - cnt >= 0) {
          sub(a[i], a[i - cnt]);
        }
        a[i] = integrate(a[i]);
        sum[i] = eval(a[i], sz[i]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n * cnt; i++) {
    add(ans, sum[i]);
  }
  printf("%d\n", ans);
  return 0;
}

n = int(input())
results = []
for i in range(n):
    results.append(list(map(int, input().split())))

for r in results:
    if r[0] != r[1]:
        print("rated")
        exit()

for i in range(n):
    for j in range(i):
        if results[i][0] > results[j][0]:
            print("unrated")
            exit()

print("maybe")

#include <bits/stdc++.h>

using namespace std;

int main() {
  int p, x, y;
  cin >> p >> x >> y;
  for (int s = y; ; s++) {
    if (s % 50 != x % 50) {
      continue;
    }
    bool me = false;
    int i = s / 50 % 475;
    for (int j = 0; j < 25; j++) {
      i = (i * 96 + 42) % 475;
      if (i + 26 == p) {
        me = true;
        break;
      }
    }
    if (me) {
      printf("%d\n", (max(0, s - x) + 50) / 100);
      break;
    }
  }
  return 0;
}

p, x, y = map(int, input().split())

def check(s):
    i = (s // 50) % 475
    for t in range(25):
        i = (i * 96 + 42) % 475
        if 26 + i == p:
            return True
    return False

for up in range(500):
    for down in range(500):
        if x + 100 * up - 50 * down >= y and check(x + 100 * up - 50 * down):
            print(up)
            exit()

assert(False)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

bool check(ll x, ll y, ll p, ll q, ll t) {
  return p * t >= x && q * t - p * t >= y - x;
}

void solve() {
  ll x, y, p, q;
  scanf("%lld%lld%lld%lld", &x, &y, &p, &q);

  ll l = -1;
  ll r = (ll) 1e9;

  if (!check(x, y, p, q, r)) {
    printf("-1\n");
    return;
  }

  while (r - l > 1) {
    ll m = (l + r) / 2;
    if (check(x, y, p, q, m)) {
      r = m;
    } else {
      l = m;
    }
  }

  printf("%lld\n", r * q - y);
}

int main() {
  int t;
  scanf("%d", &t);

  while (t--) {
    solve();
  }

  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int x, y, p, q;
    cin >> x >> y >> p >> q;
    if (p == 0) {
      cout << (x == 0 ? 0 : -1) << endl;
      continue;
    }
    if (p == q) {
      cout << (x == y ? 0 : -1) << endl;
      continue;
    }
    int t1 = (x + p - 1) / p;
    int t2 = ((y - x) + (q - p) - 1) / (q - p);
    cout << (q * 1LL * max(t1, t2) - y) << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 123456;
const int m = 5;
const int k = 6;

int a[N][m];
int score[N];
int cost[m];
int solved[m];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", a[i] + j);
      if (a[i][j] != -1) {
        solved[j]++;
      }
    }
  }
  for (int bots = 0; bots <= ((1 << (k - 1)) - 1) * n; bots++) {
    for (int j = 0; j < m; j++) {
      int total = n + bots;
      int cur = solved[j];
      if (a[0][j] != -1 && a[1][j] != -1 && a[0][j] > a[1][j]) {
        cur += bots;
      }
      cost[j] = 500;
      while (cost[j] < 500 * k && 2 * cur <= total) {
        cur *= 2;
        cost[j] += 500;
      }
    }
    for (int i = 0; i < 2; i++) {
      score[i] = 0;
      for (int j = 0; j < m; j++) {
        if (a[i][j] != -1) {
          score[i] += cost[j] / 250 * (250 - a[i][j]);
        }
      }
    }
    if (score[0] > score[1]) {
      printf("%d\n", bots);
      return 0;
    }
  }
  printf("%d\n", -1);
  return 0;
}

n = int(input())
a = sorted(list(map(int, input().split())))

maxe = max(a)
cnt = []
cur = 1
k = 0
i = 0
while i < n:
    cnt.append(0)
    while i < n and a[i] < cur:
        cnt[2 * k] += 1
        i += 1
    cnt.append(0)
    while i < n and a[i] == cur:
        cnt[2 * k + 1] += 1
        i += 1
    k += 1
    cur *= 2
cnt.append(0)
cnt.append(0)
maxe = len(cnt) - 1

maxk = cnt[1]
was = False
for l in range(maxk):
    cur = 1
    while cnt[cur] > 0:
        cnt[cur] -= 1
        cur += 2
    cnt[cur] -= 1
    cursum = 0
    ok = True
    for t in range(maxe, 0, -1):
        cursum += cnt[t]
        if cursum > 0:
            ok = False
            break
    if ok:
        print(l + 1, end=" ")
        was = True

if not was:
    print(-1)

#include <bits/stdc++.h>

using namespace std;

const int MAX = 66;

int power[MAX + 10];
int between[MAX + 10];
int extra[MAX + 10];
int ende[MAX + 10];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    long long foo;
    cin >> foo;
    int cc = 0;
    bool good = true;
    while (foo > 1) {
      if (foo & 1) {
        good = false;
      }
      cc++;
      foo >>= 1;
    }
    if (good) {
      power[cc]++;
    } else {
      between[cc]++;
    }
  }
  int low = 1, high = power[0] + 1;
  while (low < high) {
    int mid = (low + high) >> 1;
    int cur = mid;
    for (int i = 0; i < MAX; i++) {
      extra[i] = power[i] - cur;
      int new_cur = min(cur, power[i + 1]);
      ende[i] = cur - new_cur;
      cur = new_cur;
    }
    bool fail = false;
    int open = 0;
    for (int i = MAX - 1; i >= 0; i--) {
      open += ende[i];
      open -= between[i];
      open -= extra[i + 1];
      if (open < 0) {
        fail = true;
        break;
      }
    }
    open -= extra[0];
    if (open < 0) {
      fail = true;
    }
    if (fail) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  if (low > power[0]) {
    cout << -1 << endl;
    return 0;
  }
  for (int i = low; i <= power[0]; i++) {
    cout << i << " ";
  }
  cout << endl;
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const long long inf = (long long) 1e18;

const int N = 2010;

int a[N][N];
long long d[N];
bool used[N];

int main() {
  // reading input data
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    a[i][i] = 0;
    for (int j = i + 1; j < n; j++) {
      scanf("%d", a[i] + j);
      a[j][i] = a[i][j];
    }
  }
  // finding minimum edge weight
  int min_edge = a[0][1];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        min_edge = min(min_edge, a[i][j]);
      }
    }
  }
  // subtracting minimum edge weight from all edge weights
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        a[i][j] -= min_edge;
      }
    }
  }
  // initializing distance array
  for (int i = 0; i < n; i++) {
    d[i] = inf;
    for (int j = 0; j < n; j++) {
      if (i != j) {
        d[i] = min(d[i], 2LL * a[i][j]);
      }
    }
    used[i] = false;
  }
  // running Dijkstra
  for (int it = 0; it < n; it++) {
    long long min_d = inf;
    int ver = -1;
    for (int i = 0; i < n; i++) {
      if (!used[i] && d[i] < min_d) {
        min_d = d[i];
        ver = i;
      }
    }
    used[ver] = true;
    for (int i = 0; i < n; i++) {
      d[i] = min(d[i], d[ver] + a[ver][i]);
    }
  }
  // printing result
  for (int i = 0; i < n; i++) {
    cout << (d[i] + (long long) min_edge * (n - 1)) << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

inline int signum(int x) {
  return (x < 0 ? -1 : (x > 0 ? 1 : 0));
}

const int inf = (int) 1e9;

const int N = 500010;

pair <int, int> a[N];
int pos[N];

pair <int, int> mn[4 * N];
int add[4 * N];

void push(int x) {
  add[x + x] += add[x];
  mn[x + x].first += add[x];
  add[x + x + 1] += add[x];
  mn[x + x + 1].first += add[x];
  add[x] = 0;
}

void pull(int x) {
  mn[x] = min(mn[x + x], mn[x + x + 1]);
}

void build(int x, int l, int r) {
  add[x] = 0;
  if (l == r) {
    mn[x] = make_pair(a[l].first, l);
    return;
  }
  int y = (l + r) >> 1;
  build(x + x, l, y);
  build(x + x + 1, y + 1, r);
  pull(x);
}

void modify(int x, int l, int r, int ll, int rr, int v) {
  if (ll <= l && r <= rr) {
    add[x] -= v;
    mn[x].first -= v;
    return;
  }
  push(x);
  int y = (l + r) >> 1;
  if (ll <= y) {
    modify(x + x, l, y, ll, rr, v);
  }
  if (rr > y) {
    modify(x + x + 1, y + 1, r, ll, rr, v);
  }
  pull(x);
}

pair <int, int> find_min(int x, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    return mn[x];
  }
  push(x);
  int y = (l + r) >> 1;
  pair <int, int> res = make_pair(inf, -1);
  if (ll <= y) {
    res = min(res, find_min(x + x, l, y, ll, rr));
  }
  if (rr > y) {
    res = min(res, find_min(x + x + 1, y + 1, r, ll, rr));
  }
  pull(x);
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a, a + n);
  for (int i = 0; i < n; i++) {
    pos[a[i].second] = i;
  }
  build(1, 0, n - 1);
  set <int> minus, zero, plus;
  for (int id = 0; id < n; id++) {
    int i = pos[id];
    auto p = find_min(1, 0, n - 1, i, i);
    int vote = signum(p.first);
    if (vote == 0) {
      zero.insert(i);
    } else {
      if (vote == -1) {
        minus.insert(i);
        modify(1, 0, n - 1, i, n - 1, -1);
        int last_minus = *(--minus.end());
        if (a[last_minus].first == 1 - (int) minus.size()) {
          minus.erase(last_minus);
          modify(1, 0, n - 1, last_minus, n - 1, 1);
          zero.insert(last_minus);
        } else {
          if (!zero.empty()) {
            int first_zero = *(zero.begin());
            zero.erase(first_zero);
            plus.insert(first_zero);
            modify(1, 0, n - 1, first_zero, n - 1, 1);
          }
        }
      } else {
        plus.insert(i);
        modify(1, 0, n - 1, i, n - 1, 1);
        auto q = find_min(1, 0, n - 1, i, n - 1);
        if (q.first == -1) {
          int pos = q.second;
          plus.erase(pos);
          modify(1, 0, n - 1, pos, n - 1, -1);
          zero.insert(pos);
        }
      }
    }
    printf("%d\n", (int) plus.size() - (int) minus.size());
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const long double pi = acos((ld)-1.0);

const int maxn = 1 << 16;

typedef complex<double> comp;

comp oddc[maxn], evenc[maxn], tmp[maxn];
comp w[maxn], invw[maxn];
ll odd[maxn], even[maxn];
int oldodd[maxn], oldeven[maxn];
int btr[maxn];
int n, A, mod;
int st2;
int answer;

inline int bitrev(int x)
{
    return btr[x];
}

void fft(comp *a, int n, comp *w, comp *res)
{
    for (int i = 0; i < n; i++) res[bitrev(i)] = a[i];
    for (int len = 2; len <= n; len *= 2)
    {
        int step = n / len;
        for (int i = 0; i < n; i += len)
        {
            int curw = 0;
            for (int j = 0; j < len / 2; j++)
            {
                comp x = res[i + j];
                comp y = res[i + len / 2 + j] * w[curw];
                res[i + j] = x + y;
                res[i + len / 2 + j] = x - y;
                curw += step;
            }
        }
    }
}

void preparefft(int n)
{
    for (int i = 0; i < n; i++)
    {
        int cur = i;
        for (int j = 0; (1 << j) < n; j++)
        {
            btr[i] = (btr[i] << 1) | (cur & 1);
            cur >>= 1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        w[i] = comp(cos(2 * pi / n * i), sin(2 * pi / n * i));
        invw[i] = w[i];
    }
    reverse(invw + 1, invw + n);
}

void conv(ll *from, comp *to)
{
    for (int i = n + 1; i < st2; i++) tmp[i] = 0;
    for (int i = 0; i <= n; i++) tmp[i] = from[i];
    fft(tmp, st2, w, to);
}

void convback(comp *from, ll *to)
{
    fft(from, st2, invw, tmp);
    for (int i = 0; i < st2; i++) tmp[i] /= st2;
    for (int i = 0; i <= n; i++)
    {
        to[i] = (ll)(tmp[i].real() + 0.5);
        assert(abs(tmp[i].imag()) < 0.1);
    }
}

void addans()
{
    for (int i = 1; i <= n; i += 2) answer = (answer + odd[i]) % mod;
}

void go(int A)
{
    if (A == 1)
    {
        even[0] = 1;
        odd[0] = 0;
        odd[1] = 1;
        addans();
        return;
    }
    go(A / 2);

    for (int i = 0; i <= n; i++) oldodd[i] = odd[i];
    for (int i = 0; i <= n; i++) oldeven[i] = even[i];
    conv(even, evenc);
    conv(odd, oddc);
    for (int i = 0; i < st2; i++)
    {
        if ((A / 2) % 2 == 0)
        {
            tie(oddc[i], evenc[i])  = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
        } else
        {
            tie(evenc[i], oddc[i])  = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
        }
    }
    convback(oddc, odd);
    convback(evenc, even);
    for (int i = n + 1; i <= 2 * n; i++)
    {
        odd[i] = 0;
        even[i] = 0;
    }
    for (int i = 0; i <= n; i++)
    {
        odd[i] = (odd[i] + oldodd[i]) % mod;
        even[i] = (even[i] + oldeven[i]) % mod;
    }
    if (A % 2 == 1)
    {
        for (int i = n; i >= 1; i--)
        {
            odd[i] = (odd[i] + odd[i - 1] + even[i - 1]) % mod;
        }
    }
    addans();
}

int main()
{
    cin >> n >> A >> mod;
    if (A == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    st2 = 0;
    while ((1 << st2) <= n) st2++;
    st2++;
    st2 = 1 << st2;
    preparefft(st2);
    go(A / 2);
    cout << answer << endl;
    return 0;
}