Monocarp finalmente se registró en ForceCoders y creó un nombre de usuario, pero ahora está considerando la contraseña. Desea que sea lo más segura posible, por lo que definió los siguientes requisitos:

• La contraseña debe tener exactamente m caracteres.
• Solo puede contener dígitos del 0 al 9.
• No debe aparecer como subsecuencia en la base de datos de contraseñas (dada como una cadena s).

Además, Monocarp proporcionó dos cadenas de longitud m: l y r, ambas compuestas solo por dígitos. El dígito i-ésimo de la contraseña debe estar entre li y ri, inclusive.

¿Existe una contraseña que cumpla todos estos criterios?

Entrada

La primera línea contiene un entero t (1 ≤ t ≤ 104) — el número de casos de prueba.

Para cada caso de prueba:

• La primera línea es una cadena s (1 ≤ |s| ≤ 3·105) — la base de datos de contraseñas.
• La segunda línea es un entero m (1 ≤ m ≤ 10) — la longitud requerida de la contraseña.
• La tercera línea es una cadena l (|l| = m) — los límites inferiores para cada dígito.
• La cuarta línea es una cadena r (|r| = m) — los límites superiores para cada dígito, con li ≤ ri.

La suma de las longitudes de s en todos los casos no excede 3·105.

Salida

Para cada caso, imprima "YES" si existe una contraseña válida, o "NO" en caso contrario.

Ejemplo

Entrada:

5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11

Salida:

YES
NO
YES
NO
YES

Nota

En el primer caso, Monocarp puede elegir la contraseña "50", que no aparece como subsecuencia en s.

En el segundo caso, todas las combinaciones de tres dígitos entre 1 y 4 son válidas según l y r, pero todas aparecen como subsecuencias en s.

En el tercer caso, la única contraseña posible es "4321", que no es subsecuencia de s.

En el cuarto caso, solo "49" y "59" son candidatas, y ambas aparecen en s como subsecuencias.

En el quinto caso, Monocarp puede seleccionar "11".

Solución

Se utiliza un enfoque voraz: para cada posición en la contraseña, se busca el dígito más tardío posible en s dentro del rango permitido, de manera que se minimize el rango de búsqueda para los dígitos siguientes. Si en algún momento no se encuentra un dígito, la contraseña es válida.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int casos;
    cin >> casos;
    while (casos--) {
        string base, min_range, max_range;
        int longitud;
        cin >> base >> longitud >> min_range >> max_range;
        int idx_actual = 0;
        bool encontrado = false;
        for (int i = 0; i < longitud; i++) {
            int max_idx = idx_actual;
            for (char digito = min_range[i]; digito <= max_range[i]; digito++) {
                size_t pos = base.find(digito, idx_actual);
                if (pos == string::npos) {
                    cout << "YES" << endl;
                    encontrado = true;
                    break;
                }
                max_idx = max(max_idx, (int)pos + 1);
            }
            if (encontrado) break;
            idx_actual = max_idx;
        }
        if (!encontrado) cout << "NO" << endl;
    }
    return 0;
}