题目背景

想象一朵未来的玫瑰 - 贰零Levent / 星尘

题目描述

给定一棵有 $n$ 个节点的树，节点编号为 $1 \sim n$，根节点为 $1$，每个点上有一个符号（加减号其中之一）$\mathrm{op}_i$ 和一个数 $a_i$，每条边都有一个区间 $[l, r]$。

你现在在节点 $1$，手中有一个数 $x$，你需要进行以下流程：

• 假设你在节点 $u$，你将手中的数 $x$ 变为 $x \mathbin{\mathrm{op}_u} a_u$。
• 你可以选择在点 $u$ 结束流程，也可以选择一个子节点 $v$，假设连接 $u, v$ 的边的区间为 $[l, r]$，需要满足 $l \le x \le r$，然后走到 $v$ 并重复这两个步骤。

给定 $q$ 次询问，每次给出你手上的数的初值 $x$，你需要回答你能在上面结束流程的节点个数。

输入格式

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

接下来 $n - 1$ 行，第 $i$ 行三个整数 $p_{i+1}, l_{i+1}, r_{i+1}$ 表示 $i + 1$ 的父亲为 $p_{i+1}$，连接它们的边的区间为 $[l_{i + 1}, r_{i + 1}]$。

接下来 $n$ 行，第 $i$ 行一个字符 $\mathrm{op}_i$ 与一个整数 $a_i$。

接下来 $q$ 行，每行一个整数 $x$。

输出格式

输出 $q$ 行，每行一个整数，表示答案。

5 5
1 4 7
1 5 8
2 3 4
2 1 6
+ 3
- 2
+ 1
- 4
+ 7
1
2
3
4
5

3
5
5
4
2

提示

【样例解释 #1】

当 $x=1$ 时，能在节点 $1,2,5$ 上结束流程。

当 $x=2$ 时，能在节点 $1,2,3,4,5$ 上结束流程。

当 $x=3$ 时，能在节点 $1,2,3,4,5$ 上结束流程。

当 $x=4$ 时，能在节点 $1,2,3,5$ 上结束流程。

当 $x=5$ 时，能在节点 $1,3$ 上结束流程。

【样例 #2】

见选手目录下的 $\textbf{\textit{calc/calc2.in}}$ 与 $\textbf{\textit{calc/calc2.ans}}$。

该样例满足测试点 $1\sim 3$ 的约束条件。

【样例 #3】

见选手目录下的 $\textbf{\textit{calc/calc3.in}}$ 与 $\textbf{\textit{calc/calc3.ans}}$。

该样例满足测试点 $4\sim 6$ 的约束条件。

【样例 #4】

见选手目录下的 $\textbf{\textit{calc/calc4.in}}$ 与 $\textbf{\textit{calc/calc4.ans}}$。

该样例满足测试点 $7\sim 9$ 的约束条件。

【样例 #5】

见选手目录下的 $\textbf{\textit{calc/calc5.in}}$ 与 $\textbf{\textit{calc/calc5.ans}}$。

该样例满足测试点 $10$ 的约束条件。

【样例 #6】

见选手目录下的 $\textbf{\textit{calc/calc6.in}}$ 与 $\textbf{\textit{calc/calc6.ans}}$。

该样例满足测试点 $11\sim 20$ 的约束条件。

【数据范围】

本题共 $20$ 个测试点，每个 $5$ 分。

对于所有测试数据，保证：

• $1 \le n \le 5 \times 10^5$；
• $1 \le q \le 10^6$；
• $-10^{18} \le l_i \le r_i \le 10^{18}$；
• $-10^{18} \le x, a_i \le 10^{18}$；
• $\mathrm{op}_i\in\{+,-\}$；
• $1 \le p_i < i$。

::cute-table{tuack}

测试点编号	$n \le$	$q \le$	特殊性质
$1\sim 3$	$10^3$		无
$4\sim 6$	$5\times 10^5$	$10^6$	A
$7\sim 9$	^		B
$10$			C
$11\sim 20$			无

• 特殊性质 A：对于所有 $2 \le i \le n$ 均有 $p_i=i-1$。
• 特殊性质 B：对于所有 $2 \le i \le n$ 均有 $l_i=-10^3$、$r_i=10^3$，并且对于所有 $1 \le i \le n$ 均有 $-10^3\le a_i \le 10^3$，并且 $-10^3\le x \le 10^3$。
• 特殊性质 C：对于所有 $1 \le i \le n$ 均有 $a_i=0$。