#include using namespace std; using ll = long long; #define all(a) begin(a), end(a) #define rall(a) rbegin(a), rend(a) #define len(a) (int)((a).size()) /* ! WARNING: MOD must be prime if you use division or .inv(). ! WARNING: 2 * (MOD - 1) must be smaller than INT_MAX * Use .value to get the stored value. */ template int normalize(T value, int mod) { if (value < -mod || value >= 2 * mod) value %= mod; if (value < 0) value += mod; if (value >= mod) value -= mod; return value; } template struct static_modular_int { static_assert(mod - 2 <= std::numeric_limits::max() - mod, "2(mod - 1) <= INT_MAX"); using mint = static_modular_int; int value; static_modular_int() : value(0) {} static_modular_int(const mint &x) : value(x.value) {} template::value>> static_modular_int(T value) : value(normalize(value, mod)) {} static constexpr int get_mod() { return mod; } template mint power(T degree) const { mint prod = 1, a = *this; for (; degree > 0; degree >>= 1, a *= a) if (degree & 1) prod *= a; return prod; } mint inv() const { return power(mod - 2); } mint& operator=(const mint &x) { value = x.value; return *this; } mint& operator+=(const mint &x) { value += x.value; if (value >= mod) value -= mod; return *this; } mint& operator-=(const mint &x) { value -= x.value; if (value < 0) value += mod; return *this; } mint& operator*=(const mint &x) { value = int64_t(value) * x.value % mod; return *this; } mint& operator/=(const mint &x) { return *this *= x.inv(); } friend mint operator+(const mint &x, const mint &y) { return mint(x) += y; } friend mint operator-(const mint &x, const mint &y) { return mint(x) -= y; } friend mint operator*(const mint &x, const mint &y) { return mint(x) *= y; } friend mint operator/(const mint &x, const mint &y) { return mint(x) /= y; } mint& operator++() { ++value; if (value == mod) value = 0; return *this; } mint& operator--() { --value; if (value == -1) value = mod - 1; return *this; } mint operator++(int) { mint prev = *this; value++; if (value == mod) value = 0; return prev; } mint operator--(int) { mint prev = *this; value--; if (value == -1) value = mod - 1; return prev; } mint operator-() const { return mint(0) - *this; } bool operator==(const mint &x) const { return value == x.value; } bool operator!=(const mint &x) const { return value != x.value; } bool operator<(const mint &x) const { return value < x.value; } template explicit operator T() { return value; } friend std::istream& operator>>(std::istream &in, mint &x) { std::string s; in >> s; x = 0; bool neg = s[0] == '-'; for (const auto c : s) if (c != '-') x = x * 10 + (c - '0'); if (neg) x *= -1; return in; } friend std::ostream& operator<<(std::ostream &out, const mint &x) { return out << x.value; } static int primitive_root() { if constexpr (mod == 1'000'000'007) return 5; if constexpr (mod == 998'244'353) return 3; if constexpr (mod == 786433) return 10; static int root = -1; if (root != -1) return root; std::vector primes; int value = mod - 1; for (int i = 2; i * i <= value; i++) if (value % i == 0) { primes.push_back(i); while (value % i == 0) value /= i; } if (value != 1) primes.push_back(value); for (int r = 2;; r++) { bool ok = true; for (auto p : primes) if ((mint(r).power((mod - 1) / p)).value == 1) { ok = false; break; } if (ok) return root = r; } } }; // constexpr int MOD = 1'000'000'007; constexpr int MOD = 998'244'353; using mint = static_modular_int; vector adamar(vector vec) { for (ll bit = 1; bit < len(vec); bit *= 2) { for (int i = 0; i < len(vec); ++i) { if (i & bit) { mint old1 = vec[i], old0 = vec[i - bit]; vec[i] = old0 - old1; vec[i - bit] = old0 + old1; } } } return vec; } vector forward(vector> segs, int m) { struct tup { array p, c; tup() { p = {0, 0, 0, 0}; c = {0, 0, 0, 0}; } }; struct pr { array p, c; pr() { p = {0, 0}; c = {0, 0}; } }; vector vec(1 << m); for (ll bit = 1; bit < len(vec); bit *= 2) { ll mask = (bit * 2 - 1), high = bit; auto push = [&](ll l, ll r, ll ind, tup& p) { if ((l & high) == (r & high)) { p.p[ind] = ((l | (high - 1)) ^ (high - 1)); p.c[ind] = (r - l + 1); return; } ll mid = ((r | (high - 1)) ^ (high - 1)); p.p[ind + 1] = mid; p.c[ind + 1] = r - mid + 1; p.p[ind] = ((l | (high - 1)) ^ (high - 1)); p.c[ind] = mid - l; }; vector tups(len(segs)); for (int i = 0; auto c : segs) { if (c.second - (c.second & mask) == c.first - (c.first & mask)) { push(c.first, c.second, 0, tups[i]); } else { if ((c.first & mask) != 0) push(c.first, (c.first | mask), 0, tups[i]); if (((c.second + 1) & mask) != 0) push((c.second | mask) ^ mask, c.second, 2, tups[i]); } ++i; } vector pairs(len(segs)); for (int i = 0; i < len(segs); ++i) { pairs[i].p[0] = tups[i].p[0]; pairs[i].c[0] = tups[i].c[0] - tups[i].c[1]; pairs[i].p[1] = tups[i].p[2]; pairs[i].c[1] = tups[i].c[2] - tups[i].c[3]; } auto do_calc = [](const vector& pairs, ll bt, ll m) { vector res(1 << m); vector> sum(1 << m, {1, 1}), diff(1 << m, {1, 1}), par(1 << m, {0, 0}); for (auto c : pairs) { sum[c.p[0] ^ c.p[1]][0] *= (c.c[0] + c.c[1]); diff[c.p[0] ^ c.p[1]][0] *= (c.c[0] - c.c[1]); par[c.p[0]][0] += 1; } for (ll bit = 1; bit < len(res); bit *= 2) { for (int i = 0; i < len(res); i += bt) { if (i & bit) { array old_sum1 = sum[i], old_sum0 = sum[i - bit], old_diff1 = diff[i], old_diff0 = diff[i - bit], old_par1 = par[i], old_par0 = par[i - bit]; sum[i][0] = old_sum1[1] * old_sum0[0]; sum[i][1] = old_sum1[0] * old_sum0[1]; sum[i - bit][0] = old_sum1[0] * old_sum0[0]; sum[i - bit][1] = old_sum1[1] * old_sum0[1]; diff[i][0] = old_diff1[1] * old_diff0[0]; diff[i][1] = old_diff1[0] * old_diff0[1]; diff[i - bit][0] = old_diff1[0] * old_diff0[0]; diff[i - bit][1] = old_diff1[1] * old_diff0[1]; par[i][0] = old_par1[1] + old_par0[0]; par[i][1] = old_par1[0] + old_par0[1]; par[i - bit][0] = old_par1[0] + old_par0[0]; par[i - bit][1] = old_par1[1] + old_par0[1]; } } } for (int i = 0; i < len(res); i += bt) { res[i] = sum[i][0] * diff[i][1]; if (par[i][1].value % 2) res[i] *= mint(-1); } return res; }; vector res = do_calc(pairs, bit, m); for (int i = 0; i < len(vec); i += bit) { vec[i] = res[i]; } } vec[0] = 1; for (auto c : segs) vec[0] *= (c.second - c.first + 1); return vec; } void solve() { int n, m; cin >> n >> m; swap(n, m); vector> segs(n); for (auto &c : segs) cin >> c.first >> c.second; vector to = forward(segs, m); vector res = adamar(to); for (auto& c : res) c /= len(res); // for (auto c : res) cerr << c << " "; // cerr << endl; ll ans = 0; for (int i = 0; auto c : res) { cout << c << "\n"; ans ^= ll(mint(2).power(i) * c); ++i; } //cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); return 0; }