C++競プロ用ライブラリ

string s;
getline(cin, s);

#include <iomanip>

double x = 3.141592653589793;

// 有効数字（全体桁数）
cout << setprecision(10) << x;

// 小数点以下固定
cout << fixed << setprecision(5) << x;

// 指数表記
cout << scientific << setprecision(3) << x;

// 元に戻す
cout << defaultfloat << x;

int a, b;
long long x;
string s;
char c;
double d;

cin >> a >> b;
cin >> x;
cin >> s;
cin >> c;
cin >> d;

int n = stoi("123");
long long m = stoll("999999999999");
double d = stod("3.14159");

string s1 = to_string(42);
string s2 = to_string(1000000000000LL);

string s = "competitive programming";
string t = s.substr(0, 10);        // "competitive"
size_t p = s.find("program");
if (p != string::npos) {
    s.replace(p, 8, "contest");
}

stringstream ss;
ss << "10 20 30";
int a, b, c;
ss >> a >> b >> c;

// S と S[i:|S|-1] の最長共通接頭辞(LCP)を O(N) で求める構造体
struct ZArray {
  ll n;
  vector<ll> z;

  // 通常の文字列用
  ZArray(const string& s) {
    build(s);
  }

  // 複数文字列を扱う場合や数列用（番兵を利用可能）
  template <typename T>
  ZArray(const vector<T>& v) {
    build(v);
  }

private:
  template <typename Container>
  void build(const Container& s) {
    n = s.size();
    z.assign(n, 0);
    if (n == 0) return;
    z[0] = n;
    ll i = 1, j = 0;
    while (i < n) {
      while (i + j < n && s[j] == s[i + j]) j++;
      z[i] = j;
      if (j == 0) {
        i++;
        continue;
      }
      ll k = 1;
      while (i + k < n && k + z[k] < j) {
        z[i + k] = z[k];
        k++;
      }
      i += k;
      j -= k;
    }
  }
};

#include <atcoder/string>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// ACLをラップし、任意2点間LCPクエリ（RMQ）をサポートした実戦用構造体
struct AclStringAutomaton {
  int n;
  vector<int> sa;
  vector<int> lcp;
  vector<int> rank;
  vector<vector<int>> st;
  vector<int> log_table;

  // 通常の文字列用
  AclStringAutomaton(const string& s) {
    n = s.size();
    sa = atcoder::suffix_array(s);
    lcp = atcoder::lcp_array(s, sa);
    build();
  }

  // 複数文字列を扱う場合用（int配列版番兵を利用可能）
  // 例: SとTを合わせる際、Sの各文字、200000(番兵1)、Tの各文字、200001(番兵2) のように格納
  AclStringAutomaton(const vector<int>& v) {
    n = v.size();
    sa = atcoder::suffix_array(v);
    lcp = atcoder::lcp_array(v, sa);
    build();
  }

  // 元の文字配列のインデックス i と j から始まる接尾辞の LCP を O(1) で取得
  int get_lcp(int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= n) return 0; // 範囲外アクセスを防止
    if (i == j) return n - i;
    int r_i = rank[i], r_j = rank[j];
    if (r_i > r_j) swap(r_i, r_j);
    int l = r_i, r = r_j - 1;
    int len = r - l + 1;
    int k = log_table[len];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
  }

private:
  void build() {
    // rank のサイズは n ぴったりでOKです
    rank.resize(n);

    // i <= n ではなく、i < n に修正（範囲外アクセスを防止）
    for (int i = 0; i < n; i++)
      rank[sa[i]] = i;

    int m = lcp.size(); // m は確実に n-1 になります
    if (m == 0) return; // 要素が1つ以下の場合はSparse Tableの構築をスキップ

    log_table.assign(m + 1, 0);
    for (int i = 2; i <= m; i++)
      log_table[i] = log_table[i >> 1] + 1;

    int max_log = log_table[m] + 1;
    st.assign(max_log, vector<int>(m));
    for (int i = 0; i < m; i++)
      st[0][i] = lcp[i];

    for (int k = 1; k < max_log; k++) {
      for (int i = 0; i + (1 << k) <= m; i++) {
        st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
      }
    }
  }
};

#include <atcoder/string>
#include <vector>
#include <string>

using namespace std;

// ACLのSAとLCPを利用してO(N)でSuffix Treeを構築する構造体
struct SuffixTree {
  struct Node {
    int l, r;             // 親からこのノードへ向かう辺の文字列区間 S[l, r)
    int depth;            // 根からこのノードまでの総文字列長
    int parent;           // 親ノードのインデックス
    vector<int> children; // 子ノード群のインデックス

    Node(int l, int r, int depth, int parent)
      : l(l), r(r), depth(depth), parent(parent) {}
  };

  string S;
  vector<Node> nodes;

  SuffixTree(const string& s) : S(s) {
    int n = s.size();
    auto sa = atcoder::suffix_array(s);
    auto lcp = atcoder::lcp_array(s, sa);

    // root (id = 0) を追加
    nodes.emplace_back(0, 0, 0, -1);
    int curr = 0;

    for (int i = 0; i < n; i++) {
      int suffix_idx = sa[i];
      int lcp_val = (i == 0 ? 0 : lcp[i - 1]);

      // 現在のノードから根へ遡り、LCPの深さ以下の分岐点を探す
      while (curr != 0 && nodes[curr].depth > lcp_val) {
        int p = nodes[curr].parent;
        if (nodes[p].depth <= lcp_val) {
          if (nodes[p].depth < lcp_val) {
            // 辺の途中で分岐する必要があるため、ノードを分割 (Edge Split)
            int split_id = nodes.size();
            int split_l = nodes[curr].l;
            int split_r = split_l + (lcp_val - nodes[p].depth);
            nodes.emplace_back(split_l, split_r, lcp_val, p);

            // 親の参照先を新しい分割ノードに更新
            for (int& child : nodes[p].children) {
              if (child == curr) {
                child = split_id;
                break;
              }
            }
            nodes[split_id].children.push_back(curr);
            nodes[curr].parent = split_id;
            nodes[curr].l += (lcp_val - nodes[p].depth);
            
            curr = split_id;
          } else {
            // ちょうど分岐点(親ノード)が LCP の深さと一致する場合
            curr = p;
          }
          break;
        }
        curr = p;
      }

      // 新しい葉ノードを追加
      int leaf_id = nodes.size();
      nodes.emplace_back(suffix_idx + lcp_val, n, n - suffix_idx, curr);
      nodes[curr].children.push_back(leaf_id);
      curr = leaf_id;
    }
  }
};

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// char_size: 文字の種類数 (英小文字のみなら26)
// base: 基準となる文字 ('a', 'A', '0' など)
template <int char_size = 26, int base = 'a'>
struct Trie {
  struct Node {
    vector<int> next;       // 子ノードのインデックス
    int accept_count;       // このノードで終わる文字列の数
    int pass_count;         // このノードを通過した文字列の数
    
    // --- 汎用拡張データ ---
    vector<int> accept_ids; // このノードで終わる文字列のラベル(追加時のIDなど)
    long long val;          // 関数値、重み、DPの結果などを持たせる汎用変数

    Node() : next(char_size, -1), accept_count(0), pass_count(0), val(0) {}
  };

  vector<Node> nodes;

  Trie() {
    nodes.push_back(Node()); // root (id = 0) を追加
  }

  // 文字列の挿入 (同時にIDや関数の値を登録できる)
  void insert(const string &s, int id = -1, long long val = 0) {
    int curr = 0;
    nodes[curr].pass_count++;
    for (char c : s) {
      int to = c - base;
      if (nodes[curr].next[to] == -1) {
        nodes[curr].next[to] = nodes.size();
        nodes.push_back(Node());
      }
      curr = nodes[curr].next[to];
      nodes[curr].pass_count++;
    }
    nodes[curr].accept_count++;
    if (id != -1) nodes[curr].accept_ids.push_back(id);
    nodes[curr].val += val; // 用途に応じて +=, max(), = などに変更可能
  }

  // 文字列の完全一致検索 (見つかれば終端ノードのIDを、なければ -1 を返す)
  int search(const string &s) {
    int curr = 0;
    for (char c : s) {
      int to = c - base;
      if (nodes[curr].next[to] == -1) return -1;
      curr = nodes[curr].next[to];
    }
    return nodes[curr].accept_count > 0 ? curr : -1;
  }

  // Prefix(接頭辞)検索 (S から始まる文字列の数を返す)
  int count_prefix(const string &s) {
    int curr = 0;
    for (char c : s) {
      int to = c - base;
      if (nodes[curr].next[to] == -1) return 0;
      curr = nodes[curr].next[to];
    }
    return nodes[curr].pass_count;
  }
};

vector<int> v;
v.push_back(3);
v.emplace_back(5);
v.pop_back();

vector<int> v;
v.resize(10);          // 要素数10
v.assign(5, 7);        // [7, 7, 7, 7, 7]
v.clear();             // 空にする

vector<ll> v = {1, 2, 3, 2, 4};
v.erase(v.begin() + 1);  // 2番目を削除

v.erase(
    remove(v.begin(), v.end(), 2),
    v.end()
);

// 重複削除と座標圧縮
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
auto get_id = [&](long long x) {
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
};

sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<>());
stable_sort(v.begin(), v.end());
reverse(v.begin(), v.end());

// 2番目の要素(pair.second)で降順ソート
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    return a.second > b.second;
});

// 自作関数を別途定義して渡す例
// 1つ目の引数 a が 2つ目の引数 b より「真に小さい（前に来るべき）」場合に true を返す
bool compareData(const Data& a, const Data& b) {
    if (a.score != b.score) {
        return a.score > b.score; // 第1条件: スコアが高い順（a.score > b.score のとき true）
    }
    return a.id < b.id;           // 第2条件: スコアが同じならIDが小さい順（a.id < b.id のとき true）
}

sort(v.begin(), v.end(), compareData);

// ラムダ式で単一・複合条件を指定する例
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    // a が b より「真に小さい」ときのみ true（a == b のときは必ず false）
    return a.first < b.first;
});

auto it1 = lower_bound(v.begin(), v.end(), x); // x以上の最初
auto it2 = upper_bound(v.begin(), v.end(), x); // xより大きい最初

ll idx1 = it1 - v.begin();
ll idx2 = it2 - v.begin();

sort(v.begin(), v.end());
do {
    // v を1通り処理
} while (next_permutation(v.begin(), v.end()));

vector<vector<ll>> a(h, vector<ll>(w, 0));
vector<vector<long long>> dp(n, vector<long long>(m, INF));
vector<vector<vector<ll>>> g(x, vector<vector<ll>>(y, vector<ll>(z)));

// H x W のグリッドを時計回りに90度回転させる関数
vector<vector<ll>> rotate(const vector<vector<ll>>& a) {
    ll h = a.size(), w = a[0].size();
    vector<vector<ll>> res(w, vector<ll>(h));
    for (ll i = 0; i < h; ++i) {
        for (ll j = 0; j < w; ++j) {
            res[j][h - 1 - i] = a[i][j];
        }
    }
    return res;
}

// 90度時計回りに回転させた状態の (r, c) の値を取得
ll get_rotated_val(const vector<vector<ll>>& a, ll r, ll c, ll H, ll W) {
    // 元のグリッドのどの位置が (r, c) に来るかを計算
    return a[H - 1 - c][r];
}

set<ll> st;

// insert: 要素追加
st.insert(10);
st.insert(5);

// find: 探索（なければ end()）
auto it = st.find(10);

// erase: 削除（値 or iterator）
st.erase(10);

// size: setの大きさ取得
st.size();

// lower_bound: 以上で最小の要素
auto lb = st.lower_bound(7);

// 最小・最大
ll mn = *st.begin();
ll mx = *st.rbegin();

// イテレータが指す場所を削除し、次のイテレータを返す
it = st.erase(it);

multiset<ll> mst;

mst.insert(5);
mst.insert(5);
mst.insert(2);

// 1個だけ消す（重要）
mst.erase(mst.find(5));

// 全削除はこれ
mst.erase(5);

map<string, ll> mp;
mp["apple"]++;
mp["banana"] = 3;

if (mp.count("apple")) {
    // 存在確認
}

for (auto &[key, value] : mp) {
    // 昇順に巡回
}

unordered_map<long long, ll> ump;
ump[123456789LL]++;

unordered_set<string> us;
us.insert("alpha");

if (st.count(x)) { /* 存在 */ }

auto it = mp.find(key);
if (it != mp.end()) {
    // it->second を使う
}

if (us.contains("hello")) {
    // C++20
}

// ===== stack =====
stack<ll> st;

st.push(10);      // 要素を追加
st.push(20);

ll x = st.top(); // 一番上を見る（20）
st.pop();         // 一番上を削除

bool empty = st.empty(); // 空か判定
size_t sz = st.size();   // 要素数

// ===== queue =====
queue<ll> q;

q.push(10);        // 後ろに追加
q.push(20);

ll front = q.front(); // 先頭を見る（10）
q.pop();               // 先頭を削除

bool empty2 = q.empty();
size_t sz2 = q.size();

// ===== deque =====
deque<ll> dq;

dq.push_front(10); // 前に追加
dq.push_back(20);  // 後ろに追加

ll first = dq.front(); // 先頭
ll last  = dq.back();  // 末尾

dq.pop_front();    // 前を削除
dq.pop_back();     // 後ろを削除

priority_queue<ll> pq; // 最大ヒープ
pq.push(3);
pq.push(10);
ll mx = pq.top();
pq.pop();

priority_queue<ll, vector<ll>, greater<ll>> minpq; // 最小ヒープ

ll x = 1 << 3;     // 8
bool on = (mask & (1 << i)) != 0;
mask |= (1 << i);    // 立てる
mask ^= (1 << i);    // 反転
mask &= ~(1 << i);   // 落とす

ull reverse_bits(ull val, ll length) {
    ull result = 0;
    for (ll i = 0; i < length; ++i) {
        result = (result << 1) | (val & 1);
        val >>= 1;
    }
    return result;
}

// 1. bitsetの宣言と初期化の例
std::bitset<8> bs1;           // 00000000 (すべて0で初期化)
std::bitset<8> bs2(13);       // 00001101 (整数から初期化)
std::bitset<8> bs3("10110");  // 00010110 (文字列から初期化。右詰めで入る)

// 2. 提示された基本操作の具体例
std::bitset<1000> bs;          // すべて0の1000桁のビット列

bs.set(3);                     // 3番目のビットを1にする   -> bs[3]が1になる
bs.reset(3);                   // 3番目のビットを0に戻す   -> bs[3]が0になる

bool ok = bs.test(3);          // 3番目のビットの状態を取得 -> 0なのでfalse
                               // ※境界チェックのない bs[3] も使用可能

bs.flip();                     // 全てのビットを反転する   -> 全て1になる
bs.flip(3);                    // 3番目のビットだけ反転する -> 1から0になる

// 3. 状態を確認する便利な関数の例
bool any_one = bs.any();       // 1つのビットでも1があればtrue
bool all_zero = bs.none();     // 全てのビットが0ならtrue
bool all_one = bs.all();       // 全てのビットが1ならtrue
size_t num_one = bs.count();   // 1になっているビットの個数を数える (popcountと同じ)

// 4. ビット演算の一括処理例
std::bitset<8> target1("1100");
std::bitset<8> target2("1010");

std::bitset<8> res_and = target1 & target2; // 1000 (AND演算)
std::bitset<8> res_or  = target1 | target2; // 1110 (OR演算)
std::bitset<8> res_xor = target1 ^ target2; // 0110 (XOR演算)
std::bitset<8> res_shl = target1 << 2;      // 00110000 (左シフト)

