쇼핑몰

쇼핑몰 방문객을 위한 스마트폰 안내 앱을 만들려고 한다. 현재 위치와 목적지를 넣으면 앱이 목적지까지 걸어야 하는 거리가 가장 짧은 경로를 미터 단위로 알려 준다.

쇼핑몰에는 여러 층에 걸쳐 장소가 $N$개 있고, 장소끼리는 도보 통로, 엘리베이터, 계단, 에스컬레이터로 이어져 있다. 세는 것은 방문객이 실제로 걸은 거리뿐이라서 이동 수단마다 비용이 다르다. 걸은 거리가 가장 짧은 경로가 에스컬레이터를 진행 방향과 거꾸로 거슬러 가는 경로일 수도 있다.

• 도보 통로와 계단은 두 장소 사이의 유클리드 거리만큼 비용이 든다.
• 엘리베이터는 비용이 1미터다. 한번 타면 걷지 않기 때문이다. 엘리베이터 하나는 장소 두 개만 잇는다. 실제 엘리베이터는 여러 층의 같은 지점을 잇고, 지도에는 그 엘리베이터가 잇는 장소의 모든 쌍이 간선으로 들어 있다. 예를 들어 층이 3개이고 각 층의 (1, 2) 위치에 엘리베이터가 있으면, 장소를 (층, $x$, $y$)로 적을 때 입력에는 (0, 1, 2)와 (1, 1, 2), (1, 1, 2)와 (2, 1, 2), (0, 1, 2)와 (2, 1, 2)를 잇는 간선 세 개가 모두 들어온다. 엘리베이터가 모든 층에 서지 않는 지도도 있고, 그러면 그중 일부 간선은 입력에 없다.
• 에스컬레이터는 두 가지로 쓴다.
  • A에서 B로, 즉 진행 방향으로 가면 몇 걸음만 걷고 나머지는 에스컬레이터가 옮겨 주므로 비용이 1미터다.
  • B에서 A로, 즉 진행 방향과 반대로 가면 B와 A 사이의 유클리드 거리에 3을 곱한 만큼 비용이 든다.

경로는 주어진 연결만 쓸 수 있다. 모든 장소는 서로 오갈 수 있다.

입력은 쇼핑몰 한 곳의 지도와 질의 목록으로 이루어진다.

첫째 줄에 장소의 수 $N$ ($N \le 200$)과 연결의 수 $M$ ($N - 1 \le M \le 1000$)이 주어진다. 장소에는 $0$번부터 $N-1$번까지 번호가 붙어 있다. 다음 $N$줄에는 장소의 층과 좌표 $x$, $y$가 한 줄에 하나씩 주어진다. 이웃한 두 층 사이의 거리는 5미터이고 $x$와 $y$도 미터 단위다. 두 장소 사이의 유클리드 거리는 층 높이 차이까지 넣어 3차원으로 잰다.

다음 $M$줄에는 두 장소를 직접 잇는 연결이 주어진다. 각 줄에는 두 장소의 번호와 이동 수단이 주어지고, 이동 수단은 walking, stairs, lift, escalator 중 하나다. 수단별 비용은 위 설명을 따른다. 에스컬레이터는 먼저 적힌 장소에서 나중에 적힌 장소로 가는 쪽이 진행 방향이다. 같은 층에 있는 두 장소의 이동 수단은 walking이다.

다음 줄에는 질의의 수 $Q$ ($1 \le Q \le 1000$)가 주어진다. 다음 $Q$줄에는 질의마다 장소 두 개 $a$와 $b$가 주어진다.

질의마다 $a$에서 $b$까지 걸은 거리가 가장 짧은 경로를 한 줄에 출력한다. 지나는 장소의 번호를 순서대로 공백 하나로 구분해 적고, $a$와 $b$도 포함한다.

걸은 거리가 같은 경로가 여러 개면 장소 번호를 앞에서부터 견주어 사전순으로 가장 작은 것을 출력한다. $a$와 $b$가 같으면 그 번호 하나만 출력한다.