Dominik 构思了一个由正整数组成的数组 $p_1, \dots, p_n$。我们将该数组排序后的版本记为 $q_1, \dots, q_n$。

此外，他还构思了一个允许的交换集合。如果无序对 $(X, Y)$ 是允许的交换集合中的一个元素，Dominik 就可以交换数组 $p$ 中位置 $X$ 和 $Y$ 处的数字。

Marin 给 Dominik 提出了 $Q$ 个操作，每个操作是以下类型之一：

1. 交换位置 $A$ 和 $B$ 处的数字。
2. 将无序对 $(A, B)$ 添加到允许的交换集合中。 Marin 可能会添加已经存在于允许的交换集合中的对 $(A, B)$。
3. 询问是否可以仅使用允许的交换来对数组进行排序？ 这些交换可以按任意顺序使用，且每个交换可以使用任意多次。
4. 如果仅使用允许的交换，可以将位置 $A$ 处的数字移动到位置 $B$，则称位置对 $(A, B)$ 是连通的（linked）。 我们称所有与位置 $A$ 连通的位置集合为 $A$ 的云（cloud）。 如果对于一个云中的每个位置 $j$，都可以通过一系列允许的交换使得 $p_j = q_j$ 成立，则称该云是好的（good）。

你必须回答存在多少对不同的位置 $(A, B)$ 满足以下条件：

• 位置 $A$ 和 $B$ 不连通。
• $A$ 的云不是好的，且 $B$ 的云也不是好的。
• 如果我们将无序对 $(A, B)$ 添加到允许的交换集合中，则 $A$ 的云（通过将 $A$ 的云和 $B$ 的云合并而产生）将变成好的。

请注意：无序对 $(A, B)$ 和 $(B, A)$ 被视为同一对。

输入格式

第一行包含两个整数 $N$ 和 $Q$（$1 \le N, Q \le 1\,000\,000$）。

第二行包含 $N$ 个整数 $p_1, \dots, p_n$（$1 \le p_1, \dots, p_n \le 1\,000\,000$）。

接下来的 $Q$ 行，每行包含一个以下格式的操作：

• 每行的第一个数字是操作类型 $T$，取自集合 $\{1, 2, 3, 4\}$。
• 如果操作类型 $T$ 为 1 或 2，则后面跟着两个不同的整数 $A$ 和 $B$（$1 \le A, B \le N$），表示交换 $(A, B)$。

输出格式

对于每个类型为 3 或 4 的操作，在单独的一行中输出答案。

类型 3 操作的答案为 "DA"（克罗地亚语中的“是”）或 "NE"（克罗地亚语中的“否”），不带引号；类型 4 操作的答案是一个非负整数。

数据范围

在占总分 50% 的测试用例中，满足 $N, Q \le 1\,000$。

样例

输入样例 1

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

输出样例 1

1
NE
0
DA

输入样例 2

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

输出样例 2

NE
1
DA
0

输入样例 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

输出样例 3

NE
2
NE
1
3
DA

说明

样例 1 解释：

第一个操作的答案是 1，因为位置对 $(2, 3)$ 满足所有给定的要求。

第二个操作的答案是 NE（否），因为此时允许的交换集合为空，无法将数字 2 和 3 移动到对应的位置。

在第三个操作之后，我们将对 $(2, 3)$ 添加到允许的交换集合中。

第四个操作的答案现在是 0，因为 2 和 3 已经连通；第五个操作的答案是 DA（是），因为可以通过应用允许的交换 $(2, 3)$ 来对数组进行排序。