Automotive Navigation

Example

Input

4 2 1 1 1 1 1 2 2 2 2 1 2 2 1 2 1 1 2 1 9 N

Output

1 1 2 2

inputFormat

Input

4 2 1 1 1 1 1 2 2 2 2 1 2 2 1 2 1 1 2 1 9 N

outputFormat

Output

1 1 2 2

样例

4 2 1 1
1 1 1 2
2 2 2 1
2 2 1 2
1 1 2 1
9 N

1 1
2 2