C. Large Graph
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a graph of $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$, initially with no edges. You need to process $$$q$$$ queries of the following types:

  • $$$1~u~v$$$: add an undirected edge between vertices $$$u$$$ and $$$v$$$.
  • $$$2~l~r$$$: for each pair of integers $$$(x,y)$$$ such that $$$l \le x \lt y \le r$$$, add an undirected edge between vertices $$$x$$$ and $$$y$$$.

After each query, output the number of pairs of integers $$$(x,y)$$$ such that $$$1 \le x \lt y \le n$$$ and there exists a path from vertex $$$x$$$ to vertex $$$y$$$. A path from vertex $$$x$$$ to vertex $$$y$$$ is defined as a sequence of integers $$$p_1,p_2,\ldots,p_m$$$ such that $$$p_1=x$$$, $$$p_m=y$$$, and there exists an undirected edge between vertices $$$p_i$$$ and $$$p_{i+1}$$$ for all $$$1 \le i \lt m$$$.

Note that you must solve this problem in online mode. That is, you can only read the current query after outputting the answer for the previous one. Also, remember to flush the output after each query. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Input

The first line of each test contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of vertices and queries respectively.

Each of the next $$$q$$$ lines describes a query. If the line starts with the integer $$$1$$$, it is followed by two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$); if the line starts with the integer $$$2$$$, it is followed by two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le n$$$).

Output

After each query, output the number of pairs of integers $$$(x,y)$$$ such that $$$1 \le x \lt y \le n$$$ and there exists a path from vertex $$$x$$$ to vertex $$$y$$$.

Example
Input
6 3
1 1 5
2 2 4
1 1 6
Output
1
4
6