Worms move in horizontal and vertical direction only in a gridded planar world. At certain grids there will be fungus that they eat. Given initial position of a worm, find a short route to find and eat all those fungus and coming back to the original position. See the example below for N=7, M=8, F=7,X=1, the left matrix shows how the cells are numbered and the right one shows an example of an initial position.

Input

The first line contains 4 integers, N, M, F, X, which are the world size (NxM), the number of fungus, and the worm initial position (X)

The next line contains F integers, which are the positions of fungus.

1 < N, M < 20

1 < X < NxM

1 < F < 100

Output

One line containing the F positions of food positions in the order of visited by the worm.

Example

Input:
7 8 7 1
4 7 16 25 30 46 51

Output:
4 7 16 30 46 51 25

Click on the score to get more information if the score is not 100.