// 5. 組み込み関数（GCC固有）による高速なビット演算の例
// ※bitsetオブジェクトではなく、通常の整数型(int, unsigned等)に対して使用します
ull x = 13; // 2進数表記で 1101

// __builtin_popcount: 立っている(1の)ビットの数を数える
ll cnt = __builtin_popcount((unsigned)x); 
// 1101 には 1 が3つあるため、cnt = 3 となる

// __builtin_ctz: 末尾(右側)に連続する0の数を数える
// ※ x != 0 が必要（0を渡すと未定義動作）
ll tz = __builtin_ctz((unsigned)x); 
// 1101 は末尾が1（0が連続していない）ため、tz = 0 となる
// 仮に x = 4 (100) であれば、右側に0が2つあるため tz = 2 となる

long long g = gcd(a, b);
long long l = a / gcd(a, b) * b;

ll isqrt(ll x) {
    if (x <= 0) return 0;
    ll res = sqrt(x);
    while ((res + 1) * (res + 1) <= x) res++;
    while (res * res > x) res--;
    return res;
}

#include <vector>
using namespace std;
using ll = long long;

struct Matrix {
    vector<vector<ll>> mat;
    
    // コンストラクタ (r行c列の0行列)
    Matrix(int r, int c) : mat(r, vector<ll>(c, 0)) {}
    
    int h() const { return mat.size(); }
    int w() const { return mat[0].size(); }
    
    // 行列の積
    Matrix operator*(const Matrix& a) const {
        int n = h(), m = a.w(), l = w();
        Matrix res(n, m);
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < l; k++) {
                for (int j = 0; j < m; j++) {
                    res.mat[i][j] += mat[i][k] * a.mat[k][j];
                    // res.mat[i][j] %= MOD; // ※MODが必要な場合はここを有効化
                }
            }
        }
        return res;
    }
    
    // 累乗 (A^k)
    Matrix pow(ll k) const {
        int n = h();
        Matrix res(n, n);
        for (int i = 0; i < n; i++) res.mat[i][i] = 1; // 単位行列
        Matrix x = *this;
        while (k > 0) {
            if (k & 1) res = res * x;
            x = x * x;
            k >>= 1;
        }
        return res;
    }
};

#include <atcoder/math>
using namespace std;
using namespace atcoder;
using ll = long long;

int main() {
    ll n = 10;
    ll m = 3;
    ll a = 2;
    ll b = 1;
    
    // sum_{i=0}^{n-1} floor((a*i + b) / m) を計算
    // 例: i=0 -> floor(1/3)=0, i=1 -> floor(3/3)=1, ...
    ll ans = floor_sum(n, m, a, b);
    
    return 0;
}

long long norm(long long x, long long mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

long long powll(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r *= a;
        a *= a;
        e >>= 1;
    }
    return r;
}

long long modpow(long long a, long long e, long long mod) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % mod;
        a = a * a % mod;
        e >>= 1;
    }
    return r;
}

template <typename T, typename F>
T power(T a, long long e, T identity, F op) {
    T res = identity;
    while (e > 0) {
        if (e & 1) res = op(res, a);
        a = op(a, a);
        e >>= 1;
    }
    return res;
}

vector<vector<ll>> C;

// mx: 必要な最大値（Nなど）, mod: 割る数（0の場合はmodをとらない）
void init_nCr(ll mx, ll mod = 0) {
    C.assign(mx + 1, vector<ll>(mx + 1, 0));
    for (ll i = 0; i <= mx; i++) {
        C[i][0] = 1;
        for (ll j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            if (mod > 0) C[i][j] %= mod;
        }
    }
}

// 組合せ nCr
ll nCr(ll n, ll r) {
    if (n < 0 || r < 0 || r > n) return 0;
    return C[n][r];
}

// 順列 nPr (※modなしの場合、nが20を超えると階乗がオーバーフローするため注意)
ll nPr(ll n, ll r, ll mod = 0) {
    if (n < 0 || r < 0 || r > n) return 0;
    ll res = 1;
    for (ll i = 0; i < r; i++) {
        res *= (n - i);
        if (mod > 0) res %= mod;
    }
    return res;
}

// 重複組合せ nHr
ll nHr(ll n, ll r) {
    if (n == 0 && r == 0) return 1;
    if (n <= 0 || r < 0) return 0;
    return nCr(n + r - 1, r);
}


// 使用例
int main() {
    // パターン1: modなしの場合 (N <= 60 程度まで)
    ll max_n_no_mod = 60; 
    init_nCr(max_n_no_mod, 0); 
    cout << "60C30 = " << nCr(60, 30) << "\n"; // 118264581564861424

    // パターン2: 任意のmod（非素数など）の場合 (N <= 5000 程度まで)
    ll mod = 100000; // 素数ではないmodの例
    ll max_n_mod = 5000;
    init_nCr(max_n_mod, mod);
    cout << "5000C2500 mod 100000 = " << nCr(5000, 2500) << "\n";
    
    return 0;
}

vector<long long> fact, fact_inv;

