At the end of a busy day, The Chef and his assistants play a game together. The game is not just for fun but also used to decide who will have to clean the kitchen. The Chef is a Game Master, so his concern is how to manage the game but not how to win the game like his assistants do.

The game requires players to find the only ball under one of the N cups after their positions are changed in a special way. At the beginning of the game, The Chef places N cups in a row and put a ball under the C-th cup from the left (the cups are numbered from 1 to N). All players can see the initial position of the ball. Then Chef performs Q flip operations. Each flip operation is defined by two integers L and R such that 1 ≤ L ≤ R ≤ N and consists in reversing the segment [L, R] of cups. Namely, Chef swaps L-th and R-th cups, (L+1)-th and (R−1)-th cups, and so on. After performing all the operations Chef asks his assistants to choose a cup that they think the ball is under it. Who can guess the position of the ball will win the game, and of course, the others will have to clean the kitchen.

The Chef doesn't want to check all the N cups at the end of the game. He notes down the value of C and the pairs (L, R) and asked you, the mastered programmer, to determine the cup that contains the ball.

------ Input ------ 

The first line of the input contains a single integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains three space-separated integers N, C and Q, denoting the total number of cups, the initial position of the ball and the number of flip operations Chef will perform. Each of the following Q lines contains two space-separated integers L and R, denoting the ends of the segment of the current flip operation.

------ Output ------ 

For each test case output on a separate line the final position of the ball.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 100000 (10^{5})$
$1 ≤ C ≤ N$
$1 ≤ Q ≤ 10000 (10^{4})$
$1 ≤ L ≤ R ≤ N$

----- Sample Input 1 ------ 
1
5 2 3
1 4
3 5
1 5
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 

The row of cups at the beginning of the game and after each flip is shown below. Here '-' means an empty cup and 'B' is the cup that hides the ball, the segment of flip is marked bold.
-B---
--B--
----B
B----

Difficulty: EASY

Starter code:

Solutions:
T = int(input())
for i in range(T):
	(n, c, q) = map(int, input().split())
	for i in range(q):
		(l, r) = map(int, input().split())
		if c <= r and c >= l:
			c = r - (c - l)
	print(c)


for tc in range(int(input())):
	(n, c, q) = map(int, input().split())
	flip = []
	(l, r) = (0, 0)
	for i in range(q):
		(l, r) = map(int, input().split())
		if c >= l and c <= r:
			pos = c - l
			newpos = r - pos
			c = newpos
	print(c)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	x = b
	for i in range(c):
		(xx, xxx) = map(int, input().split())
		if xx <= x <= xxx:
			x = xxx + (xx - x)
	print(x)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	for _ in range(q):
		(l, r) = map(int, input().split())
		if c >= l and c <= r:
			c = l + r - c
	print(c)


for t in range(int(input())):
	(n, c, q) = map(int, input().split())
	c = c - 1
	for i in range(q):
		(l, r) = map(int, input().split())
		(l, r) = (l - 1, r - 1)
		if l <= c <= r:
			m = (l + r) // 2
			if (l + r) % 2:
				d = abs(c - m)
				if c <= m:
					c = m + d + 1
				else:
					c = m - d + 1
			else:
				d = abs(c - m)
				if d == 0:
					continue
				elif c < m:
					c = m + d
				else:
					c = m - d
	print(c + 1)


t = int(input())
for _ in range(t):
	(n, c, q) = map(int, input().split())
	for _ in range(q):
		(i, j) = map(int, input().split())
		if c >= i and c <= j:
			c = j + i - c
	print(c)


for x in range(int(input())):
	(n, c, q) = map(int, input().split())
	for i in range(q):
		(a, b) = map(int, input().split())
		if c >= a and c <= b:
			c = a + b - c
	print(c)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	for i in range(q):
		(a, b) = map(int, input().split())
		if a <= c <= b:
			initial = c - a
			final = b - initial
			c = final
		else:
			None
	print(c)


try:
	for _ in range(int(input())):
		(a, b, c) = map(int, input().split())
		for i in range(c):
			(p, q) = map(int, input().split())
			if b >= p and b <= q:
				b = q - b + p
		print(b)
except:
	pass


t = input()
for x in range(0, int(t)):
	input_data = list(map(int, input().split(' ')))
	num_cups = input_data[0]
	posin = input_data[1]
	num_flip = input_data[2]
	for item in range(num_flip):
		(left, right) = map(int, input().split(' '))
		if left <= posin <= right:
			dif = posin - left
			posin = right - dif
	print(posin)


t = int(input())
for i in range(t):
	(n, c, q) = map(int, input().split())
	for i in range(q):
		(l, r) = map(int, input().split())
		if l <= c <= r:
			c = l + r - c
	print(c)


for _ in range(int(input())):
	(b, c, q) = map(int, input().split())
	l = [0] * b
	l[c - 1] = 1
	for i in range(q):
		(x, y) = map(int, input().split())
		if x <= c and c <= y:
			l[c - 1] = 0
			c = y - c + x
			l[c - 1] = 1
	print(l.index(1) + 1)


