The squirrel nation is building a road network to transport acorns between their cities. They are scattered among ~N~ different cities, the ~k^{th}~ of which currently has ~z_k~ acorns. Initially, in the original timeline, the cities are disconnected from each other.

Over time, ~Q~ different squirrels will perform one of three types of actions:

1. A squirrel will build more roads to connect some of their cities. Of course, the squirrels, having recently discovered time travel, will sometimes go back in time and build the roads a different way. Specifically, the ~i^{th}~ squirrel will decide to time travel to the same timeline as another squirrel ~j_i~, where ~j_i < i~, and build a new road in that timeline between cities ~a_i~ and ~b_i~.
2. A squirrel will time travel back to the same timeline as another squirrel ~j_i~, where ~j_i < i~, start in a specific city ~a_i~, and eat all the acorns in the city with the largest number of acorns that is reachable from city ~a_i~ (including city ~a_i~). If there are multiple cities with the largest number of acorns, then the squirrel will pick one arbitrarily.
3. A squirrel will time travel back to the same timeline as another squirrel ~j_i~, where ~j_i < i~, start in a specific city ~a_i~, and add ~c_i~ acorns to each city reachable from city ~a_i~ (including city ~a_i~).

Note that each squirrel creates a new timeline, so future actions cannot affect past actions. When a squirrel ~i~ time travels to the same timeline as another squirrel ~j~, all actions performed by squirrel ~j~ have already occurred.

You are asked to record the number of acorns eaten after each type ~2~ action. Can you help the squirrel nation keep track of all the acorns eaten?

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N, Q \le 100\,000~
~1 \le z_k \le 10^9~ for all ~1 \le k \le N~
~0 \le j_i < i~ for all ~1 \le i \le Q~
~1 \le a_i, b_i \le N~ for all ~1 \le i \le Q~
~1 \le c_i \le 10^9~ for all ~1 \le i \le Q~

Subtask 1 [13%]

~1 \le N, Q \le 2\,000~

Subtask 2 [14%]

~j_i = i-1~ for all ~1 \le i \le Q~
There will be no actions of type ~3~.

Subtask 3 [20%]

~j_i = i-1~ for all ~1 \le i \le Q~

Subtask 4 [20%]

There will be no actions of type ~3~.

Subtask 5 [33%]

No additional constraints.

Input Specification

The first line of input contains ~2~ integers, ~N~ and ~Q~, representing the number of cities in the squirrel nation, and the number of time travelling squirrels.

The next line contains ~N~ integers, which describe the initial number of the acorns in each city. The ~k^{th}~ integer on this line is ~z_k~, indicating that the ~k^{th}~ city initially has ~z_k~ acorns.

The next ~Q~ lines describe the squirrels' actions. The input will be given in encrypted format. Instead of each variable ~x~ being given, a variable ~x'~ will be given instead. To decrypt the input, you should take the bitwise ~xor~ of the last value that was outputted, and ~x'~, that is ~x = x' \oplus lastAns~. If no previous value was outputted, then ~lastAns = 0~. Note that the first integer on each line providing the type of action is not encrypted.

The ~i^{th}~ of these lines will be in one of three forms.

• 1 j_i' a_i' b_i' indicating that squirrel ~i~ performs a type ~1~ action by time traveling back to the same timeline as squirrel ~j_i~, creating a new timeline, and building a new road between cities ~a_i~ and ~b_i~.
• 2 j_i' a_i' indicating that squirrel ~i~ performs a type ~2~ action by time traveling back to the same timeline as squirrel ~j_i~, creating a new timeline, and eating all acorns from the city with the largest number of acorns that is reachable from city ~a_i~ (including city ~a_i~). If there are multiple cities with the largest number of acorns, the squirrel will pick one arbitrarily.
• 3 j_i' a_i' c_i' indicating that squirrel ~i~ performs a type ~3~ action by time traveling back to the same timeline as squirrel ~j_i~, creating a new timeline, and adding ~c_i~ acorns to each city reachable from city ~a_i~ (including city ~a_i~).

For all squirrels, if ~j_i = 0~, then squirrel ~i~ has time travelled back to the original timeline, where all cities are disconnected.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

After each type ~2~ action, output the number of acorns eaten by that squirrel. If no acorns were eaten by that squirrel, output ~0~ instead.

Sample Input 1

2 3
1 2
2 0 2
1 3 3 0
2 0 0

Sample Input 1 Decrypted

For your convenience, below is a version of Sample Input 1 that is NOT encrypted. Note that all of the actual test files will be encrypted in the format specified above.

2 3
1 2
2 0 2
1 1 1 2
2 2 2

Sample Output 1

2
1

Sample Explanation 1

Squirrel ~1~ time travels to the original timeline, starts in city ~2~, and eats ~2~ acorns from city ~2~.
Squirrel ~2~ time travels to squirrel ~1~'s timeline and builds a road between cities ~1~ and ~2~.
Squirrel ~3~ time travels to squirrel ~2~'s timeline, starts in city ~2~, and eats ~1~ acorn from city ~1~. Note that they cannot eat any acorns from city ~2~ since they were already eaten by squirrel ~1~, and this timeline was created from squirrel ~2~'s timeline, which in turn was created from squirrel ~1~'s timeline.

Sample Input 2

3 7
1 2 1
1 0 1 2
2 1 2
3 2 1 0
1 1 0 1
2 6 0
2 3 1
2 4 0

Sample Input 2 Decrypted

For your convenience, below is a version of Sample Input 2 that is NOT encrypted. Note that all of the actual test files will be encrypted in the format specified above.

3 7
1 2 1
1 0 1 2
2 1 2
3 0 3 2
1 3 2 3
2 4 2
2 0 2
2 6 2

Sample Output 2

2
3
2
0

Sample Explanation 2

Squirrel ~1~ time travels to the original timeline and builds a road between cities ~1~ and ~2~.
Squirrel ~2~ time travels to squirrel ~1~'s timeline, starts in city ~1~, and eats ~2~ acorns from city ~2~.
Squirrel ~3~ time travels to the original timeline and adds ~2~ acorns to all cities reachable from city ~3~ (which is just city ~3~).
Squirrel ~4~ time travels to squirrel ~3~'s timeline and builds a road between cities ~2~ and ~3~.
Squirrel ~5~ time travels to squirrel ~4~'s timeline, starts in city ~2~, and eats ~3~ the acorns from city ~3~.
Squirrel ~6~ time travels to the original timeline, starts in city ~2~, and eats ~2~ acorns from city ~2~.
Squirrel ~7~ time travels to squirrel ~6~'s timeline, starts in city ~2~, and does not eat any acorns, as they are no cities reachable from city ~2~ that have acorns in this timeline.