// mx: 必要な最大値（Nなど）, mod: 割る数（素数前提）
void init_nCr(ll mx, long long mod) {
    fact.assign(mx + 1, 1);
    fact_inv.assign(mx + 1, 1);
    vector<long long> inv(mx + 1, 1);
    for (ll i = 2; i <= mx; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

// 階乗 n!
long long get_fact(ll n) {
    if (n < 0) return 0;
    return fact[n];
}

// 階乗の逆元 (n!)^-1
long long get_fact_inv(ll n) {
    if (n < 0) return 0;
    return fact_inv[n];
}

// 組合せ nCr
long long nCr(ll n, ll r, long long mod) {
    if (r < 0 || r > n) return 0;
    return fact[n] * fact_inv[r] % mod * fact_inv[n - r] % mod;
}

// 順列 nPr
long long nPr(ll n, ll r, long long mod) {
    if (r < 0 || r > n) return 0;
    return fact[n] * fact_inv[n - r] % mod;
}

// 重複組合せ nHr
long long nHr(ll n, ll r, long long mod) {
    if (n == 0 && r == 0) return 1;
    if (n <= 0 || r < 0) return 0;
    return nCr(n + r - 1, r, mod);
}


//使用例
ll main() {
    long long mod = 1000000007;
    ll max_n = 200000; // 問題内で登場する最大の N

    // 1. クエリを呼ぶ前に必ず一度だけ前計算を走らせる
    init_nCr(max_n, mod);

    // 2. 必要なタイミングで各種関数を呼び出す (各 O(1))
    long long f5 = get_fact(5);         // 5! = 120
    long long fi5 = get_fact_inv(5);    // (5!)^-1 mod 1000000007
    long long ans1 = nCr(10, 3, mod);   // 10C3 = 120

    cout << "5! = " << f5 << endl;
    cout << "(5!)^-1 mod 10^9+7 = " << fi5 << endl;
    cout << "10C3 = " << ans1 << endl;
}

#include <atcoder/all>
int main() {

    // ===== 初期化 =====
    mint a = 3;
    mint b(5);

    // ===== 四則演算 =====
    mint c = a + b;
    mint d = a - b;
    mint e = a * b;
    mint f = a / b;      // b の逆元を掛ける

    // ===== int や long long と混ぜてもOK =====
    mint x = 10;

    x += 5;
    x -= 2;
    x *= 7;
    x /= 3;

    // ===== 累乗・逆元 =====
    mint p = x.pow(10);  // x^10
    mint inv = x.inv();  // x^{-1}

    // ===== 値の取り出し =====
    cout << x.val() << endl;

    // ===== 配列でも使える =====
    vector<mint> dp(100);

    // ===== 期待値などの分数 =====
    int N = 5;
    mint invN = mint(1) / N; // 1/N (mod)

    mint ans = mint(2) / 3;  // 2/3 (mod)

    // ===== よくある書き方 =====
    ans += mint(100) * invN;
}

// a と m が互いに素なとき、a * x ≡ 1 (mod m) となる x を返す
long long mod_inv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

vector<pair<long long, ll>> prime_factorize(long long n) {
    vector<pair<long long, ll>> res;

    for (long long p = 2; p * p <= n; p++) {
        if (n % p != 0) continue;

        ll cnt = 0;
        while (n % p == 0) {
            n /= p;
            cnt++;
        }
        res.push_back({p, cnt});
    }

    if (n > 1) res.push_back({n, 1});

    return res;
}

vector<long long> enumerate_divisors(long long n) {
    vector<long long> res;

    for (long long i = 1; i * i <= n; i++) {
        if (n % i != 0) continue;

        res.push_back(i);
        // 重複しない場合のみ、ペアとなる約数も追加
        if (i * i != n) {
            res.push_back(n / i);
        }
    }

    // 小さい順に並び替える
    sort(res.begin(), res.end());
    
    return res;
}

struct Sieve {
    vector<ll> min_factor;
    vector<ll> primes;

    Sieve(ll n) : min_factor(n + 1) {
        for (ll i = 0; i <= n; i++) min_factor[i] = i;
        for (ll i = 2; i * i <= n; i++) {
            if (min_factor[i] == i) {
                for (ll j = i * i; j <= n; j += i) {
                    if (min_factor[j] == j) {
                        min_factor[j] = i;
                    }
                }
            }
        }
        for (ll i = 2; i <= n; i++) {
            if (min_factor[i] == i) primes.push_back(i);
        }
    }

    bool is_prime(ll x) const {
        if (x < 2) return false;
        return min_factor[x] == x;
    }

    vector<pair<ll, ll>> factor(ll x) const {
        vector<pair<ll, ll>> res;
        while (x > 1) {
            ll p = min_factor[x];
            ll cnt = 0;
            while (x % p == 0) {
                x /= p;
                cnt++;
            }
            res.push_back({p, cnt});
        }
        return res;
    }
};

ll main() {
    // 1. まず、探索したい最大値（N）を指定して、篩（構造体）を初期化する
    // ※この時点で、1から1000000までの「最小の素因数（SPF）」がすべて計算されます（前処理）
    Sieve sieve(1000000);

    // 2. 素数判定 (is_prime) の使い方
    cout << sieve.is_prime(53) << endl;   // 1 (true)
    cout << sieve.is_prime(100) << endl;  // 0 (false)

    // 3. 高速素因数分解 (factor) の使い方
    // 例として「24」を素因数分解する (24 = 2^3 * 3^1)
    auto res1 = sieve.factor(24);
    cout << "24の素因数分解: ";
    for (auto p : res1) {
        cout << p.first << "^" << p.second << " ";
    }
    cout << endl; // 出力: 2^3 3^1

    // 例として「9973（素数）」を素因数分解する
    auto res2 = sieve.factor(9973);
    cout << "9973の素因数分解: ";
    for (auto p : res2) {
        cout << p.first << "^" << p.second << " ";
    }
    cout << endl; // 出力: 9973^1

    // 4. 列挙された素数リスト (primes) の使い方
    // 1000000以下の素数の個数を出力してみる
    cout << "1000000以下の素数の数: " << sieve.primes.size() << endl;

    return 0;
}

// 拡張ユークリッド互除法: g = gcd(a, b), ax + by = g となる (g, x) を返す
pair<long long, long long> inv_gcd(long long a, long long b) {
    a = (a % b + b) % b;
    if (a == 0) return {b, 0};
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;
    while (t) {
        long long u = s / t;
        s -= t * u;
        swap(s, t);
        m0 -= m1 * u;
        swap(m0, m1);
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

// 複数条件 x ≡ r_i (mod m_i) を満たす x ≡ rem (mod mod) を求める
// 解が存在しない場合は {0, 0} を返す
pair<long long, long long> CRT(const vector<long long>& r, const vector<long long>& m) {
    assert(r.size() == m.size());
    int n = r.size();
    long long r0 = 0, m0 = 1;

    for (int i = 0; i < n; ++i) {
        assert(m[i] >= 1);
        long long r1 = (r[i] % m[i] + m[i]) % m[i];
        long long m1 = m[i];

        if (m0 < m1) {
            swap(r0, r1);
            swap(m0, m1);
        }
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }

        auto [g, im] = inv_gcd(m0, m1);
        long long u1 = m1 / g;
        if ((r1 - r0) % g != 0) return {0, 0};

        long long x = (r1 - r0) / g % u1;
        if (x < 0) x += u1;
        x = (long long)((__int128_t)x * im % u1);

        r0 += x * m0;
        m0 *= u1;
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}

const double PI = acos(-1.0);

// degree → radian
double rad = deg * PI / 180.0;

// radian → degree
double deg = rad * 180.0 / PI;

double x = cos(rad);
double y = sin(rad);

double t = tan(rad);

// 点 (x, y) の偏角 (-pi ~ pi)
double angle = atan2(y, x);

double theta1 = acos(x);
double theta2 = asin(x);
double theta3 = atan(x);

// degree 表示
double deg = acos(x) * 180.0 / PI;

double dx = x2 - x1;
double dy = y2 - y1;

double dist = hypot(dx, dy);
// sqrt(dx * dx + dy * dy) と同等

const double EPS = 1e-9;

bool equal(double a, double b) {
    return fabs(a - b) < EPS;
}

struct Point {
    long long x, y;
};

// 座標の上下左右の半平面（領域）を判定する関数
// [ -pi, pi ) の範囲を扱い、下半平面を先行させる例
int get_zone(const Point& p) {
    if (p.x == 0 && p.y == 0) return 0;
    if (p.y < 0) return -1; // 下半平面 (y < 0)
    if (p.y > 0) return 1;  // 上半平面 (y > 0)
    if (p.x > 0) return -1; // 正のx軸 (y == 0, x > 0)
    return 1;               // 負のx軸 (y == 0, x < 0)
}

// 偏角ソート用の比較関数
bool compare_angle(const Point& a, const Point& b) {
    int zone_a = get_zone(a);
    int zone_b = get_zone(b);
    if (zone_a != zone_b) {
        return zone_a < zone_b;
    }
    // 同じ半平面内にある場合は外積で判定
    // 外積 (a.x * b.y - a.y * b.x) > 0 ならば、aから見てbが左側（反時計回り側）にある
    long long cross_product = a.x * b.y - a.y * b.x;
    if (cross_product != 0) {
        return cross_product > 0;
    }
    // 偏角が同じ場合は、原点からの距離（等、任意の基準）でタイブレーク
    return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
}

// 使用例
    sort(points.begin(), points.end(), compare_angle);
    auto it = lower_bound(points.begin(), points.end(), target, compare_angle);

// 2D座標の構造体
struct Point {
    long long x, y;
};

// ベクトルの引き算
Point operator-(const Point& a, const Point& b) {
    return {a.x - b.x, a.y - b.y};
}

// 外積 (Cross Product)
long long cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

// 内積 (Dot Product)
long long dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y;
}

// CCW: 線分 ab に対する 点 c の位置関係を返す
// 戻り値:
//  1: a → b に対して c が反時計回り (左折)
// -1: a → b に対して c が時計回り (右折)
//  2: c - a - b の順で同一直線上
// -2: a - b - c の順で同一直線上
//  0: a - c - b の順で同一直線上 (線分 ab 上に c がある)
int ccw(Point a, Point b, Point c) {
    Point ab = b - a;
    Point ac = c - a;
    
    long long cr = cross(ab, ac);
    if (cr > 0) return 1;       // 反時計回り
    if (cr < 0) return -1;      // 時計回り
    
    // 以下は同一直線上 (cr == 0) の場合
    if (dot(ab, ac) < 0) return 2;  // cがaの反対側にある
    if (dot(ab, ab) < dot(ac, ac)) return -2; // cがbの先にある
    return 0; // cが線分ab上にある (a == c, b == c の場合も含む)
}

// GCD (最大公約数)
long long gcd(long long a, long long b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    return b == 0 ? a : gcd(b, a % b);
}

// 有理数 (分数) 構造体
struct Fraction {
    long long num, den; // 分子(numerator), 分母(denominator)

    Fraction(long long n = 0, long long d = 1) {
        if (d < 0) { n = -n; d = -d; } // 分母は常に正にする
        long long g = gcd(n, d);
        num = n / g;
        den = d / g;
    }

    // 比較演算子 (オーバーフロー防止のため __int128_t を使用)
    bool operator==(const Fraction& o) const { return num == o.num && den == o.den; }
    bool operator!=(const Fraction& o) const { return !(*this == o); }
    bool operator<(const Fraction& o) const {
        return (__int128_t)num * o.den < (__int128_t)o.num * den;
    }
    bool operator<=(const Fraction& o) const { return *this < o || *this == o; }
    bool operator>(const Fraction& o) const { return o < *this; }
    bool operator>=(const Fraction& o) const { return o <= *this; }
};

#include <cmath>

// CCW,Fractionを事前に導入しておく必要がある

struct Line {
    long long a, b, c; // ax + by + c = 0

    // a, b, c から直線を生成 (正規化)
    Line(long long a_, long long b_, long long c_) {
        long long g = gcd(gcd(a_, b_), c_);
        a = a_ / g; b = b_ / g; c = c_ / g;
        // 一意性を保つため、aが負、または「a=0かつbが負」の場合は符号を反転
        if (a < 0 || (a == 0 && b < 0)) {
            a = -a; b = -b; c = -c;
        }
    }

    // 2点 p1, p2 を通る直線
    Line(Point p1, Point p2) {
        long long a_ = p2.y - p1.y;
        long long b_ = p1.x - p2.x;
        long long c_ = p2.x * p1.y - p1.x * p2.y;
        *this = Line(a_, b_, c_);
    }

    bool operator<(const Line& o) const {
        if (a != o.a) return a < o.a;
        if (b != o.b) return b < o.b;
        return c < o.c;
    }
    bool operator==(const Line& o) const {
        return a == o.a && b == o.b && c == o.c;
    }
};

// ---------------- 作図・生成系 ----------------

// 2点の垂直二等分線を生成
Line perpendicular_bisector(Point p1, Point p2) {
    long long a = 2 * (p2.x - p1.x);
    long long b = 2 * (p2.y - p1.y);
    long long c = (p1.x * p1.x - p2.x * p2.x) + (p1.y * p1.y - p2.y * p2.y);
    return Line(a, b, c);
}

// 直線lと平行で、点pを通る直線を生成
Line parallel_line(const Line& l, Point p) {
    return Line(l.a, l.b, -(l.a * p.x + l.b * p.y));
}

// 直線lと垂直で、点pを通る直線を生成
Line perpendicular_line(const Line& l, Point p) {
    return Line(-l.b, l.a, l.b * p.x - l.a * p.y);
}

// ---------------- 判定系 ----------------

// 平行判定 (外積が0)
bool is_parallel(const Line& l1, const Line& l2) {
    return l1.a * l2.b - l1.b * l2.a == 0;
}

// 直交判定 (内積が0)
bool is_orthogonal(const Line& l1, const Line& l2) {
    return l1.a * l2.a + l1.b * l2.b == 0;
}

// 交差判定 (平行でない、または同一の直線である)
bool is_intersect(const Line& l1, const Line& l2) {
    return !is_parallel(l1, l2) || (l1 == l2);
}

// ---------------- 座標・距離計算系 ----------------

// 2直線の交点を Fraction (有理数) のペアで返す
// ※事前に is_parallel(l1, l2) が false であることを確認すること
pair<Fraction, Fraction> intersection(const Line& l1, const Line& l2) {
    long long det = l1.a * l2.b - l1.b * l2.a;
    long long x_num = l1.b * l2.c - l2.b * l1.c;
    long long y_num = l2.a * l1.c - l1.a * l2.c;
    return {Fraction(-x_num, det), Fraction(-y_num, det)};
}

// 点pから直線lに下ろした垂線の足 (Fraction のペア)
pair<Fraction, Fraction> foot_of_perpendicular(const Line& l, Point p) {
    Line perp = perpendicular_line(l, p);
    return intersection(l, perp);
}

// 点pと直線lの距離 (ここだけ double を返す)
double distance(const Line& l, Point p) {
    return abs(l.a * p.x + l.b * p.y + l.c) / sqrt(l.a * l.a + l.b * l.b);
}

#include <vector>
#include <algorithm>
#include <map>

// 直線の傾きを一意に表すキー (a, b を gcd(a,b) で割って最小約分したペア)
// ※平行な直線はすべて同じキーを返す
pair<long long, long long> get_slope_key(const Line& l) {
    long long g = gcd(l.a, l.b);
    return {l.a / g, l.b / g};
}

// 1. 数値としての傾き m = -a/b (-∞ < m <= +∞) でソートする比較関数
// 順序: 負の傾き (例: -2) < 水平(0) < 正の傾き (例: +3) < 垂直(+∞)
bool compare_by_slope(const Line& l1, const Line& l2) {
    // 垂直線 (b == 0) は傾き +∞ とみなす
    if (l1.b == 0 && l2.b == 0) return l1 < l2; // 傾きが同じなら Line の < 演算子で安定化
    if (l1.b == 0) return false; // l1 が +∞
    if (l2.b == 0) return true;  // l2 が +∞

    // -a1 / b1 < -a2 / b2 の比較 (分母を正にして分子×分母で比較)
    long long n1 = -l1.a, d1 = l1.b;
    if (d1 < 0) { n1 = -n1; d1 = -d1; }
    
    long long n2 = -l2.a, d2 = l2.b;
    if (d2 < 0) { n2 = -n2; d2 = -d2; }

    __int128_t val1 = (__int128_t)n1 * d2;
    __int128_t val2 = (__int128_t)n2 * d1;

    if (val1 != val2) return val1 < val2;
    return l1 < l2; // 傾きが同じ場合は定数項(切片)順でソート
}

// 2. 偏角 [0, π) 順でソートする比較関数 (x軸正の向きからの回転角)
// 順序: 水平(0°) -> 鋭角(例: 45°) -> 垂直(90°) -> 鈍角(例: 135°)
bool compare_by_angle(const Line& l1, const Line& l2) {
    auto get_zone = [](const Line& l) {
        if (l.b == 0) return 1; // 垂直 [90°]
        if (l.b < 0 || (l.a == 0 && l.b > 0)) return 0; // [0°, 90°) : 水平または正の傾き
        return 2; // (90°, 180°) : 負の傾き
    };

    int z1 = get_zone(l1);
    int z2 = get_zone(l2);
    if (z1 != z2) return z1 < z2;
    return compare_by_slope(l1, l2);
}

// 3. 平行な直線（同じ傾きを持つ直線）ごとにグループ化する
map<pair<long long, long long>, vector<Line>> group_by_slope(const vector<Line>& lines) {
    map<pair<long long, long long>, vector<Line>> res;
    for (const auto& l : lines) {
        res[get_slope_key(l)].push_back(l);
    }
    return res;
}

#include <cmath>
#include <vector>

// CCW,FractionとLineがあると動作する

// 浮動小数点で座標を扱うための構造体
struct PointF {
    long double x, y;
};

// 円の構造体
struct Circle {
    Point c;     // 中心座標 (整数)
    long long r; // 半径 (整数)
};

// 2円の位置関係 (共通接線の数を返す)
// 5: 同一の円, 4: 離れている, 3: 外接する, 2: 交わる, 1: 内接する, 0: 内包する
int circle_relation(Circle c1, Circle c2) {
    long long dx = c1.c.x - c2.c.x;
    long long dy = c1.c.y - c2.c.y;
    long long d2 = dx * dx + dy * dy; // 中心間の距離の2乗
    
    if (d2 == 0 && c1.r == c2.r) return 5;

    long long r_add = (c1.r + c2.r) * (c1.r + c2.r);
    long long r_sub = (c1.r - c2.r) * (c1.r - c2.r);
    
    if (d2 > r_add) return 4;
    if (d2 == r_add) return 3;
    if (d2 > r_sub) return 2;
    if (d2 == r_sub) return 1;
    return 0;
}

// 円と直線の交点 (0個, 1個(接点), または2個の PointF を返す)
vector<PointF> intersection(const Circle& c, const Line& l) {
    long double a = l.a, b = l.b, cc = l.c;
    long double cx = c.c.x, cy = c.c.y;
    long double d_den = a * a + b * b;
    
    // 中心から直線に下ろした垂線の足 (x0, y0)
    long double x0 = (b * (b * cx - a * cy) - a * cc) / d_den;
    long double y0 = (a * (a * cy - b * cx) - b * cc) / d_den;

    long double d2 = (cx - x0) * (cx - x0) + (cy - y0) * (cy - y0);
    long double r2 = (long double)c.r * c.r;

    // 誤差を考慮 (EPS = 1e-9)
    if (d2 > r2 + 1e-9) return {}; // 交点なし
    if (abs(d2 - r2) < 1e-9) return {{x0, y0}}; // 接する (1点)

    // 三平方の定理で交点までのオフセット距離を計算
    long double w = sqrt(max((long double)0.0, r2 - d2));
    long double len = sqrt(d_den);
    long double dx = (b / len) * w;
    long double dy = (-a / len) * w;
    
    return {{x0 + dx, y0 + dy}, {x0 - dx, y0 - dy}};
}

// 円と円の交点 (0個, 1個(接点), または2個の PointF を返す)
vector<PointF> intersection(Circle c1, Circle c2) {
    int rel = circle_relation(c1, c2);
    
    if (rel == 5 || rel == 4 || rel == 0) return {}; // 交点なし

    long double cx1 = c1.c.x, cy1 = c1.c.y;
    long double cx2 = c2.c.x, cy2 = c2.c.y;
    long double d = sqrt((cx1 - cx2) * (cx1 - cx2) + (cy1 - cy2) * (cy1 - cy2));
    
    // c1の中心から交線を結ぶ弦の中点までの距離 a
    long double a = (c1.r * c1.r - c2.r * c2.r + d * d) / (2.0 * d);
    long double h = sqrt(max((long double)0.0, (long double)c1.r * c1.r - a * a));
    
    // 弦の中点
    long double px = cx1 + a / d * (cx2 - cx1);
    long double py = cy1 + a / d * (cy2 - cy1);
    
    if (rel == 1 || rel == 3) return {{px, py}}; // 接する (1点)
    
    // 中点からのオフセットベクトル
    long double dx = -h / d * (cy2 - cy1);
    long double dy =  h / d * (cx2 - cx1);
    
    return {{px + dx, py + dy}, {px - dx, py - dy}};
}

#include <cmath>
#include <algorithm>

// CCW,Line,Fractionが必要

// 2点間の距離 (整数座標版)
long double dist(Point a, Point b) {
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

// 2点間の距離 (浮動小数点座標版)
long double distF(PointF a, PointF b) {
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

// 面積 (外積の半分なので、絶対値をとり2で割る)
long double triangle_area(Point a, Point b, Point c) {
    return abs(cross(b - a, c - a)) / 2.0;
}

// 重心 (Centroid) : 3頂点の平均
PointF centroid(Point a, Point b, Point c) {
    return {(a.x + b.x + c.x) / 3.0, (a.y + b.y + c.y) / 3.0};
}

// 内心 (Incenter) と 内接円の半径
// 戻り値: {内心の座標, 内接円の半径}
pair<PointF, long double> incircle(Point a, Point b, Point c) {
    long double la = dist(b, c), lb = dist(c, a), lc = dist(a, b);
    long double peri = la + lb + lc;
    PointF incenter = {
        (la * a.x + lb * b.x + lc * c.x) / peri,
        (la * a.y + lb * b.y + lc * c.y) / peri
    };
    long double r = 2.0 * triangle_area(a, b, c) / peri;
    return {incenter, r};
}

// 傍心 (Excenter) - 頂点Aの向かい側にある傍心のみ例示
// 用途は少ないが、内心の公式の la を -la に変えるだけで求まる
PointF excenterA(Point a, Point b, Point c) {
    long double la = dist(b, c), lb = dist(c, a), lc = dist(a, b);
    long double peri = -la + lb + lc;
    return {
        (-la * a.x + lb * b.x + lc * c.x) / peri,
        (-la * a.y + lb * b.y + lc * c.y) / peri
    };
}

// 外心 (Circumcenter) と 外接円の半径
// 戻り値: {外心の座標, 外接円の半径}
pair<PointF, long double> circumcircle(Point a, Point b, Point c) {
    long double d = 2.0 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
    long double a2 = a.x * a.x + a.y * a.y;
    long double b2 = b.x * b.x + b.y * b.y;
    long double c2 = c.x * c.x + c.y * c.y;
    
    PointF circumcenter = {
        (a2 * (b.y - c.y) + b2 * (c.y - a.y) + c2 * (a.y - b.y)) / d,
        (a2 * (c.x - b.x) + b2 * (a.x - c.x) + c2 * (b.x - a.x)) / d
    };
    long double r = distF({(long double)a.x, (long double)a.y}, circumcenter);
    return {circumcenter, r};
}

// 垂心 (Orthocenter)
// オイラー線 (H = 3G - 2O) を利用して高速計算
PointF orthocenter(Point a, Point b, Point c) {
    PointF g = centroid(a, b, c);
    PointF o = circumcircle(a, b, c).first;
    return {3.0 * g.x - 2.0 * o.x, 3.0 * g.y - 2.0 * o.y};
}

// Fermat点 (3頂点からの距離の和が最小になる点) と その距離の和
// 幾何的解法ではなく Weiszfeld のアルゴリズム(反復法)で解く実戦的実装
pair<PointF, long double> fermat_point(Point a, Point b, Point c) {
    PointF p = centroid(a, b, c); // 重心を初期値とする
    PointF pa = {(long double)a.x, (long double)a.y};
    PointF pb = {(long double)b.x, (long double)b.y};
    PointF pc = {(long double)c.x, (long double)c.y};
    
    // 100回程度反復すれば long double の精度上限付近まで収束する
    for (int i = 0; i < 100; ++i) {
        long double da = max((long double)1e-12, distF(p, pa));
        long double db = max((long double)1e-12, distF(p, pb));
        long double dc = max((long double)1e-12, distF(p, pc));
        p.x = (pa.x/da + pb.x/db + pc.x/dc) / (1.0/da + 1.0/db + 1.0/dc);
        p.y = (pa.y/da + pb.y/db + pc.y/dc) / (1.0/da + 1.0/db + 1.0/dc);
    }
    
    long double sum_dist = distF(p, pa) + distF(p, pb) + distF(p, pc);
    return {p, sum_dist};
}

#include <vector>
#include <algorithm>

// CCW,Fractionが必要

// Point構造体にソート用の比較演算子を追加 (x優先、次にy)
bool operator<(const Point& a, const Point& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

// 凸包を求める (反時計回りに頂点のリストを返す)
vector<Point> convex_hull(vector<Point> p) {
    int n = p.size();
    if (n <= 2) return p;
    
    sort(p.begin(), p.end()); // 辞書順ソート
    vector<Point> qs;
    
    // 下側凸包の構築
    for (int i = 0; i < n; i++) {
        // 直進 (ccw == 2, -2, 0) や右折 (ccw == -1) の場合はスタックから取り除く
        // ※辺上の点を含めたい場合は != 1 ではなく == -1 に変更する
        while (qs.size() > 1 && ccw(qs[qs.size()-2], qs.back(), p[i]) != 1) {
            qs.pop_back();
        }
        qs.push_back(p[i]);
    }
    
    int t = qs.size();
    // 上側凸包の構築 (右端から左端へ戻る)
    for (int i = n - 2; i >= 0; i--) {
        while (qs.size() > t && ccw(qs[qs.size()-2], qs.back(), p[i]) != 1) {
            qs.pop_back();
        }
        qs.push_back(p[i]);
    }
    
    qs.pop_back(); // 始点と終点が重複するため最後の1つを削除
    return qs;
}

#include <vector>
#include <random>
#include <algorithm>

// Triangle , CCW, Fraction, Line などが必要

// 2点を直径の対向とする円を生成
pair<PointF, long double> circle2(Point a, Point b) {
    PointF c = {(a.x + b.x) / 2.0, (a.y + b.y) / 2.0};
    return {c, distF(c, {(long double)a.x, (long double)a.y})};
}

// 最小包含円 (Welzl's Algorithm)
// 戻り値: {中心座標, 半径}
pair<PointF, long double> min_enclosing_circle(vector<Point> p) {
    if (p.empty()) return {{0.0, 0.0}, 0.0};
    if (p.size() == 1) return {{(long double)p[0].x, (long double)p[0].y}, 0.0};

    // 乱数で頂点順序をシャッフル (期待値O(N)にするための肝)
    mt19937 mt(1333); // 再現性のために固定シードを使用
    shuffle(p.begin(), p.end(), mt);

    // 初期円を最初の1点とする (半径0)
    pair<PointF, long double> c = {{(long double)p[0].x, (long double)p[0].y}, 0.0};

    for (int i = 1; i < p.size(); i++) {
        // 点 p[i] が現在の円の外側にある場合、円を更新
        if (distF(c.first, {(long double)p[i].x, (long double)p[i].y}) > c.second + 1e-9) {
            c = {{(long double)p[i].x, (long double)p[i].y}, 0.0}; // p[i] を中心とする半径0の円
            for (int j = 0; j < i; j++) {
                // 点 p[j] も外側にある場合、p[i] と p[j] を直径とする円に更新
                if (distF(c.first, {(long double)p[j].x, (long double)p[j].y}) > c.second + 1e-9) {
                    c = circle2(p[i], p[j]);
                    for (int k = 0; k < j; k++) {
                        // 点 p[k] も外側にある場合、3点を通る外接円に更新
                        if (distF(c.first, {(long double)p[k].x, (long double)p[k].y}) > c.second + 1e-9) {
                            c = circumcircle(p[i], p[j], p[k]);
                        }
                    }
                }
            }
        }
    }
    return c;
}

long long ng = -1;
long long ok = 1e18; // 条件を満たす十分大きな値

while (abs(ok - ng) > 1) { // ok - ng > 1 でも可
    long long mid = ng + (ok - ng) / 2;

    if (check(mid))
        ok = mid;
    else
        ng = mid;
}

long long ok = -1; // 条件を満たす十分小さな値
long long ng = 1e18;

while (abs(ok - ng) > 1) { // ng - ok > 1 でも可
    long long mid = ok + (ng - ok) / 2;

    if (check(mid))
        ok = mid;
    else
        ng = mid;
}

ll low = 0;
ll high = 1e18; // 探索範囲

while (high - low > 2) {
    ll m1 = low + (high - low) / 3;
    ll m2 = high - (high - low) / 3;

    if (f(m1) < f(m2)) // 上に凸（最大値探索）の場合は不等号を逆にする
        high = m2;
    else
        low = m1;
}

ll ans = low;
for (ll i = low + 1; i <= high; i++) {
    if (f(i) < f(ans)) ans = i; // 絞り込んだ範囲から全探索で最小を探す
}

ld low = 0.0;
ld high = 1e18; // 探索範囲
ll cnt = 100; // 許容誤差に応じた十分なループ回数

while (cnt--) {
    ld m1 = low + (high - low) / 3.0;
    ld m2 = high - (high - low) / 3.0;

    if (f(m1) < f(m2)) // 上に凸（最大値探索）の場合は不等号を逆にする
        high = m2;
    else
        low = m1;
}
// low または high が極値のx座標（必要なら f(low) が極値）

for (ll mask = 0; mask < (1 << N); mask++) {

    for (ll i = 0; i < N; i++) {
        if (mask & (1 << i)) {
            // 判定・計算をする
        }
    }
}

struct Mo {
    ll n;
    vector<pair<ll, ll>> lr;

    Mo(ll n) : n(n) {}

    // クエリを半開区間 [l, r) で追加
    void add_query(ll l, ll r) {
        lr.push_back({l, r});
    }

    // ヒルベルト曲線の順序を計算 (最大N, Qが10^6程度まで対応)
    static inline int64_t hilbert_order(ll x, ll y) {
        int64_t d = 0;
        for (ll s = 1 << 20; s > 0; s >>= 1) {
            ll rx = (x & s) > 0, ry = (y & s) > 0;
            d += (int64_t)(3 * rx ^ ry) * s * s;
            if (ry == 0) {
                if (rx == 1) {
                    x = (1 << 21) - 1 - x;
                    y = (1 << 21) - 1 - y;
                }
                swap(x, y);
            }
        }
        return d;
    }

    // 左端追加、右端追加、左端削除、右端削除、クエリ回答の関数を受け取る
    template<typename AL, typename AR, typename DL, typename DR, typename O>
    void build(AL add_left, AR add_right, DL del_left, DR del_right, O out) {
        ll q = lr.size();
        vector<int64_t> h_ord(q);
        for (ll i = 0; i < q; ++i) {
            h_ord[i] = hilbert_order(lr[i].first, lr[i].second);
        }

        vector<ll> ord(q);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](ll a, ll b) {
            return h_ord[a] < h_ord[b];
        });

        ll l = 0, r = 0;
        for (auto idx : ord) {
            // ※区間が反転しないよう「追加（区間を広げる）」を先に実行する
            while (l > lr[idx].first) add_left(--l);
            while (r < lr[idx].second) add_right(r++);
            while (l < lr[idx].first) del_left(l++);
            while (r > lr[idx].second) del_right(--r);
            out(idx);
        }
    }
};

struct HilbertOrder {
    ll lg;

    // 座標の取りうる範囲を [0, 2^lg) とする
    explicit HilbertOrder(ll n) {
        lg = 0;
        while ((1LL << lg) < n) ++lg;
    }

    // (x, y) をヒルベルト順序へ変換
    ll operator()(ll x, ll y) const {
        ll d = 0;

        for (ll s = 1LL << (lg - 1); s > 0; s >>= 1) {
            ll rx = (x & s) ? 1 : 0;
            ll ry = (y & s) ? 1 : 0;

            d += s * s * ((3 * rx) ^ ry);

            if (ry == 0) {
                if (rx == 1) {
                    x = (1LL << lg) - 1 - x;
                    y = (1LL << lg) - 1 - y;
                }
                swap(x, y);
            }
        }

        return d;
    }

    // 静的関数として直接使いたい場合
    static ll order(ll x, ll y, ll lg) {
        ll d = 0;

        for (ll s = 1LL << (lg - 1); s > 0; s >>= 1) {
            ll rx = (x & s) ? 1 : 0;
            ll ry = (y & s) ? 1 : 0;

            d += s * s * ((3 * rx) ^ ry);

            if (ry == 0) {
                if (rx == 1) {
                    x = (1LL << lg) - 1 - x;
                    y = (1LL << lg) - 1 - y;
                }
                swap(x, y);
            }
        }

        return d;
    }
};

// Union-Find の構造体
struct UnionFind {
    vector<ll> parent; // parent[i] は i の親要素。i が根（リーダー）の場合は -1
    vector<ll> siz;    // siz[i] は i を根とするグループの要素数

    // 構造体の初期化（要素数 N で作成）
    UnionFind(ll n) {
        parent.assign(n, -1); // 最初はみんな自分が根（-1）
        siz.assign(n, 1);     // 最初はみんなサイズ 1
    }

    // 1. Find: 要素 x の根（リーダー）を返す
    ll find(ll x) {
        if (parent[x] == -1) return x; // 自分が根なら自分を返す
        // 経路圧縮：親を「根」に直接繋ぎ変えながら再帰的に探す
        return parent[x] = find(parent[x]);
    }

    // 2. Union: 要素 x と要素 y のグループを合体させる
    bool unite(ll x, ll y) {
        // それぞれのリーダーを探す
        ll root_x = find(x);
        ll root_y = find(y);

        // すでに同じグループなら何もしない
        if (root_x == root_y) return false;

        // Union by Size: 小さい方を大きい方の下に合体させる
        if (siz[root_x] < siz[root_y]) {
            swap(root_x, root_y); // 常に root_x の方がサイズが大きくなるようにする
        }

        // root_y の親を root_x にする（root_x が新しいボス）
        parent[root_y] = root_x;
        siz[root_x] += siz[root_y]; // サイズを合算する
        return true;
    }

    // 3. Same: 要素 x と要素 y が同じグループに属するか判定
    bool same(ll x, ll y) {
        return find(x) == find(y);
    }

    // 4. Size: 要素 x が属するグループのサイズ（要素数）を返す
    ll size(ll x) {
        return siz[find(x)];
    }
};

// 重み付きUnion-Find の構造体
struct WeightedUnionFind {
    vector<ll> parent;      // parent[i] は i の親要素。i が根の場合は -1
    vector<ll> siz;         // siz[i] は i を根とするグループの要素数
    vector<ll> diff_weight; // 根からの距離（重み）

    // 構造体の初期化（要素数 N で作成）
    WeightedUnionFind(ll n) {
        parent.assign(n, -1);
        siz.assign(n, 1);
        diff_weight.assign(n, 0);
    }

    // 1. Find: 要素 x の根を返しつつ、経路圧縮で重みを更新
    ll find(ll x) {
        if (parent[x] == -1) return x;
        ll r = find(parent[x]);
        // 親の重みを足し合わせて根からの重みに更新
        diff_weight[x] += diff_weight[parent[x]];
        return parent[x] = r;
    }

    // 要素 x の根からの重みを返す
    ll weight(ll x) {
        find(x); // 経路圧縮を実行
        return diff_weight[x];
    }

    // 2. Relate: 要素 y が 要素 x より w 大きい (a_y - a_x = w) という情報で結合
    bool relate(ll x, ll y, ll w) {
        w += weight(x);
        w -= weight(y);
        ll root_x = find(x);
        ll root_y = find(y);

        if (root_x == root_y) return false;

        // Union by Size: 小さい方を大きい方に繋ぐ
        if (siz[root_x] < siz[root_y]) {
            swap(root_x, root_y);
            w = -w; // 繋ぐ方向が逆になるので重みも反転
        }

        parent[root_y] = root_x;
        siz[root_x] += siz[root_y];
        diff_weight[root_y] = w;
        return true;
    }

    // 3. Diff: 要素 x と 要素 y の差分 (a_y - a_x) を返す
    // ※事前に same(x, y) が true であるか確認すること
    ll diff(ll x, ll y) {
        return weight(y) - weight(x);
    }

    // 4. Same: 要素 x と要素 y が同じグループに属するか判定
    bool same(ll x, ll y) {
        return find(x) == find(y);
    }

    // 5. Size: 要素 x が属するグループのサイズ（要素数）を返す
    ll size(ll x) {
        return siz[find(x)];
    }
};

template <typename T>
struct SequenceTree {
    struct Node {
        T val;
        unsigned int pri;
        int cnt;
        Node *l, *r;
        Node(T v, unsigned int p) : val(v), pri(p), cnt(1), l(nullptr), r(nullptr) {}
    };

    Node* root;
    mt19937 mt;

    SequenceTree() : root(nullptr), mt(random_device{}()) {}

    int count(Node* t) { return t ? t->cnt : 0; }

    Node* update(Node* t) {
        if (t) t->cnt = count(t->l) + count(t->r) + 1;
        return t;
    }

    void split(Node* t, int k, Node*& l, Node*& r) {
        if (!t) { l = r = nullptr; return; }
        int c = count(t->l);
        if (k <= c) {
            split(t->l, k, l, t->l);
            r = update(t);
        } else {
            split(t->r, k - c - 1, t->r, r);
            l = update(t);
        }
    }

    Node* merge(Node* l, Node* r) {
        if (!l || !r) return l ? l : r;
        if (l->pri > r->pri) {
            l->r = merge(l->r, r);
            return update(l);
        } else {
            r->l = merge(l, r->l);
            return update(r);
        }
    }

    // pos番目に val を挿入 (0-indexed)
    void insert(int pos, T val) {
        Node *l, *r;
        split(root, pos, l, r);
        root = merge(merge(l, new Node(val, mt())), r);
    }

    // pos番目の要素を削除 (0-indexed)
    void erase(int pos) {
        Node *l, *m, *r;
        split(root, pos, l, r);
        split(r, 1, m, r);
        delete m;
        root = merge(l, r);
    }

    // pos番目の要素にアクセス (0-indexed)
    T get(int pos) {
        Node* t = root;
        while (t) {
            int c = count(t->l);
            if (pos == c) return t->val;
            if (pos < c) t = t->l;
            else { pos -= c + 1; t = t->r; }
        }
        throw out_of_range("Index out of bounds");
    }
    
    // 現在の要素数を返す
    int size() { return count(root); }
};

struct BIT {
    ll n;
    vector<long long> bit;
    BIT(ll n): n(n), bit(n + 1, 0) {}

    void add(ll idx, long long val) {
        for (++idx; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    long long sum(ll idx) { // [0, idx)
        long long s = 0;
        for (; idx > 0; idx -= idx & -idx) s += bit[idx];
        return s;
    }

    // 最小の idx (0-index) で sum(idx + 1) >= k を満たすものを返す
    // ※ bit に格納される値は非負であることが前提
    ll lower_bound(long long k) {
        if (k <= 0) return 0;

        ll idx = 0;
        ll pw = 1;
        while ((pw << 1) <= n) pw <<= 1;

        for (; pw > 0; pw >>= 1) {
            if (idx + pw <= n && bit[idx + pw] < k) {
                k -= bit[idx + pw];
                idx += pw;
            }
        }
        return idx;
    }
};

// 1. 型 S と、二項演算 op、単位元 e を定義する
ll op(ll a, ll b) { return max(a, b); }
ll e() { return -1e18; }

int main() {
    int N = 100000;
    
    // 2. 宣言 (初期値は全て e() になる)
    segtree<ll, op, e> seg(N);
    // vectorから構築する場合 O(N): segtree<ll, op, e> seg(vec);

    // 3. 点更新: p番目(0-indexed)の要素を x に更新
    seg.set(2, 15);

    // 4. 1点取得: p番目の要素を取得
    ll val = seg.get(2);

    // 5. 区間クエリ: [l, r) の演算結果を取得
    ll ans = seg.prod(0, 5);
    
    // 6. 全区間クエリ: [0, N) の演算結果を取得
    ll all_ans = seg.all_prod();
}

// 例：区間加算・区間最小値
using S = ll;
using F = ll;
const ll INF = 1e18;

S op(S a, S b) { return min(a, b); }
S e() { return INF; }
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; } // 既存のgの上に新しいfを適用
F id() { return 0; }

int main() {
    int N = 100000;
    
    // 宣言
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(N);
    // vectorから構築する場合 O(N): lazy_segtree<...> seg(vec);

    // 区間更新: [l, r) に作用素 x を適用
    seg.apply(0, 5, 10); // [0, 5) に 10 を加算
    
    // 1点更新: p番目に作用素 x を適用
    seg.apply(2, 5);

    // 区間クエリ: [l, r) の演算結果を取得
    ll ans = seg.prod(0, 5); // [0, 5) の最小値
}

class SegmentTreeBeats {
    static const long long INF = 1e18;
    int n, sz;
    vector max_v, smax_v, max_c;
    vector min_v, smin_v, min_c;
    vector sum, len, lazy_add;

    void update_node_max(int k, long long x) {
        sum[k] += (x - max_v[k]) * max_c[k];
        if (max_v[k] == min_v[k]) { max_v[k] = min_v[k] = x; }
        else if (max_v[k] == smin_v[k]) { max_v[k] = smin_v[k] = x; }
        else { max_v[k] = x; }
    }
    void update_node_min(int k, long long x) {
        sum[k] += (x - min_v[k]) * min_c[k];
        if (max_v[k] == min_v[k]) { max_v[k] = min_v[k] = x; }
        else if (smax_v[k] == min_v[k]) { min_v[k] = smax_v[k] = x; }
        else { min_v[k] = x; }
    }
    void update_node_add(int k, long long x) {
        max_v[k] += x; if (smax_v[k] != -INF) smax_v[k] += x;
        min_v[k] += x; if (smin_v[k] != INF) smin_v[k] += x;
        sum[k] += x * len[k]; lazy_add[k] += x;
    }
    void push(int k) {
        if (lazy_add[k] != 0) {
            update_node_add(2 * k + 1, lazy_add[k]);
            update_node_add(2 * k + 2, lazy_add[k]);
            lazy_add[k] = 0;
        }
        if (max_v[k] < max_v[2 * k + 1]) update_node_max(2 * k + 1, max_v[k]);
        if (max_v[k] < max_v[2 * k + 2]) update_node_max(2 * k + 2, max_v[k]);
        if (min_v[k] > min_v[2 * k + 1]) update_node_min(2 * k + 1, min_v[k]);
        if (min_v[k] > min_v[2 * k + 2]) update_node_min(2 * k + 2, min_v[k]);
    }
    void update(int k) {
        sum[k] = sum[2 * k + 1] + sum[2 * k + 2];
        if (max_v[2 * k + 1] < max_v[2 * k + 2]) {
            max_v[k] = max_v[2 * k + 2];
            max_c[k] = max_c[2 * k + 2];
            smax_v[k] = max(max_v[2 * k + 1], smax_v[2 * k + 2]);
        } else if (max_v[2 * k + 1] > max_v[2 * k + 2]) {
            max_v[k] = max_v[2 * k + 1];
            max_c[k] = max_c[2 * k + 1];
            smax_v[k] = max(smax_v[2 * k + 1], max_v[2 * k + 2]);
        } else {
            max_v[k] = max_v[2 * k + 1];
            max_c[k] = max_c[2 * k + 1] + max_c[2 * k + 2];
            smax_v[k] = max(smax_v[2 * k + 1], smax_v[2 * k + 2]);
        }
        if (min_v[2 * k + 1] < min_v[2 * k + 2]) {
            min_v[k] = min_v[2 * k + 1];
            min_c[k] = min_c[2 * k + 1];
            smin_v[k] = min(smin_v[2 * k + 1], min_v[2 * k + 2]);
        } else if (min_v[2 * k + 1] > min_v[2 * k + 2]) {
            min_v[k] = min_v[2 * k + 2];
            min_c[k] = min_c[2 * k + 2];
            smin_v[k] = min(min_v[2 * k + 1], smin_v[2 * k + 2]);
        } else {
            min_v[k] = min_v[2 * k + 1];
            min_c[k] = min_c[2 * k + 1] + min_c[2 * k + 2];
            smin_v[k] = min(smin_v[2 * k + 1], smin_v[2 * k + 2]);
        }
    }

    void _update_chmin(int a, int b, long long x, int k, int l, int r) {
        if (b <= l || r <= a || max_v[k] <= x) return;
        if (a <= l && r <= b && smax_v[k] < x) { update_node_max(k, x); return; }
        push(k);
        _update_chmin(a, b, x, 2 * k + 1, l, (l + r) / 2);
        _update_chmin(a, b, x, 2 * k + 2, (l + r) / 2, r);
        update(k);
    }
    void _update_chmax(int a, int b, long long x, int k, int l, int r) {
        if (b <= l || r <= a || min_v[k] >= x) return;
        if (a <= l && r <= b && smin_v[k] > x) { update_node_min(k, x); return; }
        push(k);
        _update_chmax(a, b, x, 2 * k + 1, l, (l + r) / 2);
        _update_chmax(a, b, x, 2 * k + 2, (l + r) / 2, r);
        update(k);
    }
    void _update_add(int a, int b, long long x, int k, int l, int r) {
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) { update_node_add(k, x); return; }
        push(k);
        _update_add(a, b, x, 2 * k + 1, l, (l + r) / 2);
        _update_add(a, b, x, 2 * k + 2, (l + r) / 2, r);
        update(k);
    }
    void _update_modulo(int a, int b, long long x, int k, int l, int r) {
        if (b <= l || r <= a || max_v[k] < x) return;
        if (l + 1 == r) {
            long long val = max_v[k] % x;
            max_v[k] = min_v[k] = sum[k] = val;
            return;
        }
        push(k);
        _update_modulo(a, b, x, 2 * k + 1, l, (l + r) / 2);
        _update_modulo(a, b, x, 2 * k + 2, (l + r) / 2, r);
        update(k);
    }
    void _update_divide(int a, int b, long long x, int k, int l, int r) {
        if (b <= l || r <= a) return;
        long long diff_max = max_v[k] - (long long)floor((double)max_v[k] / x);
        long long diff_min = min_v[k] - (long long)floor((double)min_v[k] / x);
        if (a <= l && r <= b && diff_max == diff_min) { update_node_add(k, -diff_max); return; }
        push(k);
        _update_divide(a, b, x, 2 * k + 1, l, (l + r) / 2);
        _update_divide(a, b, x, 2 * k + 2, (l + r) / 2, r);
        update(k);
    }
    long long _query_sum(int a, int b, int k, int l, int r) {
        if (b <= l || r <= a) return 0;
        if (a <= l && r <= b) return sum[k];
        push(k);
        long long vl = _query_sum(a, b, 2 * k + 1, l, (l + r) / 2);
        long long vr = _query_sum(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }

public:
    SegmentTreeBeats(int n_) {
        n = n_; sz = 1; while (sz < n) sz *= 2;
        max_v.assign(2 * sz - 1, -INF); smax_v.assign(2 * sz - 1, -INF); max_c.assign(2 * sz - 1, 0);
        min_v.assign(2 * sz - 1, INF); smin_v.assign(2 * sz - 1, INF); min_c.assign(2 * sz - 1, 0);
        sum.assign(2 * sz - 1, 0); len.assign(2 * sz - 1, 0); lazy_add.assign(2 * sz - 1, 0);
    }
    void build(const vector& v) {
        for (int i = 0; i < n; i++) {
            max_v[sz - 1 + i] = min_v[sz - 1 + i] = sum[sz - 1 + i] = v[i];
            max_c[sz - 1 + i] = min_c[sz - 1 + i] = len[sz - 1 + i] = 1;
        }
        for (int i = sz - 2; i >= 0; i--) {
            len[i] = len[2 * i + 1] + len[2 * i + 2];
            update(i);
        }
    }
    void update_chmin(int a, int b, long long x) { _update_chmin(a, b, x, 0, 0, sz); }
    void update_chmax(int a, int b, long long x) { _update_chmax(a, b, x, 0, 0, sz); }
    void update_add(int a, int b, long long x) { _update_add(a, b, x, 0, 0, sz); }
    void update_modulo(int a, int b, long long x) { _update_modulo(a, b, x, 0, 0, sz); }
    void update_divide(int a, int b, long long x) { _update_divide(a, b, x, 0, 0, sz); }
    long long query_sum(int a, int b) { return _query_sum(a, b, 0, 0, sz); }
};

// 共通の直線構造体
const long long LCT_INF = 4e18; // 最小値クエリの初期値（十分大きい値）

struct Line {
    long long a, b;
    Line(long long a = 0, long long b = LCT_INF) : a(a), b(b) {}
    long long get(long long x) const { return a * x + b; }
};

// ====================================================================
// 1. 動的 Li Chao Tree (値域が広くてもそのまま使える。線分追加も可能)
// ====================================================================
struct DynamicLiChaoTree {
    struct Node {
        Line line;
        int left, right; // 子ノードの配列インデックス
        Node() : line(Line()), left(-1), right(-1) {}
    };
    
    vector<Node> nodes;
    long long min_x, max_x;

    // xの定義域 [min_x, max_x) を指定して初期化
    DynamicLiChaoTree(long long min_x = -1e9, long long max_x = 1e9 + 1) : min_x(min_x), max_x(max_x) {
        nodes.emplace_back();
    }

    // 直線の追加: y = ax + b
    void add_line(long long a, long long b) {
        update_line(0, min_x, max_x, Line(a, b));
    }

    // 線分の追加: x が [l, r) の範囲でのみ有効な y = ax + b
    void add_segment(long long a, long long b, long long l, long long r) {
        update_segment(0, min_x, max_x, l, r, Line(a, b));
    }

    // x における最小値の取得
    long long query(long long x) {
        long long res = LCT_INF;
        int idx = 0;
        long long l = min_x, r = max_x;
        while (idx != -1) {
            long long m = l + (r - l) / 2;
            res = min(res, nodes[idx].line.get(x));
            if (x < m) {
                idx = nodes[idx].left;
                r = m;
            } else {
                idx = nodes[idx].right;
                l = m;
            }
        }
        return res;
    }

private:
    void update_line(int idx, long long l, long long r, Line new_line) {
        long long m = l + (r - l) / 2;
        bool left_lower = new_line.get(l) < nodes[idx].line.get(l);
        bool mid_lower = new_line.get(m) < nodes[idx].line.get(m);
        bool right_lower = new_line.get(r - 1) < nodes[idx].line.get(r - 1);

        if (mid_lower) swap(nodes[idx].line, new_line);
        if (r - l <= 1) return;

        if (left_lower != mid_lower) {
            if (nodes[idx].left == -1) {
                nodes[idx].left = nodes.size();
                nodes.emplace_back();
            }
            update_line(nodes[idx].left, l, m, new_line);
        } else if (right_lower != mid_lower) {
            if (nodes[idx].right == -1) {
                nodes[idx].right = nodes.size();
                nodes.emplace_back();
            }
            update_line(nodes[idx].right, m, r, new_line);
        }
    }

    void update_segment(int idx, long long l, long long r, long long a, long long b, Line new_line) {
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            update_line(idx, l, r, new_line);
            return;
        }
        long long m = l + (r - l) / 2;
        if (a < m) {
            if (nodes[idx].left == -1) {
                nodes[idx].left = nodes.size();
                nodes.emplace_back();
            }
            update_segment(nodes[idx].left, l, m, a, b, new_line);
        }
        if (m < b) {
            if (nodes[idx].right == -1) {
                nodes[idx].right = nodes.size();
                nodes.emplace_back();
            }
            update_segment(nodes[idx].right, m, r, a, b, new_line);
        }
    }
};

// ====================================================================
// 2. 静的 Li Chao Tree (事前座標圧縮版・メモリ節約・定数倍高速)
// ====================================================================
struct StaticLiChaoTree {
    int n;
    vector<long long> xs;
    vector<Line> nodes;

    // クエリで飛んでくる可能性のある全ての x 座標リスト(未ソートでOK)を渡す
    StaticLiChaoTree(const vector<long long>& xs_in) {
        xs = xs_in;
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        n = 1;
        while (n < (int)xs.size()) n *= 2;
        while ((int)xs.size() < n) xs.push_back(xs.back() + 1); // 2の冪乗になるようダミー追加
        nodes.assign(2 * n, Line());
    }

    // 直線の追加: y = ax + b
    void add_line(long long a, long long b) {
        update_line(1, 0, n, Line(a, b));
    }

    // 線分の追加: 実際の x 座標 [l_x, r_x) で有効な y = ax + b
    void add_segment(long long a, long long b, long long l_x, long long r_x) {
        int l = lower_bound(xs.begin(), xs.end(), l_x) - xs.begin();
        int r = lower_bound(xs.begin(), xs.end(), r_x) - xs.begin();
        update_segment(1, 0, n, l, r, Line(a, b));
    }

    // x における最小値の取得
    long long query(long long x) {
        int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        idx += n;
        long long res = LCT_INF;
        while (idx > 0) {
            res = min(res, nodes[idx].get(x)); // 計算時のみリアルの x 座標を使用
            idx /= 2;
        }
        return res;
    }

private:
    void update_line(int k, int l, int r, Line new_line) {
        int m = (l + r) / 2;
        long long x_m = xs[m], x_l = xs[l], x_r = xs[r - 1];
        bool left_lower = new_line.get(x_l) < nodes[k].get(x_l);
        bool mid_lower = new_line.get(x_m) < nodes[k].get(x_m);
        bool right_lower = new_line.get(x_r) < nodes[k].get(x_r);

        if (mid_lower) swap(nodes[k], new_line);
        if (r - l <= 1) return;

        if (left_lower != mid_lower) {
            update_line(2 * k, l, m, new_line);
        } else if (right_lower != mid_lower) {
            update_line(2 * k + 1, m, r, new_line);
        }
    }

    void update_segment(int k, int l, int r, int a, int b, Line new_line) {
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            update_line(k, l, r, new_line);
            return;
        }
        int m = (l + r) / 2;
        update_segment(2 * k, l, m, a, b, new_line);
        update_segment(2 * k + 1, m, r, a, b, new_line);
    }
};

// ===== BFS =====
// start から各頂点への最短距離(辺数)を求める
vector<ll> bfs(const vector<vector<ll>>& graph, ll start) {
    ll n = graph.size();

    vector<ll> dist(n, -1);
    queue<ll> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        ll v = q.front();
        q.pop();

        for (ll next : graph[v]) {
            if (dist[next] != -1) continue;

            dist[next] = dist[v] + 1;
            q.push(next);
        }
    }

    return dist;
}

// ===== DFS (再帰) =====
void dfs(const vector<vector<ll>>& graph,
         vector<bool>& seen,
         ll v) {

    seen[v] = true;

    for (ll next : graph[v]) {
        if (seen[next]) continue;
        dfs(graph, seen, next);
    }
}

// 呼び出し例
int main() {
    vector<vector<ll>> graph = {
        {1, 2},     // 0
        {0, 3},     // 1
        {0, 3},     // 2
        {1, 2, 4},  // 3
        {3}         // 4
    };

    // BFS
    vector<ll> dist = bfs(graph, 0);

    // DFS
    vector<bool> seen(graph.size(), false);
    dfs(graph, seen, 0);
}

// 閉路が存在すればその頂点列 (例: {u, v, w, u}) を返す。存在しなければ空配列を返す。
// restore = false にすると復元を行わず高速に判定のみを行う (閉路ありなら要素数1の配列を返す)。
vector<ll> find_cycle(const vector<vector<ll>> &graph, bool restore = true) {
    ll n = graph.size();
    vector<int> state(n, 0); // 0: 未訪問, 1: 訪問中, 2: 訪問済
    vector<ll> parent(n, -1);
    vector<ll> cycle;

    auto dfs = [&](auto self, ll v) -> bool {
        state[v] = 1;
        for (ll next : graph[v]) {
            if (state[next] == 1) { // バックエッジ検出（閉路存在）
                if (restore) {
                    ll curr = v;
                    while (curr != next) {
                        cycle.push_back(curr);
                        curr = parent[curr];
                    }
                    cycle.push_back(next);
                    reverse(cycle.begin(), cycle.end());
                    cycle.push_back(next); // 始点と終点を合わせる
                } else {
                    cycle.push_back(-1); // 検出判定用のダミー値
                }
                return true;
            } else if (state[next] == 0) {
                parent[next] = v;
                if (self(self, next)) return true;
            }
        }
        state[v] = 2;
        return false;
    };

    for (ll i = 0; i < n; i++) {
        if (state[i] == 0) {
            if (dfs(dfs, i)) return cycle;
        }
    }
    return {};
}

vector<ll> zero_one_BFS(ll N, ll start, vector<vector<pair<ll, ll>>> G) {
  // 隣接リストGは{頂点番号,重み(0または1)}で与えている
  vector<ll> dist(N, INF);
  deque<ll> todo;
  todo.push_back(start);
  dist[start] = 0;

  while (todo.empty() == false) {
    ll m = todo.front();
    todo.pop_front();

    rep(i, G[m].size()) {
      ll to = G[m][i].first;
      ll cost = G[m][i].second;

      if (dist[m] + cost < dist[to]) {
        dist[to] = dist[m] + cost;
        if (cost == 0) {
          todo.push_front(to);
        } else {
          todo.push_back(to);
        }
      }
    }
  }
  return dist;
}

vector<ll> Dijkstra(ll N, ll start, vector<vector<pair<ll, ll>>> G) {
  // 隣接リストGは{頂点番号,重み}で与えている
  vector<ll> dist(N, INF);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
      todo;
  todo.push({0, start});
  dist[start] = 0;

  while (todo.empty() == false) {
    ll d = todo.top().first;
    ll m = todo.top().second;
    todo.pop();

    if (d > dist[m]) {
      continue;
    }

    rep(i, G[m].size()) {
      if (d + G[m][i].second < dist[G[m][i].first]) {
        dist[G[m][i].first] = d + G[m][i].second;
        todo.push({d + G[m][i].second, G[m][i].first});
      }
    }
  }
  return dist;
}

struct Edge {
  ll from;
  ll to;
  ll cost;
};

// 戻り値: 最短距離の配列。ただし負の閉路から到達可能な頂点の距離は -INF とする
// グラフ全体に負の閉路があるかどうかは、返った後に dist の変化やフラグ等で判定可能
vector<ll> BellmanFord(ll N, ll start, vector<Edge> edges, bool &has_negative_cycle) {
  vector<ll> dist(N, INF);
  dist[start] = 0;
  has_negative_cycle = false;

  // 1. 最大 N-1 回の緩和処理で最短路を確定させる
  rep(i, N - 1) {
    for (const auto& e : edges) {
      if (dist[e.from] != INF && dist[e.from] + e.cost < dist[e.to]) {
        dist[e.to] = dist[e.from] + e.cost;
      }
    }
  }

  // 2. 負の閉路の検出と、閉路から到達可能な頂点のマーク
  // さらに N 回ループを回すことで、負の閉路の影響を受ける頂点を確実に -INF に落とす
  rep(i, N) {
    for (const auto& e : edges) {
      if (dist[e.from] != INF && dist[e.from] + e.cost < dist[e.to]) {
        dist[e.to] = -INF;
        has_negative_cycle = true;
      }
    }
  }

  return dist;
}

void WarshallFloyd(ll N, vector<vector<ll>> &dist) {
  // dist[i][j] は頂点iからjへの辺の重み。初期値は dist[i][i] = 0、経路がない場合は INF
  rep(k, N) {
    rep(i, N) {
      rep(j, N) {
        if (dist[i][k] != INF && dist[k][j] != INF) {
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }
}

// 2回BFSを行うことで木の直径を求める
pair<ll, ll> bfs_tree_diameter(ll start, ll n, const vector<vector<ll>> &graph) {
  vector<ll> dist(n, -1);
  queue<ll> que;
  dist[start] = 0;
  que.push(start);
  ll far_node = start;
  while (!que.empty()) {
    ll v = que.front();
    que.pop();
    if (dist[v] > dist[far_node]) {
      far_node = v;
    }
    for (ll next : graph[v]) {
      if (dist[next] == -1) {
        dist[next] = dist[v] + 1;
        que.push(next);
      }
    }
  }
  return {dist[far_node], far_node};
}

ll get_tree_diameter(ll n, const vector<vector<ll>> &graph) {
  if (n <= 1) return 0;
  auto p1 = bfs_tree_diameter(0, n, graph);
  auto p2 = bfs_tree_diameter(p1.second, n, graph);
  return p2.first;
}

// 各連結成分に対して木の直径を求め、その最大値を返す
ll get_forest_diameter(ll n, const vector<vector<ll>> &graph) {
  vector<bool> visited(n, false);
  vector<ll> dist(n, -1);
  ll max_diameter = 0;

  auto bfs = [&](ll start, vector<ll> &component) {
    queue<ll> que;
    dist[start] = 0;
    que.push(start);
    ll far_node = start;
    while (!que.empty()) {
      ll v = que.front();
      que.pop();
      component.push_back(v);
      if (dist[v] > dist[far_node]) {
        far_node = v;
      }
      for (ll next : graph[v]) {
        if (dist[next] == -1) {
          dist[next] = dist[v] + 1;
          que.push(next);
        }
      }
    }
    return far_node;
  };

  auto bfs_fixed = [&](ll start) {
    queue<ll> que;
    dist[start] = 0;
    que.push(start);
    ll max_d = 0;
    while (!que.empty()) {
      ll v = que.front();
      que.pop();
      if (dist[v] > max_d) {
        max_d = dist[v];
      }
      for (ll next : graph[v]) {
        if (dist[next] == -1) {
          dist[next] = dist[v] + 1;
          que.push(next);
        }
      }
    }
    return max_d;
  };

  for (ll i = 0; i < n; ++i) {
    if (visited[i]) continue;
    if (graph[i].empty()) {
      visited[i] = true;
      continue;
    }
    vector<ll> component;
    ll u = bfs(i, component);
    for (ll node : component) {
      visited[node] = true;
      dist[node] = -1;
    }
    ll d = bfs_fixed(u);
    for (ll node : component) {
      dist[node] = -1;
    }
    if (d > max_diameter) {
      max_diameter = d;
    }
  }
  return max_diameter;
}

vector<ll> indeg(n, 0);
for (ll i = 0; i < n; i++) {
    for (ll to : G[i]) indeg[to]++;
}

queue<ll> q;
for (ll i = 0; i < n; i++) {
    if (indeg[i] == 0) q.push(i);
}

vector<ll> ord;
while (!q.empty()) {
    ll v = q.front(); q.pop();
    ord.push_back(v);
    for (ll to : G[v]) {
        if (--indeg[to] == 0) q.push(to);
    }
}

// graph の連結成分を求める
// 戻り値 V[i] が i 番目の連結成分に含まれる頂点集合
vector<vector<ll>> connected_components(
    const vector<vector<ll>>& graph) {

    ll n = graph.size();

    vector<bool> seen(n, false);
    vector<vector<ll>> V;

    auto dfs = [&](auto&& self,
                   ll v,
                   vector<ll>& comp) -> void {

        seen[v] = true;
        comp.push_back(v);

        for (ll next : graph[v]) {
            if (seen[next]) continue;
            self(self, next, comp);
        }
    };

    for (ll v = 0; v < n; v++) {
        if (seen[v]) continue;

        vector<ll> comp;
        dfs(dfs, v, comp);

        V.push_back(comp);
    }

    return V;
}

// 1回目のDFS: 帰りがけ順（バックトラック時）に頂点を記録
void SCC1(const vvl &graph, vb &seen, vl &V, ll v) {
    seen[v] = true;
    for (ll next : graph[v]) {
        if (seen[next] == true) {
            continue;
        }
        SCC1(graph, seen, V, next);
    }
    V.push_back(v);
}

// 2回目のDFS: 逆方向グラフを用いて成分ごとに頂点を回収
void SCC2(const vvl &graph, vb &seen, ll v, vl &SCC_part) {
    seen[v] = true;
    for (ll next : graph[v]) {
        if (seen[next] == true) {
            continue;
        }
        SCC2(graph, seen, next, SCC_part);
    }
    SCC_part.push_back(v);
}

// =====ここから使い方=====
vvl G1(N), G2(N); // G1は順方向、G2は逆方向の隣接リスト
vb seen1(N, false);
vl V;
rep(i, N) {
    if (seen1[i] == false) {
        SCC1(G1, seen1, V, i);
    }
}

reverse(V.begin(), V.end());

vvl SCC;
vb seen2(N, false);
rep(i, N) {
    if (seen2[V[i]] == false) {
        vl SCC_part;
        SCC2(G2, seen2, V[i], SCC_part);
        SCC.push_back(SCC_part);
    }
}

// SCCのi行目がi番目の強連結成分の要素

struct EulerTour {
    int n;
    // 部分木クエリ用：頂点vの部分木は半開区間 [ in_time[v], out_time[v] ) に対応
    vector<int> in_time, out_time;
    // LCA用：訪問順の頂点(tour), その深さ(depth), 頂点vがtourに最初に現れるインデックス(first_visit)
    vector<int> tour, depth, first_visit;
    // 距離用：根からの距離（重みなし木ならdepthと同じ。重み付きならパスの重み和）
    vector<long long> dist;
    int timer_inout;

    EulerTour(const vector<vector<int>>& graph, int root = 0) {
        n = graph.size();
        in_time.assign(n, -1);
        out_time.assign(n, -1);
        first_visit.assign(n, -1);
        dist.assign(n, 0);
        timer_inout = 0;
        build(graph, root, -1, 0, 0);
    }

    void build(const vector<vector<int>>& graph, int v, int p, int d, long long dist_from_root) {
        in_time[v] = timer_inout++;
        first_visit[v] = tour.size();
        tour.push_back(v);
        depth.push_back(d);
        dist[v] = dist_from_root;

        for (int next : graph[v]) {
            if (next == p) continue;
            // ※辺に重みがあるグラフの場合は、引数を変えて dist_from_root + cost にする
            build(graph, next, v, d + 1, dist_from_root + 1);
            tour.push_back(v);
            depth.push_back(d);
        }
        out_time[v] = timer_inout;
    }
};

using ll = long long;

int main() {
    int N = 5;
    
    // 1. 宣言: 頂点数 N を指定。容量の型に ll を指定します。
    mf_graph<ll> graph(N);

    // 2. 辺の追加: add_edge(from, to, capacity)
    // 頂点は 0-indexed で指定します。戻り値として辺のID(int)が返ります。
    graph.add_edge(0, 1, 10);
    graph.add_edge(0, 2, 2);
    graph.add_edge(1, 2, 6);
    graph.add_edge(1, 3, 6);
    graph.add_edge(2, 4, 5);
    graph.add_edge(3, 4, 8);

    // 3. 最大流 (Max Flow): flow(s, t)
    // 頂点 0 から 4 への最大流量を計算して返します。
    ll max_flow = graph.flow(0, 4);

    // 4. 最小カット (Min Cut): min_cut(s)
    // 必ず flow(s, t) を実行した「後」に呼び出します。
    // 残余グラフ上で始点 s から到達可能な頂点が true (S側)、そうでない頂点が false (T側) となる配列を返します。
    vector<bool> is_S = graph.min_cut(0);

    // 5. 各辺の状態取得: edges() や get_edge(i) (任意)
    // auto edges = graph.edges();
    // for (auto e : edges) {
    //     // e.from, e.to, e.cap, e.flow にアクセスして復元等に利用できます。
    // }
}

// ===== Bipartite Matching (ACL mf_graph) =====
struct BipartiteMatching {
    ll L_size, R_size;
    ll S, T;
    mf_graph<ll> graph;

    // L側の頂点は 0 ~ L-1, R側の頂点は L ~ L+R-1 に割り当て、SとTを追加
    BipartiteMatching(ll L, ll R) : L_size(L), R_size(R), S(L + R), T(L + R + 1), graph(L + R + 2) {
        // S から L 側へ容量 1 の辺を張る
        for (ll i = 0; i < L; ++i) graph.add_edge(S, i, 1);
        // R 側から T へ容量 1 の辺を張る
        for (ll j = 0; j < R; ++j) graph.add_edge(L_size + j, T, 1);
    }

    void add_edge(ll u, ll v) {
        // L側の u から R側の v へ容量 1 の辺を張る
        graph.add_edge(u, L_size + v, 1);
    }

    // 最大マッチングのサイズを返す
    ll solve() {
        return graph.flow(S, T);
    }

    // 復元処理: (最大マッチングの辺, 左の最小頂点被覆, 右の最小頂点被覆, 左の最大独立集合, 右の最大独立集合)
    // ※必ず solve() を実行した後に呼ぶこと
    tuple<vector<pair<ll, ll>>, vector<ll>, vector<ll>, vector<ll>, vector<ll>> restore() {
        vector<pair<ll, ll>> edges;
        for (auto e : graph.edges()) {
            // SやTが絡まない辺で、流量が1になっているものがマッチングに使われた辺
            if (e.from != S && e.to != T && e.flow == 1) {
                edges.push_back({e.from, e.to - L_size});
            }
        }

        // 最小カット (min_cut) を用いて頂点被覆と独立集合を復元
        vector<bool> is_S = graph.min_cut(S);
        vector<ll> mvc_l, mvc_r, mis_l, mis_r;

        for (ll i = 0; i < L_size; ++i) {
            if (!is_S[i]) mvc_l.push_back(i); // L側: 最小カットでT側に属していれば被覆
            else mis_l.push_back(i);          // L側: 最小カットでS側に属していれば独立集合
        }
        for (ll i = 0; i < R_size; ++i) {
            if (is_S[L_size + i]) mvc_r.push_back(i); // R側: 最小カットでS側に属していれば被覆
            else mis_r.push_back(i);                  // R側: 最小カットでT側に属していれば独立集合
        }
        return {edges, mvc_l, mvc_r, mis_l, mis_r};
    }
};

int main() {
    // ① 初期化: 左側の頂点数 L と 右側の頂点数 R を指定する
    ll L_size = 3;
    ll R_size = 4;
    BipartiteMatching bm(L_size, R_size);

    // ② 辺の追加: (左の頂点番号, 右の頂点番号) ※0-indexedを想定
    bm.add_edge(0, 0);
    bm.add_edge(0, 1);
    bm.add_edge(1, 1);
    bm.add_edge(1, 2);
    bm.add_edge(2, 3);

    // ③ 計算: 最大マッチングのサイズを取得
    ll max_matching = bm.solve();
    cout << "最大マッチング数: " << max_matching << "\n";

    // ④ 復元: (最大マッチングの辺, Lの最小頂点被覆, Rの最小頂点被覆, Lの最大独立集合, Rの最大独立集合)
    // ※ C++17以降の構造化束縛を使うと便利です
    auto [edges, mvc_l, mvc_r, mis_l, mis_r] = bm.restore();

    // --- 出力して確認 ---
    cout << "\n[最大マッチングのペア]" << "\n";
    for (auto [u, v] : edges) {
        cout << "L" << u << " - R" << v << "\n";
    }

    cout << "\n[最小頂点被覆] (合計 " << mvc_l.size() + mvc_r.size() << " 個)" << "\n";
    cout << "L側: ";
    for (ll u : mvc_l) cout << u << " ";
    cout << "\nR側: ";
    for (ll v : mvc_r) cout << v << " ";
    cout << "\n";

    cout << "\n[最大独立集合] (合計 " << mis_l.size() + mis_r.size() << " 個)" << "\n";
    cout << "L側: ";
    for (ll u : mis_l) cout << u << " ";
    cout << "\nR側: ";
    for (ll v : mis_r) cout << v << " ";
    cout << "\n";

    return 0;
}

// Union-Find の構造体
struct UnionFind {
    vector<ll> parent;
    vector<ll> siz;

    UnionFind(ll n) {
        parent.assign(n, -1);
        siz.assign(n, 1);
    }

    ll find(ll x) {
        if (parent[x] == -1) return x;
        return parent[x] = find(parent[x]); 
    }

    bool unite(ll x, ll y) {
        ll root_x = find(x);
        ll root_y = find(y);
        if (root_x == root_y) return false;
        if (siz[root_x] < siz[root_y]) swap(root_x, root_y);
        parent[root_y] = root_x;
        siz[root_x] += siz[root_y];
        return true;
    }

    bool same(ll x, ll y) {
        return find(x) == find(y);
    }

    ll size(ll x) {
        return siz[find(x)];
    }
};

// 辺を表す構造体
struct Edge {
    ll u, v, cost;
    // コストの昇順にソートするための比較関数
    bool operator<(const Edge& o) const {
        return cost < o.cost;
    }
};

// クラスカル法 (最小全域木)
// 戻り値: {MSTの重みの総和, MSTを構成する隣接リスト}
pair<ll, vector<vector<pair<ll, ll>>>> kruskal(ll V, vector<Edge>& edges) {
    // 1. 辺をコストの昇順にソート
    sort(edges.begin(), edges.end());

    UnionFind uf(V);
    ll total_cost = 0;
    vector<vector<pair<ll, ll>>> mst_adj(V); // MSTの隣接リスト (to, cost)

    // 2. コストが小さい辺から順に確認
    for (const auto& e : edges) {
        // 閉路ができない場合のみ辺を採用 (異なるグループなら繋ぐ)
        if (uf.unite(e.u, e.v)) {
            total_cost += e.cost;
            // 無向グラフとして隣接リストに辺を追加
            mst_adj[e.u].push_back({e.v, e.cost});
            mst_adj[e.v].push_back({e.u, e.cost});
        }
    }

    return {total_cost, mst_adj};
}

ll main() {
    ll V = 4; // 頂点数
    // グラフの辺リスト {u, v, cost}
    vector<Edge> edges = {
        {0, 1, 1},
        {0, 2, 4},
        {1, 2, 2},
        {2, 3, 3},
        {1, 3, 5}
    };

    // クラスカル法を実行
    auto [total_cost, mst_adj] = kruskal(V, edges);

    cout << "MSTの総コスト: " << total_cost << "\n\n";
    
    cout << "--- MSTの隣接リスト ---\n";
    for (ll i = 0; i < V; ++i) {
        cout << "頂点 " << i << ": ";
        for (auto& edge : mst_adj[i]) {
            cout << "(" << edge.first << ", コスト:" << edge.second << ") ";
        }
        cout << "\n";
    }

    return 0;
}

template <typename T = long long>
struct Doubling {
    ll n;
    ll max_log;
    vector<vector<ll>> next;
    vector<vector<T>> sum;
    T identity;
    using F = function<T(T, T)>;
    F op;
    bool has_value;

    // 移動のみ（値の累積なし）の場合のコンストラクタ
    Doubling(ll n, long long max_k) : n(n), has_value(false) {
        max_log = (max_k <= 0) ? 1 : 64 - __builtin_clzll(max_k);
        next.assign(max_log, vector<ll>(n, -1));
    }

    // 値の累積を行う場合のコンストラクタ (単位元 id と 二項演算 op を指定)
    Doubling(ll n, long long max_k, T id, F op)
        : n(n), identity(id), op(op), has_value(true) {
        max_log = (max_k <= 0) ? 1 : 64 - __builtin_clzll(max_k);
        next.assign(max_log, vector<ll>(n, -1));
        sum.assign(max_log, vector<T>(n, id));
    }

    // 1ステップの遷移を設定 (u から v へ、重み/値 w)
    void set_next(ll u, ll v, T w = T()) {
        next[0][u] = v;
        if (has_value) sum[0][u] = w;
    }

    // テーブル構築 (すべての遷移を設定した後に呼び出す)
    void build() {
        for (ll k = 0; k < max_log - 1; k++) {
            for (ll i = 0; i < n; i++) {
                if (next[k][i] != -1) {
                    next[k + 1][i] = next[k][next[k][i]];
                    if (has_value) {
                        sum[k + 1][i] = op(sum[k][i], sum[k][next[k][i]]);
                    }
                }
            }
        }
    }

    // start から k 回移動した後の {行き先, 累積値} を取得
    pair<ll, T> query(ll start, long long k) const {
        ll cur = start;
        T res = identity;
        for (ll i = 0; i < max_log; i++) {
            if ((k >> i) & 1) {
                if (cur == -1) break;
                if (has_value) res = op(res, sum[i][cur]);
                cur = next[i][cur];
            }
        }
        return {cur, res};
    }
};

template <typename T>
struct MatrixTreeTheorem {
    int n;
    vector<vector<T>> laplacian;

    MatrixTreeTheorem(int n) : n(n), laplacian(n, vector<T>(n, 0)) {}

    // 無向辺 u-v を追加 (重み w、デフォルトは 1)
    // 多重辺の場合は w に追加する辺の本数を指定する
    void add_edge(int u, int v, T w = 1) {
        laplacian[u][u] += w;
        laplacian[v][v] += w;
        laplacian[u][v] -= w;
        laplacian[v][u] -= w;
    }

    // 全域木の数を計算（0行目と0列目を取り除いた余因子を計算）
    T build() {
        if (n <= 1) return 1;
        int m = n - 1;
        vector<vector<T>> mat(m, vector<T>(m));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < m; ++j) {
                mat[i][j] = laplacian[i + 1][j + 1];
            }
        }

        T res = 1;
        for (int i = 0; i < m; ++i) {
            int pivot = -1;
            for (int j = i; j < m; ++j) {
                if (mat[j][i] != 0) { // 浮動小数の場合は abs(mat[j][i]) > 1e-9 などで判定
                    pivot = j;
                    break;
                }
            }
            if (pivot == -1) return 0; // 行列式が0 = 全域木が存在しない
            
            if (i != pivot) {
                swap(mat[i], mat[pivot]);
                res = -res; // 行の入れ替えで符号反転
            }
            
            // 掃き出し法
            T inv = (T)1 / mat[i][i];
            for (int j = i + 1; j < m; ++j) {
                T factor = mat[j][i] * inv;
                for (int k = i; k < m; ++k) {
                    mat[j][k] -= mat[i][k] * factor;
                }
            }
            res *= mat[i][i];
        }
        return res;
    }
};

ll res = 0;
ll right = 0;
// sumやcountなどの区間の状態を管理する変数をここに用意

for (ll left = 0; left < n; ++left) {
    // rightを進めても条件を満たす間（または満たすまで）、rightを伸ばす
    while (right < n && /* 条件を満たすか判定 */) {
        // 状態の更新 (例: sum += a[right])
        ++right;
    }

    // この時点で [left, right) が確定。必要な処理を行う
    res += (right - left); // 例: 条件を満たす部分列の数を足す

    // 次のループ（left++）に向けて状態を正しく保つ
    if (right == left) {
        // 区間が空の場合は right も一緒に進める（状態は更新しない）
        ++right;
    } else {
        // 左端の要素を区間から除外 (例: sum -= a[left])
    }
}

ll res = 0;
ll left = 0;
// sumやcountなどの区間の状態を管理する変数をここに用意

for (ll right = 0; right < n; ++right) {
    // まず右端の要素を問答無用で追加する
    // 状態の更新 (例: sum += a[right])

    // 条件を破ってしまったら、満たすようになるまで左端を縮める
    while (left <= right && /* 条件を満たしていないか判定 */) {
        // 左端の要素を除外 (例: sum -= a[left])
        ++left;
    }

    // この時点で閉区間 [left, right] は確実に条件を満たしている
    res += (right - left + 1); // 例: 閉区間の長さを足す
}

// 区間 {始点, 終点} の配列が与えられたとする
// vector<pair<ll, ll>> intervals(N);

// 終端位置が早い順にソートしたいので、{終点, 始点} のペアにする
vector<pair<ll, ll>> sorted_intervals(N);
rep(i, N) {
    sorted_intervals[i] = {intervals[i].second, intervals[i].first};
}
sort(sorted_intervals.begin(), sorted_intervals.end());

ll ans = 0;
ll current_end_time = 0;

rep(i, N) {
    // 最後に選んだ区間の終端よりも、次の区間の始点が後（または同じ）なら選べる
    if (sorted_intervals[i].second >= current_end_time) {
        ans++;
        current_end_time = sorted_intervals[i].first; // 新しい終端時間を記録
    }
}

// 転倒数 (Fenwick Tree + 座標圧縮ベース)
// 配列内の要素がどれだけ大きくても、負の値を含んでいても動作します

#include <vector>
#include <algorithm>

template<typename T>
long long inversion_number(const std::vector<T>& A) {
    int n = A.size();
    if (n == 0) return 0;

    // 1. 座標圧縮 (配列の値を 0-indexed のランクに変換)
    std::vector<T> sorted_A = A;
    std::sort(sorted_A.begin(), sorted_A.end());
    sorted_A.erase(std::unique(sorted_A.begin(), sorted_A.end()), sorted_A.end());
    int m = sorted_A.size();

    // 2. Fenwick Tree (BIT) の実装 (内部は 1-indexed)
    std::vector<int> bit(m + 1, 0);
    auto add = [&](int i, int x) {
        for (++i; i <= m; i += i & -i) bit[i] += x;
    };
    auto sum = [&](int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    };

    // 3. 転倒数のカウント
    long long inv = 0;
    for (int i = 0; i < n; ++i) {
        // 圧縮後のランクを取得 (0-indexed)
        int rank = std::lower_bound(sorted_A.begin(), sorted_A.end(), A[i]) - sorted_A.begin();
        
        // これまでに出現した要素のうち、自分以下の要素の数を取得
        int count_less_equal = sum(rank + 1);
        
        // (これまでに出現した全要素数 i) - (自分以下の要素数) = (自分より真に大きい要素数)
        inv += i - count_less_equal;
        
        // 自分のランクを BIT に登録
        add(rank, 1);
    }
    return inv;
}

// 元の配列 a (サイズ N)
// vector<ll> a(N);

// 累積和配列 S を構築 (サイズは N + 1)
vector<ll> s(N + 1, 0);
rep(i, N) {
    s[i + 1] = s[i] + a[i];
}

// 区間 [left, right) の和を O(1) で求める関数
// 例: a[1] + a[2] + a[3] なら left = 1, right = 4
auto query = [&](ll left, ll right) {
    return s[right] - s[left];
};

// 各次元のサイズ D を指定する N 次元累積和 / 逆変換 (差分)
template <typename T>
void n_dimensional_prefix_sum(vector<T>& a, const vector<ll>& D, bool invert = false) {
    ll n = a.size();
    ll N_dim = D.size();
    // ストライド (D_0, D_0*D_1, ...) を前計算
    vector<ll> stride(N_dim + 1, 1);
    for (ll d = 0; d < N_dim; d++) {
        stride[d + 1] = stride[d] * D[d];
    }
    
    if (!invert) {
        for (ll d = 0; d < N_dim; d++) {
            for (ll i = 0; i < n; i++) {
                if ((i / stride[d]) % D[d] > 0) {
                    a[i] += a[i - stride[d]];
                }
            }
        }
    } else {
        for (ll d = 0; d < N_dim; d++) {
            for (ll i = n - 1; i >= 0; i--) {
                if ((i / stride[d]) % D[d] > 0) {
                    a[i] -= a[i - stride[d]];
                }
            }
        }
    }
}

// 累積和済みの配列 a に対して、各次元で X[i] <= p[i] <= Y[i] を満たす超立方体領域の和を求める
template <typename T>
T get_nd_range_sum(const vector<T>& a, const vector<ll>& D, const vector<ll>& X, const vector<ll>& Y) {
    ll N_dim = D.size();
    vector<ll> stride(N_dim + 1, 1);
    for (ll d = 0; d < N_dim; d++) {
        stride[d + 1] = stride[d] * D[d];
    }

    T ans = 0;
    // 包除原理: 2^N_dim 個の状態 (各次元について上限 Y[i] か 下限 X[i]-1 を選ぶか) を探索
    for (ll mask = 0; mask < (1LL << N_dim); mask++) {
        ll idx = 0;
        bool out_of_bounds = false;
        ll lower_count = 0; // 下限 (X[i]-1) を採用した次元の数

        for (ll i = 0; i < N_dim; i++) {
            ll p = 0;
            if ((mask >> i) & 1) {
                p = Y[i];
            } else {
                p = X[i] - 1;
                lower_count++;
            }

            // 下限が 0 未満になった場合は、その領域の和は 0 なのでスキップ
            if (p < 0) {
                out_of_bounds = true;
                break;
            }
            if (p >= D[i]) p = D[i] - 1;
            
            idx += p * stride[i];
        }

        if (out_of_bounds) continue;

        // 下限を採用した回数が奇数なら引き、偶数なら足す
        if (lower_count % 2 == 1) {
            ans -= a[idx];
        } else {
            ans += a[idx];
        }
    }
    return ans;
}

// 長さ M のタイムラインや配列を想定
vector<ll> table(M + 1, 0);

// Q回の区間加算: 区間 [l, r) に +1 をする
rep(i, Q) {
    ll l, r;
    cin >> l >> r;
    table[l]++;     // 始点に +1
    table[r]--;     // 終点の直後（半開区間の終端）に -1
}

// 最後に累積和をとることで、各点の実際の値を復元
rep(i, M) {
    table[i + 1] += table[i];
}

// 最終的に table[i] にはインデックス i に重なっている区間の数が格納される

template <typename T, typename F>
struct SparseTable {
    ll n;
    vector<vector<T>> table;
    vector<ll> log_table;
    F op; // 適用する二項演算 (min, max, gcd など)

    SparseTable() {}
    SparseTable(const vector<T>& v, F op) : op(op) {
        init(v);
    }

    // テーブルの初期化・構築
    void init(const vector<T>& v) {
        n = v.size();
        ll log_n = 0;
        while ((1LL << log_n) <= n) {
            log_n++;
        }
        
        table.assign(log_n, vector<T>(n));
        for (ll i = 0; i < n; i++) {
            table[0][i] = v[i];
        }
        
        for (ll i = 1; i < log_n; i++) {
            ll len = 1LL << (i - 1);
            for (ll j = 0; j + len * 2 <= n; j++) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + len]);
            }
        }
        
        log_table.assign(n + 1, 0);
        for (ll i = 2; i <= n; i++) {
            log_table[i] = log_table[i >> 1] + 1;
        }
    }

    // 半開区間 [l, r) に対するクエリ処理
    T query(ll l, ll r) {
        ll len = r - l;
        ll k = log_table[len];
        return op(table[k][l], table[k][r - (1LL << k)]);
    }
};

