M. Dead-line

You managed to get the parcel service to pick up your box you have designed in the laser CNC task. The only problem remaining is how you get to the checkpoint where they pick you up, because zombies are following you again. If you walk fast enough, they can not catch up and will follow you in a long queue. If they catch you, they will bite you and you will become one of them. If you arrive at the checkpoint too late, you miss the pickup and die in the city; if you arrive too soon, you need to stop and wait and the zombies will bite you. The only way out of this is finding a route that is long enough that you don't arrive too soon. The horde of zombies is following you like an endless stream, so you can't visit the same point on the map twice.

http://wiki.openstreetmap.org/wiki/File:Public-images-osm_logo.png

Given a map downloaded from OpenStreetMap (http://osm.org), two points, and a constant M, find a route with between the two points close to M in length but not exceeding it, without visiting a node twice.

Input

The map

The map itself is given in OpenStreetMap XML format. The most important entities are <node> and <way>. (<relation> entities should be completely ignored.)

A <node> has the following main attributes:

• id: a unique 64-bit signed integer identifier
• lat: latitude coordinate, in degrees
• lon: longitude coordinate, in degrees

A <way> has the following kinds of children: <nd> and <tag>. A <nd> element describes a reference to a node through the ref attribute, which contains the unique identifier of that node.

Some of the <nd> elements may refer to nonexistent nodes via invalid id's -- these <nd> elements should be ignored completely. This may result in ways with one or zero nodes, these ways should be ignored as well.

A <tag> element describes a key-value pair through the k (key) and v (value) attributes. Streets correspond to those ways which have a tag with key highway. If a street has a tag with key oneway and value yes, then it can only be used in the direction defined by the listing order of its node references. If a street has a tag with key oneway and value -1, then it can only be used in the opposite direction. All other streets are bidirectional. No other key/value pairs should be taken into account.

The quests

Each quest is given in a text file which consists of three whitespace-separated numbers A B M.

A is the unique identifier of the starting node and B is the unique identifier of the finishing node. M is the maximum allowed length of the route, in meters. You should use the following formula to calculate the distance of two geographical locations (in meters), substituting the latitudes and longitudes converted to radians:

acos(sin(this.Latitude) * sin(other.Latitude) +
     cos(this.Latitude) * cos(other.Latitude) * cos(other.Longitude - this.Longitude)) * R

Output

For each quest, you have to produce an output file containing whitespace-separated integers. The file must contain the number of visited nodes N, followed by exactly N integers: the unique identifiers of the nodes, in visiting order. A valid submission describes a route from A to B whose total length is at most M.

Scoring

S := M - L

The scaled real score is

SCORE := round(100 * (1 - sqrt(1 - Smin/S)))

244926905 541151835 1600

4 244926905 497096570 527360282 541151835