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
#include <iostream>

void merge(unsigned long long arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    unsigned long long *L = new unsigned long long[n1];
    unsigned long long *R = new unsigned long long[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];

    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];

    delete[] L;
    delete[] R;
}

void mergeSort(unsigned long long arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long n, m, s;
    std::cin >> n >> m >> s;

    unsigned long long* boundaries = new unsigned long long[2 * m];
    
    for (int i = 0; i < m; i++) {
        unsigned long long l, r;
        std::cin >> l >> r;
        boundaries[2 * i]     = l;
        boundaries[2 * i + 1] = r;
    }
    
    mergeSort(boundaries, 0, 2 * m - 1);
    

    long long bestCandidate = -1;
    long long bestDiff = 0x7FFFFFFFFFFFFFFFLL; 

    // Check gap before the first interval.
    if (boundaries[0] > 1ULL) {
        long long candidate = boundaries[0] - 1;
        long long diff = (candidate > s) ? candidate - s : s - candidate;
        bestDiff = diff;
        bestCandidate = candidate;
    }
    
    for (int i = 1; i < m; i++) {
        if (boundaries[2 * i] - boundaries[2 * i - 1] > 1ULL) {
            long long candidateLow = boundaries[2 * i - 1] + 1;
            long long candidateHigh = boundaries[2 * i] - 1;
            long long diffLow = (candidateLow > s) ? candidateLow - s : s - candidateLow;
            long long diffHigh = (candidateHigh > s) ? candidateHigh - s : s - candidateHigh;
            if (diffLow < bestDiff) {
                bestDiff = diffLow;
                bestCandidate = candidateLow;
            }
            if (diffHigh < bestDiff) {
                bestDiff = diffHigh;
                bestCandidate = candidateHigh;
            }
        }
    }
    
    if (boundaries[2 * m - 1] < (unsigned long long)n) {
        long long candidate = boundaries[2 * m - 1] + 1;
        long long diff = (candidate > s) ? candidate - s : s - candidate;
        if (diff < bestDiff) {
            bestDiff = diff;
            bestCandidate = candidate;
        }
    }
    
    std::cout << bestCandidate;

    delete[] boundaries;
    return 0;
}