모노톤길

올레길 코스로 유명한 산책로가 하나 있다. 이 산책로의 입구는 산책로에서 가장 서쪽에 있다. 산책로는 단순 경로이고 수평 구간과 수직 구간으로만 이루어져 있어서, 모든 코너에서 왼쪽이나 오른쪽으로 90도만 꺾인다. 또 입구에서 출구 방향으로 걸어갈 때 동쪽에서 서쪽으로 한 번도 이동하지 않고, 즉 보행자의 위치를 나타내는 x좌표가 작아지는 일 없이 출구까지 갈 수 있다. 그래서 이 산책로를 모노톤길이라고 부른다. 그림 1이 모노톤길의 예이다.

그림 1. 모노톤길의 예

산책로 곳곳에는 카페가 $n$개 있다. 입구와 출구, 그리고 모든 코너에는 반드시 카페가 있다. 코스 관리자 김씨는 이 산책로에 있는 카페의 위치 좌표를 모두 가지고 있다. 입구의 좌표는 항상 원점 $(0, 0)$이다. 김씨는 카페에 1번부터 $n$번까지 번호를 붙이려고 한다. 입구의 카페가 1번이고, 그다음부터는 길을 따라가면서 만나는 순서대로 번호를 붙인다. 입구에서 출구로 갈 때 카페 A를 카페 B보다 먼저 만난다면 A의 번호가 B의 번호보다 작다. 그래서 그림 1의 산책로에서 좌표 $(3, 1)$에 있는 카페는 5번, 좌표 $(9, 0)$에 있는 카페는 14번이고, 출구의 카페는 17번이다. 김씨는 산책로를 직접 걷지 않고 카페의 좌표만으로 이 작업을 끝내고 싶어 한다. 김씨를 도와 카페에 번호를 붙이는 프로그램을 작성하시오.

입력은 표준입력으로 주어진다. 첫째 줄에 테스트 데이터의 개수 $T$ ($1 \le T \le 10$)가 주어진다. 각 테스트 데이터의 첫째 줄에는 카페의 수를 나타내는 정수 $n$ ($2 \le n \le 100{,}000$)이 주어진다. 이어지는 $n$개의 줄에는 카페 한 곳의 좌표를 나타내는 두 정수 $x$와 $y$가 주어진다 ($0 \le x \le 100{,}000$, $-100{,}000 \le y \le 100{,}000$). 좌표는 길을 따라가는 순서와 상관없이 임의의 순서로 주어진다. 입구의 좌표는 항상 $(0, 0)$이고, 좌표가 같은 카페는 없다. 마지막 줄에는 정수 $m$ ($1 \le m \le 10$)과 $m$개의 정수가 주어진다. $m$개의 정수는 각각 1 이상 $n$ 이하의 카페 번호이다.

출력은 표준출력을 사용한다. 각 테스트 데이터마다 주어진 카페 번호 $m$개에 대한 답을 주어진 순서대로 한 줄에 하나씩 출력한다. 번호가 $k$인 카페에 대한 답은 그 카페의 좌표 $x$와 $y$이며, 두 정수를 공백 하나로 구분해 출력한다.