组合数学

博弈论

计算几何

#include <cstdio>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
//红黑树相关的宏定义函数,包括找兄弟,判断是左孩子右孩子,红黑节点
#define bro(x) (((x)->ftr->lc == (x)) ? ((x)->ftr->rc):((x)->ftr->lc))
#define islc(x) ((x)!=NULL && (x)->ftr->lc == (x))
#define isrc(x) ((x)!=NULL && (x)->ftr->rc == (x))
#define BLACK 0
#define RED 1
inline void write(int x) {
    if (x < 0)
        putchar('-'), x = -x;

    if (x > 9)
        write(x / 10);

    putchar(x % 10 + 48);
}
inline int read() {
    int k = 0, f = 1;
    char c = getchar();

    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (c >= '0' && c <= '9') {
        k = (k << 1) + (k << 3) + c - 48;
        c = getchar();
    }

    return k * f;
}
template <typename T>
struct RedBlackTree {
    /**红黑树节点**/
    struct RBNode {
        T val;//节点值
        bool color;//true为红,false为黑
        RBNode *ftr;
        RBNode *lc, * rc;//父亲节点左孩子右孩子
        int _size;//排名专用:记录以此点为根的树的规模

        RBNode(T v = T(), bool RB = RED, RBNode *f = NULL,
               RBNode *l = NULL, RBNode *r = NULL, int s = 1)
            : val(v), color(RB), ftr(f), lc(l), rc(r), _size(s) {}

        //删除节点专用后继
        RBNode *single_succ() {
            RBNode *ret = rc;

            while (ret->lc) {
                --(ret->_size);
                ret = ret->lc;
            }

            return ret;
        }
        //直接前驱,从处注意可以是NULL
        RBNode *pred() {
            RBNode *ret = this;

            if (!lc) {
                while (ret->ftr && ret->ftr->lc == ret)
                    ret = ret->ftr;

                ret = ret->ftr;
            } else {
                ret = ret->lc;

                while (ret->rc)
                    ret = ret->rc;
            }

            return ret;
        }
        //直接后继
        RBNode *succ() {
            RBNode *ret = this;

            if (!rc) {
                while (ret->ftr && ret->ftr->rc == ret)
                    ret = ret->ftr;

                ret = ret->ftr;
            } else {
                ret = ret->rc;

                while (ret->lc)
                    ret = ret->lc;
            }

            return ret;
        }
        //维护域
        void maintain() {
            _size = 1;

            if (lc)
                _size += lc->_size;

            if (rc)
                _size += rc->_size;
        }
    };

    /**外部不可见部分**/

    RBNode *_root;//根节点
    RBNode *_hot;//查找专用命中_hot

    void init(T v) {
        _root = new RBNode(v, BLACK, NULL, NULL, NULL, 1);
    }

    //统一重平衡代码,考虑3个节点4个子树
    //分类讨论排序不在此处做,传入接口时是排好序的
    void connect34(RBNode *nroot, RBNode *nlc, RBNode *nrc,
                   RBNode *ntree1, RBNode *ntree2, RBNode *ntree3, RBNode *ntree4) {
        nlc->lc = ntree1;

        if (ntree1)
            ntree1->ftr = nlc;

        nlc->rc = ntree2;

        if (ntree2)
            ntree2->ftr = nlc;

        nrc->lc = ntree3;

        if (ntree3)
            ntree3->ftr = nrc;

        nrc->rc = ntree4;

        if (ntree4)
            ntree4->ftr = nrc;

        nroot->lc = nlc, nlc->ftr = nroot;
        nroot->rc = nrc, nrc->ftr = nroot;
        nlc->maintain(), nrc->maintain();
        nroot->maintain();
    }

    //允许重复的查找,默认是找到同一个数的最后一个出现的位置
    RBNode *find(T v, const int op) {
        RBNode *ptn = _root;
        _hot = NULL;

        while (ptn) {
            _hot = ptn;
            ptn->_size += op;

            if (ptn->val > v)
                ptn = ptn->lc;
            else
                ptn = ptn->rc;
        }

        return ptn;
    }
    //不允许重复的查找,只要找到对应值就收手
    RBNode *rfind(T v, const int op) {
        RBNode *ptn = _root;
        _hot = NULL;

        while (ptn && ptn->val != v) {
            _hot = ptn;
            ptn->_size += op;

            if (ptn->val > v)
                ptn = ptn->lc;
            else
                ptn = ptn->rc;
        }

        return ptn;
    }

    //双红修正,采用迭代方式,迭代条件为RR-2上溢向上传2层
    //判断双红的时候,自己得先是红的,然后判断父亲节点
    void SolveDoubleRed(RBNode *nn) {
        while ((!(nn->ftr)) || nn->ftr->color == RED) {
            if (nn == _root) {
                //根节点强制重染色为黑色,并且增加黑高度
                _root->color = BLACK;
                return;
            }

            RBNode *p = nn->ftr;

            if (p->color == BLACK)
                return;//case 1:没有双红,直接返回

            RBNode *u = bro(p);
            RBNode *g = p->ftr;

            //case 2:RR-2
            if (u != NULL && u->color == RED) {
                g->color = RED;
                p->color = u->color = BLACK;
                nn = g;//下一次检查往上翻2层
            }
            //case 3:RR-1 直接返回
            //此时就是要先根据情况调整父子节点位置,排好3+4结构,重染色
            else {
                if (islc(p)) {
                    if (islc(nn)) {//zig
                        p->ftr = g->ftr;

                        if (g == _root)
                            _root = p;
                        else if (g->ftr->lc == g)
                            g->ftr->lc = p;
                        else
                            g->ftr->rc = p;

                        connect34(p, nn, g, nn->lc, nn->rc, p->rc, u);
                        p->color = BLACK;
                        g->color = RED;
                    } else { //zag-zig
                        nn->ftr = g->ftr;

                        if (g == _root)
                            _root = nn;
                        else if (g->ftr->lc == g)
                            g->ftr->lc = nn;
                        else
                            g->ftr->rc = nn;

                        connect34(nn, p, g, p->lc, nn->lc, nn->rc, u);
                        nn->color = BLACK;
                        g->color = RED;
                    }
                } else {
                    if (islc(nn)) {//zig-zag
                        nn->ftr = g->ftr;

                        if (g == _root)
                            _root = nn;
                        else if (g->ftr->lc == g)
                            g->ftr->lc = nn;
                        else
                            g->ftr->rc = nn;

                        connect34(nn, g, p, u, nn->lc, nn->rc, p->rc);
                        nn->color = BLACK;
                        g->color = RED;
                    } else { //zag
                        p->ftr = g->ftr;

                        if (g == _root)
                            _root = p;
                        else if (g->ftr->lc == g)
                            g->ftr->lc = p;
                        else
                            g->ftr->rc = p;

                        connect34(p, g, nn, u, p->lc, nn->lc, nn->rc);
                        p->color = BLACK;
                        g->color = RED;
                    }
                }

                return;
            }
        }
    }

