配点 : $900$ 点

問題文

シカのAtCoDeerくんは次のような条件を満たす有向グラフを欲しがっています。

• 頂点数$N$は $300$ 以下
• 自己ループや多重辺があってはいけない
• 頂点には $1$ から $N$ の番号が付けられている
• 各辺には $0$ 以上 $100$ 以下の整数値の重み、もしくは、X または Y というラベルが付けられている
• 全ての $1 \leq x \leq A$, $1 \leq y \leq B$, を満たす整数の組 $(x,y)$ に対し、 ラベル X が付けられた辺の重みを $x$ に、 Y が付けられた辺の重みを $y$ に書き換えたグラフの 頂点 $S$ から $T$ への最短距離は $d_{x,y}$

AtCoDeerくんのためにこのようなグラフ(と $S$ と $T$ の組)をひとつ構成してください。条件を満たすグラフが存在しない場合はそれを指摘してください。 出力の方法については出力の欄を参照してください。

制約

• $1$ $\leq$ $A,B$ $\leq$ $10$
• $1$ $\leq$ $d_{x,y}$ $\leq$ $100$ ($1$ $\leq$ $x$ $\leq$ $A$, $1$ $\leq$ $y$ $\leq$ $B$)
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$A$ $B$

$d_{1,1}$ $d_{1,2}$ $..$ $d_{1,B}$

$d_{2,1}$ $d_{2,2}$ $..$ $d_{2,B}$

$:$

$d_{A,1}$ $d_{A,2}$ $..$ $d_{A,B}$

出力

条件を満たすグラフが存在しない場合は Impossible と出力せよ。

条件を満たすグラフが存在する場合、 $1$ 行目に Possible と出力せよ。 $2$行目以降に 構成したグラフを以下の形式で標準出力に出力せよ。

$N$ $M$

$u_1$ $v_1$ $c_1$

$u_2$ $v_2$ $c_2$

:

$u_M$ $v_M$ $c_M$

$S$ $T$

ただし、 $M$ は出力するグラフの辺数、 $u_i,v_i,c_i$ はグラフの辺を表す。 これは頂点 $u_i$ から 頂点 $v_i$ に 重み、あるいはラベル $c_i$ の有向辺があることを意味する。 入出力例も参考にせよ。

2 3
1 2 2
1 2 3

Possible
3 4
1 2 X
2 3 1
3 2 Y
1 3 Y
1 3

1 3
100 50 1

Impossible