Dominik ha imaginado una serie de números enteros positivos $p_1,...,p_n$. Denotemos la versión ordenada de ese arreglo como $q_1,...,q_n$.

Además, imaginó un conjunto de sustituciones permitidas. Si un par $(X,Y)$ es un miembro del conjunto sustituciones permitidas, Dominik puede intercambiar los números en las posiciones de $X$ y $Y$ en el arreglo $p$.

Marin le está dando a Dominik Q consultas, y cada una de ellas es de uno de los siguientes tipos:

1- Intercambiar números en posiciones $A$ y $B$.

2- Agregar el par $(A,B)$ al conjunto de sustituciones permitidas. Marin puede dar un par que ya esté en el conjunto

3- ¿Diga si es posible ordenar la matriz usando solo las sustituciones permitidas? Las sustituciones se pueden utilizar en un orden arbitrario, y cada sustitución se puede realizado un número arbitrario de veces.

4- Llamemos a un par de posiciones $(A,B)$ vinculadas si el número de la posición $A$ es posible transferir a la posición $B$ utilizando solo las subtitulaciones permitidas. Llamemos al conjunto de todas las posiciones vinculadas para colocar $A$ la nube de $A$. Una nube es buena si es posible para cada posición $j$ de la nube lograr que $p_j=q_j$ utilizando una serie de sustituciones permitidas.

Debes responder cuántos pares diferentes las posiciones $(A,B)$ existen de tal manera que contiene:

• Las posiciones $A$ y $B$ no están vinculadas una.

• La nube de $A$ no es buena y la nube de $B$ no es buena

• Si agregamos el par $(A,B)$ al conjunto de sustituciones permitidas, la nube de $A$ (uniéndola con la de $B$) se vuelve buena.

Tenga en cuenta: Los pares $(A,B)$ y $(B,A)$ se consideran un par idéntico.

Entrada

La primera línea de entrada contiene dos enteros $N$ y $Q(1\le N,Q\le 100000)$.

La segunda línea de entrada contiene $N$ enteros $p_1,...,p_n$ $(1\le p_1,...,p_n\le 100000)$.

Cada una de las siguientes líneas $Q$ contiene una consulta en el siguiente formato:

• El primer número de la línea es el tipo de consulta $T$ del conjunto $1,2,3,4$.

• $A$ y $B$ siguen $(1\le A,B\le N)$, si el tipo de consulta $T$ es $1$ o $2$, dos números enteros diferentes Representan la sustitución $(A,B)$.

Salida

Para cada consulta de tipo $3$ o $4$, envíe la respuesta en su línea separada. La respuesta a la consulta de tipo $3$ es $"DA"$ (sí) o $"NE"$ (no), sin las comillas, y la respuesta a la consulta de tipo $4$ es un número entero no negativo de la tarea.

Puntuación

En casos de prueba que valen $50\mathrm{\%}$ del total de puntos, tendrá $N,Q\le 1000$.

Ejemplos

Ejemplo de entrada 1

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

Ejemplo de salida 1

1
NE
0
DA

Ejemplo de entrada 2

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

Ejemplo de salida 2

NE
1
DA
0

Ejemplo de entrada 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

Ejemplo de salida 3

NE
2
NE
1
3
DA

Aclaración del primer caso de prueba:

La respuesta a la primera consulta es $1$ porque el par de posiciones $(2,3)$ cumple con todos los requisitos dados. La respuesta a la segunda pregunta es $NE$ (no) porque es imposible transferir los números $2$ y $3$ a las posiciones correspondientes, porque el conjunto de sustituciones permitidas está vacío.

Después de la tercera consulta, agregamos el par $(2,3)$ al conjunto de sustituciones permitidas. La respuesta a la cuarta consulta ahora es $0$ porque $2$ y $3$ ya están vinculados, y la respuesta a la quinta La consulta es $DA$ (sí), porque es posible ordenar el arreglo aplicando la sustitución permitida $(2,3)$.