Dominik has envisioned an array of positive integers $p_1,\dots ,p_n$. Let's denote the sorted version of that array as $q_1,\dots ,q_n$.

Also, he envisioned a set of allowed substitutions. If a pair $(X,Y)$ is a member of the set of allowed substitutions, Dominik can swap the numbers at positions $X$ and $Y$ in array $p$.

Marin is giving Dominik $Q$ queries, and each of them is of one of the following types:

1. Swap numbers at positions $A$ and $B$.
2. Add pair $(A,B)$ to the set of allowed substitutions. Marin can give pair $(A,B)$ that is already in the set of allowed substitutions.
3. See if it's possible to sort the array using only the allowed substitutions? The substitutions can be used in an arbitrary order, and each substitution can be made an arbitrary number of times.
4. Let's call a pair of positions $(A,B)$ linked if the number from position $A$ is possible to transfer to position $B$ using only allowed substitutions. Let's call the set of all positions linked to position $A$ the cloud of $A$. A cloud is good if it's possible for each position $j$ from the cloud to achieve $p_j=q_j$ using a series of allowed substitutions.

You must answer how many pairs of different positions $(A,B)$ exist such that it holds:

• Positions $A$ and $B$ are not linked
• Cloud of $A$ is not good and cloud of $B$ is not good
• If we add pair $(A,B)$ to the set of allowed substitutions, the cloud of $A$ (created by linking the cloud of $A$ and cloud of $B$) becomes good.

Please note: Pairs $(A,B)$ and $(B,A)$ are considered an identical pair.

Input Specification

The first line of input contains integers $N$ and $Q$ $(1\le N,Q\le 1000000)$.

The second line of input contains $N$ integers $p_1,\dots ,p_n$ $(1\le p_1,\dots ,p_n\le 1000000)$.

Each of the following $Q$ lines contains a query in the following format:

• The first number in the line is the type of query $T$ from the set $\{1,2,3,4\}$.
• If the type of query $T$ is $1$ or $2$, two different integers $A$ and $B$ follow $(1\le A,B\le N)$ that represent the substitution $(A,B)$.

Output Specification

For each query of type $3$ or $4$, output the answer in its separate line.

The answer to query of type $3$ is DA (Croatian for yes) or NE (Croatian for no), and the answer to query of type $4$ is a non-negative integer from the task.

Scoring

In test cases worth $50\mathrm{\%}$ of total points, it will hold $N,Q\le 1000$.

Sample Input 1

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

Sample Output 1

1
NE
0
DA

Explanation for Sample Output 1

The answer to the first query is $1$ because the pair of positions $(2,3)$ meets all given requirements.

The answer to the second query is NE (no) because it is impossible to transfer numbers $2$ and $3$ to the corresponding positions, because the set of allowed substitutions is empty.

After the third query, we add pair $(2,3)$ to the set of allowed substitutions.

The answer to the fourth query is now $0$ because $2$ and $3$ are already linked, and the answer to the fifth query is DA (yes), because it is possible to sort the array by applying the allowed substitution $(2,3)$.

Sample Input 2

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

Sample Output 2

NE
1
DA
0

Sample Input 3

4 10
2 1 4 3
3
4
1 1 2
3
4
2 2 3
2 1 2
4
2 3 4
3

Sample Output 3

NE
2
NE
1
3
DA