Background

Imagine a Future Rose - 20 Levent / Xingchen.

Problem Description

You are given a tree with $n$ nodes, numbered from $1$ to $n$. The root is node $1$. Each node has an operator (either plus or minus) $\mathrm{op}_i$ and a number $a_i$. Each edge has an interval $[l, r]$.

You start at node $1$ with a number $x$ in your hand, and you need to perform the following process:

• Suppose you are at node $u$. You change the number in your hand from $x$ to $x \mathbin{\mathrm{op}_u} a_u$.
• You may choose to end the process at node $u$, or you may choose a child node $v$. Suppose the interval on the edge connecting $u$ and $v$ is $[l, r]$. You must satisfy $l \le x \le r$, then move to $v$ and repeat these two steps.

You are given $q$ queries. In each query, you are given the initial value of $x$ in your hand. You need to answer how many nodes you can end the process at.

Input Format

The first line contains two integers $n, q$.

The next $n - 1$ lines: in the $i$-th line there are three integers $p_{i+1}, l_{i+1}, r_{i+1}$, meaning the parent of node $i + 1$ is $p_{i+1}$, and the interval on the edge connecting them is $[l_{i + 1}, r_{i + 1}]$.

The next $n$ lines: in the $i$-th line there is a character $\mathrm{op}_i$ and an integer $a_i$.

The next $q$ lines: each line contains an integer $x$.

Output Format

Output $q$ lines, each line contains one integer, representing the answer.

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

Hint

Sample Explanation #1

When $x = 1$, you can end the process at nodes $1, 2, 5$.

When $x = 2$, you can end the process at nodes $1, 2, 3, 4, 5$.

When $x = 3$, you can end the process at nodes $1, 2, 3, 4, 5$.

When $x = 4$, you can end the process at nodes $1, 2, 3, 5$.

When $x = 5$, you can end the process at nodes $1, 3$.

Sample #2

See $\textbf{\textit{calc/calc2.in}}$ and $\textbf{\textit{calc/calc2.ans}}$ in the contestant directory.

This sample satisfies the constraints of test points $1 \sim 3$.

Sample #3

See $\textbf{\textit{calc/calc3.in}}$ and $\textbf{\textit{calc/calc3.ans}}$ in the contestant directory.

This sample satisfies the constraints of test points $4 \sim 6$.

Sample #4

See $\textbf{\textit{calc/calc4.in}}$ and $\textbf{\textit{calc/calc4.ans}}$ in the contestant directory.

This sample satisfies the constraints of test points $7 \sim 9$.

Sample #5

See $\textbf{\textit{calc/calc5.in}}$ and $\textbf{\textit{calc/calc5.ans}}$ in the contestant directory.

This sample satisfies the constraints of test point $10$.

Sample #6

See $\textbf{\textit{calc/calc6.in}}$ and $\textbf{\textit{calc/calc6.ans}}$ in the contestant directory.

This sample satisfies the constraints of test points $11 \sim 20$.

Constraints

There are $20$ test points in this problem, each worth $5$ points.

For all testdata, it is guaranteed that:

• $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}

• Special Property A: For all $2 \le i \le n$, $p_i = i - 1$.
• Special Property B: For all $2 \le i \le n$, $l_i = -10^3$ and $r_i = 10^3$. Also, for all $1 \le i \le n$, $-10^3 \le a_i \le 10^3$, and $-10^3 \le x \le 10^3$.
• Special Property C: For all $1 \le i \le n$, $a_i = 0$.

Translated by ChatGPT 5