B. Osama-utiful Components
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Osama started his life with his teammate Tareq, so he learnt multiple bad habits from him. One of the bad habits Osama learnt is called: "The Blender of Standards". It's a technique where you merge multiple standard problems into one complicated problem. Unfortunately for you, Osama is one of the setters for this contest.

Osama will give you a graph of $$$N$$$ vertices. The graph initially has no edges. Each vertex $$$i$$$ of the graph has a value $$$A_i$$$. Osama wants you to process $$$Q$$$ queries. Each query is one of the following forms:

  • 1 u v: which means you should add an edge between vertices $$$u$$$ and $$$v$$$.
  • 2 u t: which means you should calculate the Osama-uty of the connected component $$$S$$$ that contains vertex $$$u$$$ after the first $$$t$$$ queries $$$(1 \le t \le Q)$$$ (among queries of both types).

To calculate the Osama-uty of some connected component $$$S$$$:

  • Imagine an array $$$B$$$ of length $$$N$$$, such that $$$B_i = 1$$$ if there is at least one vertex $$$u$$$ in $$$S$$$ such that $$$A_u = i$$$. Otherwise, $$$B_i=0$$$.
  • The Osama-uty of the connected component $$$S$$$ is equal to the number of subsegments $$$(L,R)$$$ $$$(1 \le L \le R \le N)$$$ such that:
    • Values $$$B_L, B_{L+1},\dots,B_{R-1}, B_R$$$ are all equal to $$$1$$$.
    • $$$L=1$$$, or $$$B_{L-1}=0$$$.
    • $$$R=N$$$, or $$$B_{R+1}=0$$$.

Osama gave this problem a second thought and found out that it was still pretty easy, so he decided to modify the way of giving the input. Please read the input section and the notes section carefully.

Note that the graph may contain self loops and multiple edges.

Input

The first line of the input contains two integers $$$N$$$ and $$$Q$$$ $$$(1 \le N \le 10^5$$$, $$$1 \le Q \le 2\cdot10^5)$$$.

The second line of the input contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le N)$$$, the values written on the vertices.

Each line of the next $$$Q$$$ lines contains four integers describing the queries.

If the current query is an add query, the input will be:

  • $$$1$$$ $$$u'$$$ $$$v'$$$ $$$x$$$. $$$(1 \le u', v' \le N, 0 \le x \lt i)$$$.

If the current query is an ask query, the input will be:

  • $$$2$$$ $$$u'$$$ $$$t'$$$ $$$x$$$. $$$(1 \le u', t' \le N, 0 \le x \lt i)$$$.
It's guaranteed that $$$x=0$$$ in the first query.

Read the notes section for more information.

Output

For each query of the second type, print a single line containing the Osama-uty of the connected component $$$S$$$ of the vertex $$$u$$$ after the first $$$t$$$ queries.

Examples
Input
3 4
1 2 3
1 3 1 0
2 3 1 1
1 3 2 1
2 3 3 1
Output
1
1
Input
3 5
1 1 3
1 3 1 0
2 3 1 1
1 3 2 1
2 3 3 1
2 3 3 4
Output
1
2
1
Note

Input description: we will assume that the current query is the $$$i_{th}$$$ query.

  • If the current query is an add query, we set $$$u_i = (u' \cdot ans_x \bmod n) + 1$$$ and $$$v_i = (v' \cdot ans_x \bmod n) + 1$$$.
  • If the current query is an ask query, we set $$$u_i = (u' \cdot ans_x \bmod n) + 1$$$ and $$$t_i = (t' \cdot ans_x \bmod i) + 1$$$.
  • $$$ans_x$$$ is the answer to the $$$x_{th}$$$ query.
  • If $$$x$$$ is equal to zero or the $$$x_{th}$$$ query is an add query then $$$ans_x = 1$$$.

In the first example:

  • In the first query, $$$u = 1$$$ and $$$v = 2$$$ $$$(x = 0$$$ means that $$$ans_x = 1)$$$.
  • In the second query, $$$u = 1$$$ and $$$t = 2$$$ (query $$$1$$$ is an add query so $$$ans_1 = 1$$$). During the second query, the connected component of $$$u$$$ contains vertices $$$\{1,2\}$$$, so there is one subsegment $$$[1, 2]$$$ that satisfies the conditions so the Osama-uty is 1.
  • In the third query, $$$u = 1$$$ and $$$v = 3$$$.
  • In the last query, $$$u = 1$$$ and $$$t = 4$$$. There is one subsegment $$$[1, 3]$$$ that satisfies the conditions so the Osama-uty is 1.

In the second example:

  • In the first query, $$$u = 1$$$ and $$$v = 2$$$.
  • In the second query, $$$u = 1$$$ and $$$t = 2$$$. There is one subsegment $$$[1, 1]$$$ that satisfies the conditions so the Osama-uty is 1.
  • In the third query, $$$u = 1$$$ and $$$v = 3$$$.
  • In the 4th query, $$$u = 1$$$ and $$$t = 4$$$. There are two subsegment $$$[1, 1]$$$ $$$[3,3]$$$ that satisfy the conditions so the Osama-uty is 2.
  • In the last query, $$$u = (3 \cdot 2 \bmod 3) + 1 = 1$$$, $$$t = (3 \cdot 2 \bmod 5) + 1 = 2$$$. During the second query, the connected component of $$$u$$$ contains vertices $$$\{1, 2\}$$$ having values $$$\{1, 1\}$$$, so there is one subsegment $$$[1, 1]$$$ that satisfies the conditions so the Osama-uty is 1.