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
#!/usr/bin/env python3

from typing import cast


n, m, s = map(int, input().split())

data = cast(
    list[tuple[int, int]],
    list(map(lambda ign: tuple(map(int, input().split())), range(m))),
)
data.append((0, 0))
data.append((n + 1, n + 1))
data.sort()

opt = -(10**15)

lastOpen = 0

dual: list[tuple[int, int]] = []

for left, right in data:
    if lastOpen != left:
        dual.append((lastOpen, left - 1))
    lastOpen = right + 1

for left, right in dual:
    if abs(opt - s) > abs(left - s):
        opt = left
    if abs(opt - s) > abs(right - s):
        opt = right

print(opt)