Sales

The option finds a reasonable tour through a graph that visits every node. The order of visiting nodes will be displayed, with a graphical representation.

Input

Format

The first line specifies the calculation required. It must contain

format sales

Cities

Column	Description
1	'c' for city
2	x location
3	y location
4	name

The cities will all be connected by links with cost equivalent to the Pythagorean distance between them.

Links

Column	Description
1	l for link
2	src node name
3	dst node name
4	cost

Links will be added between nodes where missing with cost set to a large number. This allows a tour to be found if a critical link is missing, but otherwise only links present in the input will be used.

Example

format sales
c 1 5 a
c 3 7 b
c 5 5 c
c 5 1 d
c 2 1 e
c 3 3 f

route b -> a -> e -> f -> c -> d ->