WORMWRLD - Worm world

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.

A worm world
  1 2 3 4 5 6 7 8            1 2 3 4 5 6 7 8
 1
1 2 3 4 5 6 7 8    1
W . . F . . F .
2 9 10 11 12 13 14 15 16   2 . . . . . . . F
3 17 18 19 20 21 22 23 24   3 . . . . . . . .
4 25 26 27 28 29 30 31 32   4 F . . . . F . .
5 33 34 35 36 37 38 39 40   5 . . . . . . . .
6 41 42 43 44 45 46 47 48   6 . . . . . F . .
7 49 50 51 52 53 54 55 56   7 . . F . . . . .

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.


Added by:Jimmy Tirtawangsa
Date:2018-10-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.