有一个王国，包含 $N$ 个村庄和 $N - 1$ 条双向道路，使得公民可以在任意两个村庄之间通过一条由一条或多条道路组成的路径往来。第 $i$ 条道路连接村庄 $A_i$ 和 $B_i$，长度为 $C_i$。

国王注意到越来越多的投诉称有强盗袭击在王国道路上旅行的商人。他指派顾问通过雇佣忠诚的暴徒团体作为安保机构来解决这个问题。每个安保合同保证以总部村庄 $X_j$ 为中心，半径为 $R_j$ 范围内的所有道路的安全。如果一条道路是某条从 $X_j$ 出发到其他村庄、长度不超过 $R_j$ 的路径的一部分，则该道路受到合同保护。有些道路可能受到多个合同的保护，因此更加安全。

编写一个程序，处理关于新合同的查询，并回答关于单条道路安全性的查询，即当前保护该道路的合同数量。

输入格式

第一行包含村庄数量 $N$。接下来的 $N - 1$ 行描述连接这些村庄的道路。每条道路的描述由空格分隔的整数 $A_i, B_i$ 和 $C_i$ 组成，表示连接村庄 $A_i$ 和 $B_i$ 的长度为 $C_i$ 的道路。村庄编号为 $1$ 到 $N$。

下一行包含查询数量 $Q$。接下来的 $Q$ 行描述查询。 表示新安保合同的查询以字符 '+' 开头，后跟总部村庄 $X_j$ 和安保半径 $R_j$。 关于某条道路安全性的查询以字符 '?' 开头，后跟该道路的编号 $Y_j$。道路按照输入中给出的顺序编号为 $1$ 到 $N - 1$。

数据范围

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

输出格式

按照给定的顺序处理查询，对于每个 '?' 类型的查询，输出一行，包含当前保护道路 $Y_j$ 的合同数量。

样例

输入 1

7
1 2 4
4 2 7
5 1 3
3 6 4
1 6 9
2 7 1
7
+ 2 6
? 3
? 1
+ 6 14
? 1
? 2
? 3

输出 1

0
1
2
0
1