---
# System prepended metadata

title: 2022 ICPC Asia Taiwan Online Programming Contest

---

2022 ICPC Asia Taiwan Online Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/103990/ 

比賽影片
---
沒有ㄚ QAQ

記分板
---
![image](https://hackmd.io/_uploads/S16CkEkCA.png)


題解
---
### A. AibohphobiA(待補)
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=

```
:::

### B. Balanced Seesaw Array
---
#### 題目摘要
讓$\,A=[a_1,a_2,\dots,a_m]$，定義一個陣列為平衡翹翹板陣列，如果存在一個$\,k\,$在$\,1\,$和$\,m\,$之間$\sum_{i=1}^m(i-k) a_i = 0$

$Q\,$筆操作
* $1\; \ell\; r \; x$ 代表 $a_\ell,a_{\ell+1},\dots,a_r$ 增加 $x$
* $2\; \ell\; r\; x$ 代表 $a_\ell,a_{\ell+1},\dots,a_r$ 改為 $x$
* $3\; \ell\; r$ 輸出 $[a_\ell,a_{\ell+1},\dots,a_r]$ 是否為平衡翹翹板陣列

#### 想法
數式展開 $\sum_{i=1}^m(i-k)a_i=0$
$\sum_{i=1}^mia_i= k\sum_{i=1}^ma_i$
$k= \frac{\sum_{i=1}^mia_i}{\sum_{i=1}^ma_i}$
因此只要用線段樹好好維護$ia_i$及$a_i$的區間和，再判斷k有沒有符合條件就好。
在維護$ia_i$時可以考慮維護一個等差數列，細節的部分好好處理就好
:::spoiler 實作

```cpp=
#include<bits/stdc++.h>
using namespace std;

#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
#define pii pair<int, int> 
#define lpos pos << 1
#define rpos pos << 1 | 1

const int MAXN = 1e5 + 5;
#define int long long

struct node {
    ll val, pre, tag = 10001, st, inc;
    void update(int, int, int, ll, ll);
} tree[MAXN << 2];

node operator + (node a, node b) {
    return {a.val + b.val, a.pre + b.pre, 10001, 0, 0};
}

ll a[MAXN], p[MAXN];

void node::update(int l, int r, int lval, ll d, ll v) {
    if (v != 10001) {
        val = v * (r - l + 1);
        pre = v * (l + r) * (r - l + 1) / 2;
        st = inc = 0;
        tag = v;
    }
    val += d * (r - l + 1);
    pre += (2 * lval + (r - l) * d) * (r - l + 1) / 2;
    st += lval;
    inc += d;
}

void pull(int pos) {
    tree[pos] = tree[lpos] + tree[rpos];
}

void build(int pos, int l, int r) {
    if (l == r) {
        tree[pos] = {a[l], p[l], 10001, 0, 0};
        return;
    }
    int mid = l + r >> 1;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);
    pull(pos);
}

void push(int pos, int l, int r) {
    int mid = l + r >> 1;
    tree[lpos].update(l, mid, 0, 0, tree[pos].tag);
    tree[rpos].update(mid + 1, r, 0, 0, tree[pos].tag);
    tree[pos].tag = 10001;
    tree[lpos].update(l, mid, tree[pos].st, tree[pos].inc, 10001);
    tree[rpos].update(mid + 1, r, tree[pos].st + (mid + 1 - l) * tree[pos].inc, tree[pos].inc, 10001);
    tree[pos].st = tree[pos].inc = 0;
}

void mod(int pos, int l, int r, int ml, int mr, ll val, int d, int t) {
    if (ml <= l && mr >= r) {
        if (t == 1) {
            tree[pos].update(l, r, val, d, 10001);
        } else {
            tree[pos].update(l, r, 0, 0, d);
        }
        return;
    }
    push(pos, l, r);
    int mid = l + r >> 1;
    if (ml <= mid) mod(lpos, l, mid, ml, mr, val, d, t);
    if (mr > mid) mod(rpos, mid + 1, r, ml, mr, (mid + 1) * d, d, t);
    pull(pos);
}

