给你一棵n个节点的树,每个节点i有一个可重集A_i。你需要维护一个数据结构(可以参考标题),来维护以下几种操作:
1 x y z
表示给x,y路径上所有的点的可重集都加一个数z。2 x y z
表示求出x,y路径上所有的点的可重集的并集的第z大的数。3 x y z
表示求出x,y路径上所有的点的可重集的并集中有几个数比z小。第一行两个数n,m,表示节点数和操作数。
接下来n-1行,每行两个树表示一条树边。
接下来n行中第i行先有一个数x_i表示初始i号节点的可重集的大小,之后有x_i个数表示i号节点的可重集的各个元素(保证从小到大给出)
接下来m行,每行四个数op,x,y,z,表示一次操作
对于所有的询问操作,分行输出答案。
10 10 1 2 2 3 3 4 2 5 5 6 6 7 7 8 2 9 1 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 3 4 10 3 1 4 9 2 3 4 10 3 1 6 10 9 2 6 10 9 1 8 10 998244353 1 8 4 123456789 1 4 10 987654321 2 8 10 20 3 1 10 56
2 5 9 987654321 4
10 10 2 1 3 1 4 1 5 1 6 1 7 1 8 7 9 2 10 2 3 1156 3479 6691 2 945 8407 1 6605 4 2077 2272 6251 9786 4 488 2007 2497 7865 2 1101 7389 2 3717 5896 1 3876 3 2801 9441 9926 3 6001 9081 9976 3 8 9 4704 2 8 5 1 2 7 5 3 2 4 2 5 1 7 2 7302 3 10 4 8825 1 5 9 1441 2 2 10 4 1 1 3 1549 3 1 9 4705
6 488 2007 3479 11 7302 8
对于33\%的数据,1\leq n,m\leq10。
对于100\%的数据,n\leq10^4,m\leq5\times10^4,\sum\limits_{i=1}^nx_i\leq10^5
保证每个可重集的元素在[1,10^9]范围之内。