Falling Ants

There are N ants at distinct positions on a stick of length L millimeters. Each ant initially faces either left or right. When the start signal is given, every ant moves in its current direction at the same speed, 1 millimeter per second. Treat each ant as a point with no size.

When two ants meet at the same point, both ants immediately reverse direction and continue moving. Reversing direction takes no time. When an ant passes an end of the stick, it falls off the stick.

Each ant is represented by a signed integer ID. A negative ID means the ant initially faces left, and a positive ID means the ant initially faces right. The absolute value of an ID is between 1 and 10^9, inclusive, and all absolute ID values are distinct.

If two ants fall from the two ends of the stick at the same time, the ant with the smaller ID is considered to fall slightly earlier. Given a positive integer k, find the ID of the k-th ant to fall.

The first line contains the number of test cases T.

For each test case, the first line contains N, L, and k. Each of the next N lines contains p_i and a_i, where p_i is an ant's initial position and a_i is that ant's ID.

The positions are given in strictly increasing order: p_i < p_{i+1}.

Constraints:

• 3 ≤ N ≤ 100,000
• 10 ≤ L ≤ 5,000,000
• 1 ≤ k ≤ N
• 1 ≤ p_i ≤ L - 1
• 1 ≤ |a_i| ≤ 10^9
• All |a_i| values are distinct.

For each test case, print the ID of the k-th ant to fall. If the ID is positive, do not print a leading +.