El Granjero Juan y sus ~Q~ vacas están en Manhattan de vacaciones, pero las vacas se han escapado y ahora están andando libremente en la ciudad. Manhattan es enorme - tan enorme que sus ~N~ calles se extienden infinitamente en el plano ~x-y~, pero convenientemente, esas calles todas corren perfectamente horizontal o verticalmente. Cada calle horizontal y vertical puede ser modelada por una ecuación de la forma ~y=c_i~ o ~x=c_i~, donde ~ci~ es un entero en el rango de ~0~ a ~10^9~ inclusive.

El Granjero Juan sabe exactamente donde cada vaca comenzó a caminar y hace cuánto tiempo se escaparon. Las vacas son muy predecibles, entonces cada una de ellas camina de acuerdo al siguiente patrón:

• Solamente caminan al norte (~+y~) o al este (~+x~) una unidad por segundo.
• Si están actualmente en una sola calle, continúan caminando en dirección de la calle.
• Si están en la intersección de dos calles, ellas caminan hacia el norte si han estado caminando un número par de segundos y al este en otro caso.

Dada la distribución de Manhattan y la información de cada vaca, ayude al Granjero Juan a determinar donde están ahora sus vacas.

Entrada

• La primera línea contiene ~N~ y ~Q~.
• Las ~N~ líneas siguientes describen a las calles. Cada calle está descrita por una dirección (~H~ o ~V~) y una coordenada ~c_i~. Se garantiza que todas las calles son únicas.
• Las ~Q~ líneas siguientes describen a las vacas. Cada vaca está descrita por tres enteros ~(x_i,y_i,d_i)~, que indican que ellas comenzaron a caminar desde ~(x_i,y_i)~ exactamente hace di segundos. Se garantiza que ~(x_i,y_i)~ está en alguna calle, y que ~0 \leq x_i,y_i,d_i \leq 10^9~.

Salida

Dé como salida ~Q~ líneas, donde la línea i-ésima contiene la posición actual de la vaca i-ésima.

Restricciones

• ~1 \leq Q \leq 2 \cdot 10^5~
• ~1 \leq N \leq 2 \cdot 10^5~

Ejemplo de Entrada

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

Ejemplo de Salida

14 5
7 13
6 15
6 16
110 4

La primera vaca tomó los siguientes caminos:

~(6, 3) \rightarrow (6, 4) \rightarrow (7, 4) \rightarrow (7, 5) \rightarrow (8, 5) \rightarrow \ldots \rightarrow (14, 5)~

~(6, 4) \rightarrow (6, 5) \rightarrow (7, 5) \rightarrow (7, 6) \rightarrow ... \rightarrow (7, 13)~

USACO 2024 January Contest, Gold Problem 1. Walking in Manhattan.