En un tablero de tamaño ~n \times m~, que consta de ~n~ filas y ~m~ columnas, en la casilla ~(r, c)~, es decir, en la intersección de la ~r~ésima fila y la ~c~ésima columna, hay un chip. En este tablero tendrás que jugar contra la computadora en un juego en el que podrás mover el chip y eliminar casillas del tablero.

Cada movimiento está estructurado de la siguiente manera:

• La computadora escoge un número entero ~k > 0~.
• Usted exactamente ~k~ veces, de alguna manera, selecciona una de las casillas no eliminadas adyacentes (que comparte un lado común) con la casilla en la que se encuentra actualmente el chip, y mueve el chip a esta casilla. Puedes mover el chip a una casilla en la que ya estuvo ubicada antes. Si no hay casillas adyacentes válidas, no se realiza ningún movimiento.
• La computadora escoge la coordenada ~(i, j)~ de una casilla arbitraria del tablero que aún no se ha eliminado y se elimina inmediatamente esta casilla.

Si la computadora elimina la casilla en la que se encuentra el chip, el juego termina con tu victoria. Tu objetivo es ganar lo antes posible. Al mismo tiempo, no le dices a la computadora tus movimientos, por lo que puedes jugar de manera injusta: en lugar de mover el chip por el tablero, puedes monitorear todas sus posiciones posibles. En otras palabras, si en algún momento en el que se elimina la casilla ~(i, j)~, hay una secuencia de movimientos del chip tal que en ese momento el chip se ubique exactamente en la casilla ~(i, j)~, puedes decirle a la computadora que el juego ha terminado y que has ganado.

Por supuesto, la computadora hace cumplir las reglas, por lo que si le informas de tu victoria eliminando una casilla en la que no se pudo ubicar el chip en ese momento, automáticamente pierdes.

Determine el mínimo número de movimientos posibles después del cual podrás informarle a la computadora sobre tu victoria, es decir, después del cual el chip podría terminar en la casilla que se está eliminando.

Subtareas

• Subtarea 1 (7 puntos): ~k_1 = n + m~.
• Subtarea 2 (6 puntos): ~k_t = 1~ para todo ~t~.
• Subtarea 3 (10 puntos): los movimientos de la computadora son aleatorios e igualmente probables.
• Subtarea 4 (14 puntos): ~(i_t, j_t)~ y ~(i_{t+1}, j_{t+1})~ tienen un lado en común para todos los ~t~.
• Subtarea 5 (11 puntos): ~k_t \le 2~ para todo ~t~.
• Subtarea 6 (17 puntos): ~n=1~.
• Subtarea 7 (9 puntos): ~n, m\le 40~.
• Subtarea 8 (26 puntos): Sin restricciones adicionales.

Entrada

La primera línea de la entrada contiene cuatro números enteros ~n~, ~m~, ~r~ y ~c~: el tamaño del tablero y las coordenadas de la ubicación inicial del chip (~1 \le r \le n \le 1000~; ~1 \le c \le m \le 1000~).

La segunda línea de la entrada contiene un número entero: tu número de la suerte. Simplemente puedes decidir ignorar este entero, pero te dará suerte para poder ganarle a la computadora 😁

Las siguientes ~n \cdot m~ líneas contienen los movimientos que la computadora va a realizar secuencialmente. La descripción del ~t~-ésimo movimiento está dada por tres números enteros ~k_t~, ~i_t~ y ~j_t~: el número de movimientos del chip que necesitarás realizar y las coordenadas del tablero de la casilla que debe eliminarse después de eso (~1 \le k_t \le 10^9~; ~1 \le i_t \le n~; ~1 \le j_t \le m~).

Se garantiza que todas las casillas eliminadas sean diferentes, es decir, ninguna casilla se elimina dos veces.

Salida

Imprime un número entero desde ~1~ hasta ~n \cdot m~: el número mínimo de movimientos después del cual le informarás a la computadora sobre tu victoria.

Ejemplos

Entrada 1

2 2 1 1
0
1 1 1
2 2 1
3 2 2
4 1 2

Salida 1

2

Puedes, por ejemplo, mover el chip de ~(1, 1)~ a ~(1, 2)~ con tu primer movimiento, y con tu segundo movimiento de ~(1, 2)~ a ~(2, 2)~ y luego a ~(2, 1)~, colocándolo así en la casilla que se va a eliminar.

Entrada 2

3 3 2 2
0
1 2 2
1 1 2
1 1 1
1 2 1
1 3 1
1 3 2
1 3 3
1 2 3
1 1 3

Salida 2

9