1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from bisect import bisect_left,insort
ll=[]
inf = 10**12+5

n,m,s = [int(x) for x in input().split()]

for _ in range(m):
	a,b = [int(el) for el in input().split()]
	insort(ll,(a,b))

insort(ll,(-1,inf))
insort(ll,(0,inf))
insort(ll,(inf,inf))



def solve(n,s,ll):
    idx = bisect_left(ll,(s,inf))
    low = ll[idx-1][0]
    high = ll[idx-1][1]
    l = idx-2 #po lewej od
    r = idx # po prawej od
    ans = inf
    left_test = True
    right_test = True
    while True:
        if left_test:
            
            if (ll[l][1] != low-1): #nie ma łączności
                if low != 1: #nie jestesmy na skraju
                    if abs(low-1-s) < abs(ans-s):
                        ans = low-1
                    elif abs(low-1-s) == abs(ans-s):
                        ans = min(low-1,ans)
                        left_test = False
                left_test = False
                    

            elif abs(s - ans) < abs(ll[l][0]-1-s):
                left_test = False
        
            else: #update ciagly
                low = ll[l][0]
                l -= 1
        
        if right_test:

            if (ll[r][0] != high+1):
                if high != n: #nie na skraju
                    if abs(high+1-s) < abs(ans-s):
                        ans = high+1
                    elif abs(high+1-s) == abs(ans-s):
                        ans = min(high+1,ans)
                    
                right_test = False
            
            elif abs(s - ans) < abs(ll[r][1]+1-s):
                right_test = False

            else:
                high = ll[r][1]
                r += 1
                
        if not (left_test or right_test):
            return ans

print(solve(n,s,ll))