#includeusing namespace std; const int MAXN=30000+233;const int INF=0x3f3f3f3f; struct Edge { int to,nxt;} e[MAXN<<2]; int n,q,x,y,cnt=0,dfnt=0;int head[MAXN],val[MAXN];int dep[MAXN],siz[MAXN],fa[MAXN],son[MAXN],tp[MAXN],pos[MAXN];char opt[233]; int read() { int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); } while (isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;} void add_edge(int u,int v) { e[++cnt].nxt=head[u]; head[u]=cnt; e[cnt].to=v;} void dfs1(int x) { siz[x]=1; for (int i=head[x]; i; i=e[i].nxt) { int v=e[i].to; if (v!=fa[x]) { fa[v]=x; dep[v]=dep[x]+1; dfs1(v); siz[x]+=siz[v]; if (!son[x]||siz[v]>siz[son[x]]) son[x]=v; } }} void dfs2(int x,int TOP) { pos[x]=++dfnt; tp[x]=TOP; if (!son[x]) return; dfs2(son[x],TOP); for (int i=head[x]; i; i=e[i].nxt) { int v=e[i].to; if (v!=son[x]&&v!=fa[x]) dfs2(v,v); }} namespace Segment_Tree { struct Tree { int sum,mt; } t[MAXN<<3]; void push_up(int root) { t[root].sum=t[root<<1].sum+t[root<<1|1].sum; t[root].mt=max(t[root<<1].mt,t[root<<1|1].mt); } void update(int root,int l,int r,int qt,int dat) { if (l==r) { t[root].mt=t[root].sum=dat; return; } int mid=l+r>>1; if (qt<=mid) update(root<<1,l,mid,qt,dat); else update(root<<1|1,mid+1,r,qt,dat); push_up(root); } long long query_max(int root,int l,int r,int ql,int qr) { if (ql<=l&&qr>=r) return t[root].mt; long long ans=-INF; int mid=l+r>>1; if (ql<=mid) ans=max(ans,query_max(root<<1,l,mid,ql,qr)); if (qr>mid) ans=max(ans,query_max(root<<1|1,mid+1,r,ql,qr)); return ans; } long long query_sum(int root,int l,int r,int ql,int qr) { if (ql<=l&&qr>=r) return t[root].sum; long long ans=0; int mid=l+r>>1; if (ql<=mid) ans+=query_sum(root<<1,l,mid,ql,qr); if (qr>mid) ans+=query_sum(root<<1|1,mid+1,r,ql,qr); return ans; } long long Solve_max(int l,int r) { long long ans=-INF; for (; tp[x]!=tp[y]; x=fa[tp[x]]) { if (dep[tp[x]]