如题 看不懂单词建议百度翻译 不建议在OJ上查看 请善用编辑器的折叠功能

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::ios;

/*
Copyright : yeyou26
命名规范：
下划线分割
常量：全大写
函数：首字母大写
类型名 命名空间 变量：全小写
数据结构定义结构体
算法定义namespace

调教vscode
1.设置搜索toggle 设置切换注释 ctrl+shift+c
2.设置搜索format 设置自动格式化为file
3.父级目录创建 .clang-format
格式化如下:
BasedOnStyle: Microsoft
AllowShortLoopsOnASingleLine : True
AllowShortIfStatementsOnASingleLine : AllIfsAndElse
NamespaceIndentation : All
*/

namespace miscellaneous
{
    void Divide()
    {
        int tmp = -3;
        cout << tmp / 2 << endl;    // 向0取整
        cout << (tmp >> 1) << endl; // 向下取整
    }
    void Bitwise_operation_for_char()
    {
        char letter1 = 'a';
        char letter2 = 'A';
        cout << (letter1 & 31) << " " << (letter2 & 31) << '\n'; // &31 -> 输出这个字母在字母表中的位次
        cout << (letter1 ^ 64) << " " << (letter2 ^ 64) << "\n"; // ^64 -> 大写字母1-26 小写字母33-58
        cout << ('0' ^ 48) << '\n';                              // 数字字符^48 -> 数字本身值
    }
    void Cancel_sync()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    void Enum()
    {
        enum
        {
            N = 100,
            M = 1000
        };
        cout << N << " " << M << endl;
        enum A
        {
            apple = 11,
            banana = 22
        } ea;
        ea = apple;  // ea=11
        ea = banana; // ea=22
        // ea=N; //非法
        int tmp; // 变量
        tmp = N;
        tmp = apple; // tmp=11;
        cout << ea << " " << tmp << std::endl;
    }
} // namespace miscellaneous

namespace frequently_used_functions
{
    void Cout()
    {
        cout.precision(6);         // 设置精度
        cout.setf(ios::fixed);     // 精度指小数点后位数 使用一般方式输出浮点数
        cout.unsetf(ios::fixed);   // 精度指有效数字位数 系统可能使用E来表示浮点数
        cout.setf(ios::showpoint); // 输出小数部分的后置零
    }
    void Memset()
    {
        unsigned long long tmp[10];
        memset(tmp, 0, sizeof(tmp));    // 0000 0000
        memset(tmp, -1, sizeof(tmp));   // 1111 1111
        memset(tmp, 0x3f, sizeof(tmp)); // 1e9 / 4e18 量级 相加不爆 0011 1111
        memset(tmp, 0x7f, sizeof(tmp)); // 2e9 / 9e18 量级 相机会爆 0111 1111
        memset(tmp, 0xc0, sizeof(tmp)); //-1e9 / 4e18 量级 相机不爆 1011 0000
        memset(tmp, 0x80, sizeof(tmp)); //-2e9 / 9e18 量级 相加会爆 1000 0000
        // unsigned 类型现推就行 相加不爆 0x7f 最大值0xff
    }
    void Memcpy()
    {
        int target[10] = {}, text[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, len = 5;
        memcpy(target + 1, text + 1, sizeof(int) * len);
        for (int i = 1; i <= 9; i++) cout << target[i] << " ";
        cout << endl;
        memcpy(target, text, sizeof(text));
        for (int i = 1; i <= 9; i++) cout << target[i] << " ";
    }
    void Char_array() // 使用一定要保证字符串末尾有'\0'
    {
        char a[14], b[14];
        strcpy(a, "hello"); // 完全替换
        strcpy(b, a);
        cout << b << endl;
        strcat(a, b);
        cout << a << endl;
        cout << strlen(a) << endl;
        cout << (char)strcmp(a, b) << endl; // 返回第一个不相同字符的ascll值之差 如果相同返回0
        cout << *strchr(a, 'o') << endl;    // 返回后者在前者中第一次出现的指针，后者是int
        cout << strstr(a, "llo") << endl; // 如果后者是前者字串，返回第一次出现的左端点指针，否则返回空指针
        cin.getline(a, 10); // 实际上读9个字符（含一个\0）
    }
    void String()
    {
        using std::string;
        string a, b, c;
        a = "abcde";
        b = "12345";
        c = a + b;
        cout << c << endl;
        a += b;
        cout << a << endl;
        a.push_back('f');
        cout << a << endl;
        c = "de";
        cout << a.find(c) << endl; // 返回第一次出现的下标
        int pos;
        cout << ((pos = a.find("114514") == string::npos) ? -1 : pos) << endl;
        a.insert(0, "x"); // 插入字符串
        cout << a << endl;
        cout << a.size() << endl;
        cout << a.substr(0, 4) << endl;
    }
    void Math()
    {
        cout << std::ceil(0.5) << endl;
        cout << std::floor(0.5) << endl;
        cout << std::round(0.5) << endl;
    }
    void Std()
    {
        int a[100];
        std::reverse(a, a + 9); // 区间反转 左闭右开
        std::unique(a, a + 9);  // 去重 左闭右开 返回第一个重复元素的！！指针！！
    }
    void Others()
    {
        exit(0); // 结束程序
    }
    void Mt19937()
    {
        std::random_device seed;
        unsigned int sd = seed();
        std::mt19937 rd;
        rd.seed(sd);
        rd.operator()();
    }
} // namespace frequently_used_functions

namespace re_wa_ce
{
    // “xxx的声明指定了两个以上的数据类型”：结构体等后面没写分号
    // 注意字符串起始位置
    // priority queue 默认大根
    // ISO C++ 不允许声明无类型的‘xxx’ [-fpermissive] 注意自定义类型名是不是写错了
    //  struct 没有默认构造函数
}

// data_structure

struct trie_tree
{
    enum
    {
        N = 10000,
        M = 28
    }; // 节点数 和字符集大小
    int tr[N][M], idx = 0, cnt[N];
    void Insert(char *s)
    {
        int lens = strlen(s + 1), p = 0;
        for (int i = 1; i <= lens; i++)
        {
            int ch = s[i] & 31;
            if (tr[p][ch]) p = tr[p][ch];
            else p = tr[p][ch] = ++idx;
        }
        cnt[p]++;
    }
    int Query(char *s)
    {
        int lens = strlen(s + 1), p = 0;
        for (int i = 1; i <= lens; i++)
        {
            int ch = s[i] & 31;
            if (tr[p][ch]) p = tr[p][ch];
            else return 0;
        }
        return cnt[p];
    }
};

struct aho_corasick_automaton
{
    enum
    {
        N = 1000005,
        M = 30
    };
    int tr[N][M], idx, cnt[N], fail[N];
    void Insert(char *s)
    {
        int lens = strlen(s + 1), p = 0;
        for (int i = 1; i <= lens; i++)
        {
            int ch = s[i] & 31;
            if (tr[p][ch]) p = tr[p][ch];
            else p = tr[p][ch] = ++idx;
        }
        cnt[p]++;
    }
    void Build()
    {
        std::queue<int> q;
        for (int ch = 1; ch <= 26; ch++)
        {
            if (tr[0][ch]) q.push(tr[0][ch]);
        }
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int ch = 1; ch <= 26; ch++)
            {
                int v = tr[u][ch];
                if (v) fail[v] = tr[fail[u]][ch], q.push(v);
                else tr[u][ch] = tr[fail[u]][ch];
            }
        }
    }
    int Query(char *s) // 根据具体题目不同 此处以 “忽略主串中重复的模式串 不忽略插入时重复的模式串” 为例
    {
        int lens = strlen(s + 1), p = 0, ans = 0;
        for (int i = 1; i <= lens; i++)
        {
            int ch = s[i] & 31;
            p = tr[p][ch];
            for (int j = p; j && cnt[j] != -1; j = fail[j])
            {
                ans += cnt[j];
                cnt[j] = -1;
            }
        }
        return ans;
    }
};

