板子合集（自用）

//*************************************************************************  
// \brief: 计算两个向量的外积（叉乘）。可以根据结果的符号判断三个点的位置关系。  
// \Param: Point A 两个向量的公共起点。  
// \Param: Point B 第一个向量的终点。  
// \Param: Point C 第二个向量的终点。  
// \Returns: double 向量AC与向量AB的外积。
//如果结果为正数，表明点C在直线AB（直线方向为从A到B）的右侧；  
//如果结果为负数，表明点C在直线AB（直线方向为从A到B）的左侧；
//如果结果为0，表明点C在直线AB上。  
//*************************************************************************
double cross(Point A, Point B, Point C) { 
	double cross1 = (C.x - A.x) * (B.y - A.y);
    double cross2 = (C.y - A.y) * (B.x - A.x);
    return (cross1 - cross2);
}

T1 = cross(A1, A2, B1);
T2 = cross(A1, A2, B2);
T3 = cross(B1, B2, A1);
T4 = cross(B1, B2, A2);

//*************************************************************************
// \brief: 	快速排斥实验，判断两个线段张成的矩形区域是否相交。
// \Param: 	Point S1 第一条线段的起点。
// \Param: 	Point E1 第一条线段的终点。
// \Param: 	Point S2 第二条线段的起点。
// \Param: 	Point E2 第二条线段的终点。
// \Returns: 	bool 两个线段张成的矩形区域是否相交。
//具有对称性，即交换两条线段（参数S1与S2交换、E1与E2交换），结果不变。
//*************************************************************************  
bool rectsIntersect(Point S1, Point E1, Point S2, Point E2) {  
　　if ( min(S1.y, E1.y) <= max(S2.y, E2.y) && max(S1.y, E1.y) >= min(S2.y, E2.y) 
	&& min(S1.x, E1.x) <= max(S2.x, E2.x) && max(S1.x, E1.x) >= min(S2.x, E2.x)) {
            return true; } return false;
}

bool segmentsIntersect(Point A1, Point A2, Point B1, Point B2) { 
    double T1 = cross(A1, A2, B1);
    double T2 = cross(A1, A2, B2); 
    double T3 = cross(B1, B2, A1);
    double T4 = cross(B1, B2, A2);　　
    if (((T1 * T2) > 0) || ((T3 * T4) > 0)) {    
    // 一条线段的两个端点在另一条线段的同侧，不相交。
    //（可能需要额外处理以防止乘法溢出，视具体情况而定。）
        return false;
    } else if(T1 == 0 && T2 == 0) {             
    // 两条线段共线，利用快速排斥实验进一步判断。此时必有 T3 == 0 && T4 == 0。
        return rectsIntersect(A1, A2, B1, B2);
    } else {                                    // 其它情况，两条线段相交。
        return true;  
 }
}

sort(p+1,p+1+n); 
stk[++tp]=1; 
for(int i=2;i<=n;++i) { 
	while(tp>1&&(p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]])<=0) 
		[stk[tp--]]=0; 
	used[i]=1; 
	stk[++tp]=i; 
} 
int qaq=tp; 
for(int i=n-1;i>0;--i) 
	if(!used[i]) { 
	while(tp>qaq&&(p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]])<=0) 
		used[stk[tp--]]=0; 
	used[i]=1; 
	stk[++tp]=i; 
} 
for(int i=1;i<=tp;++i) 
	h[i]=p[stk[i]];

struct vec {
    ll x, y;
    friend vec operator -(const vec &a, const vec &b) {
        return vec{a.x - b.x, a.y - b.y};
    }
    friend ll operator *(const vec &a, const vec &b) {
        return (a.x * b.y - a.y * b.x);
    }
    ll dis_() {
        return x * x + y * y;
    }
    friend ll dis(const vec &a, const vec &b, const vec &x) {
        return abs((x - a) * (x - b));
    }
    friend bool operator <(const vec &a, const vec &b) {
        return (a.x < b.x) || (a.x == b.x && a.y < b.y);
    }
} p[100005];

int n, st[100005], top = 0;
char used[100005];

inline void convexhull() {  // 求凸包 
    sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; i++) {
        while (top > 1 && (p[st[top]] - p[st[top - 1]]) * 
               (p[i] - p[st[top]]) <= 0)
            used[st[top--]] = 0;
        st[++top] = i;
        used[i] = 1;
    }
    int qaq = top;
    for (int i = n - 1; i > 1; i--) {
        if (!used[i]) {
            while (top > qaq && (p[st[top]] - p[st[top - 1]]) * 
                   (p[i] - p[st[top]]) <= 0)
                used[st[top--]] = 0;
            st[++top] = i;
            used[i] = 1;
        }   
    }
    while (top > qaq && (p[st[top]] - p[st[top - 1]]) * 
           (p[1] - p[st[top]]) <= 0)
        used[st[top--]] = 0;
    st[++top] = 1;
}

inline ll rotating() {
    if (top < 4)  // 注意点1会在开头和结尾各自入栈一次
        return (p[st[1]] - p[st[2]]).dis_();  // 如果凸包只有两个点直接输出两点距离 
    int t = 3;
    ll mx = 0;
    for (int i = 1; i < top; i++) {
        while (dis(p[st[i]], p[st[i + 1]], p[st[t]]) <= 
               dis(p[st[i]], p[st[i + 1]], p[st[t % top + 1]]))
            t = t % top + 1;
        mx = max(mx, max((p[st[t]] - p[st[i]]).dis_(), 
                         (p[st[t]] - p[st[i + 1]]).dis_()));
    }
    return mx;
}

#define double long double
typedef long long ll;
const int MAXN = 100001;
int n;
const double eps = 1e-8;

struct vec {
    double x, y;
    friend vec operator +(vec x, vec y) {
        return vec{x.x + y.x, x.y + y.y};
    }
    friend vec operator -(vec x, vec y) {
        return vec{x.x - y.x, x.y - y.y};
    }
    friend double operator *(vec x, vec y) {
        return (x.x * y.y - x.y * y.x);
    }
    friend double operator ^(vec x, vec y) {
        return (x.x * y.x + x.y * y.y);
    }
    friend bool operator <(vec x, vec y) {
        return (x.x - y.x < eps) || 
               (fabs(x.x - y.x) < eps && x.y - y.y < eps);
    }
    double dis() {
        return sqrt(x * x + y * y);
    }
} p[MAXN], h[MAXN];

int st[MAXN], top;
char used[MAXN];

