시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 2 1 1 100.000%

문제

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

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

입력

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

M C W
A1 B1
...
AC BC

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

制約

  • 1 ≤ T ≤ 200
  • 1 ≤ C ≤ 100
  • 1 ≤ W ≤ M
  • 1 ≤ Ai ≤ M
  • 1 ≤ Bi ≤ M
  • 1 ≤ Ai + Bi - 1 ≤ M
  • 1 ≤ M ≤ 109

출력

各テストケースに対し、

Case #X: P

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

예제 입력 1

3
1 1 1
1 1
2 3 1
2 1
2 1
2 1
5 3 2
4 2
5 1
4 2

예제 출력 1

Case #1: 1
Case #2: 2
Case #3: 2

채점

  • 예제는 채점하지 않는다.