struct sparse_table
{
    enum
    {
        N = 100005,
        M = 25 // log N
    };
    int a[N], n, qr[N][M], lg2[N];
    void Generate(int _n)
    {
        n = _n;
        std::mt19937 rd;
        rd.seed(n);
        for (int i = 1; i <= n; i++) cout << (a[i] = rd.operator()() % INT_MAX) << endl;
    }
    void Build()
    {
        for (int i = 2; i <= N - 2; i++) lg2[i] = lg2[i / 2] + 1;
        for (int i = 1; i <= n; i++) qr[i][0] = a[i];
        for (int k = 1; k <= lg2[n] + 1; k++)
        {
            for (int i = 1; i + (1 << k) - 1 <= n; i++)
                qr[i][k] = std::max(qr[i][k - 1], qr[1 + (i << (k - 1))][k - 1]);
        }
    }
    int Query(int l, int r)
    {
        int k = lg2[r - l + 1];
        return std::max(qr[l][k], qr[r - (1 << k) + 1][k]);
    }
};

struct union_set
{
    enum
    {
        N = 100005
    };
    int fa[N], siz[N], high[N];
    union_set(int _n = N - 2) // 不写初始化 直接见祖宗
    {
        for (int i = 1; i <= _n; i++) fa[i] = i;
        for (int i = 1; i <= _n; i++) siz[i] = 1;
        for (int i = 1; i <= _n; i++) high[i] = 1;
    }
    inline int Find(int x)
    {
        while (x ^ fa[x]) x = fa[x];
        return x;
    }
    int Find_zip(int x) // 路径压缩
    {
        return fa[x] == x ? x : fa[x] = Find(fa[x]);
    }
    void Union_zip(int x, int y)
    {
        x = Find(x), y = Find(y);
        if (x == y) return;
        fa[y] = x;
    }
    void Union_high(int x, int y)
    {
        x = Find(x), y = Find(y);
        if (x == y) return;
        if (high[x] < high[y]) std::swap(x, y);
        fa[y] = x;
        if (high[x] == high[y]) high[x]++;
    }
    void Union_size(int x, int y)
    {
        x = Find(x), y = Find(y);
        if (x == y) return;
        if (siz[x] < siz[y]) std::swap(x, y);
        fa[y] = x;
        siz[x] += siz[y];
    }
};