def cups(n, l, r, c):
	if c >= l and c <= r:
		tem = c - l
		pos = r - tem
		return pos
	else:
		pos = c
		return pos
try:
	t = int(input())
	while t:
		t -= 1
		(n, c, q) = map(int, input().split())
		for i in range(q):
			(l, r) = map(int, input().split())
			ret = cups(n, l, r, c)
			c = ret
		print(c)
except:
	pass


for t in range(int(input())):
	(N, C, Q) = [int(x) for x in input().split()]
	for i in range(Q):
		(L, R) = [int(x) for x in input().split()]
		if L <= C <= (L + R) // 2:
			C = R - (C - L)
		elif (L + R) // 2 < C <= R:
			C = L + (R - C)
	print(C)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	for i in range(q):
		(l, r) = map(int, input().split())
		if l <= c <= r:
			initial = c - l
			c = r - initial
	print(c)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	k = c
	for i in range(q):
		(a, b) = map(int, input().split())
		if k >= a and k <= b:
			k = a + b - k
	print(k)


for _ in range(int(input())):
	(a, b, t) = map(int, input().split())
	c = b
	for i in range(t):
		(l, m) = map(int, input().split())
		if c <= m and c >= l:
			c = l - c + m
	print(c)


T = int(input())
for i in range(T):
	(N, C, Q) = map(int, input().split())
	ball_pos = C
	for j in range(Q):
		(L, R) = map(int, input().split())
		if ball_pos >= L and ball_pos <= R:
			ball_pos = ball_pos - (ball_pos - L) + (R - ball_pos)
	print(ball_pos)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	cup = [0] * n
	cup[c - 1] = 1
	for i in range(q):
		(l, r) = map(int, input().split())
		if c >= l and c <= r:
			c = r - (c - l)
	print(c)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	l = [i for i in range(n + 1)]
	l[0] = 0
	for k in range(q):
		(q1, q2) = map(int, input().split())
		if q1 <= c <= q2:
			c = q1 + q2 - c
	print(l.index(c))


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	for i in range(q):
		(a, b) = map(int, input().split())
		if c in range(a, b + 1):
			c = b - c + a
	print(c)


from sys import stdin, stdout
t = int(stdin.readline().rstrip())
while t > 0:
	(n, c, q) = map(int, stdin.readline().rstrip().split())
	lst = [0] * n
	lst[c - 1] = 1
	p = c - 1
	while q > 0:
		(a, b) = map(int, stdin.readline().rstrip().split())
		if a - 1 <= p <= b - 1:
			(lst[p], lst[b - p - 1 + a - 1]) = (lst[b - p - 1 + a - 1], lst[p])
			p = b - p - 1 + a - 1
		q -= 1
	print(p + 1)
	t -= 1


for i in range(int(input())):
	(n, c, q) = map(int, input().split())
	for j in range(q):
		(l, r) = map(int, input().split())
		if c in range(l, r + 1):
			c = l + r - c
	print(c)


2
4
t = int(input())
while t > 0:
	numbers = list(map(int, input().split()))
	n = numbers[0]
	c = numbers[1]
	s = numbers[2]
	i = 0
	while s > 0:
		numbers = list(map(int, input().split()))
		l = numbers[0]
		r = numbers[1]
		if c >= l and c <= r:
			temp = c - l
			c = r - temp
		s = s - 1
	print(c)
	t = t - 1


for _ in range(int(input())):
	(n, ip, nf) = map(int, input().split())
	for _ in range(nf):
		(l, r) = map(int, input().split())
		if l <= ip <= r:
			ip = l + r - ip
	print(ip)


a = int(input(''))
for i in range(a):
	(n, c, q) = [int(x) for x in input('').split()]
	l = [0] * n
	l[c - 1] = 1
	for j in range(q):
		(x, y) = [int(x) for x in input('').split()]
		if x <= c and c <= y:
			l[c - 1] = 0
			c = y - c + x
			l[c - 1] = 1
	print(l.index(1) + 1)


tc = int(input())
for _ in range(tc):
	(n, c, q) = [int(x) for x in input().split()]
	arr = []
	for i in range(q):
		temp = [int(x) for x in input().split()]
		arr.append(temp)
	for x in arr:
		if c >= x[0] and c <= x[1]:
			c = x[1] - c + x[0]
	print(c)


for i in range(int(input())):
	(n, c, q) = [int(x) for x in input().split()]
	for j in range(q):
		(l, r) = [int(x) for x in input().split()]
		if l <= c and c <= r:
			c = l + r - c
	print(c)


t = int(input())
for _ in range(t):
	(n, c, q) = map(int, input().split())
	row = [False] * (n + 1)
	row[c] = True
	for _ in range(q):
		(i, j) = map(int, input().split())
		if c >= i and c <= j:
			c = j - abs(i - c)
	print(c)


