お知らせ

問題文

あなたは今, 曲を作ろうとしている. この曲の使われるフレーズの候補は $N$ 個であり, それぞれ フレーズ $1, \dots,$ フレーズ $N$ とする. フレーズ $i$ を歌うのには $X_i$ 秒を要する. ここで, 作ろうとしている曲に関して, 以下の条件を満たしていなければならない.

• 曲の最初はフレーズ $S$, 最後はフレーズ $T$ でなくてはならない.
• 曲に使われるフレーズの個数は最初の $S$ と最後の $T$ も含めて $K$ 個以上でなくてはならない. ただし, 同じフレーズを複数回用いている場合はその回数分カウントする.
• 曲に使われているフレーズの個数を $R$ とし, $k~(1 \leq k \leq R)$ 番目のフレーズを $P_k$ とする. このとき, 全ての $1 \leq k < R$ に対して, $(P_k,P_{k+1})=(A_j, B_j)$ となる $1 \leq j \leq M$ が存在しなければならない.

上記の条件を全て満たすようにフレーズを組み立て, 曲を作ることは可能か? また, 可能ならば条件を満たすような曲について, 所要時間の総和の最小値を求め, それを達成する曲を1つ作れ. ここで, 所要時間とは, 各フレーズを歌うのに要する時間と, あるフレーズの歌い終わりから歌い始めに要する時間それぞれの総和である.

制約

• $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$
• $j \neq k$ ならば, $(A_j, B_j) \neq (A_k, B_k)$
• $1 \leq Y_j \leq 10^9$
• 以下の条件のうち, 少なくとも1つを満たしている. (2021/06/11 22:37 訂正 (一方→1つ))
  • [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$

入力

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

出力

条件を満たすように曲を作ることが可能である場合, 1行目に Possible と出力し, 所要時間が最小であるような曲を2行目以降から以下のようにして出力せよ: 最短時間が $V$ で, それを達成するような曲が $R$ 個のフレーズからなり, $i$ 番目のフレーズが $P_i$ であるとき, 以下の形式で出力せよ.

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

• $R \geq K$
• $1 \leq P_i \leq N$
• $P_1=S, P_R=T$
• $1 \leq i < R$ に対して, $(P_i, P_{i+1})=(A_j, B_j)$ なる $1 \leq j \leq M$ が存在する.

もし, 不可能ならば,Impossibleと出力せよ. なお, 適する曲の作り方が複数考えられる場合, どれを出力しても良い.

最後に改行を忘れないこと.

サンプル

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