Bandits

A kingdom has $N$ villages and $N-1$ bidirectional roads, so any pair of villages is connected by a path of one or more roads. The $i$-th road connects villages $A_i$ and $B_i$ and has length $C_i$.

Merchants have been attacked by bandits more and more often, so the king asked his advisor to solve the problem by hiring loyal groups of thugs to act as security agencies. Each security contract guarantees security of all roads within radius $R_j$ of the village $X_j$ where the group's headquarters is. A road is protected by a contract if it is part of a path of length at most $R_j$ from $X_j$ to some other village. A road can be protected by several contracts, and it is then more secure.

Process queries about new contracts and answer queries about the security of individual roads, that is, the number of contracts currently protecting that road.

The first line contains the number of villages $N$. The next $N-1$ lines each contain three space-separated integers $A_i$, $B_i$, and $C_i$, describing a road of length $C_i$ between villages $A_i$ and $B_i$.

The next line contains the number of queries $Q$. The following $Q$ lines describe the queries. A query that adds a new security contract starts with the character + and is followed by the headquarters village $X_j$ and the radius $R_j$. A query about the security of a road starts with the character ? and is followed by the number $Y_j$ of that road. Roads are numbered from $1$ to $N-1$ in the order they are given in the input.

For every query of type ?, output one line with the current number of contracts protecting road $Y_j$, in the order the queries are processed.

• $1 \leq N, Q \leq 10^5$
• $0 \leq C_i, R_j \leq 10^9$