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.