    //双黑修正,采用迭代方式,迭代条件为BB-2B下溢向上传1层
    //如果是根节点了,就可以直接停机了
    void SolveDoubleBlack(RBNode *nn) {
        while (nn != _root) {
            RBNode *p = nn->ftr;
            RBNode *b = bro(nn);

            if (b->color == RED) { //Case 1:BB-3
                b->color = BLACK;
                p->color = RED;

                if (_root == p)
                    _root = b;

                if (p->ftr) {
                    if (p->ftr->lc == p)
                        p->ftr->lc = b;
                    else
                        p->ftr->rc = b;
                }

                b->ftr = p->ftr;

                if (islc(nn))//zag
                    connect34(b, p, b->rc, nn, b->lc, b->rc->lc, b->rc->rc);
                else//zig
                    connect34(b, b->lc, p, b->lc->lc, b->lc->rc, b->rc, nn);

                b = bro(nn), p = nn->ftr;
                //转换问题并往后接着推,维护的核心节点nn不变
            }

            if (b->lc && b->lc->color == RED) { //Case 2-1:BB-1
                bool old_p_color = p->color;
                p->color = BLACK;

                if (p->lc == nn) {//zig-zag
                    if (p->ftr) {
                        if (p->ftr->lc == p)
                            p->ftr->lc = b->lc;
                        else
                            p->ftr->rc = b->lc;
                    }

                    b->lc->ftr = p->ftr;

                    if (_root == p)
                        _root = b->lc;

                    connect34(b->lc, p, b, nn, b->lc->lc, b->lc->rc, b->rc);
                } else { //zig
                    b->lc->color = BLACK;

                    if (p->ftr) {
                        if (p->ftr->lc == p)
                            p->ftr->lc = b;
                        else
                            p->ftr->rc = b;
                    }

                    b->ftr = p->ftr;

                    if (_root == p)
                        _root = b;

                    connect34(b, b->lc, p, b->lc->lc, b->lc->rc, b->rc, nn);
                }

                p->ftr->color = old_p_color;
                return;//BB-1直接返回
            } else if (b->rc && b->rc->color == RED) { //Case 2-2:BB-1
                bool old_p_color = p->color;
                p->color = BLACK;

                if (p->lc == nn) {//zag
                    b->rc->color = BLACK;

                    if (p->ftr) {
                        if (p->ftr->lc == p)
                            p->ftr->lc = b;
                        else
                            p->ftr->rc = b;
                    }

                    b->ftr = p->ftr;

                    if (_root == p)
                        _root = b;

                    connect34(b, p, b->rc, nn, b->lc, b->rc->lc, b->rc->rc);
                } else { //zag-zig
                    if (p->ftr) {
                        if (p->ftr->lc == p)
                            p->ftr->lc = b->rc;
                        else
                            p->ftr->rc = b->rc;
                    }

                    b->rc->ftr = p->ftr;

                    if (_root == p)
                        _root = b->rc;

                    connect34(b->rc, b, p, b->lc, b->rc->lc, b->rc->rc, nn);
                }

                p->ftr->color = old_p_color;
                return;//BB-1直接返回
            }

            if (p->color == RED) {//case 3:BB-2R
                p->color = BLACK;
                b->color = RED;
                return;//BB-2R直接返回
            } else { //case 4:BB-2B
                b->color = RED;
                nn = p;
                //BB-2B下溢上传,继续迭代
            }
        }
    }

    RBNode *findKth(int Rank, RBNode *ptn) {
        if (ptn->lc == NULL) {
            if (Rank == 1)
                return ptn;
            else
                return findKth(Rank - 1, ptn->rc);
        } else {
            if (ptn->lc->_size == Rank - 1)
                return ptn;
            else if (ptn->lc->_size >= Rank)
                return findKth(Rank, ptn->lc);
            else
                return findKth(Rank - (ptn->lc->_size) - 1, ptn->rc);
        }
    }

    int find_rank(T v, RBNode *ptn) {
        if (!ptn)
            return 1;
        else if (ptn->val >= v)
            return find_rank(v, ptn->lc);
        else
            return (1 + ((ptn->lc) ? (ptn->lc->_size) : 0) + find_rank(v, ptn->rc));
    }

    /**查看现象的debug接口**/

    void previs(RBNode *ptn) {
        printf("current node value is %d, color is %s, _size is %d\n", ptn->val, ptn->color ? "Red" : "Black",
               ptn->_size);
        printf("Lchild value is ");

        if (ptn->lc)
            printf("%d _size is %d\n", ptn->lc->val, ptn->lc->_size);
        else
            puts("NULL");

        printf("Rchild value is ");

        if (ptn->rc)
            printf("%d _size is %d\n", ptn->rc->val, ptn->lc->_size);
        else
            puts("NULL");

        if (ptn->lc)
            previs(ptn->lc);

        if (ptn->rc)
            previs(ptn->rc);
    }

    void invis(RBNode *ptn) {
        if (ptn->lc)
            invis(ptn->lc);

        printf("current node value is %d, color is %s, _size is %d\n", ptn->val, ptn->color ? "Red" : "Black",
               ptn->_size);
        printf("Lchild value is ");

        if (ptn->lc)
            printf("%d _size is %d\n", ptn->lc->val, ptn->lc->_size);
        else
            puts("NULL");

        printf("Rchild value is ");

        if (ptn->rc)
            printf("%d _size is %d\n", ptn->rc->val, ptn->lc->_size);
        else
            puts("NULL");

        if (ptn->rc)
            invis(ptn->rc);
    }

    void postvis(RBNode *ptn) {
        if (ptn->lc)
            postvis(ptn->lc);

        if (ptn->rc)
            postvis(ptn->rc);

        printf("current node value is %d, color is %s, _size is %d\n", ptn->val, ptn->color ? "Red" : "Black",
               ptn->_size);
        printf("Lchild value is ");

        if (ptn->lc)
            printf("%d _size is %d\n", ptn->lc->val, ptn->lc->_size);
        else
            puts("NULL");

        printf("Rchild value is ");

        if (ptn->rc)
            printf("%d _size is %d\n", ptn->rc->val, ptn->lc->_size);
        else
            puts("NULL");
    }

