The option finds a reasonable routes for drivers that must pickup cargos and deliver them to locations.

Input

Input is accepted in space delimited text files.

Format

The first line specifies the calculation required. It must contain

format pickup

Locations

Each line thereafter specifies the name and type occupying a location

Column	Description
1	'd' for driver'c' for cargo'e' for end( destination )
2	x location of start point
3	y location of start point
4	name

Example

format pickup
d 1 3 start
e 6 5 end
c 1 1 c1
c 5 5 c2
c 3 3 c3
c 4 4 c4
c 2 2 c5
c 6 6 c6