U287347 E.NANA与最后的旅程

在假期的最后，NANA决定尽情地在自己想去的景点中游玩。 已知NANA有$n$个想去的景点，从$1$到$n$编号，这些景点恰好有$n-1$条双向道路链接，同时恰好满足景点之间都存在唯一路径。 为了节省成本，NANA报名参加了一个旅行团。这个旅行团有$m$个旅行者，从$1$到$m$编号。 最初的时候，编号为$i$的旅行者位于$a_i$城市。每个旅行者都有一个精力值，初始时精力值为$0$。 为了刺激消费，某个景点会不定期地举办活动，当一个景点举办$a$级活动时，任何当前在这个景点的旅行者都会得到$a$精力值。 旅行者们经常会在景点之间旅游，这会消耗他们的精力值，具体地说，如果旅行者的起点终点之间隔了$k$条道路，那么旅行者会消耗$k$精力值。注意：不同的旅行者是可以呆在同一景点的。 现在，有$q$个事件顺序发生，对每一个事件，需要你进行一些操作，详情请看输入格式。

无

无

保证$2 ≤ n ≤ 200 000, 1 ≤ m, q ≤ 200 000$。