Фермер Джон та його ~Q~ (~1≤Q≤2⋅10^5~ ) корів на Манхеттені. Корови втекли і гуляють містом. У Манхеттені ~N~ (~1≤N≤2⋅10^5~ ) доріг проходять нескінченно на ~xy~ - площині. Усі вони розташовані чи горизонтально, чи вертикально. Кожна горизонтальна або вертикальна може бути змодельована рівнянням виду ~y=c_i~ або ~x=c_i~ , де ціле число ~c_i~ в інтервалі від 0 до ~10^9~ включно.

ФД знає точно де кожна корова почала подорож та час подорожі. Кожна з корів рухається за наступним шаблоном:

• Вона рухається на північ (~+y~) або схід (~+x~) на одну одиницю на секунду.
• Якщо вона на одній дорозі, вона продовжує рухатися нею.
• Якщо вона на перетині двох доріг, вона йде на північ, на парній секунді подорожі та на схід інакше.

Вам дана карта Манхеттена та інформація про кожну корову, допоможіть ФД визначити де його корови зараз.

Формат вхідних даних

Перший рядок введення містить ~N~ та ~Q~.

Наступні ~N~ рядків описують дороги. Кожна дорога описується напрямком (H чи V), координатою ~c_i~. Гарантується, що кожна дорога є унікальною.

Наступні ~Q~ рядків описують корів. Кожна корова описується трьома цілими числами (~x_i, y_i, d_i~), що означають, що вона почала подорож з позиції (~x_i, y_i~) рівно ~d_i~ секунд тому. Гарантується, що (~x_i, y_i~) лежить на деякій дорозі і ~0≤x_i,y_i,d_i≤10^9~.

Формат вихідних даних

Виведіть ~Q~ рядків, де ~i~-й рядок містить поточну позицію ~i~-ї корови.

Оцінювання

• Тести 2-4 (20 балів): ~N, Q, c_i, x_i, y_i, d_i≤100~.
• Тести 5-9 (30 балів): ~N, Q≤3000~.
• Тести 10-20 (50 балів): Немає додаткових обмежень.

Пояснення

Перші дві корови пройшли такий шлях:

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)

(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Приклад вхідних даних

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

Приклад вихідних даних

14 5
7 13
6 15
6 16
110 4