Definimos una doble permutación de orden ~n~ como una cadena que consta de los primeros ~2n~ números naturales: ~(a_1, a_2, ..., a_n, a_{n + 1}, a_{n + 2}, ..., a_{2n})~. Esta doble permutación es tres veces mayor si las siguientes tres propiedades son verdaderas:

1. La secuencia de los primeros ~n~ elementos está aumentando: ~a_1 < a_2 <... <a_{2n}~

2. La secuencia de los últimos ~n~ elementos es ascendente: ~a_{n + 1} < a_{n + 2} <... <a_{2n}~

3. Los pares ordenados que consisten en elementos en posiciones idénticas de las dos secuencias también están en orden ascendente: ~a_1 <a_{n + 1}, a_2 < a_{n + 2}, ..., a_n < 2_{2n}~.

Por ejemplo, la permutación ~(1,3,4,2,5,6)~ es una triple permutación doble, tres veces mayor, porque la secuencias ~(1,3,4)~ y ~(2,5,6)~ forman unas filas en aumento, y todos los pares compuestos de elementos en posiciones idénticas: ~(1,2)~, ~(3,5)~, ~(4,6)~ también forman filas ascendentes.

Las siguientes permutaciones dobles no tienen la propiedad tres veces mayor:

~(1,4,3,2,5,6)~ - la secuencia ~(1,4,3)~ no está aumentando,

~(1,3,4,2,6,5)~ - la secuencia ~(2,6,5)~ no está aumentando,

~(1,4,5,2,3,6)~ - la secuencia ~(4,3)~ no está aumentando.

Para una mayor simplificación, la permutación doble por tres veces en aumento se llamará permutación.

Consideraremos todas las permutaciones en orden de lexicografía, numeradas comenzando por 1. La siguiente tabla contiene datos para n = 3:

Orden Permutación

1 ~ ~ ~ ~ ~ ~ ~ ~ 1 2 3 4 5 6

2 ~ ~ ~ ~ ~ ~ ~ ~ 1 2 4 3 5 6

3 ~ ~ ~ ~ ~ ~ ~ ~ 1 2 5 3 4 6

4 ~ ~ ~ ~ ~ ~ ~ ~ 1 3 4 2 5 6

5 ~ ~ ~ ~ ~ ~ ~ ~ 1 3 5 2 4 6

Hay dos tipos de preguntas:

1. ¿Qué permutación está en una posición dada?
2. ¿Qué posición es una permutación dada?

La primera pregunta se codifica de la siguiente manera: ~1~ ~n~ ~p~ y consiste en los valores

~1~ - el tipo de pregunta,

~n~ - orden de permutación,

~p~ - posición de permutación requerida.

La segunda pregunta está codificada de la siguiente manera: ~2~ ~n~ ~a_1 a_2 ... a_{2n}~ y consiste en los valores

~2~ - tipo de pregunta,

~n~ - orden de permutación,

~a_1 a_2 ... a_{2n}~ - los elementos de permutación.

Ejemplos:

Pregunta ~1~ ~3~ ~2~ significa:

"¿Qué permutación de orden ~3~ está en la posición ~2~ en orden lexicográfico?" y tiene la respuesta: ~1~ ~2~ ~4~ ~3~ ~5~ ~6~.

Pregunta ~2~ ~3~ ~1~ ~3~ ~5~ ~2~ ~4~ ~6~ significa: "¿En qué posición se encuentra la permutación de orden ~3~: ~1~ ~3~ ~5~ ~2~ ~4~ ~6~?", y tiene la respuesta: ~5~.

Tarea

Respuesta correcta a un conjunto de preguntas.

Entrada

La entrada contiene cada pregunta en cada línea.

Salida

La salida contendrá en una línea de respuesta por pregunta en la entrada en orden de las preguntas.

Restricciones y aclaraciones.

• ~2 < n < 1,000~;

• ~0 < p <= 1 000 000 000~ (para preguntas de tipo ~1~);

• la respuesta a las preguntas de tipo ~2~ es <= ~1 000 000 000~;

• Las entradas contendrán hasta ~2,000~ preguntas.

• Para las pruebas de ~30~ puntos, las preguntas serán del tipo ~1~;

• Para las pruebas de ~30~ puntos, las preguntas serán del tipo ~2~;

• Para las pruebas de ~40~ puntos, las preguntas serán mixtas.

Ejemplo de Entrada

1 3 2
2 3 1 3 5 2 4 6
1 4 1
2 4 1 2 3 4 5 6 7 8

Ejemplo de Salida

1 2 4 3 5 6
5
1 2 3 4 5 6 7 8
1

Explicación de la salida

La segunda orden 3 permutación (1,2,4,3,5,6)

La permutación (1,3,5,2,4,6) ocupa la 5ª posición.

Permutación de primer orden 4 (1,2,3,4,5,6,7,8).

La permutación (1,2,3,4,5,6,7,7,8) tiene la 1ª posición