Descripción

Considere los números naturales ~A~ (formado por dos o tres dígitos, todos distintos y sin numerar) y ~X~ (formado por ~N~ dígitos, todos sin numerar).

A partir del número ~X~, utilizando todas sus ~N~ cifras, construya el mayor número natural ~Y~ estrictamente menor que ~X~. Por ejemplo, para ~X~ = ~121621~ construir ~Y~ = ~121612~.

También a partir del número ~X~, se puede obtener el número ~A~ suprimiendo algunas cifras de la grafía de ~X~ y uniendo las restantes, sin cambiar su orden. Por ejemplo, si ~X~ = ~121621~ y ~A~ = ~12~, hay ~Z~ = ~3~ posibilidades distintas de obtener el número ~A~ a partir de ~X~, son: 1) 121621; 2) 121621; 3) 121621. Los que no están en negrita son los que se eliminan.

Tarea

Conociendo los números ~A~, ~N~ y las ~N~ cifras de ~X~, determinar:

1. el mayor número natural ~Y~, estrictamente menor que ~X~, que se puede obtener reordenando los dígitos de ~X~;

2. el máximo número ~Z~ de posibilidades distintas por las que se puede obtener el número ~A~ a partir del número ~X~ suprimiendo algunas cifras y uniendo las restantes sin cambiar su orden.

Entrada

La entrada contiene:

• en la primera línea, un número natural p; para todas las pruebas de entrada, el número p sólo puede tener el valor ~1~ o el valor ~2~;
• en la segunda línea, el número ~A~, con el significado dado en el enunciado;
• en la tercera línea, el número de dígitos del número ~X~;
• en la cuarta línea, una cadena de ~N~ dígitos, separados por un espacio, que representan los dígitos del número ~X~, en ese orden.

Salida

• Si el valor de ~p~ es ~1~, sólo se resolverá el requisito ~1~. En este caso, la salida contendrá en la primera línea una cadena de dígitos que representan el número natural ~Y~ determinado (la respuesta al requisito ~1~).
• Si el valor de ~p~ es ~2~, sólo se resolverá el requisito ~2~. En este caso, la salida contendrá en la primera línea un número natural que representa el número ~Z~ determinado (la respuesta al requisito ~2~).

Restricciones y aclaraciones

• 12 ≤ A ≤ 987
• 10 ≤ N ≤ 30000
• Para todos los datos de la prueba, los números ~Y~ y ~A~ pueden obtenerse a partir del número ~X~
• Las respuestas correctas al requisito ~1~ reciben el ~30%~ de la puntuación y las respuestas correctas al requisito ~2~ reciben el ~70%~ de la puntuación.

Ejemplo #1 de Entrada

1
12
6
1 2 1 6 2 1

Ejemplo #1 de Salida

121612

Explicación del Ejemplo #1

El requisito ~1~ está resuelto. ~A~ = ~12~, ~N~ = ~6~, ~X~ = ~121621~ El mayor número Y estrictamente menor que ~X~ es: ~Y~ = ~121612~

Ejemplo #2 de Entrada

2
12
6
1 2 1 6 2 1

Ejemplo #2 de Salida

3

Explicación del Ejemplo #2

Resuelve el requisito ~2~. ~A~ = ~12~, ~N~ = ~6~, ~X~ = ~121621~ Existen ~Z~ = ~3~ posibilidades distintas por las que se obtiene el número ~A~ a partir de ~X~: 1) 121621; 2) 121621; 3) 121621