Evolution Monsters


問題


ポケポケ地方には,種類のモンスターが生息しています.

モンスターにはレベルがあり,成長とともにレベルが上がっていきます.

また,モンスターの中には,進化することができるモンスターがおり,進化すると,モンスターの種類が変化します.モンスターがモンスターに変化する進化は,以下のように定められています.

  • 進化には進化石が必要で,進化ごとに定められた円の進化石を持たせた状態でモンスターがレベルアップしたとき,モンスターに進化することができます.進化後,使用した進化石はなくなります.
  • モンスターは,他のモンスターにも進化することができることがありますが,モンスターに直接進化することができるモンスターはモンスターだけです.
  • モンスターは,モンスター以外のモンスターにも,同じ値段の進化石で進化できることもありますし,値段が違うこともあります.(つまり,進化石の値段は,進化前のモンスターには依存しません.)
  • モンスターに進化したあと,どのように進化を遂げてもモンスターになることはありません.(つまり,すべての進化は不可逆的です.)

個の進化の条件が与えられます.番目の進化条件は,円の進化石を持たせた状態でモンスターがレベルアップしたとき,モンスターに進化することができることを示します.

あなたは,ポケポケ地方で匹のモンスターを捕まえました.番目に捕まえたモンスターを,回以上進化させることで,にしたいと考えています.回目に捕まえたモンスターそれぞれについて,モンスターをモンスターにすることができる場合は,モンスターをどのモンスターに "まず" 進化させる必要があるか,および,モンスターをモンスターにするまでにかかるお金を求めなさい.モンスターをどのように進化させていってもモンスターにすることができない場合は IMPOSSIBLE と出力してください.

制約


  • 任意のモンスターについて,回以上の進化を遂げて自分自身にもう1度なることができるような進化の集合は与えられない
  • 入力は全て整数

入力


N M Q
X_1 A_1 B_1
X_2 A_2 B_2
...
X_M A_M B_M
P{1,1} P{1,2}
P{2,1} P{2,2}
...
P{Q,1} P{Q,2}

出力


行目には,番目に捕まえたモンスターについて,答えが存在するとき,捕まえたときのレベル以降最初の進化における進化後のモンスターの種類と,モンスターをモンスターにするまでにかかるお金を空白区切りで出力し,存在しない時, IMPOSSIBLE と出力せよ.

monster_1 cost_1 もしくは IMPOSSIBLE
monster_2 cost_2 もしくは IMPOSSIBLE
...
monster_Q cost_3 もしくは IMPOSSIBLE

サンプル


入力例1


4 3 4
20 2 3
10 1 2
30 3 4
2 3
1 4
2 4
1 3

出力例1


3 20
2 60
3 50
2 30

入力例2


10 7 6
20 10 3
40 5 1
30 9 4
20 10 7
30 1 6
10 5 10
40 3 2
8 10
3 4
10 6
5 7
10 2
5 9

出力例2


IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
10 30
3 60
IMPOSSIBLE

Submit


Go (1.14)