Despite Jeff Qiu's best efforts to avoid procrastinating, he still has yet to study for tomorrow's exam! Fortunately, his classmates are very resourceful and have taken notes during class.

In order to get his classmates to share them, he has decided to befriend some of the classmates. Some classmates are more attentive in class and therefore are able to provide more notes. His class contains $N$ people, excluding him, conveniently numbered $1$ to $N$, and each classmate has $a_i$ pages of notes. For any integer $1\le x\le N$, every classmate $p$ is in $x$'s friend list if there exists a path of direct friendships from $p$ to $x$. The resourcefulness of any classmate's friend list is the sum of the $a_i$ values of their friend list.

Initially, the only friend each classmate has is themselves. Jeff will then provide you with $Q$ queries, where each query will be one of the following:

1 a b which means to make classmates a and b friends with each other. Note that friendship is bidirectional.

2 a which means to print the size of a's friend list.

3 a which means to print the resourcefulness of classmate a's friend list.

Constraints

For all subtasks:

$2\le N,Q\le {10}^6$

$0\le a_i\le {10}^6$

Subtask 1 [15%]

$2\le N,Q\le 1000$

Subtask 2 [85%]

No additional constraints.

Input Specification

The first line will consist of the two integers $N$ and $Q$.

The next line will have $N$ integers, where the $i^{\text{th}}$ integer denotes $a_i$.

The next $Q$ lines will consist of one query per line in the format described above.

Output Specification

For each query of type 2 or 3, print out the answer in a new line.

Sample Input

4 5
1 2 1 0
1 1 2
1 1 3
2 1
2 3
3 3

Sample Output

3
3
4

Explanation

1 is friends with 2 and 3, so both 1 and 3 have three friends. Therefore, the resourcefulness of 3 is $1+2+1=4$.