struct RangeSet {
    set<pair<ll, ll>> st; // {右端, 左端} で保持
    ll black_count = 0;   // 全体で黒く塗られているマスの総数

    // 閉区間 [l, r] を追加し、重なる・隣接する区間をマージする
    void insert(ll l, ll r) {
        auto it = st.lower_bound({l - 1, -1});
        while (it != st.end() && it->second <= r + 1) {
            ll prev_r = it->first;
            ll prev_l = it->second;
            l = min(l, prev_l);
            r = max(r, prev_r);
            black_count -= (prev_r - prev_l + 1);
            it = st.erase(it);
        }
        st.insert({r, l});
        black_count += (r - l + 1);
    }

    // 閉区間 [l, r] の範囲内で黒く塗られているマスの個数を返す
    ll query(ll l, ll r) {
        ll res = 0;
        // l以上の右端を持つ最初の区間を検索
        auto it = st.lower_bound({l, -1});
        // 区間の左端が r 以下である限りループ
        while (it != st.end() && it->second <= r) {
            ll cur_r = min(r, it->first);
            ll cur_l = max(l, it->second);
            res += (cur_r - cur_l + 1);
            it++;
        }
        return res;
    }
};

// 巡回セールスマン問題の遷移例
vector<vector<long long>> dp(1 << N, vector<long long>(N, INF));
dp[1][0] = 0; // 開始点
for (ll S = 1; S < (1 << N); S++) {
    for (ll v = 0; v < N; v++) {
        if (dp[S][v] == INF) continue;
        for (ll u = 0; u < N; u++) {
            if (!(S & (1 << u))) { // uが未訪問の場合
                dp[S | (1 << u)][u] = min(dp[S | (1 << u)][u], dp[S][v] + cost[v][u]);
            }
        }
    }
}

