Problem G. Getting Faster ≡

Author:	Г. Гренкин		Time limit:	5 sec
Input file:	Standard input		Memory limit:	512 Mb
Output file:	Standard output

Statement

Navigating through Building D of the FEFU campus can be a real challenge!

To address this, students have digitized the entire building, and now they seek your help. Your task is to construct routes between specified rooms.

The layout of Building D is provided in a specific format in the file input.txt. This file also contains queries to your program — indicating which rooms require a route to be constructed.

Input format

The first line of the input file contains an integer N — the number of locations. The next N lines list the names of these locations. All names are unique and consist of Latin letters, digits, and underscores.

The following line contains an integer M — the number of paths. A path is a sequence of distinct locations. Each of the next M lines starts with the number of locations in the path, followed by a letter f, l, b, f, or r, which represents the orientation of the path relative to the direction "facing the sea": f: forward, l: left, b: back, r: right. Next, the numbers of the locations (starting from 1) corresponding to the path are listed, in the order they are visited.

The next line contains an integer L — the number of stairs and elevators. Each of the next L lines starts with the number of locations, followed by the indices of the locations connected by the corresponding stairway or elevator.

The next line contains the number of test cases T. This is followed by T lines, each containing two location names separated by a space.

Locations d1 and d2 represent the entrances to Building D. Rooms are labeled with names such as d734.

Testing will be performed on a single file, which can be downloaded via the provided link.

Output format

For each test case, the output file should include the following:

The integer R, indicating the number of steps in the route. R lines describing the steps, where each line starts with a letter representing the direction of movement: f: forward, l: left, b: back, r: right, s: stairs.

Next, the list of locations should follow on the same line. Movement to each location should follow the specified direction along one of the paths or via the stairs/elevator. The direction of movement relative to the starting location can be arbitrary. Movement along paths can occur in both forward and reverse directions. If a transition occurs between paths but the direction of movement remains the same, the route should continue on a new line with the direction of movement indicated.

An example route from an entrance to room D950 might look like this:

4
f d1 posta_ohrani 
l razvilki d751 elevators_3_4_elevator_7 d745_750 d744 d743 d742 d741 d740 d739 stairs4_stairs_7 
s stairs4_stairs_9 
r d947 d946 d948 d945 d949 d944 d950 

Constraints

---