node query(int pos, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) {
        return tree[pos];
    }
    push(pos, l, r);
    int mid = l + r >> 1;
    node res = {0, 0, 0, 0, 0};
    if (ql <= mid) res = res + query(lpos, l, mid, ql, qr);
    if (qr > mid) res = res + query(rpos, mid + 1, r, ql, qr);
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q; cin >> n >> q;
    rep (i, 1, n + 1) cin >> a[i];
    rep (i, 1, n + 1) p[i] = a[i] * i;
    build(1, 1, n);
    while (q--) {
        int t, l, r; cin >> t >> l >> r;
        if (t == 3) {
            node tmp = query(1, 1, n, l, r);
            ll val = tmp.val, pre = tmp.pre;
            pre -= val * (l - 1);
            // cout << pre << ' ' << val << '\n';
            if (val == 0) {
                if (pre == 0) {
                    cout << "Yes\n";
                } else {
                    cout << "No\n";
                }
            } else if (pre % val != 0) {
                cout << "No\n";
            } else {
                ll k = pre / val;
                if (k < 1 || k > r - l + 1) cout << "No\n";
                else cout << "Yes\n";
            }
        } else {
            int x; cin >> x;
            mod(1, 1, n, l, r, l * x, x, t);
        }
    }
}
```
:::


### C. Correct
---
#### 題目摘要
9:00開始的比賽，Charlie 在$HH, MM$時一發AC第一題，問他們penalty為多少

#### 想法
$(Hours - 9) \times 60 + Minutes$

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
 
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
#define pii pair<int, int> 
int a, b;
int main() {
    cin >> a >> b;
    cout << (a-9)*60+b;
}
```
:::

### D. Distance and Tree
---
#### 題目摘要
一個圓上有$n$個點，每點有各自的深度，要連邊並且邊邊不相交，若能不能連成一顆樹。若能，輸出所有邊，否則輸出-1
#### 想法
對於一個點，如果他跟另一個點連線，那麼他的左邊跟右邊必定無法相連，換句話說，你沒辦法跨過一個已經被連接的點連他的另一邊，所以從深度比較高的搜左右邊最近被連接過的點是不是自己的深度-1，是的話就連起來，不然就代表沒辦法連，開頭記得把1先接好

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
 