    void checkconnect(RBNode *ptn) {
        if (!ptn)
            return;

        if (ptn->lc && ptn->lc->ftr != ptn) {
            printf("Oops! %d has a lc %d, but it failed to point its ftr!\n", ptn->val, ptn->lc->val);
        }

        if (ptn->rc && ptn->rc->ftr != ptn) {
            printf("Oops! %d has a rc %d, but it failed to point its ftr!\n", ptn->val, ptn->rc->val);
        }

        int sss = ptn->_size;

        if (ptn->lc)
            sss -= ptn->lc->_size;

        if (ptn->rc)
            sss -= ptn->rc->_size;

        if (sss - 1) {
            printf("Fuck it! %d's size is %d, but the sum of its children's size is %d!\n", ptn->val, ptn->_size,
                   ptn->_size - sss);
        }

        checkconnect(ptn->lc);
        checkconnect(ptn->rc);
    }

    void correctlyconnected() {
        checkconnect(_root);
    }

    /**节点对应的迭代器**/
    struct iterator {
        //这个数据实际上也要private
        RBNode *_real__node;

        iterator &operator++() {
            _real__node = _real__node->succ();
            return *this;
        }
        iterator &operator--() {
            _real__node = _real__node->pred();
            return *this;
        }
        T operator*() {
            return _real__node->val;
        }

        iterator(RBNode *node_nn = NULL) : _real__node(node_nn) {}
        iterator(T const &val_vv) : _real__node(rfind(val_vv, 0)) {}
        iterator(iterator const &iter) : _real__node(iter._real__node) {}

    };

    /**对外端口部分**/

    RedBlackTree() : _root(NULL), _hot(NULL) {}

    //插入 返回对应迭代器
    iterator insert(T v) {
        RBNode *ptn = find(v, 1);

        if (_hot == NULL) {//仅有1个节点
            init(v);
            return iterator(_root);
        }

        ptn = new RBNode(v, RED, _hot, NULL, NULL, 1);

        if (_hot->val <= v)
            _hot->rc = ptn;
        else
            _hot->lc = ptn;

        SolveDoubleRed(ptn);
        return iterator(ptn);
    }
    //删除 返回成功或失败 本题中只可能是true
    bool remove(T v) {
        RBNode *ptn = rfind(v, -1);

        if (!ptn)
            return false;

        RBNode *node_suc;

        //单双分支情况处理
        while (ptn->lc || ptn->rc) {
            if (ptn->lc == NULL)
                node_suc = ptn->rc;
            else if (ptn->rc == NULL)
                node_suc = ptn->lc;
            else
                node_suc = ptn->single_succ();

            --(ptn->_size);
            ptn->val = node_suc->val;
            ptn = node_suc;
        }

        //当对应删去的节点为黑色,则需要双黑修正
        if (ptn->color == BLACK) {
            --(ptn->_size);
            SolveDoubleBlack(ptn);
        }

        if (ptn == _root) {
            _root = NULL;
            delete ptn;
            return true;
        }

        if (ptn->ftr->lc == ptn)
            ptn->ftr->lc = NULL;
        else
            ptn->ftr->rc = NULL;

        delete ptn;
        return true;
    }
    //查排名
    int get_rank(T v) {
        return find_rank(v, _root);
    }
    int size() {
        return _root->_size;
    }
    bool empty() {
        return !_root;
    }
    iterator Kth(int Rank) {
        return iterator(findKth(Rank, _root));
    }
    iterator lower_bound(T v) {
        RBNode *ptn = _root;

        while (ptn) {
            _hot = ptn;

            if (ptn->val < v)
                ptn = ptn->rc;
            else
                ptn = ptn->lc;
        }

        if (_hot->val < v)
            ptn = _hot;
        else
            ptn = _hot->pred();

        return iterator(ptn);
    }
    iterator upper_bound(T v) {
        RBNode *ptn = _root;

        while (ptn) {
            _hot = ptn;

            if (ptn->val > v)
                ptn = ptn->lc;
            else
                ptn = ptn->rc;
        }

        if (_hot->val > v)
            ptn = _hot;
        else
            ptn = _hot->succ();

        return iterator(ptn);
    }

};
RedBlackTree<int> Tree;
int n;
int op, x, res;
RedBlackTree<int>::iterator it;
int main() {
    n = read();
    Tree.insert(-2147483647), Tree.insert(2147483647);

    while (n--) {
        op = read(), x = read();

        switch (op) {
        case 0:
            Tree.insert(x);
            break;

        case 1:
            Tree.remove(x);
            break;

        case 2:
            write(*(Tree.Kth(x + 1))), putchar('\n');
            break;

        case 3:
            write(Tree.get_rank(x) - 2), putchar('\n');
            break;

        case 4:
            res = *(Tree.lower_bound(x));
            write(res == -2147483647 ? -1 : res), putchar('\n');
            break;

        case 5:
            res = *(Tree.upper_bound(x));
            write(res == 2147483647 ? -1 : res), putchar('\n');
            break;

        default:
            puts("Invalid Instruction."), n++;
            break;
        }
    }
}

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

#define int long long
constexpr int inf = 1e12;

struct edge
{
  int u, w, f, id;
};

vector<edge> g[200010];

struct EK
{
  int s, t;
  int MinCost, MaxFlow, len;
  int dist[5005], h[5005], f[5005];
  int pre[5005], e[5005];

  void add(int x, int y, int z, int val)
  {
    int idx = (int)g[x].size(), idy = (int)g[y].size();
    g[x].push_back({y, z, val, idy});
    g[y].push_back({x, 0, -val, idx});
  }

  bool dijkstra()
  {
    for (int i = 0; i < 5005; i ++)
    {
      f[i] = 0;
      dist[i] = inf;
    }

    priority_queue<pair<int, int>> que;
    que.push({0, s});
    dist[s] = 0;
    while (!que.empty())
    {
      int x = que.top().second;
      que.pop();
      if (f[x])
        continue;
      f[x] = 1;
      for (int i = (int)g[x].size() - 1; ~i; -- i)
      {
        int y = g[x][i].u, z = g[x][i].w, val = g[x][i].f;

        if (z && dist[y] > dist[x] + val + h[x] - h[y])
        {
          dist[y] = dist[x] + val + h[x] - h[y];
          pre[y] = x;
          e[y] = i;
          if (f[y] == 0)
            que.push({-dist[y], y});
        }
      }
    }
    for (int i = 0; i <= len; i ++)
      if (dist[i] < inf)
        h[i] += dist[i];
    memset(f, 0, sizeof f);
    return dist[t] < inf;
  }

