Express Bus Routes

Three countries A, B, and C share borders with one another. Each country has N cities numbered from 1 to N. Among all 3N cities, the 2N cities given in the input are the starting or ending cities of N routes, and the remaining N cities must each be used exactly once as an intermediate stop on a route.

For every route, its start and end are given in advance, and the two cities are different. A city name is written as the country letter immediately followed by its number: A1 is city 1 in country A, and B3 is city 3 in country B.

The routes you print must satisfy all of the following conditions.

1. Every city that is not a start or an end must be included as an intermediate stop on exactly one route.
2. A route may have from 0 to 2 intermediate stops. The country of every intermediate stop must be different from both the start country and the end country of that route. If a route has 2 intermediate stops, those two stops must also belong to different countries. Therefore, a route whose start and end are in different countries can have at most 1 intermediate stop.
3. A route whose start and end are in the same country must contain at least 1 intermediate stop.

For the given start-end pairs, at least one set of routes satisfying these conditions is guaranteed to exist. If there are several valid answers, print any one of them.

The first line contains an integer N (1 ≤ N ≤ 50,000), the number of cities in each country.

Each of the next N lines contains the start and end city of one route, separated by a space.

Print N lines in the same order as the input routes. On each line, print the city names included in that route, from the start city to the end city. Separate adjacent city names on the same line with one space.