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
#include <bits/stdc++.h>
using namespace std;
#define V vector
#define Q queue
#define PQ priority_queue
#define ST stack
#define UMAP unordered_map
typedef long long LL;
typedef pair<int, int> PII;
typedef V<int> VI;
typedef V<V<int>> VVI;

constexpr LL INF = 1'000'000'000'000'000'007;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    LL n, m, s;
    cin >> n >> m >> s;
    V<pair<LL,LL>> ranges;
    for (int i = 0; i < m; ++i) {
        LL a, b;
        cin >> a >> b;
        ranges.push_back({a, b});
    } 
    ranges.push_back({0,0});
    ranges.push_back({n+1,n+1});
    sort(ranges.begin(), ranges.end());
    V<pair<LL,LL>> merged_ranges;
    merged_ranges.push_back(ranges[0]);
    for (int i = 1; i < ranges.size(); ++i) {
        if (merged_ranges[merged_ranges.size()-1].second+1 == ranges[i].first) {
            auto a = merged_ranges[merged_ranges.size()-1];
            merged_ranges.pop_back();
            merged_ranges.push_back({a.first, ranges[i].second});
        } else {
            merged_ranges.push_back(ranges[i]);
        }
    }

    V<pair<LL,LL>> free_spaces;
    for (int i = 0; i < merged_ranges.size()-1; ++i) {
        free_spaces.push_back({merged_ranges[i].second+1, merged_ranges[i+1].first-1});
    }

    LL best_pos = -1, best_val = INF;
    for (int i = 0; i < free_spaces.size(); ++i) {
        LL dist1 = abs(free_spaces[i].first - s);
        if (dist1 < best_val) {
            best_pos = free_spaces[i].first;
            best_val = dist1;
        }
        LL dist2 = abs(free_spaces[i].second - s);
        if (dist2 < best_val) {
            best_pos = free_spaces[i].second;
            best_val = dist2;
        }
    }
    
    cout << best_pos << '\n';

    return 0;
}