  int dfs(int x, int sum)
  {
    if (x == t || sum == 0)
      return sum;
    int sz = g[x].size(), res = 0;
    f[x] = 1;
    for (int i = 0; i < sz && sum != res; i ++)
    {
      int y = g[x][i].u, z = g[x][i].w, val = g[x][i].f, id = g[x][i].id;

      if (z == 0 || f[y] || h[x] + val != h[y])
        continue;
      int now = dfs(y, min(sum - res, z));
      g[x][i].w -= now;
      g[y][id].w += now;
      res += now;
      MinCost += now * val;
    }
    f[x] = 0;
    return res;
  }

  void dinic()
  {
    int now = 0;
    while (dijkstra())
      if (now = dfs(s, inf))
        MaxFlow += now;
  }

  void ek()
  {
    int res = 0;
    while (dijkstra())
    {
      int Min = inf;
      for (int y = t, x = pre[t]; y != s; y = pre[y], x = pre[y])
        Min = min(Min, g[x][e[y]].w);
      for (int y = t, x = pre[t]; y != s; y = pre[y], x = pre[y])
        g[x][e[y]].w -= Min, g[y][g[x][e[y]].id].w += Min;
      MinCost += h[t] * Min;
      MaxFlow += Min;
    }
  }
};

signed main()
{
  int n, m; scanf("%lld %lld", &n, &m);

  EK T;
  T.s = 1;
  T.t = n;
  T.len = n;

  for (int i = 0; i < m; i ++)
  {
    int x, y, z, val; scanf("%lld %lld %lld %lld", &x, &y, &z, &val);
    T.add(x, y, z, val);
  }
  T.dinic();
  printf("%lld %lld\n", T.MaxFlow, T.MinCost);

  return 0;
}

// https://codeforces.com/contest/1677/problem/F
#include <bits/stdc++.h>
#define ll long long
const int mod=998244353,N=262145+10;

// just interpolation
namespace ns {
    using namespace std;
    int a[N],b[N],c[N],d[N],e[N],g[N],f2[N],rev[N],p[N],ans[N],qq[N],lim;
    unsigned ll s[N];
    inline int qpow(int x,int y){
        int res=1;
        while(y){
            if(y&1) res=1ll*res*x%mod;
            x=1ll*x*x%mod;
            y>>=1;
        }
        return res;
    }
    inline void init(int mxn){
        int l=0;
        lim=1;
        while(lim<mxn)
            lim<<=1,l++;
        for(int i=1;i<lim;i++)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
        int xx=qpow(3,mod>>l);
        p[lim>>1]=1;
        for(int i=lim/2+1;i<lim;i++)
            p[i]=1ll*p[i-1]*xx%mod;
        for(int i=lim/2-1;i>0;i--)
            p[i]=p[i<<1];
    }
    inline int getL(int mxn){
        return 1<<32-__builtin_clz(mxn);
    }
    inline void DFT(int *a,int len){
        int x=__builtin_ctz(lim/len);
        for(int i=0;i<len;i++)
            s[i]=a[rev[i]>>x];
        for(int i=1;i!=len;i<<=1){
            int dg=i<<1;
            for(int j=0;j!=len;j+=dg){
                for(int k=0;k<i;k++){
                    int t1=s[i|j|k]*p[i|k]%mod;
                    s[i|j|k]=s[j|k]+mod-t1;
                    s[j|k]+=t1;
                }
            }
        }
        for(int i=0;i<len;i++)
            a[i]=s[i]%mod;
    }
    inline void IDFT(int *a,int len){
        reverse(a+1,a+len);
        DFT(a,len);
        for(int i=0;i<len;i++)
            a[i]=1ll*a[i]*(mod-mod/len)%mod;
    }
    inline void Inv(int n,int *a,int *b){
        qq[0]=qpow(a[0],mod-2);
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        for(int dg=1;dg<n;dg<<=1){
            for(int i=0;i<(dg<<1)&&i<n;i++)
                c[i]=a[i];
            for(int i=0;i<dg;i++)
                d[i]=qq[i];
            DFT(c,dg<<1),DFT(d,dg<<1);
            for(int i=0;i<(dg<<1);i++)
                c[i]=1ll*c[i]*d[i]%mod;
            IDFT(c,dg<<1);
            for(int i=0;i<dg;i++)
                c[i]=0;
            DFT(c,dg<<1);
            for(int i=0;i<(dg<<1);i++)
                c[i]=1ll*c[i]*d[i]%mod;
            IDFT(c,dg<<1);
            for(int i=dg;i<(dg<<1);i++)
                qq[i]=1ll*c[i]*(mod-1)%mod;
        }
        for(int i=0;i<n;i++)
            b[i]=qq[i];
    }
    inline void mul(int *a,int *b,int *s,int n,int m){
        int len=getL(n+m-1);
        static int c[N],d[N],e[N];
        memset(c,0,len<<2);
        memset(d,0,len<<2);
        for(int i=0;i<n;i++)
            c[i]=a[i];
        for(int i=0;i<m;i++)
            d[i]=b[i];
        DFT(c,len),DFT(d,len);
        for(int i=0;i<len;i++)
            c[i]=1ll*c[i]*d[i]%mod;
        IDFT(c,len);
        for(int i=0;i<n+m-1;i++)
            s[i]=c[i];
    }
    inline void mul2(int *a,int *b,int *s,int n,int m){
        int len=getL(n);
        static int c[N],d[N],e[N];
        memset(c,0,len<<2);
        memset(d,0,len<<2);
        for(int i=0;i<n;i++)
            c[i]=a[i];
        for(int i=0;i<m;i++)
            d[i]=b[m-i-1];
        DFT(c,len),DFT(d,len);
        for(int i=0;i<len;i++)
            e[i]=1ll*c[i]*d[i]%mod;
        IDFT(e,len);
        for(int i=0;i<n-m+1;i++)
            s[i]=e[m-1+i];
    }
    inline void Der(int *a,int *b,int n){
        for(int i=1;i<n;i++)
            b[i-1]=1ll*i*a[i]%mod;
        b[n-1]=0;
    }
    int n,m,f[N],q[N],*t[N],*t2[N],buf[N<<5],*now=buf,sz[N],x[N],y[N];
    inline void build(int l,int r,int rt){
        t[rt]=now,now+=r-l+2,t2[rt]=now,now+=r-l+2;
        if(l==r){
            t[rt][0]=1;
            t[rt][1]=x[l]?mod-x[l]:0;
            return ;
        }
        int mid=l+r>>1,ls=rt<<1,rs=rt<<1|1;
        build(l,mid,ls),build(mid+1,r,rs);
        mul(t[ls],t[rs],t[rt],mid-l+2,r-mid+1);
    }
    inline void solve(int l,int r,int rt,int *a){
        if(l==r){
            a[l]=t2[rt][0];
            return ;
        }
        int mid=l+r>>1,ls=rt<<1,rs=rt<<1|1;
        mul2(t2[rt],t[rs],t2[ls],r-l+1,r-mid+1);
        solve(l,mid,ls,a);
        mul2(t2[rt],t[ls],t2[rs],r-l+1,mid-l+2);
        solve(mid+1,r,rs,a);
    }
    int tmp1[N],tmp2[N],tmp3[N],tmp4[N],answ[N],*stein[N];
    inline void interpolation(int rt,int l,int r){
        stein[rt]=new int[r-l+1];
        if(l==r){
            stein[rt][0]=answ[l];
            return ;
        }
        int mid=l+r>>1;
        interpolation(rt<<1,l,mid),interpolation(rt<<1|1,mid+1,r);
        int len=getL(r-l+1);
        for(int i=0;i<mid-l+1;i++)
            tmp3[i]=stein[rt<<1][i];
        for(int i=0;i<r-mid;i++)
            tmp4[i]=stein[rt<<1|1][i];
        mul(t[rt<<1|1],tmp3,tmp3,r-mid+1,mid-l+1);
        mul(t[rt<<1],tmp4,tmp4,mid-l+1+1,r-mid);
        for(int i=0;i<=r-l;i++)
            stein[rt][i]=(tmp3[i]+tmp4[i])%mod;
    }
    inline void Interpolation(int *x,int *y,int *ans,int n){
        int len=getL(n);
        build(1,n,1);
        for(int i=0;i<=n;i++)
            tmp1[i]=t[1][i];
        reverse(tmp1,tmp1+n+1);
        Der(tmp1,tmp1,n+1);
        Inv(n+1,t[1],tmp2);
        mul2(tmp1,tmp2,t2[1],n*2-1,n);
        solve(1,n,1,answ);
        for(int i=1;i<=n;i++)
            answ[i]=1ll*y[i]*qpow(answ[i],mod-2)%mod;
        interpolation(1,1,n);
        for(int i=0;i<n;i++)
            ans[i]=stein[1][n-1-i];
    }
}
using i64 = long long;

constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, int b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
};

std::vector<int> rev;
std::vector<Z> roots{0, 1};
void dft(std::vector<Z> &a) {
    int n = a.size();

    if (int(rev.size()) != n) {
        int k = __builtin_ctz(n) - 1;
        rev.resize(n);
        for (int i = 0; i < n; i++) {
            rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
        }
    }

    for (int i = 0; i < n; i++) {
        if (rev[i] < i) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    if (int(roots.size()) < n) {
        int k = __builtin_ctz(roots.size());
        roots.resize(n);
        while ((1 << k) < n) {
            Z e = power(Z(3), (P - 1) >> (k + 1));
            for (int i = 1 << (k - 1); i < (1 << k); i++) {
                roots[2 * i] = roots[i];
                roots[2 * i + 1] = roots[i] * e;
            }
            k++;
        }
    }
    for (int k = 1; k < n; k *= 2) {
        for (int i = 0; i < n; i += 2 * k) {
            for (int j = 0; j < k; j++) {
                Z u = a[i + j];
                Z v = a[i + j + k] * roots[k + j];
                a[i + j] = u + v;
                a[i + j + k] = u - v;
            }
        }
    }
}
void idft(std::vector<Z> &a) {
    int n = a.size();
    std::reverse(a.begin() + 1, a.end());
    dft(a);
    Z inv = (1 - P) / n;
    for (int i = 0; i < n; i++) {
        a[i] *= inv;
    }
}
struct Poly {
    std::vector<Z> a;
    Poly() {}
    Poly(const std::vector<Z> &a) : a(a) {}
    Poly(const std::initializer_list<Z> &a) : a(a) {}
    int size() const {
        return a.size();
    }
    void resize(int n) {
        a.resize(n);
    }
    Z operator[](int idx) const {
        if (idx < size()) {
            return a[idx];
        } else {
            return 0;
        }
    }
    Z &operator[](int idx) {
        return a[idx];
    }
    Poly mulxk(int k) const {
        auto b = a;
        b.insert(b.begin(), k, 0);
        return Poly(b);
    }
    Poly modxk(int k) const {
        k = std::min(k, size());
        return Poly(std::vector<Z>(a.begin(), a.begin() + k));
    }
    Poly divxk(int k) const {
        if (size() <= k) {
            return Poly();
        }
        return Poly(std::vector<Z>(a.begin() + k, a.end()));
    }
    friend Poly operator+(const Poly &a, const Poly &b) {
        std::vector<Z> res(std::max(a.size(), b.size()));
        for (int i = 0; i < int(res.size()); i++) {
            res[i] = a[i] + b[i];
        }
        return Poly(res);
    }
    friend Poly operator-(const Poly &a, const Poly &b) {
        std::vector<Z> res(std::max(a.size(), b.size()));
        for (int i = 0; i < int(res.size()); i++) {
            res[i] = a[i] - b[i];
        }
        return Poly(res);
    }
    friend Poly operator*(Poly a, Poly b) {
        if (a.size() == 0 || b.size() == 0) {
            return Poly();
        }
        int sz = 1, tot = a.size() + b.size() - 1;
        while (sz < tot) {
            sz *= 2;
        }
        a.a.resize(sz);
        b.a.resize(sz);
        dft(a.a);
        dft(b.a);
        for (int i = 0; i < sz; ++i) {
            a.a[i] = a[i] * b[i];
        }
        idft(a.a);
        a.resize(tot);
        return a;
    }
    friend Poly operator*(Z a, Poly b) {
        for (int i = 0; i < int(b.size()); i++) {
            b[i] *= a;
        }
        return b;
    }
    friend Poly operator*(Poly a, Z b) {
        for (int i = 0; i < int(a.size()); i++) {
            a[i] *= b;
        }
        return a;
    }
    Poly &operator+=(Poly b) {
        return (*this) = (*this) + b;
    }
    Poly &operator-=(Poly b) {
        return (*this) = (*this) - b;
    }
    Poly &operator*=(Poly b) {
        return (*this) = (*this) * b;
    }
    Poly deriv() const {
        if (a.empty()) {
            return Poly();
        }
        std::vector<Z> res(size() - 1);
        for (int i = 0; i < size() - 1; ++i) {
            res[i] = (i + 1) * a[i + 1];
        }
        return Poly(res);
    }
    Poly integr() const {
        std::vector<Z> res(size() + 1);
        for (int i = 0; i < size(); ++i) {
            res[i + 1] = a[i] / (i + 1);
        }
        return Poly(res);
    }
    Poly inv(int m) const {
        Poly x{a[0].inv()};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x * (Poly{2} - modxk(k) * x)).modxk(k);
        }
        return x.modxk(m);
    }
    Poly log(int m) const {
        return (deriv() * inv(m)).integr().modxk(m);
    }
    Poly exp(int m) const {
        Poly x{1};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x * (Poly{1} - x.log(k) + modxk(k))).modxk(k);
        }
        return x.modxk(m);
    }
    Poly pow(int k, int m) const {
        int i = 0;
        while (i < size() && a[i].val() == 0) {
            i++;
        }
        if (i == size() || 1LL * i * k >= m) {
            return Poly(std::vector<Z>(m));
        }
        Z v = a[i];
        auto f = divxk(i) * v.inv();
        return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k);
    }
    Poly sqrt(int m) const {
        Poly x{1};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x + (modxk(k) * x.inv(k)).modxk(k)) * ((P + 1) / 2);
        }
        return x.modxk(m);
    }
    Poly mulT(Poly b) const {
        if (b.size() == 0) {
            return Poly();
        }
        int n = b.size();
        std::reverse(b.a.begin(), b.a.end());
        return ((*this) * b).divxk(n - 1);
    }
    std::vector<Z> eval(std::vector<Z> x) const {
        if (size() == 0) {
            return std::vector<Z>(x.size(), 0);
        }
        const int n = std::max(int(x.size()), size());
        std::vector<Poly> q(4 * n);
        std::vector<Z> ans(x.size());
        x.resize(n);
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                q[p] = Poly{1, -x[l]};
            } else {
                int m = (l + r) / 2;
                build(2 * p, l, m);
                build(2 * p + 1, m, r);
                q[p] = q[2 * p] * q[2 * p + 1];
            }
        };
        build(1, 0, n);
        std::function<void(int, int, int, const Poly &)> work = [&](int p, int l, int r, const Poly &num) {
            if (r - l == 1) {
                if (l < int(ans.size())) {
                    ans[l] = num[0];
                }
            } else {
                int m = (l + r) / 2;
                work(2 * p, l, m, num.mulT(q[2 * p + 1]).modxk(m - l));
                work(2 * p + 1, m, r, num.mulT(q[2 * p]).modxk(r - m));
            }
        };
        work(1, 0, n, mulT(q[1].inv(n)));
        return ans;
    }
};
int F[N];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k, p;
    std::cin >> n >> k >> p;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<Z> g(k + 2);
    for (int i = 1; i <= k + 1; i++) {
        g[i] = g[i - 1] + power(Z(p), i) * power(Z(i), k);
    }
    std::vector<Z> fac(k + 2), invfac(k + 2);
    fac[0] = 1;
    for (int i = 1; i <= k + 1; i++) {
        fac[i] = fac[i - 1] * i;
    }
    invfac[k + 1] = fac[k + 1].inv();
    for (int i = k + 1; i; i--) {
        invfac[i - 1] = invfac[i] * i;
    }
    for (int i = 0; i <= k + 1; i++) {
        g[i] /= power(Z(p), i);
    }

    Z C = 0;
    for (int i = 0; i <= k + 1; i++) {
        C += fac[k + 1] * invfac[i] * invfac[k + 1 - i] * (i % 2 == 0 ? 1 : -1) * g[i];
    }
    C /= power(Z(1 - Z(p).inv()), k + 1);

    for (int i = 0; i <= k + 1; i++) {
        g[i] -= C / power(Z(p), i);
    }

    ns::init(2 * (k + 1));
    for (int i = 0; i <= k; i++) {
        ns::x[i + 1] = i;
        ns::y[i + 1] = g[i].val();
    }
    ns::Interpolation(ns::x, ns::y, F, k + 1);

    auto f = Poly(std::vector<Z>(F, F + k + 1)).eval(std::vector<Z>(a.begin(), a.end()));
    for (int i = 0; i < n; i++) {
        f[i] = f[i] * power(Z(p), a[i]) + C;
    }

    std::vector<Z> l(n), r(n);
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            l[i] = 1;
        } else {
            l[i] = l[i - 1] * (a[i - 1] + 1) + 1;
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i == n - 1) {
            r[i] = 1;
        } else {
            r[i] = r[i + 1] * (a[i + 1] + 1) + 1;
        }
    }

    Z ans = 0;
    Z x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        ans += f[i] * l[i] * r[i];
        ans += (f[i] * x + a[i] * y) * r[i];
        x *= a[i] + 1;
        y *= a[i] + 1;
        x += Z(a[i]) * l[i];
        y += f[i] * l[i];
    }
    std::cout << ans.val() << "\n";

    return 0;
}