// N以下の条件を満たす数を数える桁DPの遷移例
string N; // 桁数が大きい場合は文字列として受け取る
ll D = N.size();

ll dp[D + 1][2][2][MAX_J] = {};
// dp[i][smaller][leading_zero][j]
memset(dp, 0, sizeof(dp));
dp[0][0][1][0] = 1;

for (ll i = 0; i < D; i++) {
    ll Nd = N[i] - '0';

    for (ll smaller = 0; smaller < 2; smaller++) {
        for (ll leading_zero = 0; leading_zero < 2; leading_zero++) {
            for (ll j = 0; j < MAX_J; j++) {
                if (dp[i][smaller][leading_zero][j] == 0) continue;

                ll limit = smaller ? 9 : Nd;
                for (ll d = 0; d <= limit; d++) {
                    ll next_smaller = smaller || (d < Nd);
                    ll next_leading_zero = leading_zero && (d == 0);

                    // leading_zero を考慮して状態更新
                    ll next_j = /* jとdから次の状態を計算 */ j;

                    dp[i + 1][next_smaller][next_leading_zero][next_j]
                        += dp[i][smaller][leading_zero][j];
                }
            }
        }
    }
}

// 最長増加部分列（LIS）の長さを求める
ll N;
// Aは入力配列
vector<ll> A(N);