inline void convexhull() {
    top = 0;
    memset(used, 0, n + 1);
    sort(p + 1, p + 1 + n);
    st[++top] = 1;
    for (int i = 2; i <= n; i++) {
        while (top > 1 && (p[st[top]] - p[st[top - 1]]) * 
               (p[i] - p[st[top]]) < eps) 
            used[st[top--]] = 0;
        st[++top] = i;
        used[i] = 1;
    }
    for (int i = n - 1; i >= 1; i--) {
        if (!used[i]) {
            while (top > 1 && (p[st[top]] - p[st[top - 1]]) * 
                   (p[i] - p[st[top]]) < eps) 
                used[st[top--]] = 0;
            st[++top] = i;
            used[i] = 1;
        }
    }
    for (int i = 1; i <= top; i++) 
        h[i] = p[st[i]];
}

inline double sqr(vec a, vec b, vec x) {
    return (a - x) * (b - x);
}

inline double solve() {
    if (top < 4) return 0;
    int t = 3;
    while (sqr(h[1], h[2], h[t]) - 
           sqr(h[1], h[2], h[t % top + 1]) < eps) 
        t = t % top + 1;
    int t2 = 1, t3 = t;
    double ans = 1e18;
    for (int i = 1; i < top; i++) {
        while (sqr(h[i], h[i + 1], h[t]) - 
               sqr(h[i], h[i + 1], h[t % top + 1]) < eps) 
            t = t % top + 1;
        while (((h[i + 1] - h[i]) ^ (h[t2 % top + 1] - h[t2])) > -eps) 
            t2 = t2 % top + 1; // 记得都要%top再+1 
        while (((h[i + 1] - h[i]) ^ (h[t3 % top + 1] - h[t3])) < eps) 
            t3 = t3 % top + 1;
        vec vert = {-(h[i + 1].y - h[i].y), h[i + 1].x - h[i].x};
        double ar = (sqr(h[i], h[i + 1], h[t]) / 
                     (h[i] - h[i + 1]).dis()) * 
                     (sqr(h[t2], h[t2] + vert, h[t3]) / 
                     (vert).dis());
        ans = min(ans, ar);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n) {
        if (!n) return 0; 
        for (int i = 1; i <= n; i++) 
            cin >> p[i].x >> p[i].y;
        convexhull();
        printf("%.4Lf\n", solve());
    }
    return 0;
}

#define double long double
int n;
double x[1005],y[1005],r[1005];
typedef pair<double,double> P;
P q[1005];
inline double f(double v){
	int tot=0;
	for(int i=1;i<=n;i++){
		double dx=x[i]-v;
		if(r[i]*r[i]-dx*dx>1e-8){
			double dy=sqrt(r[i]*r[i]-dx*dx);
			q[++tot]=P(y[i]-dy,y[i]+dy);
		}
	}
	if(!tot) return 0;
	sort(q+1,q+1+tot);
	//以下将x=v穿过的所有y区间进行合并 
	double ans=0,st=q[1].first,ed=q[1].second;
	for(int i=2;i<=tot;i++){
		if(q[i].first<=ed)
			ed=max(ed,q[i].second);
		else{
			ans+=ed-st;
			st=q[i].first;
			ed=q[i].second;
		}
	}
	return ans+ed-st;
}
inline double simpson(double l,double r){
	return (f(l)+f(r)+4*f((l+r)/2))*(r-l)/6;
}
inline double asr(double l,double r,double eps,double ans){
	double mid=(l+r)/2;
	double ansl=simpson(l,mid),ansr=simpson(mid,r);
	if(fabs(ansl+ansr-ans)<15*eps) 
		return ansl+ansr+(ansl+ansr-ans)/15;
	return asr(l,mid,eps/2,ansl)+
	asr(mid,r,eps/2,ansr);
}
void _rotate(double &x, double &y,double angle)
{
	double x_=x;
	double y_=y;
	x=x_ * cos(angle) + y_ * sin(angle);
	y=-x_ * sin(angle) + y_ * cos(angle);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>x[1]>>y[1]>>r[1];
	int rot=1;	//坐标系旋转一个随机角度 
	_rotate(x[1],y[1],rot);
	double lf=x[1]-r[1],rf=x[1]+r[1];
	for(int i=2;i<=n;i++){
		cin>>x[i]>>y[i]>>r[i];
		_rotate(x[i],y[i],rot);
		lf=min(x[i]-r[i],lf);
		rf=max(x[i]+r[i],rf);
	}
	printf("%.3Lf",asr(lf-10,rf+10,1e-5,
	simpson(lf-10,rf+10)));
	return 0;
}

 struct MF {
    struct edge {
        int v, nxt, cap, flow;
    } e[N];

    int fir[N], cnt = 0;
    int n, S, T;
    ll maxflow = 0;
    int dep[N], cur[N];

    void init() {
        memset(fir, -1, sizeof fir);
        cnt = 0;
    }

    void addedge(int u, int v, int w) {
        e[cnt] = {v, fir[u], w, 0};
        fir[u] = cnt++;
        e[cnt] = {u, fir[v], 0, 0};
        fir[v] = cnt++;
    }

    bool bfs() {
        queue<int> q;
        memset(dep, 0, sizeof(int) * (n + 1));
        dep[S] = 1;
        q.push(S);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = fir[u]; ~i; i = e[i].nxt) {
                int v = e[i].v;
                if ((!dep[v]) && 
                (e[i].cap > e[i].flow)) {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
            }
        }
        return dep[T];
    }

    int dfs(int u, int flow) {
        if ((u == T) || (!flow)) return flow;
        int ret = 0;
        for (int& i = cur[u]; ~i; i = e[i].nxt) {
            int v = e[i].v, d;
            if ((dep[v] == dep[u] + 1) &&
                (d = dfs(v, min(flow - ret, 
                e[i].cap - e[i].flow)))) {
                ret += d;
                e[i].flow += d;
                e[i ^ 1].flow -= d;
                if (ret == flow) return ret;
            }
        }
        return ret;
    }

    void dinic() {
        while (bfs()) {
            memcpy(cur, fir, sizeof(int) * 
            (n + 1));
            maxflow += dfs(S, INF);
        }
    }
} mf;

constexpr int INF = 0x3f3f3f3f;
using namespace std;
struct edge {
    int v, f, c, next;
} e[100005];
struct node {
    int v, e;
} p[10005];
struct mypair {
    int dis, id;
    bool operator<(const mypair& a) 
	const { return dis > a.dis; }
    mypair(int d, int x) { dis = d, id = x; }
};
int head[5005], dis[5005], vis[5005], h[5005];
int n, m, s, t, cnt = 1, maxf, minc;
void addedge(int u, int v, int f, int c) {
    e[++cnt].v = v;
    e[cnt].f = f;
    e[cnt].c = c;
    e[cnt].next = head[u];
    head[u] = cnt;
}

