$\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 有一棵 $n$ 个点的树，每条边都带权。
她会问你 $m$ 个问题，每次给你一个正整数 $q$，求最大权值不大于 $q$ 的简单路径数量。
需要注意的是，对于一个点对 $(u,v)$ 只记一次，单独一个点不算路径。
输入格式
第一行两个正整数 $n,m$，意义如题目描述。
接下来 $n-1$ 行，每行三个正整数 $u,v,w$，表示 $u,v$ 之间有一条权为 $w$ 的无向边。
最后一行 $m$ 个正整数，表示询问。
输出格式
对于每个询问，输出一行一个整数表示答案。
数据范围
$1\le n,m \le 2\times10^5$
$1\le u,v \le n$
$1\le w,q \le 2\times 10^5$
您拥有一个整数 $k$，以及一个由字符 a 与字符 * 组成的长度为 $n$ 的字符串。
在这其中，每一个星号都必须替换成 $0\sim k$ 个字符 b，在所有的星号替换完成后，得到的字符串我们称为 BA-String。
请您求出给定字符串所转化出的字典序第 $x$ 小的 BA-String。
本题采用多组数据，数据组数为 $T$。
$1\leqslant T,n,k\leqslant2000$
$1\leqslant x\leqslant10^{18}$
给出$n$个数，定义一个数列是好的当且仅当$a_{i}\ne a_{i-1}$
你可以通过调整数的大小来把一个数列变成好的，将一个位置$i$上的数$+1$需要的花费是$b_i$，问：最小的花费
有$q$组询问，保证$\sum_{i=1}^q n_i\le3\times10^5$，答案在$long\ long$范围内
交互题，系统有两个整数 $(a,b)$，你每次可以询问一组整数 $(c,d)$，系统会回答：
$1$ 如果 $a\oplus c>b\oplus d$
$0$ 如果 $a\oplus c=b\oplus d$
$-1$ 如果 $a\oplus c<b\oplus d$
其中操作 $a\oplus b$ 表示 $a$ 和 $b$ 按位异或
你需要在询问不超过 $62$ 次之后输出 $(a,b)$ 的值，保证 $0\le a, b < 2^{30}$。
输入格式：
请见“交互”
输出格式：
输出 ! a b 以输出答案，不要忘了在输出答案后清除缓冲区
输出 ? c d 以询问，$c$ 和 $d$ 都应该是小于 $2^{30}$ 的非负整数，不要忘了在输出每一次询问后清除缓冲区
你可以用下列操作来清除缓冲区：
C++：fflush(stdout)
Java：System.out.flush()
Python：stdout.flush()
Pascal：fflush(stdout)
对于其它语言请参考文档
求
$$\sum_{x=0}^{m-1} [\ \gcd(a, m) = \gcd(a + x, m)\ ]$$
多组测试数据, $T \leq 50,\ 1 \leq a < m \leq 10^{10}$
在一个 $[1,m]$ 的数轴上有 n 条线段，第 i 条覆盖了 $[l_i,r_i]$ 的区间，权值为 $w_i$ ，你的任务是从这些线段中选出若干条首尾相接线段覆盖整个数轴，使得这些线段权值极差最小化，输出这个极差
首尾相接的定义是，假设你有机会从同一条线段覆盖的任意两个点中移动，如果你可以从位置 1 出发，经过一些线段到达位置 m ，就称为这些线段首尾相接
一个人在一张有向图的 $1$ 号结点，他要去到 $n$ 结点。每条边 $(a_i,b_i)$ 有边权 $s_i$，表示走过这条边需要花 $s_i$ 元。这个人一开始有 $p$ 元，到了一个点 $u$，他可以进行若干次演出，每次演出收获 $w_u$ 元。问到达 $n$ 的最小演出次数，若无解输出 -1。