Henry decides to develop a web site, which will provide the service of transit search. But he can only get the transit data of Guangzhou, so his web site can only support the transit search of Guangzhou. We suppose Guangzhou is 10240 meters by 10240 meters. The coordinate of the top-left corner is (0,0). The coordinate of the bottom-right corner is (10240,10240). The X–axis is from top to bottom and the Y-axis is from left to right. At the beginning, four pictures of the size 10cm by 10 cm make up of the whole map of Guangzhou. They are numbered from 0 to 3. It is to say at the beginning the scale of the map is 1cm:512 meters. We call the four pictures are at level 1.
When you double-click on the map using the mouse, the map will zoom in. The pictures at next level will be shown on the screen. For example, when you double-click on the above map, picture 0 will be replaced by four pictures 00, 01, 02, 03, all of whose sizes are 10 cm by 10 cm. and the scale of the map change to 1cm:256 meters. (notice that, pictures 00,01,02,03 together describe the same area as picture 0). When you continue double-click, picture 01 will be replaced by pictures 010,011,012,013, and so on.
Now, a position’s coordinate can be given by(str, x,y). str consists of 8 characters each from 0 to 3. It describes the id of the picture which the position is located at. x and y(0cm<=x,y<=10cm) describe the position’s offset relative to the top-left corner on picture str. Notice that the X–axis is from top to bottom and the Y-axis is from left to right.
Now, the start position and end position are given as (start, sx, sy), (end, ex, ey). And some information about the bus line will be also given. First, each bus stop will be described by (name, x, y), its name and its coordinate. Second, each bus line will be described by (name1, name2, name3…namek) which are the bus stops the bus line travels through. If the distance between the start position and end position is no more than 2000 meters, the web site will suggest walking there. Otherwise, the web site will find a bus stop whose distance is no more than 1000 meters from the start position. You can take buses to a bus stop whose distance is no more than 1000 meters from the end position. Along the way, you can change buses at any bus stop. If you can take buses according the above rules, the web site will find a route with fewest number of changing buses. If you can’t take buses according the above rules, the web site will suggest taking a taxi.