City Navigation

Most cities in the United States are laid out on a very simple plan. Avenues run north to south, Streets run east to west, and together they enclose square blocks. Avenues and Streets are numbered, and the numbers grow toward the west and toward the south. Each side of a block carries 50 driveways, numbered 00 to 98 on one side of the road and 01 to 99 on the other. Numbers $2k$ and $2k+1$ face each other across the road and share one section, so each side of a block is divided into 50 sections. House numbers grow in the same directions as the Street and Avenue numbers. When you drive in the direction of increasing numbers, the odd numbers are on your right.

The house at 1288 16th Street, written S16 1288, is on 16th Street, west of 12th Avenue and east of 13th Avenue, and it is on the right-hand side when you drive east. The address A11 1543 is on 11th Avenue, south of 15th Street and north of 16th Street, and it is on the right-hand side when you drive south. Both are marked on the street map below.

Quiet suburbs come from a simple trick: some Avenues and Streets are cut into pieces, as the map shows. An Avenue or a Street keeps its name even where a piece of it does not exist. Getting lost in such a city is hard, because the address tells you exactly where to go. If you do not know which pieces are missing, though, you can waste a lot of time driving into dead ends.

Write a program that reads a description of the missing areas of a city and then a series of address pairs, where an address gives a driveway and not necessarily a residence. For each pair, compute the distance between the two driveways along the shortest legal route. The distance is the number of driveways you pass on your side of the road, and it does not count the source or the destination. Assume the following:

• You drive on the right-hand side of the road.
• You may not cross a lane of traffic except at an intersection, so you must turn right when you enter or leave a driveway.
• Driveways sit at the centres of their sections.
• U-turns are illegal except at the end of a cul-de-sac.
• Streets and Avenues are numbered 00 to 49 and no road exists beyond those bounds. Driveways still exist on both sides of the bounding roads.
• A section on a corner has two driveways.
• A route exists between every pair of driveways.

The input has two portions, a missing-road portion and an address portion, and each one ends with a line holding a single #.

The missing-road portion has one line per missing area. Each line holds a road identifier and a pair of house numbers. A road identifier is A or S, for an Avenue or a Street, followed by a number in the range 00 to 49. A house number is an even number in the range 0000 to 4898. The area of that road between the two given numbers, including the positions of both numbers, is inaccessible. The blocked area runs straight across the road, so if 1612 cannot be passed then 1613 cannot be passed either. A blocked area starts and ends at the borders of sections, not at the driveways. Exactly one space separates the parts of a line.

The address portion has one line per query, and each line holds two addresses. An address is a road identifier followed by a number in the range 0000 to 4899. Exactly one space separates the parts of a line.

Print one line for every line of the address portion. Each line holds a single integer, the distance between the two given driveways, which is the number of driveways passed.

The example input describes the same city that the map above draws. Look at the place where A13 crosses S17.