33820번 - Szkoła 다국어

문제

Algolina i Bajtazar przeprowadzają się do Bajtowa i szukają dla siebie nowego lokum. W Bajtowie jest tylko jedna, długa droga, przy której stoi $n$ budynków. Ponumerujmy je liczbami od 1ドル$ do $n$. Część z nich oferuje mieszkania na wynajem, ale niektóre z nich są w pełni zamieszkałe (o takich budynkach będziemy mówić, że są zajęte).

Zajęte budynki możemy opisać za pomocą $m$ rozłącznych przedziałów numerów $[l_i , r_i ]$. Oznacza to, że jeśli numer budynku $x$ spełnia $l_i ≤ x ≤ r_i,ドル to budynek o numerze $x$ jest zajęty.

Algolina i Bajtazar muszą rozważyć wiele czynników przy wyborze ich lokum, a jednym z nich jest bliskość szkoły, do której będzie chodził ich syn Bajtek. Szkoła ta znajduje się w budynku o numerze $s$ (gwarantujemy, że ten budynek jest zajęty).

Bajtek jest jeszcze mały i rodzice nie chcą, aby musiał zbyt daleko jechać do szkoły. Z tego powodu chcą wybrać wolny budynek, który leży jak najbliżej przyszłej szkoły Bajtka. Zakładamy, że odległości między kolejnymi budynkami są zawsze takie same. To oznacza, że rodzice Bajtka chcą znaleźć budynek o numerze $p,ドル taki że $|s - p|$ jest jak najmniejsze.

입력

W pierwszym wierszu znajdują się trzy liczby całkowite $n,ドル $m$ oraz $s$ (2ドル ≤ n ≤ 10^{12},ドル 1ドル ≤ m ≤ 1000,ドル 1ドル ≤ s ≤ n$), oznaczające odpowiednio: liczbę budynków w Bajtowie, liczbę przedziałów numerów zajętych budynków oraz numer budynku, w którym znajduje się przyszła szkoła Bajtka.

W następnych $m$ wierszach znajdują się opisy kolejnych przedziałów numerów zajętych budynków, gdzie $i$-ty z tych opisów składa się z dwóch liczb całkowitych $l_i,ドル $r_i$ (1ドル ≤ l_i ≤ r_i ≤ n$). Dla każdej pary $i,ドル $j$ (1ドル ≤ i < j ≤ m$) zachodzi $r_i < l_j$ lub $r_j < l_i,ドル co oznacza, że podane przedziały są rozłączne. Dodatkowo gwarantujemy, że w Bajtowie istnieje budynek, który jest wolny.

출력

Na wyjściu powinna znaleźć się jedna liczba całkowita $p$ oznaczająca numer budynku, w którym powinni zamieszkać Algolina i Bajtazar, aby zminimalizować $|s - p|$. Jeśli istnieje wiele takich liczb $p,ドル należy wypisać tę, która jest najmniejsza.

제한

노트

Wyjaśnienie przykładów: W pierwszym przykładzie budynki o numerach $p = 4$ oraz $p = 10$ są najbliższymi do szkoły, wolnymi budynkami. Zatem odpowiedź to $p = 4,ドル ponieważ z wielu wartości $p$ minimalizujących $|s - p|$ mamy wybrać tę najmniejszą.

W drugim przykładzie jedyny wolny budynek osiągający najmniejszą odległość do szkoły (równą 5ドル$) to budynek o numerze 14ドル$.