乌托邦有 $n$ 座城市，编号为 $1$ 到 $n$。城市之间由 $n-1$ 条双向道路连接，且保证任意两座城市之间都可以通过这些道路互相到达。由于乌托邦非常美丽，目前有 $m$ 名游客正在该国旅游，编号为 $1$ 到 $m$。初始时，第 $i$ 名游客位于城市 $a_i$。多名游客可能位于同一座城市，即对于 $i \neq j$，可能存在 $a_i = a_j$。

每位游客对乌托邦的旅游体验都有一个评价，用一个数字表示。初始时，每位游客的评价均为 $0$。为了鼓励游客再次光临，乌托邦政府希望通过在特定城市举办活动来提高游客的评价。当在城市 $c$ 举办活动时，所有当前位于该城市的游客的评价都会增加 $d$，其中 $d$ 的值取决于活动的类型。

部分游客在乌托邦逗留期间计划在城市之间旅行。尽管由于乌托邦道路高效，从一座城市前往另一座城市几乎不耗费时间，但这仍然会带来不便，从而导致游客评价降低。具体而言，一名游客如果走过了由 $k$ 条道路组成的路径，其评价将减少 $k$（游客总是选择两座城市之间的最短路径）。

乌托邦政府要求你追踪游客在全国旅行时的评价。作为该请求的一部分，你将收到 $q$ 个查询。你需要按照输入中出现的顺序执行并回答所有查询。

输入格式

第一行包含三个整数 $n, m, q$ ($2 \le n \le 200\,000, 1 \le m, q \le 200\,000$)，分别表示城市数量、游客数量和查询数量。

第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$)，其中 $a_i$ 表示第 $i$ 名游客的起始城市。

接下来的 $n-1$ 行，每行包含两个整数 $v$ 和 $w$ ($1 \le v, w \le n, v \neq w$)，表示城市 $v$ 和 $w$ 之间存在一条道路。

接下来的 $q$ 行描述了按顺序进行的查询。每行属于以下三种形式之一：

• 字母 't' 后跟三个整数 $f, g, c$ ($1 \le f \le g \le m, 1 \le c \le n$)，表示编号从 $f$ 到 $g$（包含边界）的所有游客前往城市 $c$。已经在城市 $c$ 的游客不会移动，他们的评价也不会改变。
• 字母 'e' 后跟两个整数 $c, d$ ($1 \le c \le n, 0 \le d \le 10^9$)，表示在城市 $c$ 举办了一场活动，使游客的评价增加 $d$。
• 字母 'q' 后跟一个整数 $v$ ($1 \le v \le m$)，表示询问游客 $v$ 当前的评价。

保证输入中至少包含一个 'q' 查询。

输出格式

按顺序输出所有 'q' 查询的答案，每个答案占一行。

子任务

• 子任务 1 (10 分): $n, m, q \le 200$
• 子任务 2 (15 分): $n, m, q \le 2\,000$
• 子任务 3 (25 分): $m, q \le 2\,000$
• 子任务 4 (25 分): 无 'e' 查询
• 子任务 5 (25 分): 无额外限制

样例

样例输入 1

8 4 11
1 4 8 1
6 4
6 3
3 7
6 5
5 1
1 2
1 8
q 4
t 3 4 5
t 2 2 7
q 4
e 5 10
e 1 5
q 4
t 1 1 5
t 2 2 1
q 1
q 2

样例输出 1

0
-1
9
4
-7