Shopping Malls

We want to build a smartphone app for shopping mall visitors. Given the visitor's current location and destination, the app shows the route that needs the least walking, in meters.

The mall has $N$ places spread over several floors, connected by walking paths, lifts, stairs and escalators. Only the distance the visitor actually walks counts, so every kind of movement has its own cost. The route with the least walking may go against the direction of an escalator.

• A walking path or a flight of stairs costs the euclidean distance between the two places.
• A lift costs 1 meter, because once you are inside you do not walk at all. One lift connects only two places. A real lift joins the same point on different floors, and the map contains an edge for every pair of places that lift joins. For example, with three floors and a lift at position (1, 2) on each of them, writing a place as (floor, $x$, $y$), the input contains all three edges (0, 1, 2) to (1, 1, 2), (1, 1, 2) to (2, 1, 2) and (0, 1, 2) to (2, 1, 2). Some maps have a lift that does not stop at every floor, and then some of those edges are missing.
• An escalator has two uses.
  • Going from A to B, its proper direction, costs 1 meter, because you walk a few steps and the escalator carries you the rest of the way.
  • Going from B to A, against its direction, costs the euclidean distance between B and A multiplied by 3.

A route may use only the given connections. Every place can be reached from every other place.

The input holds the map of one shopping mall and a list of queries.

The first line contains the number of places $N$ ($N \le 200$) and the number of connections $M$ ($N - 1 \le M \le 1000$). The places are numbered from $0$ to $N-1$. Each of the next $N$ lines contains the floor and the coordinates $x$, $y$ of one place. Two neighbouring floors are 5 meters apart, and $x$ and $y$ are in meters too. The euclidean distance between two places is measured in three dimensions, including the height difference between their floors.

Each of the next $M$ lines describes a direct connection between two places: the numbers of both places and the type of movement, one of walking, stairs, lift, escalator. The cost of each type is described above. For an escalator the proper direction runs from the place written first to the place written second. Two places on the same floor are connected by walking.

The next line contains the number of queries $Q$ ($1 \le Q \le 1000$). Each of the next $Q$ lines contains two places $a$ and $b$.

For each query print on one line the route from $a$ to $b$ that needs the least walking. Print the numbers of the places along the route in order, separated by single spaces, including $a$ and $b$.

When several routes need the same amount of walking, print the one whose sequence of place numbers is smallest in lexicographic order. When $a$ and $b$ are the same place, print that single number.