F-筱玛的D球_牛客练习赛37

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

筱玛是一个快乐的D球主席。

在筱玛的D球上，有n个国家由n-1条边连接，每个国家都可以到达其他所有国家。

每个国家拥有一个D人手段o_i，每条道路由一个D人值w_i。

由于某些不为人知的原因，筱玛钦点D人手段只能为以下三种：

每次，筱玛会钦点一条路径。假设经过的点是v₀,v₁,...,v_n，经过的边为e₁,e₂,...,e_n，并给出两个D人参数x和y。

你需要给出一个最小的s，使得s≤ x，且 $so_{v_0}w_{e_1}o_{v_1}\dots w_{e_n}o_{v_n}y$ 最大。

注意这里的运算顺序为从左往右。

由于筱玛太快乐了，他还会修改一条边或一个点的权值。

输入描述:

第一行两个整数n,m分别表示边数和点数。
接下来n-1每行两个整数u,v代表一条边。
接下来m行，每行若干个整数，描述一个操作。
每个操作的格式如下：opt [args]
● 当opt=1时，表示询问操作，[args]为"u v x y"，表示询问的路径是u-v，x,y见题面描述。
● 当opt=2时，表示点修改，[args]为"i str"，表示修改的点为i，将这个点的运算符改为str。
● 当opt=3时，表示边修改，[args]为"i v"，表示修改的边为i，将其权值改为v。

输出描述:

对于每一个opt=1的操作，输出一行一个整数，表示你选择的s。

示例1

输入

复制

3 3
1 2
1 3
1 2 3 3135152414104478727 17505530317743439490
1 3 3 3210377389414950277 3108503171776756205
1 2 2 1294554283713988838 16470947796150090874

输出

复制

941213755966112125
1503182846650631698
1255220337180181381

说明

这组数据中，所有的节点都是，所有的边权都是0，所以相当于查询最小的的数使得其的结果最大。
第一个询问解释如下：


结果为最大值，

备注:

n,m≤ 500000
str∈{xor,or,and}
0 ≤ x,y,v ≤ 2⁶³
保证输入合法。
初始时所有的节点都为运算符，所有边权都为0。
点的编号从1开始，边的编号从1开始，且和输入顺序相同。