D. Queue Mix-Up
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

BLACKPINK has set up a digital queue of length $$$N$$$ ($$$N \le 10^9$$$) initially containing the numbers $$$1 \ldots N$$$ for fans to buy tickets to their upcoming concert. One night, however, someone hacked into the system and corrupted the queue order.

In each of $$$K$$$ operations ($$$K \le 3 \cdot 10^5$$$), the contiguous range of the queue from index $$$l$$$ to index $$$r$$$, inclusive, is reversed, and then every number in that range is negated.

Regina wants to know the value at index $$$i$$$ after all operations have been performed. All indices in this problem are one-indexed.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.

For each test case, the first line contains three integers $$$N$$$ ($$$1 \le N \le 10^9$$$), $$$K$$$ ($$$1 \le K \le 3 \cdot 10^5$$$), and $$$i$$$ ($$$1 \le i \le N$$$), representing the length of the array, the number of operations, and the index to query, respectively.

The following $$$K$$$ lines each contain two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le N$$$), representing the inclusive endpoints of a range. For each operation, the subarray from index $$$l$$$ to index $$$r$$$ is reversed, and then every value in that range is negated.

It is guaranteed that the sum of $$$K$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer representing the value of the array at index $$$i$$$ after all of the operations have been performed.

Example
Input
2
5 3 3
3 4
1 2
1 4
5 3 1
2 2
2 3
4 4
Output
1
1
Note

In the first test case, the array undergoes three operations:

  • The range $$$[3,4]$$$ is reversed and negated: $$$[1,2,3,4,5]$$$ becomes $$$[1,2,-4,-3,5]$$$.
  • The range $$$[1,2]$$$ is reversed and negated: $$$[1,2,-4,-3,5]$$$ becomes $$$[-2,-1,-4,-3,5]$$$.
  • The range $$$[1,4]$$$ is reversed and negated: $$$[-2,-1,-4,-3,5]$$$ becomes $$$[3,4,1,2,5]$$$.

The element at index $$$3$$$ is $$$1$$$, so the answer is $$$1$$$.

In the second test case, the array undergoes three operations:

  • The range $$$[2,2]$$$ is reversed and negated: $$$[1,2,3,4,5]$$$ becomes $$$[1,-2,3,4,5]$$$.
  • The range $$$[2,3]$$$ is reversed and negated: $$$[1,-2,3,4,5]$$$ becomes $$$[1,-3,2,4,5]$$$.
  • The range $$$[4,4]$$$ is reversed and negated: $$$[1,-3,2,4,5]$$$ becomes $$$[1,-3,2,-4,5]$$$.

The element at index $$$1$$$ is $$$1$$$, so the answer is $$$1$$$.