Problema número 342

¡No lo puedes saber!

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB

— He pensado un número entre 1 y 10 (incluídos), ¿intentas adivinarlo? Yo te contestaré simplemente "menor" o "mayor o igual" hasta que seas capaz de saber cuál es.

— ¡Acepto el reto! ¿Es el 1?

— Mayor o igual.

— ¿Es el 2?

— Menor

— ¡Lo tengo!

— ¡Vaya! ¡Qué rapidez! Venga, otra vez. Ahora un número entre 1 y 1000.

— ¿El 500?

— Menor

— ¿El 400?

— Mayor o igual.

— ¡Lo tengo!

— ¿Cómo que lo tienes? ¡No puede ser!

Entrada

La entrada estará compuesta por distintas partidas al juego anterior. Cada una de esas partidas ocupará dos líneas. La primera tendrá tres números, ini, fin y n con 1 ≤ ini ≤ n ≤ fin ≤ 250.000 indicando el rango de valores entre los que se puede elegir el número y el valor oculto elegido.

La segunda línea comienza con el número k de preguntas que hace el segundo jugador, al que le siguen k números con las hipótesis. Se garantiza que éstas están siempre en el intervalo [inifin].

El último caso de prueba va seguido de una línea con tres ceros que no debe procesarse.

Salida

Para cada caso de prueba se escribirá LO SABE si al final de todas las preguntas el jugador puede saber el número oculto y NO LO SABE si es imposible que lo sepa con certeza.

Se asume que la persona que contesta a las preguntas nunca miente.

Entrada de ejemplo

1 10 1
2 1 2
1 1000 450
2 400 500
0 0 0

Salida de ejemplo

LO SABE
NO LO SABE