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
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
import sys

class TreeNode:
    def __init__(self, l, r):
        self.min = l              # Start of the interval
        self.max = r              # End of the interval
        self.left = None
        self.right = None
        self.height = 1           # AVL height
        self.max_end = r

class AVLTree:
    def __init__(self):
        self.root = None

    def get_height(self, node):
        return node.height if node else 0

    def update_node(self, node):
        if node:
            node.height = 1 + max(self.get_height(node.left),
                                  self.get_height(node.right))
            node.max_end = max(node.max,
                               node.left.max_end if node.left else float('-inf'),
                               node.right.max_end if node.right else float('-inf'))

    def get_balance(self, node):
        return self.get_height(node.left) - self.get_height(node.right) if node else 0

    def rotate_right(self, y):
        x = y.left
        T2 = x.right

        x.right = y
        y.left = T2

        self.update_node(y)
        self.update_node(x)
        return x

    def rotate_left(self, x):
        y = x.right
        T2 = y.left

        y.left = x
        x.right = T2

        self.update_node(x)
        self.update_node(y)
        return y

    def insert(self, node, key, value):
        if not node:
            return TreeNode(key, value)
        if key < node.min:
            node.left = self.insert(node.left, key, value)
        else:
            node.right = self.insert(node.right, key, value)

        self.update_node(node)
        balance = self.get_balance(node)

        if balance > 1 and key < node.left.min:
            return self.rotate_right(node)
        if balance < -1 and key >= node.right.min:
            return self.rotate_left(node)
        if balance > 1 and key >= node.left.min:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        if balance < -1 and key < node.right.min:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        return node

    def _min_value_node(self, node):
        current = node
        while current.left:
            current = current.left
        return current

    def delete(self, node, key):
        if not node:
            return node

        if key < node.min:
            node.left = self.delete(node.left, key)
        elif key > node.min:
            node.right = self.delete(node.right, key)
        else:
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            temp = self._min_value_node(node.right)
            node.min, node.max = temp.min, temp.max
            node.right = self.delete(node.right, temp.min)

        self.update_node(node)
        balance = self.get_balance(node)

        if balance > 1 and self.get_balance(node.left) >= 0:
            return self.rotate_right(node)
        if balance > 1 and self.get_balance(node.left) < 0:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        if balance < -1 and self.get_balance(node.right) <= 0:
            return self.rotate_left(node)
        if balance < -1 and self.get_balance(node.right) > 0:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        return node

    def find_overlaps(self, node, start, end, overlaps):
        if not node:
            return
        # Adjusted condition: merge if intervals overlap or touch.
        if node.min <= end + 1 and node.max >= start - 1:
            overlaps.append(node)
        if node.left and node.left.max_end >= start - 1:
            self.find_overlaps(node.left, start, end, overlaps)
        if node.right and node.right.min <= end + 1:
            self.find_overlaps(node.right, start, end, overlaps)

class SortedTupleTree:
    def __init__(self):
        self.tree = AVLTree()

    def insert(self, new_tuple):
        k, l = new_tuple
        overlaps = []
        # Find all nodes that overlap (or touch) the new interval
        self.tree.find_overlaps(self.tree.root, k, l, overlaps)
        # Merge all overlapping intervals
        for node in overlaps:
            k = min(k, node.min)
            l = max(l, node.max)
            self.tree.root = self.tree.delete(self.tree.root, node.min)
        # Insert the merged interval
        self.tree.root = self.tree.insert(self.tree.root, k, l)

    def find_tuple(self, num):
        node = self.tree.root
        while node:
            if node.min <= num <= node.max:
                return (node.min, node.max)
            elif num < node.min:
                node = node.left
            else:
                node = node.right
        return None

    def get_list(self):
        result = []
        self._inorder(self.tree.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append((node.min, node.max))
            self._inorder(node.right, result)


def read_input():
    n, m, s = map(int, sys.stdin.readline().strip().split())
    data = [line.rsplit(' ', 1) for line in sys.stdin.readlines()]
    data = [(int(k), int(l)) for k, l in data]

    return n, m, s, data

n, m, s, datas = read_input()


sorted_tree = SortedTupleTree()
for data in datas:
    sorted_tree.insert(data)

#print(sorted_tree.get_list())

a, b = sorted_tree.find_tuple(s)
#print(a,b)
if a == 1:
    sys.stdout.write(str(b+1))
elif b == n:
    sys.stdout.write(str(a - 1))
else:

    if abs(s - a) <= abs(s-b):
        sys.stdout.write(str(a-1))
    else:
        sys.stdout.write(str(b+1))