En la ciudad de Carl el Erizo hay un parque rectangular. Los arboles y los visitantes en el parque están representados por círculos. Hay cuatro entradas al parque, una en cada esquina (~1 =~ abajo-izquierda, ~2 =~ abajo-derecha, ~3 =~ arriba-derecha, ~4 =~ arriba-izquierda). Los visitantes pueden entrar y salir del parque solo por las cuatro entradas y pueden moverse libremente en el parque, pero ellos no pueden solapar ninguno de los árboles o la cerca.

Tu tarea es calcular para cada visitante, dada la entrada por la que llegan al parque, por cuales pueden salir.

Entrada

La primera linea contiene dos enteros ~N~ y ~M~: el número de árboles en el parque y el número de visitantes.

La segunda linea contiene dos enteros ~W~ y ~H~: el largo y ancho del área de el parque. La esquina abajo-izquierda es ~(0, 0)~ y la esquina arriba-derecha es ~(W, H)~.

Las siguientes ~N~ líneas describen los árboles. Cada línea contiene tres enteros ~X~, ~Y~ y ~R~: el centro de el árbol es ~(X, Y)~ y su radio es ~R~. Los árboles no se solapan con otros árboles ni con la cerca.

Finalmente, ~M~ líneas que describen a los visitantes. Cada línea contiene dos enteros ~R~ y ~E~: El radio de el visitante y la entrada por la que llega al parque.

Ningún árbol solapa un área cuadrada de ~2K * 2K~ en las esquinas, donde ~K~ es el radio de el visitante mas grande

Salida

Para cada visitante debes imprimir una sola línea que contiene las entradas por las cuales el puede salir del parque, ordenadas y sin espacios en el medio.

Notas

Dos objetos se tocan si ellos tienen un punto en común. Dos objetos se solapan si ellos tienen más de un punto en común.

Ejemplo de Entrada

5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

Ejemplo de Salida

1234
2
14

La siguiente figura muestra el área de las entradas y las posibles rutas para cada visitante.

Subtareas:

En todas las subtareas ~4K < W,H \leq 10^9~ donde ~K~ es el radio de el visitante mas grande.

Subtask 1 (27 puntos)

~1 \leq N \leq 2000~

~m = 1~

Subtask 2 (31 puntos)

~1 \leq N \leq 200~

~1 \leq M \leq 10^5~

Subtask 3 (42 puntos)

~1 \leq N \leq 2000~

~1 \leq M \leq 10^5~