const int N=100005;
vector<int> v[N];
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        int d;
        cin >> d;
        v[d].push_back(i);
    }
    if (v[0].size()!=1){
        cout << -1 << '\n';
        exit(0);
    }
    map<int, int> mp;
    mp[v[0][0]]=0;
    bool phlag=1;
    vector<pair<int, int>> ans;
    for(int i=1;i<n;i++){
        for(auto pos:v[i]){
            auto it=mp.upper_bound(pos);
            if (it!=mp.end()){
                if (it->S==i-1){
                    ans.push_back({it->F, pos});
                    continue;
                }
            }else{
                it=mp.begin();
                if (it->S==i-1){
                    ans.push_back({it->F, pos});
                    continue;
                }
            }
            if (it!=mp.begin()){
                it=prev(it);
                if (it->S==i-1){
                    ans.push_back({it->F, pos});
                    continue;
                }
            }else{
                it=prev(mp.end());
                if (it->S==i-1){
                    ans.push_back({it->F, pos});
                    continue;
                }
            }
        }
        for(auto pos:v[i]) mp[pos]=i;
    }
    if (ans.size()!=n-1) phlag=0;
    if (phlag){
        for(auto p:ans){
            cout << p.first << ' ' << p.second << '\n';
        }
    }else{
        cout << -1 << '\n';
    }
}
```
:::

### E. Etched Emerald Orbs
---
#### 題目摘要
找到一組$(x,\, y) \ {(x < y)}$符合：
$\frac{2}{k} = \frac{1}{x} + \frac{1}{y} \ (3\le k \le 4\times 10^{18})$
如有多組解輸出$\,x + y \,$最小的一組
#### 想法
炸柿子
$\ \ \ \ \ \ \frac{2}{k} = \frac{1}{x} + \frac{1}{y}$
$\Rightarrow 2xy=kx+ky$
$\Rightarrow 4xy-kx-ky=0$
$\Rightarrow 4xy-kx-ky+k^2=k^2$
$\Rightarrow k^2=(2x-k)(2y-k)!!!$
會發現我們只要將$k^2$的所有因數枚舉過一遍就能找出解
$k^2$的因數可以利用先找$\, k \,$的所有因數來枚舉出來
因數分解的部分則可使用Pollard's Rho演算法
注意要__int128
複雜度應該還行

:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = __int128(res) * x % mod; x = __int128(x) * x % mod; exp >>= 1;} return res; }

bool Miller_Rabin(ll n) {
    const int lim = 10;
    if (n < 3 || n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    ll d = n - 1, t = 0;
    while (d & 1 ^ 1) d >>= 1, t++;
    rep (i, 0, lim) {
        ll x = rng() % (n - 3) + 2, val = fpow(x, d, n);
        if (val == 1) continue;
        int s = 0;
        while (s < t) {
            if (val == n - 1) break;
            val = __int128(val) * val % n;
            s++;
        }
        if (s == t) return false;
    }    
    return true;
}

ll Pollard_Rho(ll n) {
    ll c = rng() % (n - 1) + 1;
    auto calc = [&](ll x) -> ll {
        return (__int128(x) * x + c) % n;
    };
    ll s = 0, t = 0;
    ll val = 1;
    for (int goal = 1;; goal <<= 1, s = t, val = 1) {
        rep (step, 1, goal + 1) {
            t = calc(t);
            val = __int128(val) * abs(s - t) % n;
            if (val == 0) return n;
            if (step % 127 == 0) {
                ll d = __gcd(val, n);
                if (d > 1) return d;
            }
        }
        ll d = __gcd(val, n);
        if (d > 1) return d;
    }
}

void print(__int128 x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

void solve() {
    ll k; cin >> k;
    ll tmp = k;
    vector<pll> prime;
    auto fac = [&](auto self, ll x) -> void {
        if (x < 2) return;
        if (Miller_Rabin(x)) {
            prime.pb({x, 0});
            while (tmp % x == 0) {
                prime.back().S++;
                tmp /= x;
            }
            return;
        }
        ll p = x;
        while (p >= x) p = Pollard_Rho(x);
        while (x % p == 0) x /= p;
        self(self, p), self(self, x);
    }; 
    fac(fac, k);
    vector<ll> div;
    auto gen_div = [&](auto self, int d, ll cur) -> void {
        if (d == prime.size()) {
            div.pb(cur);
            return;
        }
        self(self, d + 1, cur);
        rep (i, 1, prime[d].S + 1) {
            cur *= prime[d].F;
            self(self, d + 1, cur);
        }
    };
    gen_div(gen_div, 0, 1);
    // (2x - k) * (2y - k) = k ^ 2
    sort(all(div));
    // cout << div;
    __int128 mx = __int128(1) << 126, a, b;
    int sz = div.size();
    rep (i, 0, sz) {
        rep (j, 0, i + 1) {
            ll x = div[i], y = div[j];
            __int128 mul = __int128(x) * y;
            if (mul >= k) break;
            __int128 mul2 = __int128(k) * k / mul;
            if (((mul + k) & 1) || ((mul2 + k) & 1)) continue;
            mul = (mul + k) / 2, mul2 = (mul2 + k) / 2;
            if (mx > mul + mul2) {
                a = mul, b = mul2;
                mx = mul + mul2;
            }
        }
    }
    print(a);
    putchar(' ');
    print(b);
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::

### F. Finalists
---
#### 題目摘要
題序超長自己看，給六個國家的很多分數，給你一個公式算出每個國家的分數，然後按照排名分配名額，問台灣拿幾個名額
#### 想法
他有浮點數所以開long double，然後用簡單數學
(每個人都有=$\frac{total}{6}$,多拿=$\frac{total \% 6}{排名}$)算一下名額
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
 
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define ll long long
#define pii pair<int, int> 
long double ru, rt, pu, pt, f;
int n;
long double site_score;
int main() {
    cin >> n;
    string s;
    int tai;
    vector<pair<long double, int>> c;
    rep(i,0,6){
        cin >> s >> pt >> pu >> rt >> ru >> f;
        site_score = 0.56f*ru+0.24f*rt+0.14f*pu+0.06f*pt+0.3f*f;
        if(s == "Taiwan") tai = i;
        c.push_back({-site_score,i});
    }
    sort(c.begin(),c.end());
    rep(i,0,6){
        if(c[i].second == tai){
            cout << n/6+(n%6)/(i+1);
        }
    }
}
```
:::

