#3 「 时间旅行传送门 」

统计

R君开发出了时间旅行传送门。

R君将$n-1$个时间旅行传送门部署到了$n$个星球。如果只走这$n-1$个时间旅行传送门,R君发现这$n$个星球是两两可达的(也就是一棵树)。

但是时间旅行传送门除了传送的功能外还额外有着时间旅行的功能,比如说($X_i$, $Y_i$, $T_i$)这个传送门,通过这个传送门从$X_i$到$Y_i$时间就会增加$T_i$($T_i$可正可负),通过这个传送门从$Y_i$到$X_i$时间就会减少$T_i$($T_i$可正可负)。

现在R君关心的问题是从$x$星球能不能通往$y$星球,同时时间恰好增加$z$($z$可正可负)。

由于现在是一个树形的结构,所以实际上两点之间的路径唯一,所以R君很快写了个程序计算出了这个结果。

但是随着R君继续部署传送门,这个问题变得复杂了起来,所以请你来帮帮忙。

输入格式

第一行两个整数$n$,$q$。

接下来$n-1$行,每行三个整数$x_i, y_i, T_i$。

接下来$q$行,每行四个正整数$k$, $x$, $y$, $t$。

若$k=0$,表示部署一个新的传送门$(x,y,t)$。

若$k=1$,表示询问是否可以从$x$到$y$,使得时间恰好增加$t$。

输出格式

对于每个k=1的询问,输出一行一个答案yes/no。(小写)

样例数据

input

5 5
1 2 1
2 3 1
3 4 1
4 5 2
1 1 5 5
1 2 5 5
1 1 5 10
0 2 4 -3
1 1 5 10

output

yes
no
no
yes

样例解释

添加$(2,4,-3)$后可以从$1->2->3->4->2->3->4->5$,时间变化是$1+1+1-(-3)+1+1+2=10$。

数据规模与约定

$1 \le n \le 10^5$, $1 \le q \le 4 \times 10^5$ , $|T_i| \le 10^9$。

数据保证添加过程不会产生自环。

时间限制:1s

空间限制:512MB

Author: zrt

本题为【清华集训2015】遥远的星系弱化版。