Chillee

int binExp(int b, int pw) {
    if (pw == 0)
        return 1;
    return binExp(b * b % MOD, pw / 2) * (pw & 1 ? b : 1) % MOD;
}

Chillee

ll bin_exp(ll base, ll exp){ 
    if (exp==0) return 1;
    return bin_exp(base*base%MOD, exp/2)*(exp%2==1 ? base : 1)%MOD;
}

ll mod_inv(ll a){
    return bin_exp(a, MOD-2);
}

Chillee

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)
typedef long long ll;
using namespace std;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}

Chillee

struct Trie {
    const static int MAXCHAR = 26;
    struct Vertex {
        int nxt[MAXCHAR];
        bool leaf = false;
        Vertex() { fill(begin(nxt), end(nxt), -1); }
        int &operator[](int x) { return nxt[x]; }
    };
    Trie() : trie(1) {}
    vector<Vertex> trie;

Chillee

vector<int> Z(string S) { // z[i] = Longest common prefix of S[i:] and S
    vector<int> z(S.size());
    for (int i = 1, l = -1, r = -1; i < S.size(); i++) {
        z[i] = i >= r ? 0 : min(r - i, z[i - l]);
        while (i + z[i] < S.size() && S[i + z[i]] == S[z[i]])
            z[i]++;
        if (i + z[i] > r)
            l = i, r = i + z[i];
    }
    return z;

Chillee

struct AhoCorasick {
    struct Vertex {
        int next[MAXCHAR], go[MAXCHAR];
        int leaf = -1;
        int p = -1;
        char pch;
        int link = -1, leaflink = -1;

        Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
            fill(begin(next), end(next), -1);

Chillee

vector<array<int, 2>> adj[MAXN];
int dist[MAXN];
void dijkstra(int start) {
    fill(begin(dist), end(dist), INF);
    priority_queue<array<int, 2>, vector<array<int,2>>, greater<array<int, 2>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto t = pq.top();
        pq.pop();
        if (dist[t[1]] <= t[0])

Chillee

template <int MAXN> struct SCC {
    int num[MAXN], low[MAXN];
    bool curProcess[MAXN];
    stack<int> curVis;
    int dfsCnt = 0;
    SCC() { fill(begin(num), end(num), -1), fill(begin(low), end(low), -1); }
    void dfs(int cur) {
        num[cur] = low[cur] = dfsCnt++;
        curProcess[cur] = true;
        curVis.push(cur);

Chillee

struct H {
    ull x;
    H(ull x = 0) : x(x) {}
    ull get() const { return x; }
    const static ull M = (1ull << 61) - 1;
    H operator+(H o) {
        o.x += x + 1;
        o.x = (o.x & M) + (o.x >> 61);
        return o.x - 1;
    }

Chillee

bool vis[MAXN];
void topodfs(int cur, vector<int> &ans) {
    if (vis[cur])
        return;
    vis[cur] = true;
    for (auto i : adj[cur])
        topodfs(i, ans);
    ans.push_back(cur);
}
vector<int> toposort() {