struct heap
{
    enum
    {
        N = 10005
    };
    int a[N], size;
    heap()
    {
        size = 0;
        memset(a, 0, sizeof(a));
    }
    int Empty()
    {
        return size ? 0 : 1;
    }
    int Size()
    {
        return size;
    }
    int Top()
    {
        return a[1];
    }
    void Push(int val)
    {
        a[++size] = val;
        int u = size;
        while (u / 2 > 0 && a[u] < a[u / 2])
        {
            std::swap(a[u], a[u / 2]);
            u /= 2;
        }
    }
    int Pop()
    {
        if (!size) return 0;
        a[1] = a[size--];
        int u = 1, pos = 1;
        while (1)
        {
            if (u * 2 <= size && a[u] > a[u * 2]) pos = u * 2;
            if (u * 2 + 1 <= size && a[pos] > a[u * 2 + 1]) pos = u * 2 + 1;
            if (pos == u) return 1;
            std::swap(a[pos], a[u]);
            u = pos;
        }
        return 0;
    }
};

struct binary_indexed_tree
{
    enum
    {
        N = 100005
    };
    int a[N], n;
    binary_indexed_tree(int _n)
    {
        memset(a, 0, sizeof(a));
        n = _n;
    }
    inline int Lowbit(int x)
    {
        return x & (-x);
    }
    void Modify(int index, int val)
    {
        while (index <= n)
        {
            a[index] += val;
            index += Lowbit(index);
        }
    }
    int Query(int index)
    {
        int ans = 0;
        while (index)
        {
            ans += a[index];
            index -= Lowbit(index);
        }
        return ans;
    }
    int Query(int i, int j)
    {
        return Query(j) - Query(i - 1);
    }
};

struct segment_tree
{
    enum
    {
        N = 100005
    };
#define lc (u << 1)
#define rc (u << 1 | 1)
    struct node
    {
        int l, r, sum, lazy;
    } tr[4 * N];
    int a[N], n;
    segment_tree(int _n = N - 4)
    {
        n = _n;
        memset(tr, 0, sizeof(tr));
    }
    void Pushup(int u)
    {
        tr[u].sum = tr[lc].sum + tr[rc].sum;
    }
    void Build(int u, int l, int r)
    {
        if (l >= r)
        {
            tr[u] = {l, r, a[l], 0};
            return;
        }
        int mid = (l + r) / 2;
        tr[u].l = l;
        tr[u].r = r;
        Build(lc, l, mid);
        Build(rc, mid + 1, r);
        Pushup(u);
    }
    void Init()
    {
        for (int i = 1; i <= n; i++) cin >> a[i];
        Build(1, 1, n);
    }
    void Pushdown(int u)
    {
        if (tr[u].lazy)
        {
            tr[lc].lazy += tr[u].lazy;
            tr[rc].lazy += tr[u].lazy;
            tr[lc].sum += tr[u].lazy * (tr[lc].r - tr[lc].l + 1);
            tr[rc].sum += tr[u].lazy * (tr[rc].r - tr[rc].l + 1);
            tr[u].lazy = 0;
        }
    }
    void Modify(int u, int l, int r, int val) // 裂区间的时候注意是裂的lr是节点的lr而不是操作区间的lr
    {
        if (l <= tr[u].l && r >= tr[u].r)
        {
            tr[u].lazy += val;
            tr[u].sum += val * (tr[u].r - tr[u].l + 1);
            return;
        }
        int mid = (tr[u].l + tr[u].r) / 2;
        Pushdown(u);
        if (l <= mid) Modify(lc, l, r, val);
        if (r >= mid + 1) Modify(rc, l, r, val);
        Pushup(u);
    }
    int Query(int u, int l, int r) // 裂区间的时候注意是裂的lr是节点的lr而不是操作区间的lr
    {
        if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
        int mid = (tr[u].l + tr[u].r) / 2, ans = 0;
        Pushdown(u);
        if (l <= mid) ans += Query(lc, l, r);
        if (r >= mid + 1) ans += Query(rc, l, r);
        return ans;
    }
#undef lc
#undef rc
};

// algorithms

namespace kmp
{
    enum
    {
        N = 100005
    }; // 字符串长度
    int lst[N], lenp, lens;
    char p[N], s[N];
    int Kmp()
    {
        cin >> (s + 1) >> (p + 1); // 输入模式串和主串
        lens = strlen(s + 1), lenp = strlen(p + 1);
        lst[1] = 0;
        for (int i = 2, j = 0; i <= lenp; i++) // Get_pre
        {
            while (j && p[j + 1] != p[i]) j = lst[j];
            if (p[i] == p[j + 1]) j++;
            lst[i] = j;
        }
        for (int i = 1, j = 0; i <= lens; i++) // Compare
        {
            while (j && p[j + 1] != s[i]) j = lst[j];
            if (s[i] == p[j + 1]) j++;
            if (j == lenp) return i - lenp + 1; // 返回第一次匹配的起始位置
        }
        return -1;
    }
} // namespace kmp

