카드 셔플 (Large)

문제

프랭크는 카드 게임을 좋아해서 주말마다 친구 집에서 열리는 게임 파티에 간다. 이들이 쓰는 카드 한 벌은 $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

첫 줄에는 공백 하나로 구분된 세 정수 $M$ , $C$ , $W$ 가 주어진다. $M$ 은 카드의 장수, $C$ 는 컷 횟수, $W$ 는 알고 싶은 카드의 위치다. 이어지는 $C$ 개의 줄에는 각각 공백 하나로 구분된 두 정수 $A_i$ , $B_i$ 가 주어진다. $i$ 번째 컷에서 위에서 $A_i$ 번째 카드부터 $B_i$ 장을 더미 맨 위로 옮긴다는 뜻이다.

제약 조건

$1 \le T \le 200$
$1 \le C \le 100$
$1 \le W \le M$
$1 \le A_i \le M$
$1 \le B_i \le M$
$1 \le A_i + B_i - 1 \le M$
$1 \le M \le 10^9$

출력

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

Case #X: P

$X$ 는 $1$ 부터 시작하는 테스트 케이스 번호이고, $P$ 는 다 섞은 뒤 카드 더미 위에서 $W$ 번째에 놓인 카드다.