bool dijkstra() {
    priority_queue<mypair> q;
    for (int i = 1; i <= n; i++) dis[i] = INF;
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push(mypair(0, s));
    while (!q.empty()) {
        int u = q.top().id;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v, 
	        nc = e[i].c + h[u] - h[v];
            if (e[i].f && dis[v] > dis[u] + nc) {
                dis[v] = dis[u] + nc;
                p[v].v = u;
                p[v].e = i;
                if (!vis[v]) 
	                q.push(mypair(dis[v], v));
            }
        }
    }
    return dis[t] != INF;
}

void spfa() {
    queue<int> q;
    memset(h, 63, sizeof(h));
    h[s] = 0, vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (e[i].f && h[v] > h[u] + e[i].c) {
                h[v] = h[u] + e[i].c;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, f, c;
        scanf("%d%d%d%d", &u, &v, &f, &c);
        addedge(u, v, f, c);
        addedge(v, u, 0, -c);
    }
    spfa();  // 先求出初始势能
    while (dijkstra()) {
        int minf = INF;
        for (int i = 1; i <= n; i++) 
	        h[i] += dis[i];
        for (int i = t; i != s; i = p[i].v) 
	        minf = min(minf, e[p[i].e].f);
        for (int i = t; i != s; i = p[i].v) {
            e[p[i].e].f -= minf;
            e[p[i].e ^ 1].f += minf;
        }
        maxf += minf;
        minc += minf * h[t];
    }
    printf("%d %d\n", maxf, minc);
    return 0;
}

struct augment_path {
    vector<vector<int>> g;
    vector<int> pa;  // 匹配
    vector<int> pb;
    vector<int> vis;  // 访问
    int n, m;         // 两个点集中的顶点数量
    int dfn;          // 时间戳记
    int res;          // 匹配数

    augment_path(int _n, int _m) : n(_n), m(_m){
        assert(0 <= n && 0 <= m);
        pa = vector<int>(n, -1);
        pb = vector<int>(m, -1);
        vis = vector<int>(n);
        g.resize(n);
        res = 0;
        dfn = 0;
    }

    void add(int from, int to) {
        assert(0 <= from && from < n &&
         0 <= to && to < m);
        g[from].push_back(to);
    }

    bool dfs(int v) {
        vis[v] = dfn;
        for (int u : g[v]) {
            if (pb[u] == -1) {
                pb[u] = v;
                pa[v] = u;
                return true;
            }
        }
        for (int u : g[v]) {
            if (vis[pb[u]] != dfn 
            && dfs(pb[u])) {
                pa[v] = u;
                pb[u] = v;
                return true;
            }
        }
        return false;
    }

    int solve() {
        while (true) {
            dfn++;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (pa[i] == -1 && dfs(i)) {
                    cnt++;
                }
            }
            if (cnt == 0) {
                break;
            }
            res += cnt;
        }
        return res;
    }
};

int dfn[N], low[N], dfncnt, 
s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 SCC 的编号
int sz[N];       // 强连通 i 的大小

void tarjan(int u) {
    low[u] = dfn[u] = ++dfncnt, 
    s[++tp] = u, in_stack[u] = 1;
    for (int i = h[u]; i; i = e[i].nex) {
        const int &v = e[i].t;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++sc;
        while (s[tp] != u) {
            scc[s[tp]] = sc;
            sz[sc]++;
            in_stack[s[tp]] = 0;
            --tp;
        }
        scc[s[tp]] = sc;
        sz[sc]++;
        in_stack[s[tp]] = 0;
        --tp;
    }
}

#include <algorithm>
#include <cstdio>
#include <vector>

constexpr int MN = 100005;

int N, M, cnt;
std::vector<int> G[MN], T[MN * 2];

int dfn[MN], low[MN], dfc;
int stk[MN], tp;

void Tarjan(int u) {
    printf("  Enter : #%d\n", u);
    low[u] = dfn[u] = ++dfc;                // low 初始化为当前节点 dfn
    stk[++tp] = u;                          // 加入栈中
    for (int v : G[u]) {                    // 遍历 u 的相邻节点
        if (!dfn[v]) {                       // 如果未访问过
            Tarjan(v);                       // 递归
            low[u] = std::min(low[u], low[v]);  // 未访问的和 low 取 min
            if (low[v] == dfn[u]) {          // 找到一个以 u 为根的 BCC
                ++cnt;                       // 增加方点个数
                printf("  Found a New BCC #%d.\n", cnt - N);
                // 将点双中除了 u 的点退栈，并在圆方树中连边
                for (int x = 0; x != v; --tp) {
                    x = stk[tp];
                    T[cnt].push_back(x);
                    T[x].push_back(cnt);
                    printf("    BCC #%d has vertex #%d\n", cnt - N, x);
                }
                // 注意 u 自身也要连边（但不退栈）
                T[cnt].push_back(u);
                T[u].push_back(cnt);
                printf("    BCC #%d has vertex #%d\n", cnt - N, u);
            }
        } else
            low[u] = std::min(low[u], dfn[v]);  // 已访问的和 dfn 取 min
    }
    printf("  Exit : #%d : low = %d\n", u, low[u]);
    printf("  Stack:\n    ");
    for (int i = 1; i <= tp; ++i) 
        printf("%d, ", stk[i]);
    puts("");
}

int main() {
    scanf("%d%d", &N, &M);
    cnt = N;  // 点双 / 方点标号从 N 开始
    for (int i = 1; i <= M; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);  // 加双向边
        G[v].push_back(u);
    }
    // 处理非连通图
    for (int u = 1; u <= N; ++u)
        if (!dfn[u]) Tarjan(u), --tp;
    // 注意到退出 Tarjan 时栈中还有一个元素即根，将其退栈
    return 0;
}

#include <iostream>
using namespace std;

int n, m;

struct Edge {
    int to, nxt;
} edge[500];

int cntEdge, head[20];

void addEdge(int u, int v) {
    edge[++cntEdge] = {v, head[u]}, head[u] = cntEdge;
}