namespace sort
{
    enum
    {
        N = 1000006, // 元素个数
        M = 1000006  // 值域
    };
    int a[N], n;
    void Generate(int _n) // 生成一些随机数
    {
        n = _n;
        std::random_device seed;
        std::mt19937 rd;
        unsigned int sd = seed();
        rd.seed(sd);
        for (int i = 1; i <= n; i++) cout << (a[i] = rd.operator()() % (M - 10)) << '\n';
        cout << endl;
    }
    void Show(int _n = n)
    {
        for (int i = 1; i <= _n; i++) cout << a[i] << "\n";
        cout << endl;
    }
    void Bubble_sort()
    {
        for (int i = 1; i <= n - 1; i++)
        {
            int check = 1;
            for (int j = 1; j <= n - i; j++)
            {
                if (a[j] > a[j + 1]) std::swap(a[j], a[j + 1]), check = 0;
            }
            if (check) break;
        }
    }
    void Selection_sort()
    {
        for (int i = 1; i <= n - 1; i++)
        {
            int jp = i;
            for (int j = i + 1; j <= n; j++)
            {
                if (a[j] < a[jp]) jp = j;
            }
            std::swap(a[jp], a[i]);
        }
    }
    void Insertion_sort()
    {
        for (int i = 2; i <= n; i++)
        {
            int val = a[i], j;
            for (j = i; j >= 1; j--)
            {
                if (a[j] > val) std::swap(a[j], a[j + 1]);
                else break;
            }
            a[j + 1] = val;
        }
    }
    int b[N], cnt = 0;
    void Mgst(int l, int r)
    {
        int mid = (l + r) / 2;
        if (l >= r) return;
        Mgst(l, mid);
        Mgst(mid + 1, r);
        int i = l, j = mid + 1, k = l;
        while (i <= mid && j <= r)
        {
            if (a[i] <= a[j]) b[k++] = a[i++];
            else b[k++] = a[j++], cnt += mid - i + 1;
        }
        while (i <= mid && k <= r) b[k++] = a[i++];
        while (j <= r && k <= r) b[k++] = a[j++];
        for (i = l; i <= r; i++) a[i] = b[i];
    }
    int Merge_sort()
    {
        Mgst(1, n);
        return cnt;
    }
    void Radix_sort()
    {
    }
    void Quick_sort()
    {
    }
    void Bucket_sort()
    {
        for (int i = 1; i <= n; i++) b[a[i]]++;
        for (int i = 1, idx = 0; i <= M - 10; i++)
        {
            while (b[i]--) a[++idx] = i;
        }
    }
    int c[N];
    void Counting_sort()
    {
        for (int i = 1; i <= n; i++) c[a[i]]++;
        for (int i = 1; i <= M - 5; i++) c[i] += c[i - 1];
        for (int i = 1; i <= n; i++) b[c[a[i]]--] = a[i];
        for (int i = 1; i <= n; i++) a[i] = b[i];
    }
} // namespace sort

namespace hash
{
    const int p = 13331;
    int Compare(char *s1, char *s2)
    {
        unsigned int val1 = 0, val2 = 0;
        int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);
        for (int i = 1; i <= len1; i++) val1 = val1 * p + s1[i];
        for (int i = 1; i <= len2; i++) val2 = val2 * p + s2[i];
        return (val1 == val2);
    }
} // namespace hash

namespace discrete
{
    enum
    {
        N = 100005
    };
    struct node
    {
        int val, id;
    } nod[N];
    bool Cmp(node x, node y)
    {
        return x.val == y.val ? x.id < y.id : x.val < y.val;
    }
    int ori[N], dsc[N], tmp[N], n, len;
    void Generate(int _n)
    {
        n = _n;
        std::mt19937 rd;
        rd.seed(n);
        for (int i = 1; i <= n; i++) cout << (ori[i] = rd.operator()() % INT_MAX) << '\n';
    }
    void Show(int _n = n)
    {
        for (int i = 1; i <= _n; i++) cout << dsc[i] << " ";
        cout << endl;
    }
    void Discrete_unique()
    {
        for (int i = 1; i <= n; i++) tmp[i] = ori[i];
        std::sort(tmp + 1, tmp + 1 + n);
        len = std::unique(tmp + 1, tmp + 1 + n) - (tmp + 1); // 这里要+1 unique返回尾指针
        for (int i = 1; i <= n; i++) dsc[i] = std::lower_bound(tmp + 1, tmp + len + 1, ori[i]) - tmp;
    }
    void Discrete_not_unique()
    {
        for (int i = 1; i <= n; i++) nod[i].val = ori[i], nod[i].id = i;
        std::sort(nod + 1, nod + 1 + n, Cmp);
        for (int i = 1; i <= n; i++) dsc[nod[i].id] = i;
    }
} // namespace discrete

namespace kruskal
{
    enum
    {
        N = 5006,
        M = 200005
    };
    struct edge
    {
        int u, v, w;
        bool operator<(const edge &o) const
        {
            return w < o.w;
        }
    } e[M];
    int n, m, cnt, ans;
    union_set ust(N);
    void Init()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    }
    int Kruskal()
    {
        std::sort(e + 1, e + 1 + m);
        for (int i = 1; i <= m && cnt < n - 1; i++)
        {
            int u = e[i].u, v = e[i].v;
            if (ust.Find_zip(u) == ust.Find_zip(v)) continue;
            cnt++, ans += e[i].w, ust.Union_zip(u, v);
        }
        if (cnt < n - 1) return -1;
        else return ans;
    }
} // namespace kruskal

