题目内容

小塔有一棵由$n$个节点、$n-1$条无向边构成的树，每条边的权值为$w_i$。

定义树上两个点$(u,v)$的权值为，从$u$到$v$的简单路径上，全部边权的异或和，特别的，当$u$和$v$为同一个点时，权值为$0$。

小塔会提出$q$次询间，每次询问要求计算有多少个点到节点$u$的权值恰好为$k$。

树是指这样的一张图，其上的任意两个点都连通，且不存在环。

简单路径是指两个节点之间的一条路径，其不包含任何重复的节点。

也就是说，在简单路径上每个节点只能出现一次。

输入描述

第一行输入两个整数 $n,q(1≤n,q≤10^5)$，分别表示节点总数和询问次数。

此后 $n-1$行，第$i$行输入三个整数$u_i,v_i$和$w_i$(1≤u_i,v_i≤n;u_i≠v_i;0≤w<2^60)表示树

上第$i$条边连接节点$u_i$和$v_i$目边权为$w_i$。保证树联通，没有重边。

此后$q$行，每行输入两个整数$u,k(1≤u≤n,0≤k<2^{60})$代表被询问的节点和限定。

输出描述

对于每一个询问，在一行上输出一个整数，代表到节点$u$的权值恰好为$k$的节点数量。

样例1

输入

3 2
1 2 2
1 3 3
1 0
2 2

输出

1
1