The input consists of multiply test cases. The first line of each test case contains two integers, n (3 <= n <= 100), m (0 <= m <= 10000), where n is the number of vertexes of the maze, and m is the time limit. The next n lines represent the maze, each line contains a coordinate, x, y (-10000 <= x, y <= 10000) and a DoorType. If DoorType equals to -1, then you can get in from this vertex; if DoorType equals to 0, then it’s not a door; if DoorType equals to 1, then you can get out from this vertex. The last line of each test case is a coordinate, indicating the location of the precious. You can assume that the precious is always in the maze.
The last test case is followed by a line containing two zeros, which means the end of the input.