namespace prim_heap
{
    using std::make_pair;
    using std::pair;
    enum
    {
        N = 5005,
        M = 200005
    };
    struct edge
    {
        int v, w, nxt;
        bool operator<(const edge &o) const
        {
            return w < o.w;
        }
    } e[2 * M];
    int head[N], eid, vis[N], d[N];
    void Adde(int u, int v, int w)
    {
        eid++;
        e[eid].v = v;
        e[eid].w = w;
        e[eid].nxt = head[u];
        head[u] = eid;
    }
    int n, m;
    void Init()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            Adde(u, v, w);
            Adde(v, u, w);
        }
    }
    struct pii
    {
        int id, dis;
        bool operator<(const pii &o) const
        {
            return dis > o.dis;
        }
    };
    std::priority_queue<pii> pq;
    int Prim_heap(int st = 1)
    {
        memset(vis, 0, sizeof(vis));
        memset(d, 0x3f, sizeof(d));
        int cnt = 0, ans = 0;
        d[st] = 0;
        pq.push((pii){st, 0});
        while (!pq.empty())
        {
            int u = pq.top().id, w = pq.top().dis;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            cnt++;
            ans += w;
            for (int i = head[u]; i; i = e[i].nxt)
            {
                int v = e[i].v;
                if (vis[v]) continue;
                if (d[v] > e[i].w)
                {
                    d[v] = e[i].w;
                    pq.push((pii){v, e[i].w});
                }
            }
        }
        if (cnt < n) return -1;
        return ans;
    }

} // namespace prim_heap

namespace dijkstra_heap
{
    enum
    {
        N = 100005,
        M = 200005
    };
    int n, m;
    struct edge
    {
        int v, w, nxt;
    } e[M * 2];
    int head[N], d[N], eid, vis[N], s;
    struct pii
    {
        int id, dis;
        bool operator<(const pii &o) const
        {
            return dis > o.dis;
        }
    };
    std::priority_queue<pii> pq;
    void Adde(int u, int v, int w)
    {
        eid++;
        e[eid].v = v;
        e[eid].w = w;
        e[eid].nxt = head[u];
        head[u] = eid;
    }
    void Init()
    {
        cin >> n >> m >> s;
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            Adde(u, v, w);
        }
    }
    void Dijkstra(int st = 1)
    {
        memset(vis, 0, sizeof(vis));
        memset(d, 0x3f, sizeof(d));
        d[st] = 0;
        pq.push((pii){st, 0});
        while (!pq.empty())
        {
            int u = pq.top().id;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (int i = head[u]; i; i = e[i].nxt)
            {
                int v = e[i].v;
                if (vis[v]) continue;
                if (d[v] > d[u] + e[i].w)
                {
                    d[v] = d[u] + e[i].w;
                    pq.push((pii){v, d[v]});
                }
            }
        }
    }
} // namespace dijkstra_heap

namespace spfa
{
    enum
    {
        N = 100005,
        M = 200005
    };
    int n, m, s;
    struct edge
    {
        int v, w, nxt;
    } e[M * 2];
    int head[N], eid, inq[N], d[N];
    void Adde(int u, int v, int w)
    {
        eid++;
        e[eid].v = v;
        e[eid].w = w;
        e[eid].nxt = head[u];
        head[u] = eid;
    }
    std::queue<int> q;
    void Init()
    {
        cin >> n >> m >> s;
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            Adde(u, v, w);
        }
    }
    void Spfa(int st = 1)
    {
        memset(inq, 0, sizeof(inq));
        memset(d, 0x3f, sizeof(d));
        d[st] = 0;
        q.push(st), inq[st] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (int i = head[u]; i; i = e[i].nxt)
            {
                int v = e[i].v;
                if (d[v] > d[u] + e[i].w)
                {
                    d[v] = d[u] + e[i].w;
                    if (!inq[v]) q.push(v), inq[v] = 1;
                }
            }
        }
    }
} // namespace spfa

namespace topo_sort
{
    enum
    {
        N = 104
    };
    int n, ans[N], idx, r[N];
    std::vector<int> e[N];
    std::queue<int> q;
    void Init()
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int v;
            while (cin >> v)
            {
                if (v == 0) break;
                r[v]++;
                e[i].push_back(v);
            }
        }
    }
    void Topo_sort()
    {
        for (int i = 1; i <= n; i++)
        {
            if (r[i] == 0) q.push(i);
        }
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            ans[++idx] = u;
            for (int v : e[u])
            {
                r[v]--;
                if (r[v] == 0) q.push(v);
            }
        }
        for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    }

} // namespace topo_sort

