The problem statement for UR#24 has been stolen by a mole!

To recover the lost problem statement, the UOJ administrator decided to cooperate with the Pjudge administrator to leave the mole with nowhere to run.

The mole is traveling on a simple undirected connected graph with $n$ vertices and $m$ edges. The mole starts at vertex $1$ and aims to reach vertex $n$.

UOJ and Pjudge have recruited $k$ and $n-k$ guards, respectively. Each vertex in the graph is assigned exactly one guard, who is responsible for questioning passersby. Due to varying traffic, the time required for a person to pass through vertex $i$ is $t_i$. The time taken to traverse an edge is negligible.

The UOJ guards know that other UOJ guards are slackers, and the Pjudge guards know that other Pjudge guards are slackers, but they do not know whether guards from the other organization are slackers. Therefore, the mole is caught if and only if the guards at both endpoints of an edge traversed by the mole belong to the same OJ.

You need to construct an assignment of guards such that for any shortest path from $1$ to $n$, the mole will be caught if they take that path. Or, determine if no such solution exists.

Input

The first line contains three positive integers $n, m, k$.

The second line contains $n$ positive integers $t_1, t_2, \dots, t_n$.

The next $m$ lines each contain two positive integers $u_i, v_i$, representing an edge in the undirected graph.

Output

If a valid assignment exists, output a string $s$ of length $n$, where $s_i \in \{'P', 'U'\}$ indicates whether the guard at vertex $i$ is from Pjudge or UOJ.

Otherwise, output impossible.

Examples

Input 1

3 2 0
1 1 1
1 2
2 3

Output 1

PPP

Note 1

UOJ did not recruit any guards! However, this ensures that the guards at both endpoints of every edge are from Pjudge, so the mole will be caught regardless of which edge they take.

Input 2

2 1 1
1 1
1 2

Output 2

impossible

Note 2

The UOJ and Pjudge guards both assume the other side will perform the inspection, so they slack off themselves, and the mole escapes!

Input 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

Output 3

PUPUPPUU

Constraints

This problem uses bundled subtasks.

For all data, it is guaranteed that $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$.