結果
問題 | No.650 行列木クエリ |
ユーザー | vwxyz |
提出日時 | 2021-11-07 04:44:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,228 ms / 2,000 ms |
コード長 | 53,505 bytes |
コンパイル時間 | 508 ms |
コンパイル使用メモリ | 90,820 KB |
実行使用メモリ | 150,244 KB |
最終ジャッジ日時 | 2024-10-03 01:23:56 |
合計ジャッジ時間 | 8,010 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 65 ms
68,340 KB |
testcase_01 | AC | 810 ms
114,944 KB |
testcase_02 | AC | 1,228 ms
150,228 KB |
testcase_03 | AC | 63 ms
68,016 KB |
testcase_04 | AC | 819 ms
115,204 KB |
testcase_05 | AC | 1,131 ms
148,400 KB |
testcase_06 | AC | 64 ms
68,060 KB |
testcase_07 | AC | 63 ms
67,228 KB |
testcase_08 | AC | 800 ms
113,196 KB |
testcase_09 | AC | 938 ms
150,244 KB |
testcase_10 | AC | 62 ms
68,220 KB |
ソースコード
import sysreadline=sys.stdin.readlineimport heapqfrom collections import defaultdict,dequeclass Graph:def __init__(self,V,edges=False,graph=False,directed=False,weighted=False):self.V=Vself.directed=directedself.weighted=weightedif not graph:self.edges=edgesself.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=graphself.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,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False):seen=[False]*self.Vseen[s]=Trueif linked_components:lc=[s]if parents:ps=[None]*self.Vps[s]=sif unweighted_dist or bipartite_graph:uwd=[float('inf')]*self.Vuwd[s]=0if weighted_dist:wd=[float('inf')]*self.Vwd[s]=0queue=deque([s])while queue:x=queue.popleft()for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:seen[y]=Truequeue.append(y)if linked_components:lc.append(y)if parents:ps[y]=xif unweighted_dist or bipartite_graph:uwd[y]=uwd[x]+1if weighted_dist:wd[y]=wd[x]+dif bipartite_graph:bg=[[],[]]for tpl in self.edges:i,j=tpl[:2] if self.weighted else tplif type(uwd[i])==float or type(uwd[j])==float:continueif not uwd[i]%2^uwd[j]%2:bg=Falsebreakelse:for x in range(self.V):if type(uwd[x])==float:continuebg[uwd[x]%2].append(x)tpl=()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 tpldef AP_BFS(self,bipartite_graph=False,linked_components=False,parents=False):seen=[False]*self.Vif bipartite_graph:bg=[None]*self.Vcnt=-1if linked_components:lc=[]if parents:ps=[None]*self.Vfor s in range(self.V):if seen[s]:continueseen[s]=Trueif bipartite_graph:cnt+=1bg[s]=(cnt,0)if linked_components:lc.append([s])if parents:ps[s]=squeue=deque([s])while queue:x=queue.popleft()for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:seen[y]=Truequeue.append(y)if bipartite_graph:bg[y]=(cnt,bg[x][1]^1)if linked_components:lc[-1].append(y)if parents:ps[y]=xif bipartite_graph:bg_=bgbg=[[[],[]] for i in range(cnt+1)]for tpl in self.edges:i,j=tpl[:2] if self.weighted else tplif not bg_[i][1]^bg_[j][1]:bg[bg_[i][0]]=Falsefor 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 tpldef 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.Vfinished=[False]*self.Vif directed_acyclic or cycle_detection or topological_sort:dag=Trueif euler_tour:et=[]if linked_components:lc=[]if parents or cycle_detection or subtree_size:ps=[None]*self.Vps[s]=sif postorder or topological_sort:post=[]if preorder:pre=[]if subtree_size:ss=[1]*self.Vif unweighted_dist or bipartite_graph:uwd=[float('inf')]*self.Vuwd[s]=0if weighted_dist:wd=[float('inf')]*self.Vwd[s]=0stack=[(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]=Truestack.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=yif not seen[y]:stack.append((y,d) if self.weighted else y)if parents or cycle_detection or subtree_size:ps[y]=xif unweighted_dist or bipartite_graph:uwd[y]=uwd[x]+1if weighted_dist:wd[y]=wd[x]+delif not finished[y]:if (directed_acyclic or cycle_detection or topological_sort) and dag:dag=Falseif cycle_detection:cd=(y,x)elif not finished[x]:finished[x]=Trueif 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=yif y==ps[x]:continuess[x]+=ss[y]if bipartite_graph:bg=[[],[]]for tpl in self.edges:i,j=tpl[:2] if self.weighted else tplif type(uwd[i])==float or type(uwd[j])==float:continueif not uwd[i]%2^uwd[j]%2:bg=Falsebreakelse:for x in range(self.V):if type(uwd[x])==float:continuebg[uwd[x]%2].append(x)tpl=()if bipartite_graph:tpl+=(bg,)if cycle_detection:if dag:cd=[]else:y,x=cdcd=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 tpldef 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.Vfinished=[False]*self.Vif bipartite_graph:bg=[None]*self.Vcnt=-1if directed_acyclic or cycle_detection or topological_sort:dag=Trueif euler_tour:et=[]if linked_components:lc=[]if parents or cycle_detection:ps=[None]*self.Vif postorder or topological_sort:post=[]if preorder:pre=[]for s in range(self.V):if seen[s]:continueif bipartite_graph:cnt+=1bg[s]=(cnt,0)if linked_components:lc.append([])if parents:ps[s]=sstack=[(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]=Truestack.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=yif 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]=xelif not finished[y]:if directed_acyclic and dag:dag=Falseif cycle_detection:cd=(y,x)elif not finished[x]:finished[x]=Trueif euler_tour:et.append(~x)if postorder or topological_sort:post.append(x)if bipartite_graph:bg_=bgbg=[[[],[]] for i in range(cnt+1)]for tpl in self.edges:i,j=tpl[:2] if self.weighted else tplif not bg_[i][1]^bg_[j][1]:bg[bg_[i][0]]=Falsefor 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=cdcd=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 tpldef 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=0for i in range(self.V):if dist[fp]<dist[i]:fp=ireturn fp,dist[fp]u,d=Farthest_Point(0)v,d=Farthest_Point(u)return u,v,ddef SCC(self):reverse_graph=[[] for i in range(self.V)]for tpl in self.edges:i,j=tpl[:2] if self.weighted else tplreverse_graph[j].append(i)postorder=self.AP_DFS(postorder=True)scc=[]seen=[False]*self.Vfor s in postorder[::-1]:if seen[s]:continuequeue=deque([s])seen[s]=Truelst=[]while queue:x=queue.popleft()lst.append(x)for y in reverse_graph[x]:if self.weighted:y=y[0]if not seen[y]:seen[y]=Truequeue.append(y)scc.append(lst)return sccdef Build_LCA(self,s):self.lca_euler_tour,self.lca_parents,depth=self.SS_DFS(s,euler_tour=True,parents=True,unweighted_dist=True)self.lca_dfs_in_index=[None]*self.Vself.lca_dfs_out_index=[None]*self.Vfor i,x in enumerate(self.euler_tour):if x>=0:self.lca_dfs_in_index[x]=ielse:self.lca_dfs_out_index[~x]=iself.ST=Segment_Tree(2*self.V,lambda x,y:min(x,y),float('inf'))lst=[None]*2*self.Vfor i in range(2*self.V):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]]]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 xelse:return self.lca_parents[~x]def Build_HLD(self,s):size=self.SS_DFS(s,subtree_size=True)seen=[False]*self.Vstack=[s]self.hld_tour=[]self.hld_parents=[None]*self.Vself.hld_depth=[None]*self.Vself.hld_path_parents=[None]*self.Vself.hld_path_parents[s]=sself.hld_depth[s]=0while stack:x=stack.pop()seen[x]=Trueself.hld_tour.append(x)max_size=0max_size_y=Nonefor y in self.graph[x]:if self.weighted:y,d=yif not seen[y] and max_size<size[y]:max_size=size[y]max_size_y=yfor y in self.graph[x]:if self.weighted:y,d=yif not seen[y] and y!=max_size_y:stack.append(y)self.hld_parents[y]=xself.hld_depth[y]=self.hld_depth[x]+1self.hld_path_parents[y]=yif max_size_y!=None:stack.append(max_size_y)self.hld_parents[max_size_y]=xself.hld_depth[max_size_y]=self.hld_depth[x]+1self.hld_path_parents[max_size_y]=self.hld_path_parents[x]self.hld_tour_idx=[None]*self.Vfor i in range(self.V):self.hld_tour_idx[self.hld_tour[i]]=idef HLD(self,a,b,edge=False):L,R=[],[]while self.hld_path_parents[a]!=self.hld_path_parents[b]:if self.hld_depth[self.hld_path_parents[a]]<self.hld_depth[self.hld_path_parents[b]]:R.append((self.hld_tour_idx[self.hld_path_parents[b]],self.hld_tour_idx[b]+1))b=self.hld_parents[self.hld_path_parents[b]]else:L.append((self.hld_tour_idx[a]+1,self.hld_tour_idx[self.hld_path_parents[a]]))a=self.hld_parents[self.hld_path_parents[a]]if edge:if self.hld_depth[a]!=self.hld_depth[b]:retu=L+[(self.hld_tour_idx[a]+1,self.hld_tour_idx[b]+1)]+R[::-1]else:retu=L+R[::-1]else:if self.hld_depth[a]<self.hld_depth[b]:retu=L+[(self.hld_tour_idx[a],self.hld_tour_idx[b]+1)]+R[::-1]else:retu=L+[(self.hld_tour_idx[a]+1,self.hld_tour_idx[b])]+R[::-1]return retudef Dijkstra(self,s,route_restoration=False):dist=[float('inf')]*self.Vdist[s]=0hq=[(0,s)]if route_restoration:parents=[None]*self.Vparents[s]=swhile hq:dx,x=heapq.heappop(hq)if dist[x]<dx:continuefor y,dy in self.graph[x]:if dist[y]>dx+dy:dist[y]=dx+dyif route_restoration:parents[y]=xheapq.heappush(hq,(dist[y],y))if route_restoration:return dist,parentselse:return distdef Bellman_Ford(self,s,route_restoration=False):dist=[float('inf')]*self.Vdist[s]=0if route_restoration:parents=[s]*self.Vfor _ in range(self.V-1):for i,j,d in self.edges:if dist[j]>dist[i]+d:dist[j]=dist[i]+dif route_restoration:parents[j]=iif not self.directed and dist[i]>dist[j]+d:dist[i]=dist[j]+dif route_restoration:parents[i]=jnegative_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.Vfor i in negative_cycle:if is_negative_cycle[i]:continueelse:queue=deque([i])is_negative_cycle[i]=Truewhile queue:x=queue.popleft()for y,d in self.graph[x]:if not is_negative_cycle[y]:queue.append(y)is_negative_cycle[y]=Trueif route_restoration:parents[y]=xfor i in range(self.V):if is_negative_cycle[i]:dist[i]=-float('inf')if route_restoration:return dist,parentselse:return distdef 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]=0if route_restoration:parents=[[j for j in range(self.V)] for i in range(self.V)]for i,j,d in self.edges:if dist[i][j]>d:dist[i][j]=dif route_restoration:parents[i][j]=iif not self.directed and dist[j][i]>d:dist[j][i]=dif route_restoration:parents[j][i]=jfor 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:return dist,parentselse:return distdef Route_Restoration(self,s,g,parents):route=[g]while s!=g and parents[g]!=g:g=parents[g]route.append(g)route=route[::-1]return routedef 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_treedef Ford_Fulkerson(self,s,t):max_flow=0residual_graph=[defaultdict(int) for i in range(self.V)]if self.weighted:for i,j,d in self.edges:if not d:continueresidual_graph[i][j]+=dif not self.directed:residual_graph[j][i]+=delse:for i,j in self.edges:residual_graph[i][j]+=1if not self.directed:residual_graph[j][i]+=1while True:parents=[None]*self.Vparents[s]=sseen=[False]*self.Vseen[s]=Truequeue=deque([s])while queue:x=queue.popleft()for y in residual_graph[x].keys():if not seen[y]:seen[y]=Truequeue.append(y)parents[y]=xif y==t:tt=twhile tt!=s:residual_graph[parents[tt]][tt]-=1residual_graph[tt][parents[tt]]+=1if not residual_graph[parents[tt]][tt]:residual_graph[parents[tt]].pop(tt)tt=parents[tt]max_flow+=1breakelse:continuebreakelse:breakreturn max_flowdef BFS(self,s):seen=[False]*self.Vseen[s]=Truequeue=deque([s])while queue:x=queue.popleft()for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:seen[y]=Truequeue.append(y)returndef DFS(self,s):seen=[False]*self.Vfinished=[False]*self.Vstack=[(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]=Truestack.append((x,d) if self.weighted else x)for y in self.graph[x]:if self.weighted:y,d=yif not seen[y]:stack.append((y,d) if self.weighted else y)elif not finished[x]:finished[x]=Truereturnclass Segment_Tree:def __init__(self,N,f,e,lst=None):self.f=fself.e=eself.N=Nif lst==None:self.segment_tree=[self.e]*2*self.Nelse:assert len(lst)<=self.Nself.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<=i<self.N:return self.segment_tree[i+self.N]else:raise IndexError('list index out of range')else:a,b,c=i.start,i.stop,i.stepif a==None or a<-self.N:a=self.Nelif self.N<=a:a=self.N*2elif a<0:a+=self.N*2else:a+=self.Nif b==None or self.N<=b:b=self.N*2elif b<-self.N:b=self.Nelif b<0:b+=self.N*2else:b+=self.Nreturn self.segment_tree[slice(a,b,c)]def __setitem__(self,i,x):if -self.N<=i<0:i+=self.N*2elif 0<=i<self.N:i+=self.Nelse:raise IndexError('list index out of range')self.segment_tree[i]=xwhile i>1:i>>= 1self.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]=xfor 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.Nelif self.N<=L:L=self.N*2elif L<0:L+=self.N*2else:L+=self.Nif R==None or self.N<=R:R=self.N*2elif R<-self.N:R=self.Nelif R<0:R+=self.N*2else:R+=self.NvL=self.evR=self.ewhile L<R:if L&1:vL=self.f(vL,self.segment_tree[L])L+=1if R&1:R-=1vR=self.f(self.segment_tree[R],vR)L>>=1R>>=1return self.f(vL,vR)def Fold_Index(self,L=None,R=None):if L==None or L<-self.N:L=self.Nelif self.N<=L:L=self.N*2elif L<0:L+=self.N*2else:L+=self.Nif R==None or self.N<=R:R=self.N*2elif R<-self.N:R=self.Nelif R<0:R+=self.N*2else:R+=self.Nif L==R:return Nonex=self.Fold(L-self.N,R-self.N)while L<R:if L&1:if self.segment_tree[L]==x:i=LbreakL+=1if R&1:R-=1if self.segment_tree[R]==x:i=RbreakL>>=1R>>=1while i<self.N:if self.segment_tree[i]==self.segment_tree[i<<1]:i<<=1else:i<<=1i|=1i-=self.Nreturn idef __str__(self):return '['+', '.join(map(str,self.segment_tree[self.N:]))+']'def Extended_Euclid(n,m):stack=[]while m:stack.append((n,m))n,m=m,n%mif n>=0:x,y=1,0else:x,y=-1,0for i in range(len(stack)-1,-1,-1):n,m=stack[i]x,y=y,x-(n//m)*yreturn x,yclass MOD:def __init__(self,p,e=1):self.p=pself.e=eself.mod=self.p**self.edef Pow(self,a,n):a%=self.modif n>=0:return pow(a,n,self.mod)else:assert math.gcd(a,self.mod)==1x=Extended_Euclid(a,self.mod)[0]return pow(x,-n,self.mod)def Build_Fact(self,N):assert N>=0self.factorial=[1]self.cnt=[0]*(N+1)for i in range(1,N+1):ii=iself.cnt[i]=self.cnt[i-1]while ii%self.p==0:ii//=self.pself.cnt[i]+=1self.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+1while ii%self.p==0:ii//=self.pself.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.moddef Fact(self,N):return self.factorial[N]*pow(self.p,self.cnt[N],self.mod)%self.moddef Fact_Inve(self,N):if self.cnt[N]:return Nonereturn self.factorial_inve[N]def Comb(self,N,K,divisible_count=False):if K<0 or K>N:return 0retu=self.factorial[N]*self.factorial_inve[K]*self.factorial_inve[N-K]%self.modcnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]if divisible_count:return retu,cntelse:retu*=pow(self.p,cnt,self.mod)retu%=self.modreturn retuclass Matrix:def __init__(self,H=0,W=0,matrix=False,eps=0,mod=0,identity=0):if identity:if H:self.H=Hself.W=Helse:self.H=Wself.W=Wself.matrix=[[0]*self.W for i in range(self.H)]for i in range(self.H):self.matrix[i][i]=identityelif matrix:self.matrix=matrixself.H=len(self.matrix)self.W=len(self.matrix[0]) if self.matrix else 0else:self.H=Hself.W=Wself.matrix=[[0]*self.W for i in range(self.H)]self.mod=modself.eps=epsdef __eq__(self,other):if type(other)!=Matrix:return Falseif self.H!=other.H:return Falseif 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 Falseelse:for i in range(self.H):for j in range(self.W):if self.eps<abs(self.matrix[i][j]-other.matrix[i][j]):return Falsereturn Truedef __ne__(self,other):if type(other)!=Matrix:return Trueif self.H!=other.H:return Trueif 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 Trueelse:for i in range(self.H):for j in range(self.W):if self.eps<abs(self.matrix[i][j]-other.matrix[i][j]):return Truereturn Falsedef __add__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif self.mod:summ=Matrix(matrix=[[(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:summ=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:summ=Matrix(matrix=[[(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:summ=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 summdef __sub__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif self.mod:diff=Matrix(matrix=[[(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:diff=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:diff=Matrix(matrix=[[(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:diff=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 diffdef __mul__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif self.mod:prod=Matrix(matrix=[[(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:prod=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:prod=Matrix(matrix=[[(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:prod=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 proddef __matmul__(self,other):if type(other)==Matrix:assert self.W==other.Hprod=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.modelif type(other)==int:assert self.H==self.Wif other==0:prod=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=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)while other>=2:if other&1:prod@=doubdoub@=doubother>>=1prod@=doubreturn proddef __truediv__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif 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 quotdef __floordiv__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wquot=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 quotdef __mod__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wrema=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 remadef __pow__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif 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 powedef __lshift__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wlshi=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:lshi=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 lshidef __rshift__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wrshi=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 rshidef __and__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wconj=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 conjdef __or__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wdisj=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 disjdef __xor__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wexcl=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 excldef __iadd__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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.modelse:for i in range(self.H):for j in range(self.W):self.matrix[i][j]+=otherif self.mod:self.matrix[i][j]%=self.modreturn selfdef __isub__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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.modelse:for i in range(self.H):for j in range(self.W):self.matrix[i][j]-=otherif self.mod:self.matrix[i][j]%=self.modreturn selfdef __imul__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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.modelse:for i in range(self.H):for j in range(self.W):self.matrix[i][j]*=otherif self.mod:self.matrix[i][j]%=self.modreturn selfdef __imatmul__(self,other):if type(other)==Matrix:assert self.W==other.Hprod=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.modelif type(other)==int:assert self.H==self.Wif 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=selfwhile other>=2:if other&1:prod@=doubdoub@=doubother>>=1prod@=doubreturn proddef __itruediv__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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.modelse: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.modelse:self.matrix[i][j]/=otherreturn selfdef __ifloordiv__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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]//=otherreturn selfdef __imod__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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]%=otherreturn selfdef __ipow__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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 selfdef __ilshift__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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]<<=otherreturn selfdef __irshift__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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]>>=otherreturn selfdef __iand__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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]&=otherreturn selfdef __ior__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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]|=otherreturn selfdef __ixor__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor 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]^=otherreturn selfdef __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 negadef __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 posidef __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 invedef __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 absodef __getitem__(self,i):if type(i)==int:return self.matrix[i]elif type(i)==tuple:i,j=iif 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 Truereturn Falsedef __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 Truedef 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.Wtrace=sum(self.matrix[i][i] for i in range(self.H))if self.mod:trace%=self.modreturn tracedef 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=0ut=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.Wdet=1if inverse_matrix:assert self.H==self.Wim=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)if linear_equation:assert self.H==linear_equation.Hle=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.modif 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*=inveif ut.mod:det%=ut.modif 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:continuex=-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+=1breakelse:det=0tpl=()if determinant:tpl+=(det,)if inverse_matrix:if det<=0:im=Falsetpl+=(im,)if linear_equation:tpl+=(le,)if rank:tpl+=(h,)if upper_triangular:tpl+=(ut,)if len(tpl)==1:tpl=tpl[0]return tplN=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+7ST=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,uST[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])