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 100 000)~.

La segunda línea de entrada contiene ~N~ enteros ~p_1, ..., p_n~ ~(1 \le p_1, ..., p_n \le 100 000)~.

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\%~ 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)~.