Avtobus

Hər səhər Anton işə avtobusla gedir.

Avtobus marşrutu $n$ dayanacaqdan ibarətdir, dayanacaqlar $1$-dən $n$-ə qədər nömrələnib və ardıcıllıqla düzülüb. Avtobus hər dayanacaqdan növbəti dayanacağa bir dəqiqəyə gedir və dayanacaqlarda dayanma vaxtını nəzərə almamaq olar. Anton birinci dayanacaqda minib, sonuncu dayanacaqda düşür.

Avtobusda $m$ oturacaq var, oturacaqlar bir sırada yerləşir və $1$-dən $m$-ə qədər nömrələnib. Girişə ən yaxın oturacaq $1$ nömrəli, ən uzaq isə $m$ nömrəlidir. Hər oturacaqda bir sərnişin otura bilər və hər oturacağın yanında bir sərnişin dayana bilər. Avtobusa daxil olan şəxs girişə ən yaxın boş oturacaqda oturur. Əgər bütün oturacaqlar doludursa, o, girişə ən yaxın oturacağın yanında heç kimin dayanmadığı yeri axtarır və orada oturan şəxsin başı üstündə dayanır. Əgər belə yer yoxdursa, o, avtobusdan çıxır.

Hər sərnişin lazım olan dayanacağa çatana qədər öz yerində qalır. Dayanan sərnişin oturacaq boşalsa belə, dayanmağa davam edir.

Hər dayanacaqda əvvəlcə həmin dayanacaqda düşmək istəyən bütün sərnişinlər avtobusdan çıxır və yalnız sonra yeniləri daxil olur.

Anton avtobusa birinci minib, o, istənilən oturacaqda otura bilər və səyahət sonuna qədər orada qala bilər. O, avtobusda kimlərin olacağını yaxşı bilir, hər sərnişin haqqında Anton bilir ki, hansı dayanacaqda avtobusa minəcək və hansı dayanacaqda düşəcək. Antona elə bir yer seçməyə kömək edin ki, səyahət zamanı onun başı üstündə mümkün qədər az sərnişin dayansın.

Giriş verilənləri

Giriş məlumatlarının birinci sətirində üç tam ədəd $n,m$ və $k(2\le n\le 10^9,1\le m\le 2\cdot 10^5,0\le k\le 2\cdot 10^5)$ — dayanacaqların sayı, avtobusdakı oturacaqların sayı və Anton istisna olmaqla sərnişinlərin sayı verilib.

Növbəti $k$ sətirdə hər biri iki ədəd $a_i$ və $b_i$ verilib, bu $i$-ci sərnişinin $a_i$-ci dayanacaqda avtobusa minəcəyini və $b_i$-ci dayanacaqda düşəcəyini göstərir ($1\le a_i<b_i\le n)$.

Əgər bir dayanacaqda avtobusa bir neçə nəfər minirsə, onlar giriş məlumatlarında göstərilən ardıcıllıqla daxil olurlar.

Çıxış verilənləri

Bir sətirdə iki ədəd çıxarın — Antonun başı üstündə dayanılacaq minimal ümumi vaxt dəqiqələrlə və bunun üçün oturmalı olduğu yerin nömrəsi. Əgər belə yerlər bir neçə varsa, girişə ən yaxın olanı çıxarın.

Nümunələr