https://codeforces.com/contest/1684/problem/G
#include <bits/stdc++.h>

using i64 = long long;
struct Flow
{
  static constexpr int INF = 1e9;
  int n;
  struct Edge
  {
    int to, cap;
    Edge(int to, int cap) : to(to), cap(cap) {}
  };
  std::vector<Edge> e;
  std::vector<std::vector<int>> g;
  std::vector<int> cur, h;
  Flow(int n) : n(n), g(n) {}
  bool bfs(int s, int t)
  {
    h.assign(n, -1);
    std::queue<int> que;
    h[s] = 0;
    que.push(s);
    while (!que.empty())
    {
      int u = que.front();
      que.pop();
      for (int i : g[u])
      {
        int v = e[i].to;
        int c = e[i].cap;
        if (c > 0 && h[v] == -1)
        {
          h[v] = h[u] + 1;
          if (v == t)
            return true;
          que.push(v);
        }
      }
    }
    return false;
  }
  int dfs(int u, int t, int f)
  {
    if (u == t)
      return f;
    int r = f;
    for (int &i = cur[u]; i < int(g[u].size()); ++i)
    {
      int j = g[u][i];
      int v = e[j].to;
      int c = e[j].cap;
      if (c > 0 && h[v] == h[u] + 1)
      {
        int a = dfs(v, t, std::min(r, c));
        e[j].cap -= a;
        e[j ^ 1].cap += a;
        r -= a;
        if (r == 0)
          return f;
      }
    }
    return f - r;
  }
  void addEdge(int u, int v, int c)
  {
    g[u].push_back(e.size());
    e.emplace_back(v, c);
    g[v].push_back(e.size());
    e.emplace_back(u, 0);
  }
  int maxFlow(int s, int t)
  {
    int ans = 0;
    while (bfs(s, t))
    {
      cur.assign(n, 0);
      ans += dfs(s, t, INF);
    }
    return ans;
  }
};
int main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m;
  std::cin >> n >> m;

  std::vector<int> t(n);
  for (int i = 0; i < n; i++)
  {
    std::cin >> t[i];
  }

  Flow flow(n + 2);
  int source = n, sink = n + 1;

  int count = 0;

  for (int i = 0; i < n; i++)
  {
    if (3LL * t[i] > m)
    {
      count++;
      flow.addEdge(source, i, 1);
    }
    else
    {
      flow.addEdge(i, sink, 1);
    }
  }

  for (int i = 0; i < n; i++)
  {
    if (3LL * t[i] > m)
    {
      for (int j = 0; j < n; j++)
      {
        if (3LL * t[j] <= m && t[i] % t[j] == 0 && 2LL * t[i] + t[j] <= m)
        {
          flow.addEdge(i, j, 1);
        }
      }
    }
  }

  if (count != flow.maxFlow(source, sink))
  {
    std::cout << "-1\n";
    return 0;
  }

  std::vector<bool> vis(n);
  std::vector<std::array<int, 2>> ans;
  for (int i = 2 * n; i < int(flow.e.size()); i += 2)
  {
    int u = flow.e[i + 1].to;
    int v = flow.e[i].to;
    int c = flow.e[i + 1].cap;

    if (c > 0)
    {
      vis[u] = vis[v] = true;
      ans.push_back({2 * t[u] + t[v], t[u] + t[v]});
    }
  }

  for (int i = 0; i < n; i++)
  {
    if (!vis[i])
    {
      ans.push_back({3 * t[i], 2 * t[i]});
    }
  }

  std::cout << ans.size() << "\n";
  for (auto [x, y] : ans)
  {
    std::cout << x << " " << y << "\n";
  }

  return 0;
}