long long answer, dp[1 << 19][20];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }
    for (int i = 1; i <= n; i++) 
        dp[1 << (i - 1)][i] = 1;
    for (int s = 1; s < (1 << n); s++)
        for (int i = 1; i <= n; i++) {
            if (!dp[s][i]) continue;
            for (int j = head[i]; j; j = edge[j].nxt) {
                int u = i, v = edge[j].to;
                if ((s & -s) > (1 << (v - 1))) continue;
                if (s & (1 << (v - 1))) {
                    if ((s & -s) == (1 << (v - 1))) 
                        answer += dp[s][u];
                } else
                    dp[s | (1 << (v - 1))][v] += dp[s][u];
            }
        }
    cout << (answer - m) / 2 << '\n';
    return 0;
}

#include <iostream>
using namespace std;

int n, m, total;
int deg[200001], u[200001], v[200001];
bool vis[200001];

struct Edge {
    int to, nxt;
} edge[200001];

int cntEdge, head[100001];

void addEdge(int u, int v) {
    edge[++cntEdge] = {v, head[u]}, head[u] = cntEdge;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) 
        cin >> u[i] >> v[i], deg[u[i]]++, deg[v[i]]++;
    for (int i = 1; i <= m; i++) {
        if ((deg[u[i]] == deg[v[i]] && u[i] > v[i]) || 
            deg[u[i]] < deg[v[i]])
            swap(u[i], v[i]);
        addEdge(u[i], v[i]);
    }
    for (int u = 1; u <= n; u++) {
        for (int i = head[u]; i; i = edge[i].nxt) 
            vis[edge[i].to] = true;
        for (int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].to;
            for (int j = head[v]; j; j = edge[j].nxt) {
                int w = edge[j].to;
                if (vis[w]) total++;
            }
        }
        for (int i = head[u]; i; i = edge[i].nxt) 
            vis[edge[i].to] = false;
    }
    cout << total << '\n';
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int n, m, deg[100001], cnt[100001];
vector<int> E[100001], E1[100001];

long long total;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    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);
        deg[u]++, deg[v]++;
    }
    for (int u = 1; u <= n; u++)
        for (int v : E[u])
            if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) 
                E1[u].push_back(v);
    for (int a = 1; a <= n; a++) {
        for (int b : E1[a])
            for (int c : E[b]) {
                if (deg[a] < deg[c] || (deg[a] == deg[c] && a <= c)) 
                    continue;
                total += cnt[c]++;
            }
        for (int b : E1[a])
            for (int c : E[b]) 
                cnt[c] = 0;
    }
    cout << total << '\n';
    return 0;
}

constexpr int MXN = 40005;
using namespace std;
vector<int> v[MXN];
vector<int> w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

void dfs(int root, int fno) {
    fa[root][0] = fno;
    dep[root] = dep[fa[root][0]] + 1;
    for (int i = 1; i < 31; ++i) {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
        cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
    }
    int sz = v[root].size();
    for (int i = 0; i < sz; ++i) {
        if (v[root][i] == fno) continue;
        cost[v[root][i]][0] = w[root][i];
        dfs(v[root][i], root);
    }
}

int lca(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    int tmp = dep[y] - dep[x];
    for (int j = 0; tmp; ++j, tmp >>= 1)
        if (tmp & 1) {
            y = fa[y][j];
        }
    if (y == x) return 0;
    for (int j = 30; j >= 0 && y != x; --j) {
        if (fa[x][j] != fa[y][j]) {
            x = fa[x][j];
            y = fa[y][j];
        }
    }
    return cost[x][0] + cost[y][0];
}

constexpr int N = 10000 + 10;
int n, c, d[N];
vector<int> E[N];
void dfs(int u, int fa) {
    for (int v : E[u]) {
        if (v == fa) continue;
        d[v] = d[u] + 1;
        if (d[v] > d[c]) c = v;
        dfs(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        E[u].push_back(v), E[v].push_back(u);
    }
    dfs(1, 0);
    d[c] = 0, dfs(c, 0);
    printf("%d\n", d[c]);
    return 0;
}

// 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]，使用vector存图
int d1[N], d2[N], up[N], x, y, mini = 1e9;  // d1,d2对应上文中的len1,len2

struct node {
  int to, val;  // to为边指向的节点，val为边权
};

vector<node> nbr[N];

void dfsd(int cur, int fa) {  // 求取len1和len2
  for (node nxtn : nbr[cur]) {
    int nxt = nxtn.to, w = nxtn.val;  // nxt为这条边通向的节点，val为边权
    if (nxt == fa) {
      continue;
    }
    dfsd(nxt, cur);
    if (d1[nxt] + w > d1[cur]) {  // 可以更新最长链
      d2[cur] = d1[cur];
      d1[cur] = d1[nxt] + w;
    } else if (d1[nxt] + w > d2[cur]) {  // 不能更新最长链，但可更新次长链
      d2[cur] = d1[nxt] + w;
    }
  }
}

void dfsu(int cur, int fa) {
  for (node nxtn : nbr[cur]) {
    int nxt = nxtn.to, w = nxtn.val;
    if (nxt == fa) {
      continue;
    }
    up[nxt] = up[cur] + w;
    if (d1[nxt] + w != d1[cur]) {  // 如果自己子树里的最长链不在nxt子树里
      up[nxt] = max(up[nxt], d1[cur] + w);
    } else {  // 自己子树里的最长链在nxt子树里，只能使用次长链
      up[nxt] = max(up[nxt], d2[cur] + w);
    }
    dfsu(nxt, cur);
  }
}

void GetTreeCenter() {  // 统计树的中心，记为x和y（若存在）
  dfsd(1, 0);
  dfsu(1, 0);
  for (int i = 1; i <= n; i++) {
    if (max(d1[i], up[i]) < mini) {  // 找到了当前max(len1[x],up[x])最小点
      mini = max(d1[i], up[i]);
      x = i;
      y = 0;
    } else if (max(d1[i], up[i]) == mini) {  // 另一个中心
      y = i;
    }
  }
}

// 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]
int size[MAXN],  // 这个节点的「大小」（所有子树上节点数 + 该节点）
    weight[MAXN],  // 这个节点的「重量」，即所有子树「大小」的最大值
    centroid[2];  // 用于记录树的重心（存的是节点编号）

void GetCentroid(int cur, int fa) {
    size[cur] = 1;
    weight[cur] = 0;
    for (int i = head[cur]; i != -1; i = e[i].nxt) {
        if (e[i].to != fa) {
            GetCentroid(e[i].to, cur);
            size[cur] += size[e[i].to];
            weight[cur] = max(weight[cur], size[e[i].to]);
        }
    }
    weight[cur] = max(weight[cur], n - size[cur]);
    if (weight[cur] <= n / 2) {
        centroid[centroid[0] != 0] = cur;
    }
}

void dfs1(int o) {
    son[o] = -1;
    siz[o] = 1;
    for (int j = h[o]; j; j = nxt[j])
        if (!dep[p[j]]) {
            dep[p[j]] = dep[o] + 1;
            fa[p[j]] = o;
            dfs1(p[j]);
            siz[o] += siz[p[j]];
            if (son[o] == -1 || siz[p[j]] > siz[son[o]]) son[o] = p[j];
        }
}

void dfs2(int o, int t) {
    top[o] = t;
    cnt++;
    dfn[o] = cnt;
    rnk[cnt] = o;
    if (son[o] == -1) return;
    dfs2(son[o], t);  // 优先对重儿子进行 DFS，可以保证同一条重链上的点 DFS 序连续
    for (int j = h[o]; j; j = nxt[j])
        if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}

// st 是线段树结构体
int querymax(int x, int y) {
    int ret = -inf, fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] >= dep[fy])
            ret = max(ret, st.query1(1, 1, n, dfn[fx], dfn[x])), x = fa[fx];
        else
            ret = max(ret, st.query1(1, 1, n, dfn[fy], dfn[y])), y = fa[fy];
        fx = top[x];
        fy = top[y];
    }
    if (dfn[x] < dfn[y])
        ret = max(ret, st.query1(1, 1, n, dfn[x], dfn[y]));
    else
        ret = max(ret, st.query1(1, 1, n, dfn[y], dfn[x]));
    return ret;
}