vector<ll> dp;
for (ll i = 0; i < N; i++) {
    // 二分探索で挿入位置を特定する
    auto it = lower_bound(dp.begin(), dp.end(), A[i]);
    if (it == dp.end()) {
        dp.push_back(A[i]);
    } else {
        *it = A[i];
    }
}
ll ans = dp.size();

// 2次元最長増加部分列の長さを求める
ll N;
vector<pair<ll, ll>> points(N); // {x, y}

// xの昇順、xが等しい場合はyの降順にソートする
sort(points.begin(), points.end(), [](const pair<ll, ll>& a, const pair<ll, ll>& b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second;
});

vector<ll> dp;
for (ll i = 0; i < N; i++) {
    ll y = points[i].second;
    auto it = lower_bound(dp.begin(), dp.end(), y);
    if (it == dp.end()) {
        dp.push_back(y);
    } else {
        *it = y;
    }
}
ll ans = dp.size();

vector<long long> memo(n + 1, -1);

long long fib(ll n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

ll H, W;
vector<vector<ll>> grid;
vector<vector<long long>> memo;

long long dfs(ll r, ll c) {
    if (r == H - 1 && c == W - 1) return 1; // ゴールに到達
    if (memo[r][c] != -1) return memo[r][c];
    
    long long res = 0;
    if (c + 1 < W) res += dfs(r, c + 1); // 右へ移動
    if (r + 1 < H) res += dfs(r + 1, c); // 下へ移動
    
    return memo[r][c] = res;
}

map<long long, long long> memo;

long long solve(long long n) {
    if (n == 0) return 0;
    if (memo.count(n)) return memo[n];
    
    // 遷移例: solve(n) = solve(n / 2) + solve(n / 3) + n
    long long res = solve(n / 2) + solve(n / 3) + n;
    return memo[n] = res;
}

#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;

#include <complex>
#include <cmath>
using C = complex<double>;

void fft(vector<C>& a, bool invert) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * M_PI / len * (invert ? -1 : 1);
        C wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            C w(1);
            for (int j = 0; j < len / 2; j++) {
                C u = a[i + j];
                C v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert) {
        for (C& x : a) x /= n;
    }
}