namespace high_precision
{
    enum
    {
        N = 100005
    };
    struct high_precision_num
    {
        int num[N], len, negative;
        high_precision_num()
        {
            memset(num, 0, sizeof(num));
            len = 0;
            negative = 0;
        }
        void Input()
        {
            char ch = getchar();
            while (ch != '-' && !(ch >= '0' && ch <= '9')) ch = getchar();
            if (ch == '-') negative = 1, ch = getchar();
            while (ch >= '0' && ch <= '9')
            {
                num[++len] = (ch ^ 48);
                ch = getchar();
            }
            std::reverse(num + 1, num + 1 + len);
        }
        void Show()
        {
            if (negative) cout << '-';
            for (int i = len; i >= 1; i--) cout << num[i];
            if (!len) cout << 0;
        }
    };
    typedef high_precision_num hpn;
    int Leq(const hpn &A, const hpn &B)
    {
        if (A.len > B.len) return 0;
        if (A.len < B.len) return 1;
        for (int i = A.len; i >= 1; i--)
        {
            if (A.num[i] > B.num[i]) return 0;
            if (A.num[i] < B.num[i]) return 1;
        }
        return 2;
    }
    hpn Add(const hpn &A, const hpn &B)
    {
        hpn R;
        R.len = std::max(A.len, B.len);
        for (int i = 1; i <= R.len; i++)
        {
            R.num[i] += A.num[i] + B.num[i];
            if (R.num[i] >= 10) R.num[i] -= 10, R.num[i + 1]++;
        }
        if (R.num[R.len + 1]) R.len++;
        return R;
    }
    hpn Minus(const hpn &A, const hpn &B)
    {
        hpn R;
        R.len = std::max(A.len, B.len);
        for (int i = 1; i <= R.len; i++)
        {
            R.num[i] += A.num[i] - B.num[i];
            if (R.num[i] < 0) R.num[i] += 10, R.num[i + 1]--;
        }
        while (!R.num[R.len] && R.len) R.len--;
        return R;
    }
    hpn Multiply(const hpn &A, const hpn &B)
    {
        hpn R;
        R.len = A.len + B.len;
        for (int i = 1; i <= A.len; i++)
        {
            for (int j = 1; j <= B.len; j++)
            {
                R.num[i + j - 1] += A.num[i] * B.num[j];
                if (R.num[i + j - 1] >= 10) R.num[i + j] += R.num[i + j - 1] / 10, R.num[i + j - 1] %= 10;
            }
        }
        while (!R.num[R.len] && R.len) R.len--;
        return R;
    }
    hpn Divide_by_low_precision(const hpn &A, const int &b, int &remainder)
    {
        hpn R;
        R.len = A.len;
        int res = 0;
        for (int i = A.len; i >= 1; i--)
        {
            res = res * 10 + A.num[i];
            R.num[i] += res / b;
            res %= b;
        }
        while (!R.num[R.len] && R.len) R.len--;
        remainder = res;
        return R;
    }
    hpn operator+(const hpn &A, const hpn &B)
    {
        hpn R;
        if (A.negative && B.negative)
        {
            R = Add(A, B);
            R.negative = 1;
            return R;
        }
        if (A.negative) return B + A;
        if (!B.negative)
        {
            return Add(A, B);
        }
        if (!Leq(B, A))
        {
            R = Minus(B, A);
            R.negative = 1;
            return R;
        }
        return Minus(A, B);
    }
    hpn operator-(const hpn &A, hpn B)
    {
        B.negative ^= 1;
        return A + B;
    }
    hpn operator*(const hpn &A, const hpn &B)
    {
        if (!(A.negative ^ B.negative)) return Multiply(A, B);
        hpn R;
        R = Multiply(A, B);
        R.negative = 1;
        return R;
    }
    hpn operator/(const hpn &A, const int b)
    {
        int remainder;
        if (!(A.negative ^ (b < 0))) return Divide_by_low_precision(A, std::abs(b), remainder);
        hpn R;
        R = Divide_by_low_precision(A, std::abs(b), remainder);
        R.negative = 1;
        return R;
    }
    hpn Divide_by_high_precision(const hpn &_A, const hpn &_B, hpn &A)
    {
        hpn R, B = _B;
        A = _A;
        R.len = A.len;
        A.negative = B.negative = 0;
        int ori_len = B.len;
        hpn fac, ten;
        fac.num[1] = 1, fac.len = 1;
        ten.num[2] = 1, ten.len = 2;
        for (int i = B.len; i < A.len; i++) fac = fac * ten;
        B = B * fac;
        while (B.len >= ori_len)
        {
            while (Leq(B, A)) R.num[B.len - ori_len + 1]++, A = A - B;
            B = B / 10;
        }
        while (!R.num[R.len] && R.len) R.len--;
        return R;
    }
    hpn operator/(const hpn &A, const hpn &B)
    {
        hpn remainder;
        if (!(A.negative ^ B.negative)) return Divide_by_high_precision(A, B, remainder);
        hpn R;
        R = Divide_by_high_precision(A, B, remainder);
        R.negative = 1;
        return R;
    }
    /*关于除法：
    1.在这个板子中，含负数除法的余数是未定义的，使用重载过的 / 只能获得商
    2.商的绝对值是被除数的绝对值除以除数的绝对值，这可能与严谨除法定义不符
    3.如果要获取余数，则使用
        Divide_by_high/low_precesion( 被除数(高精)，除数(高精或低精)，传址调用获得余数(高精或低精) )
        并保证被除数与除数都是非负的
    4.以上，笔者认为实用意义更大
    */
} // namespace high_precision

