CF757G 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}...,a_{n} $ which is a permutation of $ 1,2,...,n $ . Now, Mewoth makes $ q $ queries of one of the following forms: - 1 l r v: meaning Bash should report , where $ 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!

N/A

N/A

In the sample, the actual queries are the following: - 1 1 5 4 - 1 1 3 3 - 2 3 - 2 2 - 1 1 3 3