vector<double> convolution_fft(const vector<double>& a, const vector<double>& b) {
    vector<C> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n); fb.resize(n);
    
    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);
    
    vector<double> res(n);
    for (int i = 0; i < n; i++) res[i] = fa[i].real();
    return res;
}

// 下位集合に関する高速ゼータ変換 (OR畳み込みの前処理)
template <typename T>
void fast_zeta_transform_or(vector<T>& a) {
    int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if (!(j & i)) a[j | i] += a[j];
        }
    }
}

// 下位集合に関する高速メビウス変換 (OR畳み込みの後処理)
template <typename T>
void fast_mobius_transform_or(vector<T>& a) {
    int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if (!(j & i)) a[j | i] -= a[j];
        }
    }
}

// Bitwise OR 畳み込み: c[k] = sum_{i | j = k} a[i] * b[j]
template <typename T>
vector<T> bitwise_or_convolution(vector<T> a, vector<T> b) {
    fast_zeta_transform_or(a);
    fast_zeta_transform_or(b);
    for (size_t i = 0; i < a.size(); i++) a[i] *= b[i];
    fast_mobius_transform_or(a);
    return a;
}

// 高速アダマール変換 / 逆変換
template <typename T>
void fast_walsh_hadamard_transform(vector<T>& a, bool invert = false) {
    int n = a.size();
    for (int len = 1; len < n; len <<= 1) {
        for (int i = 0; i < n; i += 2 * len) {
            for (int j = 0; j < len; j++) {
                T u = a[i + j];
                T v = a[i + j + len];
                a[i + j] = u + v;
                a[i + j + len] = u - v;
            }
        }
    }
    if (invert) {
        T inv_n = T(1) / T(n);
        for (auto& x : a) x *= inv_n;
    }
}