namespace strongly_connected_component
{
    enum
    {
        N = 10005
    };
    int instk[N], scc[N], scc_cnt = 0, scc_size[N], dfn[N], low[N], idx, n, m;
    std::vector<int> e[N];
    std::stack<int> stk;
    void Tarjan(int u)
    {
        dfn[u] = low[u] = ++idx;
        instk[u] = 1;
        stk.push(u);
        for (int v : e[u])
        {
            if (dfn[v] && !instk[v]) continue;
            if (!dfn[v]) Tarjan(v);
            low[u] = std::min(low[u], low[v]);
        }
        if (dfn[u] == low[u])
        {
            scc_cnt++;
            while (stk.top() != u)
            {
                instk[stk.top()] = 0;
                scc[stk.top()] = scc_cnt;
                scc_size[scc_cnt]++;
                stk.pop();
            }
            instk[stk.top()] = 0;
            scc[stk.top()] = scc_cnt;
            scc_size[scc_cnt]++;
            stk.pop();
        }
    }
} // namespace strongly_connected_component

namespace cut
{
    enum
    {
        N = 20005
    };
    int n, m, dfn[N], low[N], iscut[N], cut_cnt, idx;
    std::vector<int> e[N];
    void Init()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
    }
    void Dfs(int u, int father) // 割边与割点完全一样 删个等于号就行 且 不用考虑根节点问题
    {
        int child = 0;
        low[u] = dfn[u] = ++idx;
        for (int v : e[u])
        {
            if (v == father) continue;
            if (!dfn[v])
            {
                child++;
                Dfs(v, u);
                low[u] = std::min(low[u], low[v]);
                if (u != father && low[v] >= dfn[u] && !iscut[u]) iscut[u] = 1, cut_cnt++;
            }
            else low[u] = std::min(low[u], dfn[v]);
        }
        if (father == u && child > 1 && !iscut[u]) iscut[u] = 1, cut_cnt++;
    }
    void Get_cut()
    {
        for (int i = 1; i <= n; i++)
        {
            if (!dfn[i]) Dfs(i, i);
        }
        cout << cut_cnt << '\n';
        for (int i = 1; i <= n; i++)
        {
            if (iscut[i]) cout << i << " ";
        }
    }
} // namespace cut

namespace scanning_line
{
    enum
    {
        N = 100005
    }; // 矩形个数
#define lc (u << 1)
#define rc (u << 1 | 1)
    int posx[N * 2], n, posx_cnt;
    struct line
    {
        int x1, x2, y, type;
        bool operator<(const line &o) const
        {
            return y < o.y;
        }
    } ln[N * 2];
    struct node
    {
        int l, r, cnt, len;
    } tr[N * 2 * 4]; // 矩形个数为N x坐标关键点数量最多为2N 所以线段树节点数最多8N
    void Build(int u, int l, int r)
    {
        tr[u] = {l, r, 0, 0};
        if (l >= r) return;
        int mid = (l + r) / 2;
        Build(lc, l, mid);
        Build(rc, mid + 1, r);
    }
    void Pushup(int u)
    {
        if (tr[u].cnt) tr[u].len = posx[tr[u].r + 1] - posx[tr[u].l];
        else if (tr[u].l == tr[u].r) tr[u].len = 0; // 防止叶子节点访问不存在的孩子导致越界 也可以给节点数*2解决
        else tr[u].len = tr[lc].len + tr[rc].len;
    }
    void Modify(int u, int l, int r, int val)
    {
        if (l <= tr[u].l && r >= tr[u].r)
        {
            tr[u].cnt += val;
            Pushup(u);
            return;
        }
        int mid = (tr[u].l + tr[u].r) / 2;
        if (l <= mid) Modify(lc, l, r, val);
        if (r >= mid + 1) Modify(rc, l, r, val);
        Pushup(u);
    }
    void Init()
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            ln[i] = {x1, x2, y1, 1};
            ln[i + n] = {x1, x2, y2, -1};
            posx[i] = x1, posx[i + n] = x2;
        }
        n *= 2;
        std::sort(posx + 1, posx + 1 + n);
        std::sort(ln + 1, ln + 1 + n);
        posx_cnt = std::unique(posx + 1, posx + 1 + n) - posx - 1;
        Build(1, 1, posx_cnt);
    }
    long long ans = 0;
    void Scan()
    {
        for (int i = 1; i <= n - 1; i++)
        {
            int l = std::lower_bound(posx + 1, posx + 1 + posx_cnt, ln[i].x1) - posx;
            int r = std::lower_bound(posx + 1, posx + 1 + posx_cnt, ln[i].x2) - posx;
            Modify(1, l, r - 1, ln[i].type);
            ans += 1ll * tr[1].len * (ln[i + 1].y - ln[i].y);
        }
    }
#undef lc
#undef rc

} // namespace scanning_line