### G. Geekflix
---
#### 題目摘要
有$n$個直播，每看一個直播拿到點數，第$i$個直播看第$k$次能拿到的點數為$\, \max(a_i-(k-1)b_i, \; 0)$。你有三種操作，往前一台轉(1會到$n$)、往後一台轉($n$會到1)以及播放目前的直播，你會從第1場直播開始，問你做$m$個操作後最多能有多少點數
#### 想法
相信聰明的讀者一看到這題$n$的大小，就能馬上看出這是複雜度為$O(n^2m\log m)$的枚舉區間題了。對於每個區間，只要先算出最少需要幾個操作才能讓區間內所有直播都被轉到，剩下再用pq去維護最大的點數就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N=205;
int a[N<<1], b[N<<1];
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> a[i];
        a[i+n]=a[i];
    }
    for(int i=0;i<n;i++){
        cin >> b[i];
        b[i+n]=b[i];
    }
    ll ans=0;
    for(int r=0;r<(n<<1);r++){
        for(int l=max(0, r-n+1);l<=min(n-1, r);l++){
            int t=0;
            if (0<=l&&r<=n){
                t=min(r, n-l);
            }else{
                t+=r-l;
                t+=min(r-n, n-l);
            }
            t=m-t;
            priority_queue<pair<int, int>> pq;
            for(int k=l;k<=r;k++) pq.push({a[k], k});
            ll res=0;
            while((t>0)&&(!pq.empty())){
                auto [val, idx]=pq.top();
                pq.pop();
                if (val==0) break;
                res+=val;
                val-=b[idx];
                pq.push({max(0, val), idx});
                t--;
            }
            ans=max(ans, res);
        }
    }
    cout << ans << '\n';
}
```
:::


### H. Heximal
---
#### 題目摘要
給一個10進位數字$N,$ 並且 $0 \le N < 10^{500000}$
求轉成6進位後長度為多少
#### 想法
二分搜第一個滿足 $6^{ans} > N$ 的$ans$，大數運算交給python
:::spoiler 實作
```python=
a = int(input(''))
l=1
r=1000000
while(l<r):
    m=(l+r)>>1
    if (pow(6, m)>a):
        r=m
    else:
       l=m+1
if a==0:
    print(1)
else:
    print(l)
```
:::

### I. Invitation(待補)
---
#### 題目摘要
#### 想法

:::spoiler 實作
```cpp=
#ifdef LOCAL
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second

#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif

void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow (ll x, ll exp, ll mod = LLONG_MAX) { if (x == 0) return 0; ll res = 1; while (exp > 0) { if (exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1; } return res; }

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder_modint {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename conditional<is_same<T, __int128_t>::value ||
                                  is_same<T, __int128>::value,
                              true_type,
                              false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename conditional<is_same<T, __uint128_t>::value ||
                                  is_same<T, unsigned __int128>::value,
                              true_type,
                              false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename conditional<is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              true_type,
                                              false_type>::type;

template <class T>
using is_signed_int = typename conditional<(is_integral<T>::value &&
                                                 is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                true_type,
                                                false_type>::type;

template <class T>
using is_unsigned_int =
    typename conditional<(is_integral<T>::value &&
                               is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              true_type,
                              false_type>::type;

template <class T>
using to_unsigned = typename conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename conditional<is_signed<T>::value,
                              make_unsigned<T>,
                              common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename is_integral<T>;

template <class T>
using is_signed_int =
    typename conditional<is_integral<T>::value && is_signed<T>::value,
                              true_type,
                              false_type>::type;

template <class T>
using is_unsigned_int =
    typename conditional<is_integral<T>::value &&
                                  is_unsigned<T>::value,
                              true_type,
                              false_type>::type;

template <class T>
using to_unsigned = typename conditional<is_signed_int<T>::value,
                                              make_unsigned<T>,
                                              common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};

    // Contracts:
    // [1] s - m0 * a = 0 (mod b)
    // [2] t - m1 * a = 0 (mod b)
    // [3] s * |m1| + t * |m0| <= b
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

        // [3]:
        // (s - t * u) * |m1| + t * |m0 - m1 * u|
        // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        // = s * |m1| + t * |m0| <= b

        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    // by [3]: |m0| <= b/g
    // by g != b: |m0| < b/g
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
    unsigned int _m;
    unsigned long long im;

    // @param m `1 <= m < 2^31`
    explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}

    // @return m
    unsigned int umod() const { return _m; }

    // @param a `0 <= a < m`
    // @param b `0 <= b < m`
    // @return `a * b % m`
    unsigned int mul(unsigned int a, unsigned int b) const {
        // [1] m = 1
        // a = b = im = 0, so okay

        // [2] m >= 2
        // im = ceil(2^64 / m)
        // -> im * m = 2^64 + r (0 <= r < m)
        // let z = a*b = c*m + d (0 <= c, d < m)
        // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
        // ((ab * im) >> 64) == c or c + 1
        unsigned long long z = a;
        z *= b;
#ifdef _MSC_VER
        unsigned long long x;
        _umul128(z, im, &x);
#else
        unsigned long long x =
            (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
        unsigned int v = (unsigned int)(z - x * _m);
        if (_m <= v) v += _m;
        return v;
    }
};

struct modint_base {};
struct static_modint_base : modint_base {};

template <class T> using is_modint = is_base_of<modint_base, T>;
template <class T> using is_modint_t = enable_if_t<is_modint<T>::value>;

}  // namespace internal

template <int m, enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
    using mint = static_modint;

  public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    static_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = internal::is_prime<m>;
};

