Autor: Blaz Korecic

Tiempo límite: 1 segundo

Memoria límite: 256 megabytes

En la famosa serie de videojuegos Roptal desarrollada por la prestigiosa compañía Palpe, los jugadores controlan a los robots SALTA y Q-Body para resolver una serie de puzzles.

Como es de costumbre en los videojuegos de Palpe, se acerca la tercera entrega de la saga de Roptal. Esta presenta un novedoso puzzle en el que los robots deben rotar una serie de cajas de manera que un láser pueda llegar desde un inicio hasta el final y así abrir la puerta hacia el siguiente nivel.

Dado que en este puzzle todas las cajas son pequeñas y están en un mismo plano, las representaremos como puntos en un plano cartesiano. En particular, tenemos \(n\) puntos con coordenadas enteras, numerados del \(1\) al \(n\).

Cuando el láser impacta en una caja desde cualquier dirección, este se redirige gracias a una cara especial de la caja, que siempre apunta en una dirección paralela a los ejes: arriba, derecha, abajo o izquierda. Por ejemplo, si el láser llega desde la izquierda a una caja cuya cara especial apunta hacia abajo, su trayectoria continuará hacia abajo a partir de esa caja.

Las cajas \(1\) y \(n\) son especiales: la caja \(1\) es el origen del láser (lo emite por su cara especial sin necesidad de recibirlo por alguna cara), mientras que la caja \(n\) es el objetivo al que el láser debe llegar (solo puede recibir el láser y no lo redirige, por lo que su cara especial es irrelevante).

Los jugadores pueden realizar la siguiente operación: escoger una caja y rotarla 90, 180 o 270 grados, cambiando la dirección hacia la que redirige el láser a otra de las direcciones posibles.

El objetivo es resolver el puzzle con la menor cantidad de operaciones. Para calcular el óptimo, los desarrolladores de Roptal escribieron un algoritmo, pero resultó ser muy lento, por lo que necesitan tu ayuda.

Entrada

La primera línea contiene un entero \(n\) (\(2 \le n\le 2 \cdot 10^{5}\)), la cantidad de cajas.

La \(i\)-ésima de las siguientes \(n\) líneas contiene dos enteros y un string \(x_{i}, y_{i}, d_{i}\) (\(-10^{9} \le x_{i}, y_{i}\le 10^{9}, d_{i}\in\) \(\{arriba, derecha, abajo, izquierda\}\)), representando las coordenadas de la \(i\)-ésima caja y la dirección inicial a la que redirige el láser.

Salida

Imprime una sola línea con un número entero, indicando la mínima cantidad de operaciones para que el láser llegue hasta la caja \(n\) o -1 si no es posible.

Ejemplos

Entrada 1

5
1 1 arriba
1 2 izquierda
1 3 derecha
2 2 derecha
2 3 izquierda

Salida 1

1

Nota

El ejemplo se puede resolver en una operación, rotando la caja que está en \((1, 2)\) de forma que redirija el láser hacia arriba.