for _ in range(int(input())):
	(n, p, r) = map(int, input().split())
	for i in range(r):
		(a, b) = map(int, input().split())
		if p in range(a, b + 1):
			k = p - a
			p = b - k
	print(p)


for t in range(int(input())):
	(n, c, o) = map(int, input().split())
	for i in range(0, o):
		(l, r) = map(int, input().split())
		if l <= c <= r:
			c = l + r - c
	print(c)


t = int(input())
for x in range(t):
	(n, c, q) = map(int, input().split())
	a = []
	for j in range(q):
		(l, r) = map(int, input().split())
		if l <= c and c <= r:
			c = r - c + l
	print(c)


t = int(input())
for i in range(t):
	(N, C, Q) = map(int, input().split())
	for j in range(Q):
		(L, R) = map(int, input().split())
		if L <= C <= R:
			C = R - C + L
	print(C)


ujju = int(input())
for t in range(ujju):
	(m, u, p) = map(int, input().split())
	u = u - 1
	for i in range(p):
		(h, r) = map(int, input().split())
		(h, r) = (h - 1, r - 1)
		if h <= u <= r:
			k = (h + r) // 2
			if (h + r) % 2:
				d = abs(u - k)
				if u <= k:
					u = k + d + 1
				else:
					u = k - d + 1
			else:
				d = abs(u - k)
				if d == 0:
					continue
				elif u < k:
					u = k + d
				else:
					u = k - d
	print(u + 1)


t = int(input())
for _ in range(t):
	(n, c, q) = map(int, input().split())
	while q:
		(l, r) = map(int, input().split())
		if l <= c and r >= c:
			c = l + r - c
		q -= 1
	print(c)


from sys import stdin

def main():
	T = int(stdin.readline().strip())
	for _ in range(T):
		(N, C, Q) = map(int, stdin.readline().strip().split())
		C -= 1
		for loop in range(Q):
			(first, last) = map(int, stdin.readline().strip().split())
			first -= 1
			last -= 1
			if first <= C <= last:
				diff = C - first
				C = last - diff
		print(C + 1)
main()


subtask = int(input())
for _ in range(subtask):
	(N, C, Q) = map(int, input().split())
	cups = ['*'] * N
	for i in range(Q):
		(L, R) = [int(i) for i in input().split()]
		if C in range(L, R + 1):
			C = L + R - C
	print(C)


tc = int(input())
for _ in range(tc):
	(n, c, q) = map(int, input().split())
	for i in range(q):
		(l, r) = map(int, input().split())
		if c in range(l, r + 1):
			c = l + (r - c)
	print(c)


t = int(input())
while t != 0:
	(n, c, q) = map(int, input().split())
	while q != 0:
		(l, r) = map(int, input().split())
		if c >= l and c <= r:
			x = c - l + 1
			c = r - x + 1
		q -= 1
	print(c)
	t -= 1


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = []
	for _ in range(q):
		s.append(list(map(int, input().split())))
	pointer = c - 1
	for p in s:
		if pointer >= p[0] - 1 and pointer <= p[1] - 1:
			x = pointer - (p[0] - 1)
			pointer = p[1] - 1 - x
	print(pointer + 1)


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	for x in range(b):
		(m, n) = map(int, input().split())
		if a >= m and a <= n:
			a = m + n - a
	print(a)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	for i in range(q):
		(l, r) = map(int, input().split())
		if c < l or c > r:
			continue
		elif c >= l and c <= r:
			sub = c - l
			c = r - sub
	print(c)


for _ in range(int(input())):
	(N, C, Q) = map(int, input().split())
	for __ in range(Q):
		(L, R) = map(int, input().split())
		if L <= C <= R:
			delta = C - L
			C = R - delta
	print(C)


T = int(input())
for i in range(T):
	(N, C, Q) = (int(n) for n in input().split())
	for j in range(Q):
		(L, R) = [int(n) for n in input().split()]
		if L <= C <= R:
			C = L + R - C
	print(C)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	for t in range(q):
		(a, b) = map(int, input().split())
		if c >= a and c <= b:
			c = b - (c - a)
	print(c)


t = int(input())
for ewe in range(t):
	(n, c, q) = map(int, input().split())
	while q > 0:
		(pos1, pos2) = map(int, input().split())
		if pos1 <= c and pos2 >= c:
			c = pos1 + pos2 - c
		q = q - 1
	print(c)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, c, q) = list(map(int, input().split()))
	for i in range(q):
		(l, r) = list(map(int, input().split()))
		if l <= c <= r:
			c = l + r - c
	print(c)


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	for _ in range(q):
		(left, right) = map(int, input().split())
		if left <= c <= right:
			c = right - c + left
	print(c)


test_cnt = int(input())
from math import ceil
for elements in range(test_cnt):
	input_data = list(map(int, input().split(' ')))
	num_cups = input_data[0]
	posin = input_data[1]
	num_flip = input_data[2]
	for item in range(num_flip):
		(left, right) = map(int, input().split(' '))
		if left <= posin <= right:
			dif = posin - left
			posin = right - dif
	print(posin)