template <int id> struct dynamic_modint : internal::modint_base {
    using mint = dynamic_modint;

  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = internal::barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        long long x = (long long)(v % (long long)(mod()));
        if (x < 0) x += mod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        _v = (unsigned int)(v % mod());
    }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = internal::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static internal::barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

namespace internal {

template <class T>
using is_static_modint = is_base_of<internal::static_modint_base, T>;

template <class T>
using is_static_modint_t = enable_if_t<is_static_modint<T>::value>;

template <class> struct is_dynamic_modint : public false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public true_type {};

template <class T>
using is_dynamic_modint_t = enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

}  // namespace atcoder_modint

// need atcoder_modint
namespace atcoder_convolution {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        divs[cnt++] = x;
    }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (atcoder_modint::internal::pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

template <class mint,
          int g = internal::primitive_root<mint::mod()>,
          atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
struct fft_info {
    static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);
    array<mint, rank2 + 1> root;   // root[i]^(2^i) == 1
    array<mint, rank2 + 1> iroot;  // root[i] * iroot[i] == 1

    array<mint, max(0, rank2 - 2 + 1)> rate2;
    array<mint, max(0, rank2 - 2 + 1)> irate2;

    array<mint, max(0, rank2 - 3 + 1)> rate3;
    array<mint, max(0, rank2 - 3 + 1)> irate3;

    fft_info() {
        root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
        iroot[rank2] = root[rank2].inv();
        for (int i = rank2 - 1; i >= 0; i--) {
            root[i] = root[i + 1] * root[i + 1];
            iroot[i] = iroot[i + 1] * iroot[i + 1];
        }

        {
            mint prod = 1, iprod = 1;
            for (int i = 0; i <= rank2 - 2; i++) {
                rate2[i] = root[i + 2] * prod;
                irate2[i] = iroot[i + 2] * iprod;
                prod *= iroot[i + 2];
                iprod *= root[i + 2];
            }
        }
        {
            mint prod = 1, iprod = 1;
            for (int i = 0; i <= rank2 - 3; i++) {
                rate3[i] = root[i + 3] * prod;
                irate3[i] = iroot[i + 3] * iprod;
                prod *= iroot[i + 3];
                iprod *= root[i + 3];
            }
        }
    }
};

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
void butterfly(vector<mint>& a) {
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static const fft_info<mint> info;

    int len = 0;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
    while (len < h) {
        if (h - len == 1) {
            int p = 1 << (h - len - 1);
            mint rot = 1;
            for (int s = 0; s < (1 << len); s++) {
                int offset = s << (h - len);
                for (int i = 0; i < p; i++) {
                    auto l = a[i + offset];
                    auto r = a[i + offset + p] * rot;
                    a[i + offset] = l + r;
                    a[i + offset + p] = l - r;
                }
                if (s + 1 != (1 << len))
                    rot *= info.rate2[bsf(~(unsigned int)(s))];
            }
            len++;
        } else {
            // 4-base
            int p = 1 << (h - len - 2);
            mint rot = 1, imag = info.root[2];
            for (int s = 0; s < (1 << len); s++) {
                mint rot2 = rot * rot;
                mint rot3 = rot2 * rot;
                int offset = s << (h - len);
                for (int i = 0; i < p; i++) {
                    auto mod2 = 1ULL * mint::mod() * mint::mod();
                    auto a0 = 1ULL * a[i + offset].val();
                    auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
                    auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
                    auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
                    auto a1na3imag =
                        1ULL * mint(a1 + mod2 - a3).val() * imag.val();
                    auto na2 = mod2 - a2;
                    a[i + offset] = a0 + a2 + a1 + a3;
                    a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
                    a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
                    a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
                }
                if (s + 1 != (1 << len))
                    rot *= info.rate3[bsf(~(unsigned int)(s))];
            }
            len += 2;
        }
    }
}

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(vector<mint>& a) {
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static const fft_info<mint> info;

    int len = h;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
    while (len) {
        if (len == 1) {
            int p = 1 << (h - len);
            mint irot = 1;
            for (int s = 0; s < (1 << (len - 1)); s++) {
                int offset = s << (h - len + 1);
                for (int i = 0; i < p; i++) {
                    auto l = a[i + offset];
                    auto r = a[i + offset + p];
                    a[i + offset] = l + r;
                    a[i + offset + p] =
                        (unsigned long long)(mint::mod() + l.val() - r.val()) *
                        irot.val();
                    ;
                }
                if (s + 1 != (1 << (len - 1)))
                    irot *= info.irate2[bsf(~(unsigned int)(s))];
            }
            len--;
        } else {
            // 4-base
            int p = 1 << (h - len);
            mint irot = 1, iimag = info.iroot[2];
            for (int s = 0; s < (1 << (len - 2)); s++) {
                mint irot2 = irot * irot;
                mint irot3 = irot2 * irot;
                int offset = s << (h - len + 2);
                for (int i = 0; i < p; i++) {
                    auto a0 = 1ULL * a[i + offset + 0 * p].val();
                    auto a1 = 1ULL * a[i + offset + 1 * p].val();
                    auto a2 = 1ULL * a[i + offset + 2 * p].val();
                    auto a3 = 1ULL * a[i + offset + 3 * p].val();

                    auto a2na3iimag =
                        1ULL *
                        mint((mint::mod() + a2 - a3) * iimag.val()).val();

                    a[i + offset] = a0 + a1 + a2 + a3;
                    a[i + offset + 1 * p] =
                        (a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();
                    a[i + offset + 2 * p] =
                        (a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *
                        irot2.val();
                    a[i + offset + 3 * p] =
                        (a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *
                        irot3.val();
                }
                if (s + 1 != (1 << (len - 2)))
                    irot *= info.irate3[bsf(~(unsigned int)(s))];
            }
            len -= 2;
        }
    }
}

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution_naive(const vector<mint>& a,
                                    const vector<mint>& b) {
    int n = int(a.size()), m = int(b.size());
    vector<mint> ans(n + m - 1);
    if (n < m) {
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                ans[i + j] += a[i] * b[j];
            }
        }
    } else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i + j] += a[i] * b[j];
            }
        }
    }
    return ans;
}

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution_fft(vector<mint> a, vector<mint> b) {
    int n = int(a.size()), m = int(b.size());
    int z = 1 << internal::ceil_pow2(n + m - 1);
    a.resize(z);
    internal::butterfly(a);
    b.resize(z);
    internal::butterfly(b);
    for (int i = 0; i < z; i++) {
        a[i] *= b[i];
    }
    internal::butterfly_inv(a);
    a.resize(n + m - 1);
    mint iz = mint(z).inv();
    for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
    return a;
}

}  // namespace internal

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution(vector<mint>&& a, vector<mint>&& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if (min(n, m) <= 60) return atcoder_convolution::internal::convolution_naive(a, b);
    return internal::convolution_fft(a, b);
}

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution(const vector<mint>& a,
                              const vector<mint>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if (min(n, m) <= 60) return atcoder_convolution::internal::convolution_naive(a, b);
    return internal::convolution_fft(a, b);
}