vector<int> pri;
bool not_prime[N];
// int  phi[N]; 欧拉函数
// int  mu[N]; 莫比乌斯函数
// int  d[N]; i的约数个数
// int num[N]; i的最小质因子出现次数
// int  g[N],  f[N]; i的约束和，i的最小质因子0~k幂次和
void pre(int n) {
	// phi[1]  =  1;
	// mu[1]  =  1;
	// d[1]  =  1;
	// g[1]  =  f[1]  =  1;
    for (int i = 2; i <= n; ++i) {
        if (!not_prime[i]) {
            pri.push_back(i);
            // phi[i]  =  i  -  1;
            // mu[i]  =  -1;
	        // d[i]  =  2;  
	        // num[i]  =  1;
	        // g[i]  =  i  +  1;  
	        // f[i]  =  i  +  1;
        }
        for (int pri_j : pri) {
            if (i * pri_j > n) break;
            not_prime[i * pri_j] = true;
            if (i % pri_j == 0) {
	            // phi[i  *  pri_j]  =  phi[i]  *  pri_j;
	            // mu[i  *  pri_j]  =  0;
	            // num[i  *  pri_j]  =  num[i]  +  1;  
	            // d[i  *  pri_j]  =  d[i]  /  num[i  *  pri_j]  
	            // *  (num[i  *  pri_j]  +  1);
	            // g[i  *  pri_j]  =  g[i]  *  pri_j  +  1;  
	            // f[i  *  pri_j]  =  f[i]  /  g[i]  
	            // *  g[i  *  pri_j];
                break;
            }
            // phi[i  *  pri_j]  =  phi[i]  *  phi[pri_j];'
            // mu[i  *  pri_j]  =  -mu[i];
            // num[i  *  pri_j]  =  1;  
            // d[i  *  pri_j]  =  d[i]  *  2;
            // f[i  *  pri_j]  =  f[i]  *  f[pri_j];  
            // g[i  *  pri_j]  =  1  +  pri_j;
        }
    }
}

long long H(int n) {
  long long res = 0;
  int l = 1, r;
  while (l <= n) {
    r = n / (n / l);
    res += 1LL * (r - l + 1) * (n / l);
    l = r + 1;
  }
  return res;
}

void exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

LL CRT(int k, LL* a, LL* r) {
    LL n = 1, ans = 0;
    for (int i = 1; i <= k; i++) 
        n = n * r[i];
    for (int i = 1; i <= k; i++) {
        LL m = n / r[i], b, y;
        exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n;
    }
    return (ans % n + n) % n;
}

bool millerRabin(int n) {
    if (n < 3 || n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    int u = n - 1, t = 0;
    while (u % 2 == 0) u /= 2, ++t;
    // test_time 为测试次数，建议设为不小于 8
    // 的整数以保证正确率，但也不宜过大，否则会影响效率
    for (int i = 0; i < test_time; ++i) {
        // 0, 1, n-1 可以直接通过测试, a 取值范围 [2, n-2]
        int a = rand() % (n - 3) + 2, v = quickPow(a, u, n);
        if (v == 1) continue;
        int s;
        for (s = 0; s < t; ++s) {
            if (v == n - 1) break;  // 得到平凡平方根 n-1，通过此轮测试
            v = (long long)v * v % n;
        }
        // 如果找到了非平凡平方根，则会由于无法提前 break; 
        // 而运行到 s == t
        // 如果 Fermat 素性测试无法通过，则一直运行到 s == t 
        // 前 v 都不会等于 -1
        if (s == t) return 0;
    }
    return 1;
}

ll Pollard_Rho(ll x) {
    ll t = 0;
    ll c = rand() % (x - 1) + 1;  // 随机常数 c
    ll s = t;
    int step = 0, goal = 1;
    ll val = 1;

    for (goal = 1;; goal <<= 1, s = t, val = 1) {
        for (step = 1; step <= goal; ++step) {
            t = f(t, c, x);  // 迭代函数 f
            val = val * abs(t - s) % x;
            // 如果 val 为 0，退出重新分解
            if (!val) return x;

            if (step % 127 == 0) {
                ll d = gcd(val, x);  // 计算当前 val 和 x 的最大公约数
                if (d > 1) return d;  // 找到因子
            }
        }
        ll d = gcd(val, x);
        if (d > 1) return d;  // 找到因子
    }
}

// n! mod p
int factmod(int n, int p) {
    vector<int> f(p);
    f[0] = 1;
    for (int i = 1; i < p; i++)
        f[i] = f[i - 1] * i % p;
    int res = 1;
    while (n > 1) {
        if ((n / p) % 2)
            res = p - res;
        res = res * f[n % p] % p;
        n /= p;
    }
    return res;
}

long long Lucas(long long n, long long m, long long p) {
    if (m == 0) 
        return 1;
    return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}

#define reg register
#define EN std::puts("")
#define LL long long
inline int read() {
    reg int x = 0;
    reg int y = 1;
    reg char c = std::getchar();
    while (c < '0' || c > '9') {
        if (c == '-') y = 0;
        c = std::getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c ^ 48);
        c = std::getchar();
    }
    return y ? x : -x;
}

