Dominik has envisioned an array of positive integers . Let's denote the sorted version of that array as .
Also, he envisioned a set of allowed substitutions. If a pair is a member of the set of allowed substitutions, Dominik can swap the numbers at positions and in array .
Marin is giving Dominik queries, and each of them is of one of the following types:
- Swap numbers at positions and .
- Add pair to the set of allowed substitutions. Marin can give pair that is already in the set of allowed substitutions.
- 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.
- Let's call a pair of positions linked if the number from position is possible to transfer to position using only allowed substitutions. Let's call the set of all positions linked to position the cloud of . A cloud is good if it's possible for each position from the cloud to achieve using a series of allowed substitutions.
You must answer how many pairs of different positions exist such that it holds:
- Positions and are not linked
- Cloud of is not good and cloud of is not good
- If we add pair to the set of allowed substitutions, the cloud of (created by linking the cloud of and cloud of ) becomes good.
Please note: Pairs and are considered an identical pair.
Input Specification
The first line of input contains integers and .
The second line of input contains integers .
Each of the following lines contains a query in the following format:
- The first number in the line is the type of query from the set .
- If the type of query is or , two different integers and follow that represent the substitution .
Output Specification
For each query of type or , output the answer in its separate line.
The answer to query of type is DA
(Croatian for yes) or NE
(Croatian for no), and the answer to query of type is a non-negative integer from the task.
Scoring
In test cases worth of total points, it will hold .
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 because the pair of positions meets all given requirements.
The answer to the second query is NE
(no) because it is impossible to transfer numbers and to the corresponding positions, because the set of allowed substitutions is empty.
After the third query, we add pair to the set of allowed substitutions.
The answer to the fourth query is now because and 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 .
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
Comments