template <unsigned int mod = 998244353,
          class T,
          enable_if_t<atcoder_modint::internal::is_integral<T>::value>* = nullptr>
vector<T> convolution(const vector<T>& a, const vector<T>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    using mint = atcoder_modint::static_modint<mod>;
    vector<mint> a2(n), b2(m);
    for (int i = 0; i < n; i++) {
        a2[i] = mint(a[i]);
    }
    for (int i = 0; i < m; i++) {
        b2[i] = mint(b[i]);
    }
    auto c2 = convolution(move(a2), move(b2));
    vector<T> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        c[i] = c2[i].val();
    }
    return c;
}

vector<long long> convolution_ll(const vector<long long>& a,
                                      const vector<long long>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    static constexpr unsigned long long MOD1 = 754974721;  // 2^24
    static constexpr unsigned long long MOD2 = 167772161;  // 2^25
    static constexpr unsigned long long MOD3 = 469762049;  // 2^26
    static constexpr unsigned long long M2M3 = MOD2 * MOD3;
    static constexpr unsigned long long M1M3 = MOD1 * MOD3;
    static constexpr unsigned long long M1M2 = MOD1 * MOD2;
    static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;

    static constexpr unsigned long long i1 =
        atcoder_modint::internal::inv_gcd(MOD2 * MOD3, MOD1).second;
    static constexpr unsigned long long i2 =
        atcoder_modint::internal::inv_gcd(MOD1 * MOD3, MOD2).second;
    static constexpr unsigned long long i3 =
        atcoder_modint::internal::inv_gcd(MOD1 * MOD2, MOD3).second;

    auto c1 = convolution<MOD1>(a, b);
    auto c2 = convolution<MOD2>(a, b);
    auto c3 = convolution<MOD3>(a, b);

    vector<long long> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        unsigned long long x = 0;
        x += (c1[i] * i1) % MOD1 * M2M3;
        x += (c2[i] * i2) % MOD2 * M1M3;
        x += (c3[i] * i3) % MOD3 * M1M2;
        // B = 2^63, -B <= x, r(real value) < B
        // (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
        // r = c1[i] (mod MOD1)
        // focus on MOD1
        // r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
        // r = x,
        //     x - M' + (0 or 2B),
        //     x - 2M' + (0, 2B or 4B),
        //     x - 3M' + (0, 2B, 4B or 6B) (without mod!)
        // (r - x) = 0, (0)
        //           - M' + (0 or 2B), (1)
        //           -2M' + (0 or 2B or 4B), (2)
        //           -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
        // we checked that
        //   ((1) mod MOD1) mod 5 = 2
        //   ((2) mod MOD1) mod 5 = 3
        //   ((3) mod MOD1) mod 5 = 4
        long long diff =
            c1[i] - atcoder_modint::internal::safe_mod((long long)(x), (long long)(MOD1));
        if (diff < 0) diff += MOD1;
        static constexpr unsigned long long offset[5] = {
            0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
        x -= offset[diff % 5];
        c[i] = x;
    }

    return c;
}

}  // namespace atcoder_convolution

