//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "线段树分治 (线性基) (八纵八横)": {
        "prefix": "acm-2.6时间分治",
        "body": [
            "#include<algorithm>",
            "#include<iostream>",
            "#include<cstring>",
            "#include<cstdio>",
            "#include<bitset>",
            "#include<stack>",
            "#define LL long long",
            "#define Re register int",
            "#define Int bitset<M>",
            "using namespace std;",
            "const int N=550+5,M=1000+5;",
            "int n,m,x,y,o,O,T,logN,X[N],Y[N],fa[N],last[N],head[N];Int z,Z[N],dis[N],Ans[M];char op[20];",
            "struct QAQ{int to,next;Int w;}a[N<<1];",
            "inline void add(Re x,Re y,Int z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}",
            "inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}",
            "inline int getlen(Int &x){Re n=1000;while(n>=1&&!x[n])--n;return n;}",
            "inline void print(Int &x){for(Re i=getlen(x);i>=0;--i)putchar(x[i]+'0');puts(\"\");}",
            "inline void in(Int &x){cin>>x,logN=max(logN,getlen(x));}",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "struct Line_JI{",
            "\tInt p[M];bool pp[M];stack<int>Q;",
            "\tinline void insert(Int x){",
            "\t\tfor(Re i=logN;i>=0;--i)",
            "\t\t\tif(x[i]){",
            "\t\t\t\tif(!pp[i]){Q.push(i),p[i]=x,pp[i]=1;break;}",
            "\t\t\t\tx^=p[i];",
            "\t\t\t}",
            "\t}",
            "\tinline Int ask(){",
            "\t\tInt ans;ans.reset();",
            "\t\tfor(Re i=logN;i>=0;--i)if(pp[i]&&(!ans[i]))ans^=p[i];",
            "\t\treturn ans;",
            "\t}",
            "\tinline void back(Re to){",
            "\t\twhile(Q.size()>to)x=Q.top(),Q.pop(),p[x].reset(),pp[x]=0;",
            "\t}",
            "}JI;",
            "struct Segment_Tree{",
            "\tint o,head[M<<2];",
            "\tstruct QAQ{int x,y,next;Int w;}a[(N+M)*10];",
            "\tinline void add(Re t,Re x,Re y,Int &z){a[++o].x=x,a[o].y=y,a[o].w=z,a[o].next=head[t],head[t]=o;}",
            "\t#define pl (p<<1)",
            "\t#define pr (p<<1|1)",
            "\t#define mid ((L+R)>>1)",
            "\tinline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y,Int &z){",
            "\t\tif(l<=L&&R<=r){add(p,x,y,z);return;}",
            "\t\tif(l<=mid)change(pl,L,mid,l,r,x,y,z);",
            "\t\tif(r>mid)change(pr,mid+1,R,l,r,x,y,z);",
            "\t}",
            "\tinline void dfs(Re p,Re L,Re R){",
            "\t\tRe tmp=JI.Q.size();",
            "\t\tfor(Re i=head[p];i;i=a[i].next)JI.insert(dis[a[i].x]^dis[a[i].y]^a[i].w);",
            "\t\tif(L==R)Ans[L]=JI.ask();// 这里还没做back撤销操作,不能return!!!",
            "\t\telse dfs(pl,L,mid),dfs(pr,mid+1,R);",
            "\t\tJI.back(tmp);",
            "\t}",
            "}TR;",
            "inline void dfs(Re x,Re fa,Re w){",
            "\tdis[x]=dis[fa]^a[w].w;",
            "\tfor(Re i=head[x];i;i=a[i].next)",
            "\t\tif(a[i].to!=fa)dfs(a[i].to,x,i);",
            "}",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(n),in(m),in(T),++T;",
            "\tfor(Re i=1;i<=n;++i)fa[i]=i;",
            "\twhile(m--){",
            "\t\tin(x),in(y),in(z);",
            "\t\tif(find(x)!=find(y))add(x,y,z),add(y,x,z),fa[find(x)]=find(y);",
            "\t\telse TR.change(1,1,T,1,T,x,y,z);",
            "\t}",
            "\tfor(Re i=2;i<=T;++i){",
            "\t\tscanf(\"%s\",op);",
            "\t\tif(op[0]=='A')last[++O]=i,in(X[O]),in(Y[O]),in(Z[O]);",
            "\t\telse if(op[1]=='h'){",
            "\t\t\tin(x),in(z);",
            "\t\t\tTR.change(1,1,T,last[x],i-1,X[x],Y[x],Z[x]);",
            "\t\t\tlast[x]=i,Z[x]=z;",
            "\t\t}",
            "\t\telse in(x),TR.change(1,1,T,last[x],i-1,X[x],Y[x],Z[x]),last[x]=0;",
            "\t}",
            "\tfor(Re i=1;i<=O;++i)if(last[i])TR.change(1,1,T,last[i],T,X[i],Y[i],Z[i]);",
            "\tdfs(1,0,0),TR.dfs(1,1,T);",
            "\tfor(Re i=1;i<=T;++i)print(Ans[i]);",
            "}",
            ""
        ],
        "description": "插入 线段树分治 (线性基) (八纵八横)"
    }
}