随着限制的解除，挪威和瑞典之间的边境贸易必将恢复往日的繁荣。但当局担心，这也意味着非法走私活动的增加。挪威和瑞典的海关当局必须通力合作，以防止这一问题变得过于严重。

为了通过海关，人们必须经过一系列检查站，即北欧海关和护照管制站。总共有 $n$ 个检查站，编号从 $1$ 到 $n$，其中 $1$ 是入口，$n$ 是出口。有 $m$ 对双向道路连接着不同的检查站。通过第 $i$ 个检查站需要花费一定的时间 $t_i$，这是跨越边境的瓶颈（在道路上行走的时间可以忽略不计）。

每个检查站都可以由一个海关单位监控，可以是挪威海关单位，也可以是瑞典海关单位。现有 $k$ 个挪威海关单位和 $n - k$ 个瑞典海关单位。当一条道路的两个端点都由同一个国家的海关单位监控时，任何使用该道路的走私者都将被抓获。走私者当然总是行色匆匆，并且总是试图以尽可能短的时间从 $1$ 到 $n$。

你的任务是决定如何放置这 $n$ 个海关单位，以便任何采取从 $1$ 到 $n$ 最快路线的走私者都能被抓获。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$ ($2 \le n \le 10^5$, $1 \le m \le 2 \cdot 10^5$, $0 \le k \le n$)，分别表示检查站的数量、道路的数量以及挪威海关单位的数量。输入的第二行包含 $n$ 个正整数 $t_1, \dots, t_n$ ($1 \le t_i \le 10^4$)，表示通过每个检查站所需的时间。接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示检查站 $u$ 和 $v$ 之间有一条道路。

保证从任何检查站都可以通过道路到达其他任何检查站。每对检查站之间最多只有一条道路，且没有道路连接检查站自身。

输出格式

如果存在一种放置海关单位的方法使得所有走私者都能被抓获，则输出一个长度为 $n$ 的字符串，其中第 $i$ 个字符表示在第 $i$ 个检查站放置的海关单位类型（'N' 表示挪威海关单位，'S' 表示瑞典海关单位）。否则，如果无法抓获所有走私者，则输出 "impossible"。

样例

样例输入 1

3 2 0
1 1 1
1 2
2 3

样例输出 1

SSS

样例输入 2

2 1 1
1 1
1 2

样例输出 2

impossible

样例输入 3

8 9 4
3 3 1 2 2 3 2 1
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 8
7 8

样例输出 3

SNSNSSNN