多年的玛雅文字破译工作让著名的考古学家 Wood 博士迎来了这一时刻：在拉克顿丛林（Lacandon Jungle）深处的雅克奇兰（Yaxchilán）迷宫的一间密室里，最后一本未被发现的玛雅古抄本（codex）展现在她面前。它美丽非凡，由美洲豹皮保护，并饰有翡翠。然而，就在她触碰它的那一刻，迷宫的所有通道都关闭了。她现在成了迷宫的囚徒。更糟糕的是，她并非孤身一人，她的整个考古团队也和她一起被囚禁在迷宫的不同密室中。

当她仔细研究古抄本时，一系列复杂的图表引起了她的注意。这些图表描绘了迷宫，其通道会变形为不同的配置，每种配置都与太阳的特定位置相对应。另一组图表展示了墙壁上雕刻复杂的孔洞，以及对一只巨型黄蜂令人毛骨悚然的描绘。她突然意识到——玛雅人设计这个迷宫是为了让它随太阳的位置而改变，而且一些密室里设有致命巨型黄蜂巢穴的机关。

具体来说，迷宫中有 $N$ 个密室，编号为 $0, \dots, N-1$。Wood 博士和她的团队成员从密室 $0, 1, \dots, A-1$ 开始（每人一个密室）。有 $E$ 个出口：密室 $N-E, \dots, N-1$。最初，迷宫中没有开启的通道。在每个整点（00:00, 01:00, 02:00 等，用整数 $0, 1, 2$ 等表示），一条连接两个密室的新通道会开启。这条通道将保持开启整整 $M$ 小时减去一分钟。通道是双向的。

在 $N$ 个密室中，有 $B$ 个设有机关。当一个密室与至少 $K$ 个其他密室相连时，该密室的机关就会触发。一旦触发，一大群致命的黄蜂就会出现在该密室中，并立即蔓延到所有与该机关密室相连的密室。此外，随着时间的推移，黄蜂永远不会从密室中消失，更糟糕的是，它们会继续瞬间从含有黄蜂的密室蔓延到新连接的密室。在给定时间，如果存在一条由一条或多条开启的通道组成的路径可以从一个密室到达另一个密室，则认为这两个密室是相连的。

多亏了古抄本和她对迷宫的了解（以及智能手机！），Wood 博士和她团队的每个成员在第 $0$ 小时都掌握了关于迷宫的完整信息，包括所有未来的事件：特别是，他们每个人都知道自己在迷宫中的位置、通道通往何处、确切的时间、通道开启和关闭的时间以及它们连接哪些密室、机关的位置、出口、$K$，并能推断出哪些密室已经或将被致命的黄蜂填满。所有考古学家在任何时候都可以利用开启的通道自由且独立地移动。他们跑得很快，可以在不到 59 分钟内移动到任何可达的密室。如果考古学家最终进入了一个填满致命黄蜂的密室，他或她就会死亡，无法离开迷宫。

出口密室的行为与其他密室相同：它们也可以被黄蜂填满，也可以设有机关。

一旦考古学家到达任何未被黄蜂填满的出口密室，他或她就会离开迷宫并脱离危险。你能告诉我们每个考古学家最早可以在什么时间离开迷宫吗？

输入格式

• 第一行包含整数 $A$，表示考古学家的数量。
• 第二行包含整数 $N$。
• 第三行包含整数 $M$。
• 第四行包含整数 $E$。
• 第五行包含整数 $T$，表示通道开启的小时数。
• 第六行包含 $B$，后跟由空格分隔的 $B$ 个设有机关的密室列表 $b_i$。
• 第七行包含 $K$。
• 接下来的 $T$ 行中，第 $t$ 行包含两个空格分隔的整数 $u_t, v_t$，表示在第 $t$ 小时开启并连接密室 $u_t$ 和 $v_t$ 的通道。$t$ 从 $0$ 到 $T-1$（含）。多条通道可以连接相同的两个密室。一条通道可以连接一个密室与它自身。

输出格式

输出应包含 $A$ 行。第 $i$ 行代表第 $i$ 个考古学家。如果第 $i$ 个考古学家可以离开迷宫，则应输出代表他或她最早可以离开的小时的整数。否则，应输出 IMPOSSIBLE。

数据范围

• $1 \le A \le 50$
• $2 \le N \le 50\,000$
• $1 \le M \le 100\,000$
• $1 \le E \le 100$
• $A + E \le N$（没有密室既是起点又是出口）
• $1 \le T \le 500\,000$
• $0 \le B \le N$
• 对于 $i = 0, \dots, B-1$，$0 \le b_i < N$
• $b_i$ 互不相同
• $0 \le K < N$
• 对于 $t = 0, \dots, T-1$，$0 \le u_t < N$
• 对于 $t = 0, \dots, T-1$，$0 \le v_t < N$

样例

输入样例 1

1
5
1
1
5
0
0
0 1
0 2
2 3
2 4
0 4

输出样例 1

3

说明 1

没有机关。Wood 博士（唯一的考古学家）从 0 开始，出口是 4。在通道 0 2 开启后，她从密室 0 前往密室 2。她留在那里，直到通道 2 4 开启，这使她能够到达密室 4 并在第 3 小时离开。

输入样例 2

1
4
1
1
3
0
0
0 1
2 3
1 2

输出样例 2

IMPOSSIBLE

说明 2

没有机关。Wood 博士（唯一的考古学家）从 0 开始，出口是 3。不幸的是，Wood 博士只能在通往出口的通道 2 3 关闭后才能到达密室 2。她无法离开迷宫。

输入样例 3

4
10
2
2
11
2 3 7
2
0 1
1 2
2 3
1 4
4 9
5 6
0 6
5 7
1 6
7 8
6 8

输出样例 3

9
9
9
IMPOSSIBLE

说明 3

对于从 0 开始的第一位考古学家，通往出口的最快路径是在第 6 小时使用通道 0 6 和 5 6 前往密室 5，然后在第 7 小时使用通道 5 7 前往密室 7，最后在第 9 小时使用通道 7 8 到达密室 8（一个出口）。请注意，密室 7 设有机关，但黄蜂直到第 10 小时才出现，此时第一位考古学家已经离开了迷宫。

从 1 开始的第二位考古学家可以在第 0 小时移动到密室 0，然后沿着第一位考古学家的路径前进。

从 2 开始的第三位考古学家可以在第 1 小时移动到密室 0，然后跟随前两位考古学家。

从 3 开始的最后一位考古学家在第 2 小时被黄蜂杀死。

最终，密室 1, 2, 3, 4, 6, 7, 8, 9 都被黄蜂填满。