namespace lca_double
{
    enum
    {
        N = 500005,
    };
    int dep[N], fa[N][22];
    std::vector<int> e[N];
    int n, q, root;
    void Init()
    {
        cin >> n >> q >> root;
        for (int i = 1; i <= n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
    }
    void Dfs(int u, int father)
    {
        dep[u] = dep[father] + 1;
        fa[u][0] = father;
        for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
        for (int v : e[u])
        {
            if (v == father) continue;
            Dfs(v, u);
        }
    }
    int Query(int u, int v)
    {
        if (dep[u] > dep[v]) std::swap(u, v);
        for (int i = 20; i >= 0; i--)
        {
            if (dep[fa[v][i]] >= dep[u]) v = fa[v][i];
        }
        if (u == v) return u;
        for (int i = 20; i >= 0; i--)
        {
            if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
        }
        return fa[u][0];
    }

} // namespace lca_double

namespace lca_tarjan
{
    enum
    {
        N = 500005
    };
    int n, m, root, vis[N], ans[N], fa[N];
    struct query
    {
        int v, idx;
    };
    std::vector<int> e[N];
    std::vector<query> q[N];
    void Init()
    {
        cin >> n >> m >> root;
        for (int i = 1; i <= n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;
            q[u].push_back((query){v, i});
            q[v].push_back((query){u, i});
        }
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    int Find(int x)
    {
        if (fa[x] == x) return x;
        else return fa[x] = Find(fa[x]);
    }
    void Dfs(int u)
    {
        vis[u] = 1;
        for (int v : e[u])
        {
            if (vis[v]) continue;
            Dfs(v);
            fa[v] = u;
        }
        for (auto que : q[u])
        {
            if (!vis[que.v]) continue;
            ans[que.idx] = Find(que.v);
        }
    }
} // namespace lca_tarjan

namespace euler_path
{
    // 欧拉路径存在判断
    // 无向图欧拉回路：所有点度都是偶数
    // 无向图欧拉路径：有且仅有两个点度为奇数
    // 有向图欧拉回路：所有点的入度等于出度
    // 有向图欧拉路径：有且仅有一个点入度比出度多一 有且仅有一个点出度比入度多一
    enum
    {
        N = 100005
    };
    int n, m, rin[N], rout[N], st, cur[N];
    std::vector<int> e[N];
    std::stack<int> stk;
    void Init()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;
            e[u].push_back(v);
            rin[v]++, rout[u]++;
        }
    }
    void Dfs(int u)
    {
        for (int &i = cur[u]; i < (int)e[u].size();) Dfs(e[u][i++]); // 巧妙至极
        stk.push(u);
        // 算法核心是递归式地把路径上的点替换成环
        // 如果是欧拉回路，那么Dfs的时候就可以直接输出
        // 如果是欧拉路径，那么Dfs直接输出就可能出错 如1->2 2->1 1>-3
        // 入1 显然可能直接走3了 寄
        // 采用后序遍历，如果走到环，肯定会回到这个点，等u遍历完才能入栈，
        // 所以 链的部分一定是最先开始回溯的，也就是最先入栈的，推广到整张图，入栈顺序其实是找的欧拉路的逆序
        // 所以需要用栈，其实就是为了倒着输出找到的路径
    }
    void Euler_path()
    {
        for (int i = 1; i <= n; i++)
        {
            std::sort(e[i].begin(), e[i].end());
            if (std::abs(rin[i] - rout[i]) > 1) cout << "No", exit(0);
            if (rin[i] == rout[i] - 1)
            {
                if (!st) st = i;
                else cout << "No", exit(0);
            }
        }
        Dfs(st ? st : 1);
        while (!stk.empty())
        {
            cout << stk.top() << " ";
            stk.pop();
        }
    }
} // namespace euler_path

namespace ternary
{
    enum
    {
        N = 10005
    };
    const double eps = 1e-10;
    int a[N], b[N], c[N], n;
    void Init()
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i] >> b[i] >> c[i];
        }
    }
    double F(double x)
    {
        double ans = -1e20;
        for (int i = 1; i <= n; i++)
        {
            ans = std::max(ans, 1.0 * x * a[i] * x + 1.0 * b[i] * x + 1.0 * c[i]);
        }
        return ans;
    }
    void Ternary()
    {
        double l = 0, r = 1000;
        while (l + eps < r)
        {
            double mid1 = (l + r) / 2;
            double mid2 = (mid1 + r) / 2;
            if (F(mid1) > F(mid2)) l = mid1;
            else r = mid2;
        }
        cout.precision(4);
        printf("%.4lf\n", F(l));
    }
} // namespace ternary

namespace monotonous_queue
{
    enum
    {
        N = 1000006
    };
    typedef long long ll;
    int n, k;
    ll a[N];
    std::deque<int> q;
    void Init()
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];
    }
    void Get_max()
    {
        q.clear();
        for (int i = 1; i <= n; i++)
        {
            while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
            q.push_back(i);
            if (!q.empty() && q.front() + k <= i) q.pop_front();
            if (i >= k) cout << a[q.front()] << " ";
        }
        cout << '\n';
    }
    void Get_min()
    {
        q.clear();
        for (int i = 1; i <= n; i++)
        {
            while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
            q.push_back(i);
            if (!q.empty() && q.front() + k <= i) q.pop_front();
            if (i >= k) cout << a[q.front()] << " ";
        }
        cout << '\n';
    }
} // namespace monotonous_queue

namespace mf
{
}

int main()
{
    using namespace mf;
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    
    return 0;
}