### Can Bash Save the Day?

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:

• $$1$$ $$l$$ $$r$$ $$v$$: meaning Bash should report $$\displaystyle \sum_{i = l}^{r}{\textrm{dist}(a_i, v)}$$, where $$\textrm{dist}(a, b)$$ is the length of the shortest path from node $$a$$ to node $$b$$ in the given tree.
• $$2$$ $$x$$: meaning Bash should swap $$a_x$$ and $$a_{x + 1}$$ in the given sequence. This new sequence is used for later queries.
Help Bash to answer the questions!

### Input format

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$$ space-separated 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 space-separated 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:

• t = 1: Three integers $$l$$, $$r$$ and $$v$$ $$(1 \leq l \leq r \leq n, 1 \leq v \leq n)$$.
• t = 2: A single integer $$x$$ $$(1 \leq x \leq n - 1)$$.

### Output format

For each query of type $$1$$, output a single integer in a separate line, denoting the answer to the query.

### Limits

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$$.

### Samples

 Sample Input 1 Sample Output 1 5 5 4 5 1 3 2 4 2 4 1 3 9 4 1 4 4 5 2 1 1 5 4 1 1 3 3 2 3 2 2 1 1 3 3 233728

### Compile Errors

Time Limit: 5 Seconds
Memory Limit: 1024MB
No. of ACs: 5