Notice

Problem Statement

You are now trying to compose a song. There are $N$ candidate phrases for use in this song, called phrase $1, \dots,$ phrase $N$. Singing phrase $i$ takes $X_i$ seconds. The song you are composing must satisfy the following conditions.

• The song must begin with phrase $S$ and end with phrase $T$.
• The number of phrases used in the song, including the first $S$ and the last $T$, must be at least $K$. If the same phrase is used multiple times, it is counted that many times.
• Let $R$ be the number of phrases used in the song, and let $P_k$ be the $k~(1 \leq k \leq R)$-th phrase. Then, for every $1 \leq k < R$, there must exist $1 \leq j \leq M$ such that $(P_k,P_{k+1})=(A_j, B_j)$.

Is it possible to arrange phrases into a song satisfying all of the above conditions? If it is possible, find the minimum total time required among songs satisfying the conditions, and construct one song that achieves it. Here, the time required is the sum of the time taken to sing each phrase and the time taken from the end of singing one phrase to the start of singing the next.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq S,T \leq N$
• $1 \leq K \leq 3 \times 10^4$
• $1 \leq X_i \leq 10^9$
• $1 \leq M \leq \min (N^2, 2 \times 10^5) $
• $1 \leq A_j, B_j \leq N$
• If $j \neq k$, then $(A_j, B_j) \neq (A_k, B_k)$
• $1 \leq Y_j \leq 10^9$
• At least one of the following conditions is satisfied. (Corrected 2021/06/11 22:37 ("one of the two" → "one"))
  • [A] $1 \leq N \leq 10^5, 1 \leq K \leq 10$
  • [B] $1 \leq N, K \leq 130$
  • [C] $1 \leq N \leq 10, 1 \leq K \leq 3 \times 10^4$

Input

$N$ $S$ $T$ $K$
$X_1$ $\dots$ $X_N$
$M$
$A_1$ $B_1$ $Y_1$
$\vdots$
$A_M$ $B_M$ $Y_M$

Output

If it is possible to compose a song satisfying the conditions, print Possible on the first line, and from the second line onward print a song with the minimum required time as follows: if the minimum time is $V$, and a song achieving it consists of $R$ phrases with the $i$-th phrase being $P_i$, print in the following format.

$V$
$R$
$P_1$ $\dots$ $P_R$

• $R \geq K$
• $1 \leq P_i \leq N$
• $P_1=S, P_R=T$
• For each $1 \leq i < R$, there exists $1 \leq j \leq M$ such that $(P_i, P_{i+1})=(A_j, B_j)$.

If it is impossible, print Impossible. If there are multiple valid songs, you may print any of them.

Do not forget the newline at the end.

Sample

3 1 3 3
5 7 6
5
1 1 2
1 2 1
1 3 3
2 3 4
3 3 1

Possible
21
3
1 3 3

Possible
21
3
1 1 3

4 1 4 5
1 2 3 400
3
1 2 10
2 3 100
3 4 1000

Impossible

6 3 2 1
3 3 3 3 3 3
6
3 2 1000000000
3 1 1
1 6 1
6 4 1
4 5 1
5 2 1

Possible
23
6
3 1 6 4 5 2

1 1 1 11
1
1
1 1 1

Possible
21
11
1 1 1 1 1 1 1 1 1 1 1