题目描述

UR#24 的题面被内鬼偷走了！

为了找回丢失的题面，uoj 管理员决定和 pjudge 管理员合作，让内鬼无路可逃。

内鬼在一个 $n$ 个点 $m$ 条边的简单无向连通图上行走，他从 $1$ 号点出发，目标是 $n$ 号点。

uoj 和 pjudge 分别抓了 $k$ 和 $n-k$ 个壮丁。图上的每个点会恰好分配一个壮丁，负责盘问来往行人。因为人流量不同，一个人经过第 $i$ 个点需要花费的时间是 $t_i$ 。经过一条边的时间可以忽略不计。

uoj 的壮丁很清楚其他 uoj 的壮丁都是鸽子，pjudge 的壮丁也很清楚其他 pjudge 的壮丁都是鸽子，但他们相互不知道对方是不是鸽子。所以，只有当内鬼经过的一条边的两边的壮丁来自同一个 oj 时，他才会被抓住。

你需要构造一个分配壮丁的方案，使得对于任意一条 $1$ 到 $n$ 的最短路，内鬼走这条路都会被抓住。或者判断无解。

输入格式

第一行三个正整数 $n,m,k$ 。

第二行 $n$ 个正整数 $t_1,t_2,\cdots,t_n$ 。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$ ，表示无向图中的一条边。

输出格式

如果存在合法方案，那么输出一个长度为 $n$ 的字符串 $s$ ，其中 $s_i\in \{'P', 'U'\}$ 表示第 $i$ 个点的壮丁是来自 pjudge 还是 uoj 。

否则，输出 impossible 。

样例一

input

3 2 0
1 1 1
1 2
2 3

output

PPP

explanation

uoj 一个壮丁都没有抓到！但是这样就使得每条边的两边的壮丁都来自 pjudge ，因此内鬼走任意一条边都会被抓住。

样例二

input

2 1 1
1 1
1 2

output

impossible

explanation

uoj 和 pjudge 的壮丁互相认为对方会认真盘查，于是自己当鸽子，结果内鬼跑掉了！

样例三

input

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

output

PUPUPPUU

样例四、五、六

见下发文件。

数据范围

本题采用子任务捆绑测试。

对于所有数据，保证 $2\le n\le 10^5, 1\le m\le 2\times 10^5, 0\le k\le n, 1\le t_i\le 10^4$ 。

时间限制：$\texttt{3s}$

空间限制：$\texttt{1024MB}$