떨어지는 개미

길이 Lmm인 막대 위에 개미 N마리가 서로 다른 위치에 있다. 각 개미는 처음에 왼쪽 또는 오른쪽을 바라보고 있으며, 시작 신호가 나면 바라보는 방향으로 초속 1mm의 같은 속도로 이동한다. 개미는 크기가 없는 점으로 생각한다.

두 개미가 같은 지점에서 만나면 두 개미는 즉시 방향을 바꾸어 계속 움직인다. 방향을 바꾸는 데 걸리는 시간은 없다. 개미가 막대의 끝을 지나면 막대에서 떨어진다.

각 개미는 부호 있는 정수 ID로 표현된다. 음수 ID는 처음에 왼쪽을 바라보는 개미, 양수 ID는 처음에 오른쪽을 바라보는 개미를 뜻한다. ID의 절댓값은 1 이상 10^9 이하이며, 모든 개미의 ID 절댓값은 서로 다르다.

두 개미가 동시에 막대의 양쪽 끝에서 떨어지는 경우에는 ID가 더 작은 개미가 조금 더 먼저 떨어진 것으로 본다. 양의 정수 k가 주어졌을 때, k번째로 떨어지는 개미의 ID를 구하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 N, L, k가 주어진다. 다음 N개 줄에는 p_i와 a_i가 주어진다. p_i는 개미의 초기 위치이고, a_i는 그 개미의 ID이다.

위치는 항상 증가하는 순서로 주어진다. 즉, p_i < p_{i+1}이다.

제한은 다음과 같다.

• 3 ≤ N ≤ 100,000
• 10 ≤ L ≤ 5,000,000
• 1 ≤ k ≤ N
• 1 ≤ p_i ≤ L - 1
• 1 ≤ |a_i| ≤ 10^9
• 모든 |a_i|는 서로 다르다.

각 테스트 케이스마다 k번째로 떨어지는 개미의 ID를 한 줄에 출력한다. ID가 양수이면 앞에 +를 붙이지 않는다.