Manjatan P48375

Sacarse el carnet de conducir no es nada fácil, y menos si lo intentas en Manjatan. En esta famosa ciudad las calles son segmentos cuyos extremos tienen coordenadas enteras. Las calles únicamente tienen dos direcciones posibles: vertical y horizontal. Además, algunas calles son de sentido único. El examinador te pedirá que realices un trayecto por la ciudad (“primera a la izquierda, tercera a la derecha, segunda a la derecha”, etc.); tu deberás cumplir sus órdenes, con las siguientes restricciones:

• Si el examinador te pide girar por una calle por la que no deberías avanzar, por ser contradirección (estas cosas pasan) debes negarte a cumplir su orden, y seguir avanzando hasta el próximo giro válido en la dirección indicada.

• El examen acaba cuando no hay más órdenes (en tal caso, debes seguir avanzando hasta llegar al final de la calle) o si llegas al final de una calle sin que te haya sido posible cumplir la orden del examinador.

En este problema te pedimos que calcules la distancia que avanzarás mientras realizas el examen.

Entrada

Una línea con el número $0<k<1000$ de calles de Manjatan, seguido de $k$ líneas con $5$ números cada una, separados por una cantidad arbitraria de espacios: estos 5 números son las coordenadas $x, y$ de los dos extremos de cada calle, y un número adicional para indicar si la calle es de doble sentido ($0$) o de sentido único ($1$); en este caso la dirección permitida va del primer extremo al segundo. No habrá dos calles que se superpongan (exceptuando en los puntos de cruce); las calles horizontales sólo intersecan con las verticales, y viceversa.

Los tres ejemplos de entrada se corresponden con los siguientes diagramas (las flechas indican calles de un único sentido).

A continuación, un número $0\leq n \leq 10000$ con los exámenes a realizar sobre la ciudad, seguido de los $n$ exámenes. Cada examen está formado por un número $1\leq i\leq k$ en una línea que indica el punto de partida del examen (el primero de los dos extremos de la calle $i$-ésima, en dirección hacia el segundo extremo), seguido de un número indeterminado de líneas, cada una de las cuales contiene una orden de la forma $x$I o $x$D con $x>0$ (gira la $x$-ésima calle a la izquierda, o la $x$-ésima calle a la derecha). Todo examen acaba con la orden 0X (que debes ignorar). Ningún examen tendrá más de 100 órdenes.

Salida

Escribe la distancia que recorres hasta que acaba el examen, por cualquiera de los dos motivos posibles. Si el examen acaba antes de tiempo por no haber sido posible cumplir alguna de las órdenes, escribe también un signo de exclamación después de la respuesta.

Puntuación

• Test1:

  Resolver casos donde los extremos de todos los segmentos no inciden con ningún otro segmento, y donde todas las calles son de doble sentido (como el ejemplo 1), y cuyas coordenadas están entre $0$ y $10^4$.

• Test2:

  Resolver casos donde los extremos de todos los segmentos no inciden con ningún otro segmento (como el ejemplo 2), y cuyas coordenadas están entre $0$ y $10^4$.

• Test3:

  Resolver casos de todo tipo (como el ejemplo 3), con calles cuyas coordenadas están entre $10^{-9}$ y $10^9$.