using mint = atcoder_modint::modint998244353;
using namespace atcoder_convolution;

ostream& operator << (ostream &os, const mint &p) { os << p.val(); return os; }

// need modint
vector<mint> fac, inv;

inline void init (int n) {
    fac.resize(n + 1);
    inv.resize(n + 1);
    fac[0] = inv[0] = 1;
    rep (i, 1, n + 1) fac[i] = fac[i - 1] * i;
    inv[n] = fac[n].inv();
    for (int i = n; i > 0; --i) inv[i - 1] = inv[i] * i;
}

inline mint Comb(int n, int k) {
    if (k > n || k < 0) return 0;
    return fac[n] * inv[k] * inv[n - k];
}

inline mint H(int n, int m) {
    return Comb(n + m - 1, m);
}

inline mint catalan(int n){
    return fac[2 * n] * inv[n + 1] * inv[n];
}

void solve() {
    int n; cin >> n;
    init(n);
    vector<pii> seg;
    vector<int> dic;
    rep (i, 0, n) {
        int l, r; cin >> l >> r;
        seg.pb({l, r});
        dic.pb(l);
        dic.pb(r);
    }
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
    int m = ssize(dic);
    for (auto &[l, r] : seg) {
        l = lower_bound(all(dic), l) - dic.begin();
        r = lower_bound(all(dic), r) - dic.begin();
    }
    auto calc = [&]() -> vector<mint> {
        vector<int> cnt(m + 2, 0);
        for (auto [l, r] : seg) cnt[l]++, cnt[r + 1]--;
        partial_sum(all(cnt), cnt.begin());
        vector<mint> a(n + 1, 0), b(n + 1, 0);
        rep (i, 0, m + 1) a[cnt[i]] += fac[cnt[i]];
        rep (i, 0, n + 1) b[i] = inv[n - i];
        auto c = convolution(a, b);
        c = vector(c.begin() + n, c.end());
        rep (i, 0, n + 1) c[i] *= inv[i];
        return c;
    };
    auto sum = calc();
    for (auto &[l, r] : seg) r--;
    auto sum2 = calc();
    rep (i, 1, n + 1) cout << sum[i] - sum2[i] << " \n" [i == n];
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

```
:::
