12453번 - カードシャッフル (Small) 다국어

フランクはカードゲームが好きで、週末は友達の家でゲームパーティーに参加しています。彼らがゲームに使うカードは M 枚からなり、それぞれ 1 から M までの数字が重複しないように書かれています。フランクはパーティーで友人が使っている自動カードシャッフル装置と同じものを持っていて、どのように動作するか理解しています。その装置はカードの山を C 回カットすることでシャッフルを行います。i 回目のカットではカードの山の上から A_i 番目から B_i 枚、つまり A_i 番目から A_i + B_i - 1 番目のカードがそのままの順番で山の上に移動します。

ある日、いつも使っているカードが汚れたため、新しいカードを使うことになりました。新しいカードは上から順番に 1 から M まで並んだ状態でそのままシャッフル装置にかけられました。フランクはシャッフル装置の性質を利用し、シャッフル後に上から W 番目にあるカードが何かを知ろうとしています。

最初の行はテストケースの個数 T を表す正の整数です。続いて、各テストケースが次のようなフォーマットで与えられます。

M C W
A1 B1
...
AC BC

1行目では、1 つのスペースで区切られた 3 つの整数 M, C, W が与えられます。ここで M はカードの枚数 、C はカットの回数、W は知りたいカードの位置です。 続く C 行の各行では、1 つのスペースで区切られた 2 つの整数 A_i, B_i が与えられます。 ここで A_i, B_i はカットの操作で、i 回目の操作で上から A_i 番目から B_i 枚のカードを山の上に移動させることを意味しています。

制約

• 1 ≤ T ≤ 200
• 1 ≤ C ≤ 100
• 1 ≤ W ≤ M
• 1 ≤ A_i ≤ M
• 1 ≤ B_i ≤ M
• 1 ≤ A_i + B_i - 1 ≤ M
• 1 ≤ M ≤ 100

各テストケースに対し、

Case #X: P

という内容を1行出力してください。ここで X は 1 から始まるテストケース番号、P はシャッフル後のカードの山の上から W 番目にあるカードを表します。