import heapq from collections import defaultdict,deque class Graph: def __init__(self,V,edges=False,graph=False,directed=False,weighted=False): self.V=V self.directed=directed self.weighted=weighted if not graph: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) else: self.graph=graph self.edges=[] for i in range(self.V): if self.weighted: for j,d in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j,d)) else: for j in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j)) def SS_BFS(self,s,bfs_tour=False,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V seen[s]=True if bfs_tour: bt=[s] if linked_components: lc=[s] if parents: ps=[None]*self.V if unweighted_dist or bipartite_graph: uwd=[float('inf')]*self.V uwd[s]=0 if weighted_dist: wd=[float('inf')]*self.V wd[s]=0 queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bfs_tour: bt.append(y) if linked_components: lc.append(y) if parents: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d if bipartite_graph: bg=[[],[]] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if type(uwd[i])==float or type(uwd[j])==float: continue if not uwd[i]%2^uwd[j]%2: bg=False break else: for x in range(self.V): if type(uwd[x])==float: continue bg[uwd[x]%2].append(x) tpl=() if bfs_tour: tpl+=(bt,) if bipartite_graph: tpl+=(bg,) if linked_components: tpl+=(lc,) if parents: tpl+=(ps,) if unweighted_dist: tpl+=(uwd,) if weighted_dist: tpl+=(wd,) if len(tpl)==1: tpl=tpl[0] return tpl def AP_BFS(self,bipartite_graph=False,linked_components=False,parents=False): seen=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if linked_components: lc=[] if parents: ps=[None]*self.V for s in range(self.V): if seen[s]: continue seen[s]=True if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([s]) queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if linked_components: lc[-1].append(y) if parents: ps[y]=x if bipartite_graph: bg_=bg bg=[[[],[]] for i in range(cnt+1)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if not bg_[i][1]^bg_[j][1]: bg[bg_[i][0]]=False for x in range(self.V): if bg[bg_[x][0]]: bg[bg_[x][0]][bg_[x][1]].append(x) tpl=() if bipartite_graph: tpl+=(bg,) if linked_components: tpl+=(lc,) if parents: tpl+=(ps,) if len(tpl)==1: tpl=tpl[0] return tpl def SS_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V finished=[False]*self.V if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if parents or cycle_detection or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if unweighted_dist or bipartite_graph: uwd=[float('inf')]*self.V uwd[s]=0 if weighted_dist: wd=[float('inf')]*self.V wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc.append(x) if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if parents or cycle_detection or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if (directed_acyclic or cycle_detection or topological_sort) and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg=[[],[]] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if type(uwd[i])==float or type(uwd[j])==float: continue if not uwd[i]%2^uwd[j]%2: bg=False break else: for x in range(self.V): if type(uwd[x])==float: continue bg[uwd[x]%2].append(x) tpl=() if bipartite_graph: tpl+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) tpl+=(cd,) if directed_acyclic: tpl+=(dag,) if euler_tour: tpl+=(et,) if linked_components: tpl+=(lc,) if parents: tpl+=(ps,) if postorder: tpl+=(post,) if preorder: tpl+=(pre,) if subtree_size: tpl+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] tpl+=(tp_sort,) if unweighted_dist: tpl+=(uwd,) if weighted_dist: tpl+=(wd,) if len(tpl)==1: tpl=tpl[0] return tpl def AP_DFS(self,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,parents=False,postorder=False,preorder=False,topological_sort=False): seen=[False]*self.V finished=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if parents or cycle_detection: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] for s in range(self.V): if seen[s]: continue if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([]) stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc[-1].append(x) if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if parents or cycle_detection: ps[y]=x elif not finished[y]: if directed_acyclic and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if postorder or topological_sort: post.append(x) if bipartite_graph: bg_=bg bg=[[[],[]] for i in range(cnt+1)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if not bg_[i][1]^bg_[j][1]: bg[bg_[i][0]]=False for x in range(self.V): if bg[bg_[x][0]]: bg[bg_[x][0]][bg_[x][1]].append(x) tpl=() if bipartite_graph: tpl+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) tpl+=(cd,) if directed_acyclic: tpl+=(dag,) if euler_tour: tpl+=(et,) if linked_components: tpl+=(lc,) if parents: tpl+=(ps,) if postorder: tpl+=(post,) if preorder: tpl+=(pre,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] tpl+=(tp_sort,) if len(tpl)==1: tpl=tpl[0] return tpl def Tree_Diameter(self,weighted=False): def Farthest_Point(u): dist=self.SS_BFS(u,weighted_dist=True) if weighted else self.SS_BFS(u,unweighted_dist=True) fp=0 for i in range(self.V): if dist[fp]=0: self.lca_dfs_in_index[x]=i else: self.lca_dfs_out_index[~x]=i self.ST=Segment_Tree(2*self.V,lambda x,y:min(x,y),self.V) lst=[None]*(2*self.V) for i in range(2*self.V-1): if self.lca_euler_tour[i]>=0: lst[i]=depth[self.lca_euler_tour[i]] else: lst[i]=depth[self.lca_parents[~self.lca_euler_tour[i]]] lst[2*self.V-1]=-1 self.ST.Build(lst) def LCA(self,a,b): m=min(self.lca_dfs_in_index[a],self.lca_dfs_in_index[b]) M=max(self.lca_dfs_in_index[a],self.lca_dfs_in_index[b]) x=self.lca_euler_tour[self.ST.Fold_Index(m,M+1)] if x>=0: return x else: return self.lca_parents[~x] def Build_HLD(self,s): self.hld_parents,size,self.hld_depth=self.SS_DFS(s,parents=True,subtree_size=True,unweighted_dist=True) seen=[False]*self.V stack=[s] self.hld_tour=[] self.hld_path_parents=[None]*self.V self.hld_path_parents[s]=s while stack: x=stack.pop() seen[x]=True self.hld_tour.append(x) max_size=0 max_size_y=None for y in self.graph[x]: if self.weighted: y,d=y if not seen[y] and max_sizedx+dy: dist[y]=dx+dy if route_restoration: parents[y]=x heapq.heappush(hq,(dist[y],y)) if route_restoration: return dist,parents else: return dist def Bellman_Ford(self,s,route_restoration=False): dist=[float('inf')]*self.V dist[s]=0 if route_restoration: parents=[None]*self.V for _ in range(self.V-1): for i,j,d in self.edges: if dist[j]>dist[i]+d: dist[j]=dist[i]+d if route_restoration: parents[j]=i if not self.directed and dist[i]>dist[j]+d: dist[i]=dist[j]+d if route_restoration: parents[i]=j negative_cycle=[] for i,j,d in self.edges: if dist[j]>dist[i]+d: negative_cycle.append(j) if not self.directed and dist[i]>dist[j]+d: negative_cycle.append(i) if negative_cycle: is_negative_cycle=[False]*self.V for i in negative_cycle: if is_negative_cycle[i]: continue else: queue=deque([i]) is_negative_cycle[i]=True while queue: x=queue.popleft() for y,d in self.graph[x]: if not is_negative_cycle[y]: queue.append(y) is_negative_cycle[y]=True if route_restoration: parents[y]=x for i in range(self.V): if is_negative_cycle[i]: dist[i]=-float('inf') if route_restoration: return dist,parents else: return dist def Warshall_Floyd(self,route_restoration=False): dist=[[float('inf')]*self.V for i in range(self.V)] for i in range(self.V): dist[i][i]=0 if route_restoration: parents=[[j for j in range(self.V)] for i in range(self.V)] for i,j,d in self.edges: if i==j: continue if dist[i][j]>d: dist[i][j]=d if route_restoration: parents[i][j]=i if not self.directed and dist[j][i]>d: dist[j][i]=d if route_restoration: parents[j][i]=j for k in range(self.V): for i in range(self.V): for j in range(self.V): if dist[i][j]>dist[i][k]+dist[k][j]: dist[i][j]=dist[i][k]+dist[k][j] if route_restoration: parents[i][j]=parents[k][j] for i in range(self.V): if dist[i][i]<0: for j in range(self.V): if dist[i][j]!=float('inf'): dist[i][j]=-float('inf') if route_restoration: for i in range(self.V): if dist[i][i]==0: parents[i][i]=None return dist,parents else: return dist def Route_Restoration(self,s,g,parents): route=[g] while s!=g: if parents[g]==None: route=[] break g=parents[g] route.append(g) route=route[::-1] return route def Kruskal(self): UF=UnionFind(self.V) sorted_edges=sorted(self.edges,key=lambda x:x[2]) minimum_spnning_tree=[] for i,j,d in sorted_edges: if not UF.Same(i,j): UF.Union(i,j) minimum_spnning_tree.append((i,j,d)) return minimum_spnning_tree def Ford_Fulkerson(self,s,t): max_flow=0 residual_graph=[defaultdict(int) for i in range(self.V)] if self.weighted: for i,j,d in self.edges: if not d: continue residual_graph[i][j]+=d if not self.directed: residual_graph[j][i]+=d else: for i,j in self.edges: residual_graph[i][j]+=1 if not self.directed: residual_graph[j][i]+=1 while True: parents=[None]*self.V parents[s]=s seen=[False]*self.V seen[s]=True queue=deque([s]) while queue: x=queue.popleft() for y in residual_graph[x].keys(): if not seen[y]: seen[y]=True queue.append(y) parents[y]=x if y==t: tt=t while tt!=s: residual_graph[parents[tt]][tt]-=1 residual_graph[tt][parents[tt]]+=1 if not residual_graph[parents[tt]][tt]: residual_graph[parents[tt]].pop(tt) tt=parents[tt] max_flow+=1 break else: continue break else: break return max_flow def BFS(self,s): seen=[False]*self.V seen[s]=True queue=deque([s]) while queue: x=queue.popleft() for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: seen[y]=True queue.append(y) return def DFS(self,s): seen=[False]*self.V finished=[False]*self.V stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) elif not finished[x]: finished[x]=True return class Segment_Tree: def __init__(self,N,f,e,lst=None): self.f=f self.e=e self.N=N if lst==None: self.segment_tree=[self.e]*2*self.N else: assert len(lst)<=self.N self.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst)) for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def __getitem__(self,i): if type(i)==int: if -self.N<=i<0: return self.segment_tree[i+self.N*2] elif 0<=i1: i>>= 1 self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Build(self,lst): for i,x in enumerate(lst,self.N): self.segment_tree[i]=x for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Fold(self,L=None,R=None): if L==None or L<-self.N: L=self.N elif self.N<=L: L=self.N*2 elif L<0: L+=self.N*2 else: L+=self.N if R==None or self.N<=R: R=self.N*2 elif R<-self.N: R=self.N elif R<0: R+=self.N*2 else: R+=self.N vL=self.e vR=self.e while L>=1 R>>=1 return self.f(vL,vR) def Fold_Index(self,L=None,R=None): if L==None or L<-self.N: L=self.N elif self.N<=L: L=self.N*2 elif L<0: L+=self.N*2 else: L+=self.N if R==None or self.N<=R: R=self.N*2 elif R<-self.N: R=self.N elif R<0: R+=self.N*2 else: R+=self.N if L==R: return None x=self.Fold(L-self.N,R-self.N) while L>=1 R>>=1 while i=0: x,y=1,0 else: x,y=-1,0 for i in range(len(stack)-1,-1,-1): n,m=stack[i] x,y=y,x-(n//m)*y return x,y class MOD: def __init__(self,p,e=1): self.p=p self.e=e self.mod=self.p**self.e def Pow(self,a,n): a%=self.mod if n>=0: return pow(a,n,self.mod) else: assert math.gcd(a,self.mod)==1 x=Extended_Euclid(a,self.mod)[0] return pow(x,-n,self.mod) def Build_Fact(self,N): assert N>=0 self.factorial=[1] self.cnt=[0]*(N+1) for i in range(1,N+1): ii=i self.cnt[i]=self.cnt[i-1] while ii%self.p==0: ii//=self.p self.cnt[i]+=1 self.factorial.append((self.factorial[-1]*ii)%self.mod) self.factorial_inve=[None]*(N+1) self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1) for i in range(N-1,-1,-1): ii=i+1 while ii%self.p==0: ii//=self.p self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.mod def Fact(self,N): return self.factorial[N]*pow(self.p,self.cnt[N],self.mod)%self.mod def Fact_Inve(self,N): if self.cnt[N]: return None return self.factorial_inve[N] def Comb(self,N,K,divisible_count=False): if K<0 or K>N: return 0 retu=self.factorial[N]*self.factorial_inve[K]*self.factorial_inve[N-K]%self.mod cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K] if divisible_count: return retu,cnt else: retu*=pow(self.p,cnt,self.mod) retu%=self.mod return retu class Matrix: def __init__(self,H=0,W=0,matrix=False,eps=0,mod=0,identity=0): if identity: if H: self.H=H self.W=H else: self.H=W self.W=W self.matrix=[[0]*self.W for i in range(self.H)] for i in range(self.H): self.matrix[i][i]=identity elif matrix: self.matrix=matrix self.H=len(self.matrix) self.W=len(self.matrix[0]) if self.matrix else 0 else: self.H=H self.W=W self.matrix=[[0]*self.W for i in range(self.H)] self.mod=mod self.eps=eps def __eq__(self,other): if type(other)!=Matrix: return False if self.H!=other.H: return False if self.mod: for i in range(self.H): for j in range(self.W): if self.matrix[i][j]%self.mod!=other.matrix[i][j]%self.mod: return False else: for i in range(self.H): for j in range(self.W): if self.eps=2: if other&1: prod@=doub doub@=doub other>>=1 prod@=doub return prod def __truediv__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W if self.mod: quot=Matrix(matrix=[[(self.matrix[i][j]*MOD(self.mod).Pow(other.matrix[i][j],-1))%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: quot=Matrix(matrix=[[self.matrix[i][j]/other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: if self.mod: inve=MOD(self.mod).Pow(other,-1) quot=Matrix(matrix=[[(self.matrix[i][j]*inve)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: quot=Matrix(matrix=[[self.matrix[i][j]/other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return quot def __floordiv__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W quot=Matrix(matrix=[[self.matrix[i][j]//other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: quot=Matrix(matrix=[[self.matrix[i][j]//other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return quot def __mod__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W rema=Matrix(matrix=[[self.matrix[i][j]%other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: rema=Matrix(matrix=[[self.matrix[i][j]%other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return rema def __pow__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W if self.mod: powe=Matrix(matrix=[[pow(self.matrix[i][j],other.matrix[i][j],self.mod) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: powe=Matrix(matrix=[[pow(self.matrix[i][j],other.matrix[i][j]) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: if self.mod: powe=Matrix(matrix=[[pow(self.matrix[i][j],other,self.mod) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: powe=Matrix(matrix=[[pow(self.matrix[i][j],other) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return powe def __lshift__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W lshi=Matrix(matrix=[[self.matrix[i][j]<>other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: rshi=Matrix(matrix=[[self.matrix[i][j]>>other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return rshi def __and__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W conj=Matrix(matrix=[[self.matrix[i][j]&other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: conj=Matrix(matrix=[[self.matrix[i][j]&other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return conj def __or__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W disj=Matrix(matrix=[[self.matrix[i][j]|other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: disj=Matrix(matrix=[[self.matrix[i][j]|other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return disj def __xor__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W excl=Matrix(matrix=[[self.matrix[i][j]^other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: excl=Matrix(matrix=[[self.matrix[i][j]^other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return excl def __iadd__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]+=other.matrix[i][j] if self.mod: self.matrix[i][j]%=self.mod else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]+=other if self.mod: self.matrix[i][j]%=self.mod return self def __isub__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]-=other.matrix[i][j] if self.mod: self.matrix[i][j]%=self.mod else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]-=other if self.mod: self.matrix[i][j]%=self.mod return self def __imul__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]*=other.matrix[i][j] if self.mod: self.matrix[i][j]%=self.mod else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]*=other if self.mod: self.matrix[i][j]%=self.mod return self def __imatmul__(self,other): if type(other)==Matrix: assert self.W==other.H prod=Matrix(H=self.H,W=other.W,eps=self.eps,mod=self.mod) for i in range(self.H): for j in range(other.W): for k in range(self.W): prod.matrix[i][j]+=self.matrix[i][k]*other.matrix[k][j] if self.mod: prod.matrix[i][j]%=self.mod elif type(other)==int: assert self.H==self.W if other==0: return Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1) elif other==1: prod=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: prod=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1) doub=self while other>=2: if other&1: prod@=doub doub@=doub other>>=1 prod@=doub return prod def __itruediv__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): if self.mod: self.matrix[i][j]=self.matrix[i][j]*MOD(self.mod).Pow(other.matrix[i][j],-1)%self.mod else: self.matrix[i][j]/=other.matrix[i][j] else: if self.mod: inve=MOD(self.mod).Pow(other,-1) for i in range(self.H): for j in range(self.W): if self.mod: self.matrix[i][j]=self.matrix[i][j]*inve%self.mod else: self.matrix[i][j]/=other return self def __ifloordiv__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]//=other.matrix[i][j] else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]//=other return self def __imod__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]%=other.matrix[i][j] else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]%=other return self def __ipow__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): if self.mod: self.matrix[i][j]=pow(self.matrix[i][j],other.matrix[i][j],self.mod) else: self.matrix[i][j]=pow(self.matrix[i][j],other.matrix[i][j]) else: for i in range(self.H): for j in range(self.W): if self.mod: self.matrix[i][j]=pow(self.matrix[i][j],other,self.mod) else: self.matrix[i][j]=pow(self.matrix[i][j],other) return self def __ilshift__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]<<=other.matrix[i][j] else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]<<=other return self def __irshift__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]>>=other.matrix[i][j] else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]>>=other return self def __iand__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]&=other.matrix[i][j] else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]&=other return self def __ior__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]|=other.matrix[i][j] else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]|=other return self def __ixor__(self,other): if type(other)==Matrix: assert self.H==other.H assert self.W==other.W for i in range(self.H): for j in range(self.W): self.matrix[i][j]^=other.matrix[i][j] else: for i in range(self.H): for j in range(self.W): self.matrix[i][j]^=other return self def __neg__(self): if self.mod: nega=Matrix(matrix=[[(-self.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) else: nega=Matrix(matrix=[[-self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return nega def __pos__(self): posi=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return posi def __invert__(self): inve=Matrix(matrix=[[~self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return inve def __abs__(self): abso=Matrix(matrix=[[abs(self.matrix[i][j]) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) return abso def __getitem__(self,i): if type(i)==int: return self.matrix[i] elif type(i)==tuple: i,j=i if type(i)==int: i=slice(i,i+1) if type(j)==int: j=slice(j,j+1) return Matrix(matrix=[lst[j] for lst in self.matrix[i]],eps=self.eps,mod=self.mod) def __contains__(self,x): for i in range(self.H): if x in self.matrix[i]: return True return False def __str__(self): digit=[max(len(str(self.matrix[i][j])) for i in range(self.H)) for j in range(self.W)] return "\n".join([(" [" if i else "[[")+", ".join([str(self.matrix[i][j]).rjust(digit[j]," ") for j in range(self.W)])+"]" for i in range(self.H)])+"]" def __bool__(self): return True def Transpose(self): return Matrix(matrix=[[self.matrix[i][j] for i in range(self.H)] for j in range(self.W)]) def Trace(self): assert self.H==self.W trace=sum(self.matrix[i][i] for i in range(self.H)) if self.mod: trace%=self.mod return trace def Elem_Raw_Operate_1(self,i1,i2): self.matrix[i1],self.matrix[i2]=self.matrix[i2],self.matrix[i1] def Elem_Raw_Operate_2(self,i,c): if self.mod: self.matrix[i]=[self.matrix[i][j]*c%self.mod for j in range(self.W)] else: self.matrix[i]=[self.matrix[i][j]*c for j in range(self.W)] def Elem_Raw_Operate_3(self,i1,i2,c): if self.mod: self.matrix[i1]=[(self.matrix[i1][j]+c*self.matrix[i2][j])%self.mod for j in range(self.W)] else: self.matrix[i1]=[self.matrix[i1][j]+c*self.matrix[i2][j] for j in range(self.W)] def Elimination(self,determinant=False,inverse_matrix=False,linear_equation=False,rank=False,upper_triangular=False): h=0 ut=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod) if determinant or inverse_matrix: assert self.H==self.W det=1 if inverse_matrix: assert self.H==self.W im=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1) if linear_equation: assert self.H==linear_equation.H le=Matrix(matrix=[[linear_equation.matrix[i][j] for j in range(linear_equation.W)] for i in range(linear_equation.H)],eps=self.eps,mod=self.mod) for j in range(ut.W): for i in range(h,ut.H): if abs(ut.matrix[i][j])>ut.eps: if ut.mod: inve=MOD(ut.mod).Pow(ut.matrix[i][j],-1) else: inve=1/ut.matrix[i][j] ut.Elem_Raw_Operate_1(i,h) if determinant and h%2!=i%2: det=(-det)%self.mod if inverse_matrix: im.Elem_Raw_Operate_1(i,h) if linear_equation: le.Elem_Raw_Operate_1(i,h) ut.Elem_Raw_Operate_2(h,inve) if determinant or inverse_matrix: det*=inve if ut.mod: det%=ut.mod if inverse_matrix: im.Elem_Raw_Operate_2(h,inve) if linear_equation: le.Elem_Raw_Operate_2(h,inve) for ii in range(ut.H): if ii==h: continue x=-ut.matrix[ii][j] ut.Elem_Raw_Operate_3(ii,h,x) if inverse_matrix: im.Elem_Raw_Operate_3(ii,h,x) if linear_equation: le.Elem_Raw_Operate_3(ii,h,x) h+=1 break else: det=0 tpl=() if determinant: tpl+=(det,) if inverse_matrix: if det<=0: im=False tpl+=(im,) if linear_equation: tpl+=(le,) if rank: tpl+=(h,) if upper_triangular: tpl+=(ut,) if len(tpl)==1: tpl=tpl[0] return tpl N=int(readline()) edges=[] for i in range(N-1): a,b=map(int,readline().split()) edges.append((a,b)) G=Graph(N,edges=edges) G.Build_HLD(0) parents=G.SS_DFS(0,parents=True) mod=10**9+7 ST=Segment_Tree(N,lambda x,y:x@y,Matrix(H=2,identity=1,mod=mod)) Q=int(readline()) for i in range(Q): query=readline().rstrip() if query[0]=="x": i,a,b,c,d=map(int,query[2:].split()) u,v=edges[i] if u==parents[v]: u,v=v,u ST[G.hld_tour_idx[u]]=Matrix(matrix=[[a,b],[c,d]],mod=mod) else: i,j=map(int,query[2:].split()) ans=Matrix(H=2,identity=1,mod=mod) for a,b in G.HLD(i,j,edge=True): ans@=ST.Fold(a,b) print(ans[0][0],ans[0][1],ans[1][0],ans[1][1])