만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

카드 셔플 (Large)

면접 대비

시간 제한5초메모리 제한512 MB

요약
번호 순서대로 놓인 M장의 카드 더미에서 주어진 구간을 C번 맨 위로 옮긴 뒤 W번째 카드를 구합니다.
난이도

보통10점 중 5점

유형
시뮬레이션, 구간
정답자
아직 제출이 없습니다

문제

프랭크는 카드 게임을 좋아해서 주말마다 친구 집에서 열리는 게임 파티에 간다. 이들이 쓰는 카드 한 벌은 MM장이고, 각 카드에는 11부터 MM까지의 수가 겹치지 않게 하나씩 적혀 있다. 프랭크에게도 친구가 파티에서 쓰는 자동 셔플 기계와 똑같은 기계가 있어서 작동 방식을 안다. 이 기계는 카드 더미를 CC번 잘라 옮기는 식으로 카드를 섞는다. ii번째 컷은 더미 위에서 AiA_i번째 카드부터 BiB_i장, 즉 AiA_i번째부터 Ai+Bi−1A_i + B_i - 1번째까지의 카드를 순서를 그대로 유지한 채 더미 맨 위로 옮긴다.

어느 날 늘 쓰던 카드가 더러워져서 새 카드를 쓰기로 했다. 새 카드는 위에서부터 11부터 MM까지 차례대로 놓인 상태 그대로 셔플 기계에 들어갔다. 프랭크는 셔플 기계의 성질을 이용해, 다 섞은 뒤 위에서 WW번째에 놓인 카드가 무엇인지 알아내려 한다.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다. 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

M C W
A1 B1
...
AC BC

첫 줄에는 공백 하나로 구분된 세 정수 MM, CC, WW가 주어진다. MM은 카드의 장수, CC는 컷 횟수, WW는 알고 싶은 카드의 위치다. 이어지는 CC개의 줄에는 각각 공백 하나로 구분된 두 정수 AiA_i, BiB_i가 주어진다. ii번째 컷에서 위에서 AiA_i번째 카드부터 BiB_i장을 더미 맨 위로 옮긴다는 뜻이다.

제약 조건

  • 1≤T≤2001 \le T \le 200
  • 1≤C≤1001 \le C \le 100
  • 1≤W≤M1 \le W \le M
  • 1≤Ai≤M1 \le A_i \le M
  • 1≤Bi≤M1 \le B_i \le M
  • 1≤Ai+Bi−1≤M1 \le A_i + B_i - 1 \le M
  • 1≤M≤1091 \le M \le 10^9

출력

각 테스트 케이스마다 다음 내용을 한 줄에 출력한다.

Case #X: P

XX는 11부터 시작하는 테스트 케이스 번호이고, PP는 다 섞은 뒤 카드 더미 위에서 WW번째에 놓인 카드다.

예제5

  1. 예제 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
    예상 출력
    Case #1: 1
Case #2: 2
Case #3: 2

  2. 예제 2

    입력
    1
1 100 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
    예상 출력
    Case #1: 1

  3. 예제 3

    입력
    2
10 3 10
1 10
1 10
1 10
10 100 1
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
    예상 출력
    Case #1: 10
Case #2: 1

  4. 예제 4

    입력
    2
7 5 3
1 1
1 4
5 3
1 7
3 2
7 3 7
1 2
2 5
1 1
    예상 출력
    Case #1: 5
Case #2: 7

  5. 예제 5

    입력
    10
10 1 1
4 3
10 1 2
4 3
10 1 3
4 3
10 1 4
4 3
10 1 5
4 3
10 1 6
4 3
10 1 7
4 3
10 1 8
4 3
10 1 9
4 3
10 1 10
4 3
    예상 출력
    Case #1: 4
Case #2: 5
Case #3: 6
Case #4: 1
Case #5: 2
Case #6: 3
Case #7: 7
Case #8: 8
Case #9: 9
Case #10: 10