题目背景

智利在修机场。

题目描述

有 $n$ 个城市排成一列，最开始是互不连通的。
每个城市初始都没有人口。
会出现以下操作 / 查询共 $m$ 个：

1. 1 x y 开通城市 $x$ 和城市 $y$ 之间的双向航班。
2. 2 l r a 城市 $[l, r]$ 的人口数都 $+a$。
3. 3 x 如果所有能够到达城市 $x$ 的人都来到城市 $x$，城市 $x$ 有多少人。

输入格式

第一行两个数 $n, m$。
接下来 $m$ 行，每行一个操作。

输出格式

对于所有的操作 $3$ ，输出答案。

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

2
4

提示

本题捆绑测试。

• Easy（5pts）：$1 \le n, m \le 2 \times 10^5$，且不存在操作 $1$。
• Normal（10pts）：$1 \le n, m \le 1000$。
• Hard（20pts）：$1 \le n, m \le 10^5$，且操作 $3$ 之后不存在操作 $2$。
• Lunatic（30pts）：$1 \le n, m \le 5 \times 10^4$。
• Overdrive（35pts）：$1 \le n, m \le 2 \times 10^5$。

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$，$0 \le a \le 10^9$。保证答案在 64 位有符号整形表示的范围内。

出于某些原因，给了较多的部分分。