ポケポケ地方には,の種類のモンスターが生息しています.
モンスターにはレベルがあり,成長とともにレベルが上がっていきます.
また,モンスターの中には,進化することができるモンスターがおり,進化すると,モンスターの種類が変化します.モンスターがモンスターに変化する進化は,以下のように定められています.
個の進化の条件が与えられます.番目の進化条件は,円の進化石を持たせた状態でモンスターがレベルアップしたとき,モンスターに進化することができることを示します.
あなたは,ポケポケ地方で匹のモンスターを捕まえました.番目に捕まえたモンスターを,回以上進化させることで,にしたいと考えています.回目に捕まえたモンスターそれぞれについて,モンスターをモンスターにすることができる場合は,モンスターをどのモンスターに "まず" 進化させる必要があるか,および,モンスターをモンスターにするまでにかかるお金を求めなさい.モンスターをどのように進化させていってもモンスターにすることができない場合は IMPOSSIBLE
と出力してください.
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
4 3 4 20 2 3 10 1 2 30 3 4 2 3 1 4 2 4 1 3
3 20 2 60 3 50 2 30
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
IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE 10 30 3 60 IMPOSSIBLE