https://codeforces.com/contest/1685/problem/E

// https://codeforces.com/contest/1697/problem/F
#include <bits/stdc++.h>
using namespace std;
struct TwoSat
{
  int n;
  vector<vector<int>> e;
  vector<bool> ans;
  TwoSat(int n) : n(n), e(2 * n), ans(n) {}
  void addClause(int u, bool f, int v, bool g)
  {
    e[2 * u + !f].push_back(2 * v + g);
    e[2 * v + !g].push_back(2 * u + f);
  }
  bool satisfiable()
  {
    vector<int> id(2 * n, -1), dfn(2 * n, -1), low(2 * n, -1);
    vector<int> stk;
    int now = 0, cnt = 0;
    function<void(int)> tarjan = [&](int u)
    {
      stk.push_back(u);
      dfn[u] = low[u] = now++;
      for (auto v : e[u])
      {
        if (dfn[v] == -1)
        {
          tarjan(v);
          low[u] = min(low[u], low[v]);
        }
        else if (id[v] == -1)
        {
          low[u] = min(low[u], dfn[v]);
        }
      }
      if (dfn[u] == low[u])
      {
        int v;
        do
        {
          v = stk.back();
          stk.pop_back();
          id[v] = cnt;
        } while (v != u);
        ++cnt;
      }
    };
    for (int i = 0; i < 2 * n; ++i)
      if (dfn[i] == -1)
        tarjan(i);
    for (int i = 0; i < n; ++i)
    {
      if (id[2 * i] == id[2 * i + 1])
        return false;
      ans[i] = id[2 * i] > id[2 * i + 1];
    }
    return true;
  }
  vector<bool> answer() { return ans; }
};

