Problem Description

The phone screen lights up faintly, and the icon of the social platform “Blue Little Circle” flickers slightly. Xiao Lan, the backend architect of the platform, is staring at the traffic monitoring dashboard where the numbers keep jumping.

To improve user engagement, the product manager proposes a brand-new “circle interaction” feature. There are $N$ user nodes in the system. Initially, every user’s “activity” is $0$, and all users are strangers to each other, with no social connections.

After the feature goes online, the backend log will record $Q$ user action commands in order. The commands are as follows:

1. Add friends: user $X$ and user $Y$ follow each other, and the social circles they belong to become connected. If they are already in the same social circle, ignore this operation.
2. Post a personal update: user $X$ posts a personal update, and their activity increases by $A$.
3. Circle trending topic: user $X$ starts a trending topic. This topic has a strong spreading effect, causing all users in the same social circle as $X$ (i.e., directly or indirectly connected through friendships) to have their activity increased by $A$.
4. Data query: the operations team requests the current activity value of user $X$ for analyzing user quality.

As the number of users grows rapidly, frequent social interaction requests put huge pressure on the server’s core computing module. As Xiao Lan’s assistant, please take over the log processing unit and output all query results in order.

Input Format

The first line contains two positive integers $N$ and $Q$, representing the total number of platform users and the total number of action log entries.

The next $Q$ lines each describe one specific action command, following one of the four formats below:

• $1$ $X$ $Y$: perform “add friends”, connecting the social circles of users $X$ and $Y$.
• $2$ $X$ $A$: perform “personal update”, increasing user $X$’s activity by $A$.
• $3$ $X$ $A$: perform “circle trending topic”, increasing the activity of all users in $X$’s social circle by $A$.
• $4$ $X$: perform “data query”, querying the current activity of user $X$.

Output Format

For each “data query” command, output a single line containing an integer, representing the current activity value of the target user.

3 6
1 1 2
1 1 3
2 1 5
3 2 5
4 1
4 2

10
5

Hint

[Test Case Scale and Conventions]

For $30\%$ of the testdata, $1 \leq N \leq 1000$, $1 \leq Q \leq 1000$.

For all testdata, $1 \leq N \leq 2 \times 10^5$, $1 \leq Q \leq 2 \times 10^5$, $1 \leq X, Y \leq N$, $1 \leq A \leq 10^9$. It is guaranteed that the testdata contains at least one type $4$ “data query” command.

Translated by ChatGPT 5