You are given $n\ (0 \le n \le 500000)$ and $q\ (1 \le q \le 600000)$ where $n$ is a number of vertexes and $q$ is a number of queries. Initially, you have a graph with no edges and 0 is written on every vertex, then you need to process $q$ queries.

You have three types of queries:

• 1 type is to add an undirected edge between $A \ and\ B$. $(1 \le A, B \le n)$
  The graph is guaranteed to be simple (without self-loops and multiple edges) even after adding edges.
• 2 type is to add number B to every number written on vertexes with are in the same component with A. $(1 \le A \le n, 1 \le B \le 1000000)$
• 3 type is to show the written number on A. $(1 \le A \le n)$

Input format

• The first line contains an integer T ($1 \le T \le 1000$) representing the number of test cases that will follow.
• The first line of each test case contains two integers n and q.
• Next q lines in test case given queries in the following format:
  Type of query if the type of query is 3 there given one integer A. Otherwise there given two integers $A \ and\ B$.

Output format

For each query of 3 type, you should print answers on a different line.