这是一个交互式问题。

给定一个二分图，其第一部分有 $n$ 个顶点，第二部分有 $m$ 个顶点。图中包含零条或多条边，且允许重边。此外，有一个棋子初始放置在第一部分的一个顶点上。两名玩家在这个图上进行游戏：每一轮，他们将棋子沿图中的一条边移动。棋子沿某条边移动后，该边即消失。无法进行移动的玩家输掉游戏。第一名玩家先手。

给定图的结构和棋子的初始位置，你的任务是编写一个程序，作为第一名玩家进行游戏。评测程序将作为第二名玩家，并在可能的情况下赢得游戏。你的程序也应在可能的情况下赢得游戏。如果无法获胜，你的程序应持续进行游戏直到结束。

对手的移动将通过交互模式提供：在你完成每一步移动后，你将获得对手的下一步移动。请务必在每次移动后执行流刷新操作，以防止输出缓冲。例如，在 C 或 C++ 中可以使用 fflush(stdout)，在 Java 中可以使用 System.out.flush()，在 Pascal 中可以使用 flush(output)。

输入格式

第一行包含四个整数 $n, m, e$ 和 $v$ ($1 \le n, m \le 50, 0 \le e \le 2500, 1 \le v \le n$)：分别表示图第一部分的顶点数、第二部分的顶点数、边数以及棋子初始所在的、第一部分中顶点的编号（从 1 开始）。

接下来的 $e$ 行描述边。每行包含两个整数 $x$ 和 $y$ ($1 \le x \le n, 1 \le y \le m$)，由空格分隔，表示图第一部分的顶点 $x$ 与第二部分的顶点 $y$ 之间的一条边。

此后，你将获得对手的移动。每次移动为一个从 1 开始的整数 $v_i$ ($1 \le v_i \le n$)，表示对手将棋子移动到的第一部分中的顶点编号。

输出格式

如果你无法进行下一步移动，只需在单独的一行中打印 “Player 2 wins” 并优雅地终止程序。如果可以移动，打印一行，包含一个整数：你将棋子移动到的第二部分中的顶点编号。如果在你移动后，对手无法进行移动，则额外在新的一行中打印 “Player 1 wins” 并优雅地终止程序。请不要忘记在每次移动后刷新输出缓冲区。

每次有多种可能的移动方式时，你可以选择其中任意一种，前提是如果初始状态下你能获胜，你最终仍能获胜。

样例

样例输入 1

3 2 5 3
1 1
1 2
2 1
2 2
3 2
1
2

样例输出 1

2
1
2
Player 1 wins

样例输入 2

2 2 3 1
1 1
1 2
2 2
1

样例输出 2

1
Player 1 wins

样例输入 3

2 2 6 1
2 2
2 2
1 1
1 2
2 1
2 2
2
1

样例输出 3

1
2
Player 2 wins