// Bitwise XOR 畳み込み: c[k] = sum_{i ^ j = k} a[i] * b[j]
template <typename T>
vector<T> bitwise_xor_convolution(vector<T> a, vector<T> b) {
    fast_walsh_hadamard_transform(a);
    fast_walsh_hadamard_transform(b);
    for (size_t i = 0; i < a.size(); i++) a[i] *= b[i];
    fast_walsh_hadamard_transform(a, true);
    return a;
}

template <typename mint>
struct FPS : std::vector<mint> {
    using std::vector<mint>::vector;
    FPS(const std::vector<mint>& v) { this->assign(v.begin(), v.end()); }

    // 指定した次数までで切り打ち（リサイズ）
    FPS pre(ll deg) const {
        FPS res(*this);
        res.resize(deg);
        return res;
    }

    FPS& operator+=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (ll i = 0; i < (ll)r.size(); i++) (*this)[i] += r[i];
        return *this;
    }

    FPS& operator-=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (ll i = 0; i < (ll)r.size(); i++) (*this)[i] -= r[i];
        return *this;
    }

    // ACL の convolution を使った乗算
    FPS& operator*=(const FPS& r) {
        if (this->empty() || r.empty()) {
            this->clear();
            return *this;
        }
        auto res = atcoder::convolution(*this, r);
        this->assign(res.begin(), res.end());
        return *this;
    }

    FPS operator+(const FPS& r) const { return FPS(*this) += r; }
    FPS operator-(const FPS& r) const { return FPS(*this) -= r; }
    FPS operator*(const FPS& r) const { return FPS(*this) *= r; }

    FPS operator*(mint v) const {
        FPS res(*this);
        for (ll i = 0; i < (ll)res.size(); i++) res[i] *= v;
        return res;
    }
    FPS& operator*=(mint v) {
        for (ll i = 0; i < (ll)this->size(); i++) (*this)[i] *= v;
        return *this;
    }

    // 微分
    FPS deriv() const {
        if (this->empty()) return FPS();
        FPS res(this->size() - 1);
        for (ll i = 1; i < (ll)this->size(); i++) res[i - 1] = (*this)[i] * i;
        return res;
    }

    // 積分
    FPS integral() const {
        if (this->empty()) return FPS();
        FPS res(this->size() + 1);
        res[0] = 0;
        for (ll i = 0; i < (ll)this->size(); i++) res[i + 1] = (*this)[i] / (i + 1);
        return res;
    }

    // 逆元 (Inverse)
    FPS inv(ll deg = -1) const {
        if (deg == -1) deg = this->size();
        FPS res{(*this)[0].inv()};
        for (ll d = 1; d < deg; d *= 2) {
            FPS f = pre(2 * d);
            FPS g = res;
            f *= g;
            f.resize(2 * d);
            for (ll i = 0; i < 2 * d; i++) f[i] = -f[i];
            f[0] += 2;
            f *= g;
            f.resize(2 * d);
            res = f;
        }
        return res.pre(deg);
    }

    // 対数 (Log) : F[0] == 1 が必須
    FPS log(ll deg = -1) const {
        if (deg == -1) deg = this->size();
        FPS f = deriv();
        FPS g = inv(deg);
        f *= g;
        return f.integral().pre(deg);
    }

    // 指数 (Exp) : F[0] == 0 が必須
    FPS exp(ll deg = -1) const {
        if (deg == -1) deg = this->size();
        FPS res{1};
        for (ll d = 1; d < deg; d *= 2) {
            FPS f = res.log(2 * d);
            f[0] -= 1;
            for (ll i = 0; i < 2 * d; i++) f[i] = -f[i];
            FPS g = pre(2 * d);
            f += g;
            res *= f;
            res.resize(2 * d);
        }
        return res.pre(deg);
    }

    // 累乗 (Pow) : 定数項が0の場合（先行ゼロ）にも対応
    FPS pow(long long k, ll deg = -1) const {
        if (deg == -1) deg = this->size();
        if (k == 0) {
            FPS res(deg, 0);
            if (deg > 0) res[0] = 1;
            return res;
        }
        for (ll i = 0; i < (ll)this->size(); i++) {
            if ((*this)[i] != 0) {
                mint rev = (*this)[i].inv();
                FPS f(*this);
                for (ll j = 0; j < (ll)f.size(); j++) f[j] *= rev;
                f = f.pre(deg);
                f.erase(f.begin(), f.begin() + i);
                f = f.log(deg);
                for (ll j = 0; j < (ll)f.size(); j++) f[j] *= k;
                f = f.exp(deg);
                for (ll j = 0; j < (ll)f.size(); j++) f[j] *= (*this)[i].pow(k);
                
                FPS res(deg, 0);
                long long shift = i * k;
                if (shift >= deg) return res;
                for (ll j = 0; j < (ll)f.size() && j + shift < deg; j++) {
                    res[j + shift] = f[j];
                }
                return res;
            }
        }
        return FPS(deg, 0);
    }
};

using mint = modint998244353;
using fps = FPS<mint>;

// 乱数生成を扱いやすくする構造体
struct Random {
    mt19937_64 mt; // 64ビット版メルセンヌ・ツイスター

    // コンストラクタ：引数なしなら現在時刻、引数ありならその値をシードにする
    Random(uint64_t seed = chrono::steady_clock::now().time_since_epoch().count()) : mt(seed) {}

    // 1. nextInt: [L, R] の閉区間の整数を等確率でランダムに返す
    ll nextInt(ll L, ll R) {
        uniform_int_distribution<ll> dist(L, R);
        return dist(mt);
    }

    // 2. nextDouble: [0.0, 1.0) の実数を一様分布でランダムに返す
    double nextDouble() {
        uniform_real_distribution<double> dist(0.0, 1.0);
        return dist(mt);
    }
};

#include <chrono>

// Randomの導入が必要

// 実行時間を計測するための構造体
struct Timer {
    chrono::steady_clock::time_point start_time;
    
    // コンストラクタで生成時の時間を記録
    Timer() : start_time(chrono::steady_clock::now()) {}

    // 経過時間を秒単位の実数 (double) で返す
    double elapsed() const {
        return chrono::duration_cast<chrono::duration<double>>(
            chrono::steady_clock::now() - start_time).count();
    }
};

// 時間制限付き乱択アルゴリズムのテンプレート
void solve() {
    Timer timer;
    Random rnd;
    
    // TLEを避けるため、実際の制限時間より少し短めに設定 (例: 2.0秒制限なら1.8〜1.9秒)
    const double TIME_LIMIT = 1.8; 

    long long best_score = -1; // 最小化問題の場合は 1e18 などにする
    // ここに最良の解（状態）を保持する変数を定義する (例: vector<int> best_state;)

    int loop_count = 0; // 性能評価用（何回ループを回せたか）

    // 制限時間になるまでひたすらループを回す
    while (timer.elapsed() < TIME_LIMIT) {
        loop_count++;

        // 1. ランダムに解の候補を生成、または現在の解を少し変化させる（近傍遷移）
        // 例: int v = rnd.nextInt(0, N - 1);
        
        // 2. その解のスコアを計算する
        long long current_score = /* 評価関数の結果 */;

        // 3. スコアが改善されていたら、ベストスコアとベスト状態を更新する
        if (current_score > best_score) {
            best_score = current_score;
            // best_state = current_state; などの状態保存処理
        }
    }

    // デバッグ用: ループ回数や最終スコアを出力（本番では消すか cerr のままにする）
    // cerr << "Loop Count: " << loop_count << endl;
    // cerr << "Best Score: " << best_score << endl;

    // 最後に最良の解を出力する
    // print(best_state);
}

// pair の定義
pair<ll, ll> p = {1, 2};
auto q = make_pair(3, 4);

// 要素の読み出し
cout << p.first << " " << p.second << "\n";

// structured binding (C++17)
auto [x, y] = p;
cout << x << " " << y << "\n";

// tuple の定義
tuple<ll, ll, ll> t = {1, 2, 3};

// tuple の分解
auto [a, b, c] = t;

// tuple の要素取得
cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << "\n";

long long s = accumulate(v.begin(), v.end(), 0LL);

vector<ll> id(n);
iota(id.begin(), id.end(), 0);

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

auto it = min_element(v.begin(), v.end());
auto jt = max_element(v.begin(), v.end());

ll y = clamp(x, 0, 100);

auto f = [&](ll x) {
    return x * x;
};

// a=1, b=2, ..., z=26
ll alphabetIndexLower(char c) {
    if ('a' <= c && c <= 'z') {
        return c - 'a' + 1;
    }
    return -1; // 範囲外
}

// 使用例
char c = 'c';
cout << alphabetIndexLower(c) << "\n"; // 3

// A=1, B=2, ..., Z=26
ll alphabetIndexUpper(char c) {
    if ('A' <= c && c <= 'Z') {
        return c - 'A' + 1;
    }
    return -1; // 範囲外
}

// 使用例
char c = 'C';
cout << alphabetIndexUpper(c) << "\n"; // 3

vector<long long> xs = {10, 100, 1000};
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());

auto get_id = [&](long long x) {
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
};

for (auto &x : xs)
    x = get_id(x);

vector<pair<char, long long>> rle;

for (ll i = 0; i < N; ) {
    ll j = i;
    while (j < N && S[j] == S[i]) j++;

    rle.push_back({S[i], j - i});
    i = j;
}