std::unordered_map<int, int> map;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

inline int BSGS(int a, int n, int p, int ad) {
    map.clear();
    reg int m = std::ceil(std::sqrt(p));
    reg int s = 1;
    for (reg int i = 0; i < m; i++, s = 1ll * s * a % p)
        map[1ll * s * n % p] = i;
    for (reg int i = 0, tmp = s, s = ad; i <= m; i++, s = 1ll * s * tmp % p)
        if (map.find(s) != map.end())
            if (1ll * i * m - map[s] >= 0)
                return 1ll * i * m - map[s];
    return -1;
}

inline int exBSGS(int a, int n, int p) {
    a %= p;
    n %= p;
    if (n == 1 || p == 1) return 0;
    reg int cnt = 0;
    reg int d, ad = 1;
    while ((d = gcd(a, p)) ^ 1) {
        if (n % d) return -1;
        cnt++;
        n /= d;
        p /= d;
        ad = (1ll * ad * a / d) % p;
        if (ad == n) return cnt;
    }
    LL ans = BSGS(a, n, p, ad);
    if (ans == -1) return -1;
    return ans + cnt;
}

signed main() {
    int a = read(), p = read(), n = read();
    while (a || p || n) {
        int ans = exBSGS(a, n, p);
        if (~ans) std::printf("%d\n", ans);
        else std::puts("No Solution");
        a = read(); p = read(); n = read();
    }
    return 0;
}

// 给定 n 个整数（数字可能重复），
// 求在这些数中选取任意个，使得他们的异或和最大。
using ull = unsigned long long;
constexpr int MAXN = 1e5 + 5;

ull deg(ull num, int deg) { 
    return num & (1ull << deg); 
}

ull a[MAXN];
using std::cin;
using std::cout;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) 
        cin >> a[i];
    
    int row = 1;
    for (int col = 63; ~col && row <= n; --col) {
        for (int i = row; i <= n; ++i) {
            if (deg(a[i], col)) {
                std::swap(a[row], a[i]);
                break;
            }
        }
        if (!deg(a[row], col)) continue;
        for (int i = 1; i <= n; ++i) {
            if (i == row) continue;
            if (deg(a[i], col)) {
                a[i] ^= a[row];
            }
        }
        ++row;
    }
    
    ull ans = 0;
    for (int i = 1; i < row; ++i) {
        ans ^= a[i];
    }
    cout << ans << '\n';
    return 0;
}

constexpr double EPS = 1E-9;
int n;
vector<vector<double>> a(n, vector<double>(n));

double det = 1;
for (int i = 0; i < n; ++i) {
    int k = i;
    for (int j = i + 1; j < n; ++j)
        if (abs(a[j][i]) > abs(a[k][i])) k = j;
    if (abs(a[k][i]) < EPS) {
        det = 0;
        break;
    }
    swap(a[i], a[k]);
    if (i != k) det = -det;
    det *= a[i][i];
    for (int j = i + 1; j < n; ++j) 
        a[i][j] /= a[i][i];
    for (int j = 0; j < n; ++j)
        if (j != i && abs(a[j][i]) > EPS)
            for (int k = i + 1; k < n; ++k) 
                a[j][k] -= a[i][k] * a[j][i];
}
cout << det;

using ull = unsigned long long;
ull base = 131;
ull mod1 = 212370440130137957, mod2 = 1e9 + 7;

ull get_hash1(std::string s) {
    int len = s.size();
    ull ans = 0;
    for (int i = 0; i < len; i++) 
        ans = (ans * base + (ull)s[i]) % mod1;
    return ans;
}

ull get_hash2(std::string s) {
    int len = s.size();
    ull ans = 0;
    for (int i = 0; i < len; i++) 
        ans = (ans * base + (ull)s[i]) % mod2;
    return ans;
}

bool cmp(const std::string s, const std::string t) {
    bool f1 = get_hash1(s) != get_hash1(t);
    bool f2 = get_hash2(s) != get_hash2(t);
    return f1 || f2;
}

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}
vector<int> find_occurrences(string text, string pattern) {
    string cur = pattern + '#' + text;
    int sz1 = text.size(), sz2 = pattern.size();
    vector<int> v;
    vector<int> lps = prefix_function(cur);
    for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
        if (lps[i] == sz2) 
            v.push_back(i - 2 * sz2);
    }
    return v;
}

// 统计每个前缀的出现次数
vector<int> ans(n + 1);
for (int i = 0; i < n; i++) 
    ans[pi[i]]++;
for (int i = n - 1; i > 0; i--) 
    ans[pi[i - 1]] += ans[i];
for (int i = 0; i <= n; i++) 
    ans[i]++;

constexpr int N = 2e5 + 6;
constexpr int LEN = 2e6 + 6;
constexpr int SIZE = 2e5 + 6;

int n;

namespace AC {
struct Node {
    int son[26];
    int ans;
    int fail;
    int idx;

    void init() {
        memset(son, 0, sizeof(son));
        ans = idx = 0;
    }
} tr[SIZE];

int tot;
int ans[N], pidx;
vector<int> g[SIZE];  // fail 树

void init() {
    tot = pidx = 0;
    tr[0].init();
}

void insert(char s[], int &idx) {
    int u = 0;
    for (int i = 1; s[i]; i++) {
        int &son = tr[u].son[s[i] - 'a'];
        if (!son) son = ++tot, tr[son].init();
        u = son;
    }
    // 由于有可能出现相同的模式串，需要将相同的映射到同一个编号
    if (!tr[u].idx) tr[u].idx = ++pidx;  // 第一次出现，新增编号
    idx = tr[u].idx;  // 这个模式串的编号对应这个结点的编号
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (tr[0].son[i]) {
            q.push(tr[0].son[i]);
            g[0].push_back(tr[0].son[i]);  // 不要忘记这里的 fail
        }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            if (tr[u].son[i]) {
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                g[tr[tr[u].fail].son[i]].push_back(tr[u].son[i]);  
                q.push(tr[u].son[i]);
            } else
                tr[u].son[i] = tr[tr[u].fail].son[i];
        }
    }
}

void query(char t[]) {
    int u = 0;
    for (int i = 1; t[i]; i++) {
        u = tr[u].son[t[i] - 'a'];
        tr[u].ans++;
    }
}

