Whoa! You did a great job helping Team Rocket who managed to capture all the Pokemons sent by Bash. Meowth, part of Team Rocket, having already mastered the human language, now wants to become a master in programming as well. He agrees to free the Pokemons if Bash can answer his questions.
Initially, Meowth gives Bash a weighted tree containing \(n\) nodes and a sequence \(a_1, a_2, \ldots, a_n\) which is a permutation of \(1, 2, \ldots, n\). Now, Mewoth makes \(q\) queries of one of the following forms:
The first line contains two integers \(n\) and \(q\) \((1 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5)\) — the number of nodes in the tree and the number of queries, respectively.
The next line contains \(n\) spaceseparated integers — the sequence \(a_1, a_2, \ldots, a_n\) which is a permutation of \(1, 2, \ldots, n\).
Each of the next \(n  1\) lines contain three spaceseparated integers \(u\), \(v\), and \(w\) denoting that there exists an undirected edge between node \(u\) and node \(v\) of weight \(w\), \((1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^6)\). It is guaranteed that the given graph is a tree.
Each query consists of one line. The first integer is \(t\), indicating the type of the query. Some integers follow:
For each query of type \(1\), output a single integer in a separate line, denoting the answer to the query.
Subtask #  Score  Constraints 

1  8  \(n, q \leq 2000\) 
2  15  \(l = 1\) \(r = n\) 
3  20  \(n, q \leq 50000\) All queries are of type \(1\). 
4  21  All queries are of type \(1\). 
5  36  No additional constraints 
Sample Input 1  Sample Output 1 
5 5

23

Subtask  Score 

1  8 
2  15 
3  20 
4  21 
5  36 
6  0 
7  0 