P9410 [STA - R2] Airport Construction.

Chile is building airports.

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?

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

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

**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