void dfs(int u) {
    for (int v : g[u]) {
        dfs(v);
        tr[u].ans += tr[v].ans;
    }
    ans[tr[u].idx] = tr[u].ans;
}
}  // namespace AC

char s[LEN];
int idx[N];

int main() {
    AC::init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        AC::insert(s, idx[i]);
        AC::ans[i] = 0;
    }
    AC::build();
    scanf("%s", s + 1);
    AC::query(s);
    AC::dfs(0);
    for (int i = 1; i <= n; i++) {
        printf("%d\n", AC::ans[idx[i]]);
    }
    return 0;
}

int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) {
    if (sec[(i + k) % n] == sec[(j + k) % n]) {
        k++;
    } else {
        sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
        if (i == j) i++;
        k = 0;
    }
}
i = min(i, j);

vector<int> d1(n);  // 存储奇数长度回文的半径
for (int i = 0, l = 0, r = -1; i < n; i++) {
    int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
    while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
        k++;
    }
    d1[i] = k--;
    if (i + k > r) {
        l = i - k;
        r = i + k;
    }
}
vector<int> d2(n);  // 存储偶数长度回文的半径
for (int i = 0, l = 0, r = -1; i < n; i++) {
    int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
    while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
        k++;
    }
    d2[i] = k--;
    if (i + k > r) {
        l = i - k - 1;
        r = i + k;
    }
}

#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
int n, m, k;
constexpr int N = 2e5 + 5;
int fa[N << 1], siz[N << 1];
struct UndoObject {
    int pos, val;
    UndoObject(int p, int v) : pos(p), val(v) {}
};
stack<UndoObject> undo_sz, undo_fa;
int find(int x) {
    if (fa[x] == x)
        return x;
    else
        return find(fa[x]);
}
void merge(int u, int v) {
    int x = find(u), y = find(v);
    if (x == y) return;
    if (siz[x] < siz[y]) {
        swap(x, y);
    }
    undo_sz.push(UndoObject(x, siz[x]));
    siz[x] += siz[y];
    undo_fa.push(UndoObject(y, fa[y]));
    fa[y] = x;
}
void undo() {
    fa[undo_fa.top().pos] = undo_fa.top().val;
    undo_fa.pop();
    siz[undo_sz.top().pos] = undo_sz.top().val;
    undo_sz.pop();
}
vector<int> tree[N << 2];
void update(int ql, int qr, int v, int i, int l, int r) {
    if (ql <= l && r <= qr) {
        tree[i].push_back(v);
        return;
    }
    if (ql <= mid) update(ql, qr, v, ls, l, mid);
    if (qr > mid) update(ql, qr, v, rs, mid + 1, r);
}
struct edge {
    int u, v;
} g[N];
vector<bool> ret;
void solve(int i, int l, int r) {
    auto level = undo_fa.size();
    bool ans = true;
    for (int u : tree[i]) {
        int a = find(g[u].u);
        int b = find(g[u].v);
        if (a == b) {
            for (int k = l; k <= r; k++) {
                ret.push_back(false);
            }
            ans = false;
            break;
        }
        merge(g[u].u, g[u].v + n);
        merge(g[u].v, g[u].u + n);
    }
    if (ans) {
        if (l == r) {
            ret.push_back(true);
        } else {
            solve(ls, l, mid);
            solve(rs, mid + 1, r);
        }
    }
    while (undo_fa.size() > level) {
        undo();
    }
}
signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= (n << 1); i++) {
        fa[i] = i;
        siz[i] = 1;
    }
    for (int i = 1, l, r; i <= m; i++) {
        cin >> g[i].u >> g[i].v >> l >> r;
        update(l + 1, r, i, 1, 1, k);
    }
    solve(1, 1, k);
    for (bool i : ret) {
        cout << (i ? "Yes" : "No") << '\n';
    }
    return 0;
}

int cmp(query a, query b) 
{ 
	return belong[a.l] == belong[b.l] ?
	a.r < b.r : belong[a.l] < belong[b.l]; 
}
// 奇偶性排序
int cmp(query a, query b) { 
	return (belong[a.l] ^ belong[b.l]) ?
	 belong[a.l] < belong[b.l] :
	  ((belong[a.l] & 1) ? a.r < b.r :
	   a.r > b.r); }

#define maxn 1010000
#define maxb 1010
int aa[maxn], cnt[maxn], belong[maxn];
int n, m, size, bnum, now, ans[maxn];
struct query {
    int l, r, id;
} q[maxn];