void solve()
{
  int n, m, k; cin >> n >> m >> k;

  TwoSat ts(n * 2 * k);
  for (int i = 0; i < n; i++)
  {
    int offset = 2 * k * i;
    for (int j = 0; j < k - 1; j++)
    {
      ts.addClause(offset + j, false, offset + j + 1, true);
      ts.addClause(offset + k + j, true, offset + k + j + 1, false);
      ts.addClause(offset + j, true, offset + k + j + 1, true);
      ts.addClause(offset + j, false, offset + k + j + 1, false);
    }
    ts.addClause(offset + k - 1, true, offset + k - 1, true);
    ts.addClause(offset + k, true, offset + k, true);
  }
  for (int i = 0; i < n - 1; i++)
  {
    int offset1 = 2 * k * i;
    int offset2 = 2 * k * (i + 1);
    for (int j = 0; j < k; j++)
    {
      ts.addClause(offset1 + k + j, false, offset2 + k + j, true);
    }
  }

  for (int i = 0; i < m; i++)
  {
    int t;
    cin >> t;

    if (t == 1)
    {
      int p, x;
      cin >> p >> x;
      x--;
      p--;

      int offset = 2 * k * p;

      ts.addClause(offset + x, false, offset + k + x, false);
    }
    else if (t == 2)
    {

      int p, q, x;
      cin >> p >> q >> x;
      x -= 2;
      p--;
      q--;

      int offset1 = 2 * k * p;
      int offset2 = 2 * k * q;

      if (x < k - 1)
      {
        ts.addClause(offset1 + x, true, offset1 + x, true);
        ts.addClause(offset2 + x, true, offset2 + x, true);
      }
      for (int j = 0; j < x; j++)
      {
        if (j < k && x - 1 - j < k)
        {
          ts.addClause(offset1 + j, true, offset2 + x - 1 - j, true);
        }
      }
    }
    else
    {

      int p, q, x;
      cin >> p >> q >> x;
      x -= 2;
      p--;
      q--;

      int offset1 = 2 * k * p;
      int offset2 = 2 * k * q;

      if (x > k - 1)
      {
        ts.addClause(offset1 + k + x - (k - 1), true, offset1 + k + x - (k - 1), true);
        ts.addClause(offset2 + k + x - (k - 1), true, offset2 + k + x - (k - 1), true);
      }
      for (int j = 0; j < x + 1; j++)
      {
        if (j < k && x + 1 - j < k)
        {
          ts.addClause(offset1 + k + j, true, offset2 + k + x + 1 - j, true);
        }
      }
    }
  }

  if (!ts.satisfiable())
  {
    cout << "-1\n";
    return;
  }

  vector<int> a(n);

  auto ans = ts.answer();
  for (int i = 0; i < n; i++)
  {
    int offset = 2 * k * i;
    for (int j = 0; j < k; j++)
    {
      if (ans[offset + j] && ans[offset + k + j])
      {
        a[i] = j;
      }
    }
    cout << a[i] + 1 << " \n"[i == n - 1];
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T; cin >> T;
  while (T --)
  solve();

  return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

struct treap
{
#define ls t[p].lc
#define rs t[p].rc
  struct tree
  {
    int val, cnt, siz, priority, lc, rc;
  } t[maxn];
  int root, tot, p1, p2, p3;
  void push_up(int p)
  {
    t[p].siz = t[ls].siz + t[rs].siz + t[p].cnt;
  }
  int New(int val)
  {
    t[++tot] = tree{val, 1, 1, rand(), 0, 0};
    return tot;
  }
  void split(int p, int val, int &x, int &y)
  {
    if (!p)
    {
      x = 0;
      y = 0;
      return;
    }

    if (t[p].val <= val)
    {
      x = p;
      split(t[p].rc, val, t[p].rc, y);
    }
    else
    {
      y = p;
      split(t[p].lc, val, x, t[p].lc);
    }

    push_up(p);
  }
  int merge(int x, int y)
  {
    if (!x || !y)
      return x + y;

    if (t[x].priority > t[y].priority)
    {
      t[x].rc = merge(t[x].rc, y);
      push_up(x);
      return x;
    }
    else
    {
      t[y].lc = merge(x, t[y].lc);
      push_up(y);
      return y;
    }
  }
  int find(int p, int val)
  {
    if (!p)
      return 0;

    if (t[p].val == val)
      return p;

    if (t[p].val < val)
      return find(rs, val);
    else
      return find(ls, val);
  }
  void change(int p, int val, int k)
  {
    if (!p)
      return;

    if (t[p].val == val)
      t[p].cnt += k;

    if (t[p].val < val)
      change(rs, val, k);
    else if (t[p].val > val)
      change(ls, val, k);

    push_up(p);
  }
  void insert(int val)
  {
    int p = find(root, val);

    if (p)
    {
      change(root, t[p].val, 1);
      return;
    }

    split(root, val, p1, p2);
    root = merge(merge(p1, New(val)), p2);
  }
  void erase(int val)
  {
    int p = find(root, val);

    if (!p)
      return;

    if (t[p].cnt - 1 > 0)
    {
      change(root, t[p].val, -1);
      return;
    }

    split(root, val - 1, p1, p2);
    split(p2, val, p2, p3);
    root = merge(p1, p3);
  }
  int point_rank(int val)
  {
    split(root, val - 1, p1, p2);
    int ans = t[p1].siz + 1;
    root = merge(p1, p2);
    return ans;
  }
  int find_rank(int p, int rk)
  {
    if (!p)
      return 0;

    if (t[ls].siz >= rk)
      return find_rank(ls, rk);

    if (t[ls].siz + 1 <= rk && t[ls].siz + t[p].cnt >= rk)
      return t[p].val;

    return find_rank(rs, rk - t[ls].siz - t[p].cnt);
  }
  int get_pre(int val)
  {
    split(root, val - 1, p1, p2);
    int ans = find_rank(p1, t[p1].siz);
    root = merge(p1, p2);
    return ans;
  }
  int get_after(int val)
  {
    split(root, val, p1, p2);
    int ans = find_rank(p2, 1);
    root = merge(p1, p2);
    return ans;
  }
} t;

int n, a1, a2;
int main()
{
  scanf("%d", &n);

  while (n--)
  {
    scanf("%d %d", &a1, &a2);

    if (a1 == 1)
      t.insert(a2);
    else if (a1 == 2)
      t.erase(a2);
    else if (a1 == 3)
      printf("%d\n", t.point_rank(a2));
    else if (a1 == 4)
      printf("%d\n", t.find_rank(t.root, a2));
    else if (a1 == 5)
      printf("%d\n", t.get_pre(a2));
    else if (a1 == 6)
      printf("%d\n", t.get_after(a2));
  }
}

// https://atcoder.jp/contests/abc254/tasks/abc254_f
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1e18;
constexpr int maxn = 2e5 + 5;
constexpr int mod = 998244353;

inline void solve()
{
  int n, q; cin >> n >> q;

  vector sta(20, vector<int>(n)), stb(sta);
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i ++)
    cin >> a[i];
  for (int i = 0; i < n; i ++)
    cin >> b[i];

  for (int i = 0; i < n - 1; i ++)
  {
    sta[0][i] = abs(a[i + 1] - a[i]);
    stb[0][i] = abs(b[i + 1] - b[i]);
  }

  for (int i = 1; (1LL << i) <= n; i ++) // 初始化
    for (int j = 0; j + (1LL << i) <= n; j ++)
    {
      sta[i][j] = gcd(sta[i - 1][j], sta[i - 1][j + (1LL << (i - 1))]);
      stb[i][j] = gcd(stb[i - 1][j], stb[i - 1][j + (1LL << (i - 1))]);
    }

  auto calc = [&](auto &st, int l, int r) // 区间查
  {
    if (l == r) return 0LL;
    int x = 31 - (int)__builtin_clz(r - l);
    return gcd(st[x][l], st[x][r - (1LL << x)]);
  };

  while (q --)
  {
    int x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2;
    x1 --;
    x2 --;
    y1 --;
    y2 --;
    int c = calc(sta, x1, x2);
    int r = calc(stb, y1, y2);
    cout << gcd(gcd(c, r), a[x1] + b[y1]) << '\n';
  }
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}
/*
The details you should care:

*/

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s; cin >> s;
  int n = (int)s.size();
  vector<int> sa(n), lc(n - 1), rk(n);
  iota(sa.begin(), sa.end(), 0);
  sort(sa.begin(), sa.end(), [&](const int &i, const int &j)
  {
    return s[i] < s[j];
  });
  rk[sa[0]] = 0;

  for (int i = 1; i < n; i ++)
    rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);

  vector<int> tmp(n), cnt(n);
  for (int k = 1; rk[sa[n - 1]] < n - 1; k *= 2)
  {
    tmp.clear();
    for (int i = 0; i < k; i ++)
      tmp.emplace_back(n - k + i);
    for (int x : sa)
      if (x >= k)
        tmp.emplace_back(x - k);
    fill(cnt.begin(), cnt.end(), 0);
    for (int i = 0; i < n; i ++)
      cnt[rk[i]] ++;
    for (int i = 1; i < n; i ++)
      cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; -- i)
      sa[-- cnt[rk[tmp[i]]]] = tmp[i];
    swap(rk, tmp);
    rk[sa[0]] = 0;
    for (int i = 1; i < n; i ++)
      rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || 
                                   sa[i - 1] + k == n ||
                                   tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
  }
  for (int i = 0, j = 0; i < n; i ++)
    if (rk[i] == 0)
      j = 0;
    else
    {
      for (j -= (j > 0); i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1]] + j; j ++);
      lc[rk[i] - 1] = j;
    }
  for (int i = 0; i < n; i ++)
    cout << sa[i] << ' ';
  cout << '\n';

  return 0;
}