Background

Chile is building airports.

Problem Description

There are $n$ cities in a line, and at the beginning they are not connected to each other.
Each city initially has no population.
There will be a total of $m$ operations / queries as follows:

1. 1 x y Open a bidirectional flight between city $x$ and city $y$.
2. 2 l r a The population of every city in $[l, r]$ increases by $a$.
3. 3 x If everyone who can reach city $x$ comes to city $x$, how many people will city $x$ have?

Input Format

The first line contains two integers $n, m$.
The next $m$ lines each contain one operation.

Output Format

For every operation of type $3$, output the answer.

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

2
4

Hint

This problem uses bundled testdata.

• Easy (5 pts): $1 \le n, m \le 2 \times 10^5$, and there is no operation $1$.
• Normal (10 pts): $1 \le n, m \le 1000$.
• Hard (20 pts): $1 \le n, m \le 10^5$, and after any operation $3$ there is no operation $2$.
• Lunatic (30 pts): $1 \le n, m \le 5 \times 10^4$.
• Overdrive (35 pts): $1 \le n, m \le 2 \times 10^5$.

For $100\%$ of the data, $1 \le n, m \le 2 \times 10^5$, $0 \le a \le 10^9$. It is guaranteed that the answer fits in the range of a 64-bit signed integer.

For some reasons, there are many partial scores.

Translated by ChatGPT 5