int cmp(query a, query b) {
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : 
((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
#define isdigit(x) ((x) >= '0' && (x) <= '9')
int read() {
    int res = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
    return res;
}
void printi(int x) {
    if (x / 10) printi(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    scanf("%d", &n);
    size = sqrt(n);
    bnum = ceil((double)n / size);
    for (int i = 1; i <= bnum; ++i)
        for (int j = (i - 1) * size + 1; j <= i * size; ++j) {
            belong[j] = i;
        }
    for (int i = 1; i <= n; ++i) aa[i] = read(); 
    m = read();
    for (int i = 1; i <= m; ++i) {
        q[i].l = read(), q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        int ql = q[i].l, qr = q[i].r;
        while (l < ql) now -= !--cnt[aa[l++]];
        while (l > ql) now += !cnt[aa[--l]]++;
        while (r < qr) now += !cnt[aa[++r]]++;
        while (r > qr) now -= !--cnt[aa[r--]];
        ans[q[i].id] = now;
    }
    for (int i = 1; i <= m; ++i) printi(ans[i]), putchar('\n');
    return 0;
}

int cmp(query a, query b) { 
	return (belong[a.l] ^ belong[b.l]) ?
	 belong[a.l] < belong[b.l] 
	 : ((belong[a.r] ^ belong[b.r]) 
	 ? belong[a.r] < belong[b.r] 
	 : a.time < b.time); 
}

#include <cstdio>
#include <algorithm>

#define Fa(x) (node[x].fa)
#define Ls(x) (node[x].ch[0])
#define Rs(x) (node[x].ch[1])

const int N = 3e4 + 10;
struct Splay {
    int fa, ch[2], w, sum, revFlag;
} node[N];

inline void pushup(int x) {
    node[x].sum = node[Ls(x)].sum + node[Rs(x)].sum + node[x].w;
}

inline void reverse(int x) {
    std::swap(Ls(x), Rs(x));
    node[x].revFlag ^= 1;
}

inline void pushdown(int x) {
    if (!node[x].revFlag) return;
    if (Ls(x)) reverse(Ls(x));
    if (Rs(x)) reverse(Rs(x));
    node[x].revFlag = 0;
}

inline int get(int x) {
    return Rs(Fa(x)) == x;
}

inline int nRoot(int x) {
    return Rs(Fa(x)) == x || Ls(Fa(x)) == x;
}

inline void rotate(int x) {
    int fa = Fa(x), gf = Fa(fa), d = get(x), dd = get(fa);
    if (nRoot(fa)) node[gf].ch[dd] = x;
    node[fa].ch[d] = node[x].ch[d ^ 1];
    Fa(node[x].ch[d ^ 1]) = fa;
    node[x].ch[d ^ 1] = fa;
    Fa(fa) = x;
    Fa(x) = gf;
    pushup(fa);
    pushup(x);
}

int st[N], tp;

inline void splay(int x) {
    int y = st[tp = 1] = x;
    while (nRoot(y)) st[++tp] = y = Fa(y);
    while (tp) pushdown(st[tp--]);
    for (; nRoot(x); rotate(x)) if (nRoot(Fa(x)))
        rotate(get(Fa(x)) == get(x) ? Fa(x) : x);
    pushup(x);
}

inline void access(int x) {
    int y = 0;
    while (x) {
        splay(x);
        Rs(x) = y;
        pushup(x);
        x = Fa(y = x);
    }
}

inline void makeroot(int x) {
    access(x);
    splay(x);
    reverse(x);
}

inline void split(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
}

inline void link(int x, int y) {
    makeroot(x);
    Fa(x) = y;
}

inline void cut(int x, int y) {
    split(x, y);
    Fa(x) = Ls(y) = 0;
}

inline int findRoot(int x) {
    access(x);
    splay(x);
    while (Ls(x)) x = Ls(x), pushdown(x);
    splay(x);
    return x;
}
/*
-   `bridge u v`：询问结点u与结点v是否连通。如果是则输出  `no`；否则输出  `yes`，并且在结点  uu  和结点  vv  之间连一条无向边。
-   `penguins u x`：将结点  uu  对应的权值  wuwu​  修改为  xx。
-   `excursion u v`：如果结点  uu  和结点  vv  不连通，则输出  `impossible`。否则输出结点  uu  到结点  vv  的路径上的点对应的权值的和。
*/
int main() {
    int n, m;
    char s[15];
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &node[i].w);
    scanf("%d", &m);
    int u, v;
    for (int i = 1; i <= m; ++i) {
        scanf("%s%d%d", s + 1, &u, &v);
        if (s[1] == 'e') {
            if (findRoot(u) != findRoot(v)) printf("impossible\n");
            else split(u, v), printf("%d\n", node[v].sum);
        } else if (s[1] == 'p') {
            splay(u);
            node[u].w = v;
            pushup(u);
        } else {
            if (findRoot(u) == findRoot(v)) printf("no\n");
            else printf("yes\n"), link(u, v);
        }
    }
    return 0;
}

typedef long long ll;
const ll MOD = 1000000007;
const ll MAXN = 100005;

struct Node {
    ll l, r; // l和r表示这一段的起点和终点
    mutable ll v; // v表示这一段上所有元素相同的值是多少

    Node(ll l, ll r = 0, ll v = 0) : l(l), r(r), v(v) {}

    bool operator<(const Node &a) const {
        return l < a.l; // 规定按照每段的左端点排序
    }
};

ll n, m, seed, vmax, a[MAXN];
set<Node> s;

// 以pos去做切割，找到一个包含pos的区间，把它分成[l,pos-1],[pos,r]两半
set<Node>::iterator split(int pos) {
    set<Node>::iterator it = s.lower_bound(Node(pos));
    if (it != s.end() && it->l == pos) {
        return it;
    }
    it--;
    if (it->r < pos) return s.end();
    ll l = it->l;
    ll r = it->r;
    ll v = it->v;
    s.erase(it);
    s.insert(Node(l, pos - 1, v));
    return s.insert(Node(pos, r, v)).first;
}

void add(ll l, ll r, ll x) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    for (set<Node>::iterator it = itl; it != itr; ++it) {
        it->v += x;
    }
}

void assign(ll l, ll r, ll x) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(Node(l, r, x));
}

struct Rank {
    ll num, cnt;

    bool operator<(const Rank &a) const {
        return num < a.num;
    }

    Rank(ll num, ll cnt) : num(num), cnt(cnt) {}
};

ll rnk(ll l, ll r, ll x) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    vector<Rank> v;
    for (set<Node>::iterator i = itl; i != itr; ++i) {
        v.push_back(Rank(i->v, i->r - i->l + 1));
    }
    sort(v.begin(), v.end());
    int i;
    for (i = 0; i < v.size(); ++i) {
        if (v[i].cnt < x) {
            x -= v[i].cnt;
        } else {
            break;
        }
    }
    return v[i].num;
}

ll ksm(ll x, ll y, ll p) {
    ll r = 1;
    ll base = x % p;
    while (y) {
        if (y & 1) {
            r = r * base % p;
        }
        base = base * base % p;
        y >>= 1;
    }
    return r;
}

ll calP(ll l, ll r, ll x, ll y) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    ll ans = 0;
    for (set<Node>::iterator i = itl; i != itr; ++i) {
        ans = (ans + ksm(i->v, x, y) * (i->r - i->l + 1) % y) % y;
    }
    return ans;
}

ll rnd() {
    ll ret = seed;
    seed = (seed * 7 + 13) % MOD;
    return ret;
}

int main() {
    cin >> n >> m >> seed >> vmax;
    for (int i = 1; i <= n; ++i) {
        a[i] = (rnd() % vmax) + 1;
        s.insert(Node(i, i, a[i]));
    }
    for (int i = 1; i <= m; ++i) {
        ll op, l, r, x, y;
        op = (rnd() % 4) + 1;
        l = (rnd() % n) + 1;
        r = (rnd() % n) + 1;
        if (l > r) swap(l, r);
        if (op == 3) {
            x = (rnd() % (r - l + 1)) + 1;
        } else {
            x = (rnd() % vmax) + 1;
        }
        if (op == 4) {
            y = (rnd() % vmax) + 1;
        }
        if (op == 1) {
            add(l, r, x);
        } else if (op == 2) {
            assign(l, r, x);
        } else if (op == 3) {
            cout << rnk(l, r, x) << endl;
        } else {
            cout << calP(l, r, x, y) << endl;
        }
    }
    return 0;
}