かくれんぼ (숨바꼭질)

당신은 JOI 사가 출시한 TV 게임 소프트웨어를 손에 넣었다. 꽤 잘 만들어진 게임이라 나름대로 즐기면서 매일 플레이하고 있었다.

어느 날, 게이머들 사이에서 "숨바꼭질"이라고 불리는 스테이지가 등장했다. 아무래도 그 스테이지에는 버그가 있어서, 뛰어난 게이머조차 아주 적은 확률로밖에 클리어할 수 없는 것 같았다.

그 스테이지에 여러 번 도전하는 가운데 당신은 매우 빠른 판단을 하면 클리어할 가능성이 있다는 것을 깨닫고, 프로그램을 작성해 대처할 수 있지 않을까 생각했다.

숨바꼭질 스테이지는 많은 장애물이 배치된 장소를 무대로 한다. 무대는 직사각형이고 1 × 1의 정사각형 칸으로 나뉘어 있으며, 각 칸은 1 ≤ x ≤ 100,000, 1 ≤ y ≤ 1,000,000,000을 만족하는 정수 x, y로 (x, y)라고 표현된다. (1, 1)은 왼쪽 위 모서리 칸이고, (x + 1, y + 1)은 (1, 1)에서 오른쪽으로 x, 아래로 y만큼 진행한 칸을 나타낸다.

각 장애물은 y 좌표가 같은 연속된 w개의 칸에 놓인다. 즉, 장애물은 w × 1개의 칸을 차지하는 직사각형 모양으로 보인다. 그중 x 좌표가 가장 작은 칸의 좌표 (x, y)와 길이 w의 쌍으로 하나의 장애물이 표현된다. 장애물은 2 ≤ y인 칸에 배치된다. 장애물끼리 겹치지 않는다.

스테이지가 시작되면 플레이어는 무대를 돌아다닌다. 플레이어는 장애물이 있는 칸을 포함한 임의의 칸으로 이동할 수 있다.

일정 시간이 지나면 적이 나타나 공격을 한다. 플레이어는 이때 반드시 장애물 속에 숨어야 한다. 장애물 속에 숨으려면 장애물이 있는 칸에 있으면 된다. 적절한 장애물 속에 숨으면 플레이어는 공격을 받지 않고, 적에게 반격할 기회를 얻는다. 그 기회를 이용하면 스테이지를 클리어할 수 있다.

적은 M종류의 무기(예를 들어 권총, 라이플, 무반동포, 전자기 투사포 등등)를 가지고 있다. 무기에는 1부터 M까지 고유한 번호가 붙어 있고, i번 무기에는 공격력 ai가 설정되어 있다. 공격력은 그 수치만큼 장애물을 파괴할 수 있다는 것을 나타낸다.

파괴된 장애물 속에 플레이어가 숨어 있으면 플레이어는 대미지를 입는다.

적은 무작위로 선택된 x를 사용해 (x, 1)에 나타나 아래쪽을 향해 무작위로 선택한 무기로 공격할 예정이었다. 그런데 게임 버그 때문에 적은 반드시 플레이어가 있는 x 좌표를 선택해 플레이어를 향해 공격하게 되었다.

당신은 직접 만든 프로그램을 사용해, 적이 어떤 무기로 공격하더라도 괜찮도록 무기마다 공격을 받지 않는 최적의 숨을 곳을 찾기로 했다. 공격을 받지 않는 최적의 숨을 곳은 플레이어가 반격하기 쉽도록 y 좌표가 가장 작은 곳이다. 또, 그러한 곳이 여러 개 있으면 그중에서도 x 좌표가 가장 작은 곳이 최적이다.

장애물의 정보와 각 무기의 공격력이 주어졌을 때, 적이 가진 무기마다 최적의 숨을 곳을 구하는 프로그램을 작성하라. 단, 어떻게 숨어도 공격을 받게 되는 경우에는 숨을 곳이 없다는 뜻으로 (-1,-1)을 출력하라.

그림 1: 공격력이 4인 무기에 대응하는 숨는 방법

표준 입력에서 다음 입력을 읽는다.

• 1행에는 정수 N과 M이 공백을 구분으로 쓰여 있다.
• 이어지는 N행 중 i행에는 정수 xi, yi, wi가 공백을 구분으로 쓰여 있다.
• 이어지는 M행 중 j행에는 정수 aj가 쓰여 있다.

표준 출력에 다음 데이터를 출력한다.

• 데이터는 M행으로 이루어진다. j행에는 두 정수 xj와 yj가 공백 구분으로 쓰여 있고, j번째 무기에 대응하는 최적의 숨을 곳 좌표가 (xj, yj)임을 나타낸다. 어떻게 숨어도 j번째 무기의 공격을 받게 되는 경우에는 xj = yj = −1로 하라.

• 1 ≤ N ≤ 50,000 장애물의 수
• 1 ≤ M ≤ 50,000 무기의 종류
• 1 ≤ xi ≤ 100,000 장애물 i가 배치되는 칸 중에서 가장 작은 x 좌표
• 2 ≤ yi ≤ 1,000,000,000 장애물 i의 y 좌표
• 1 ≤ wi + xi − 1 ≤ 100,000 wi는 장애물 i의 길이
• 1 ≤ aj ≤ N 무기 j의 공격력