버스

안톤은 매일 아침 버스를 타고 출근한다.

버스 노선에는 $n$개의 정류장이 있고, 진행 순서대로 $1$번부터 $n$번까지 번호가 붙어 있다. 버스는 각 정류장에서 다음 정류장까지 1분에 이동하며, 정차 시간은 무시할 수 있다. 안톤은 첫 번째 정류장에서 타서 마지막 정류장에서 내린다.

버스에는 $m$개의 좌석이 한 줄로 놓여 있고 $1$번부터 $m$번까지 번호가 붙어 있다. 출입구에 가장 가까운 좌석이 $1$번이고 가장 먼 좌석이 $m$번이다. 각 좌석에는 한 명이 앉을 수 있고, 각 좌석 옆에는 한 명이 설 수 있다.

사람이 버스에 타면 출입구에 가장 가까운 빈 좌석에 앉는다. 모든 좌석이 차 있으면, 아무도 서 있지 않은 좌석 중 출입구에 가장 가까운 것을 찾아 그 좌석에 앉은 사람 위에 서서 견제한다. 그런 자리도 없으면 버스에서 내린다.

각 승객은 목적지 정류장에 도착할 때까지 자기 자리에 머문다. 서 있는 승객은 좌석이 비더라도 계속 서 있는다.

각 정류장에서는 그 정류장에서 내리려던 승객이 모두 내린 뒤에야 새 승객이 탄다.

안톤은 버스에 가장 먼저 탔고, 아무 좌석에나 앉아 여정이 끝날 때까지 그 자리에 머물 수 있다. 그는 버스에 누가 더 타는지 잘 알고 있으며, 각 승객이 어느 정류장에서 타고 어느 정류장에서 내리는지도 안다. 안톤이 여정 동안 자기 위에 서서 견제하는 시간의 합이 최소가 되도록 자리를 고르게 도와주자.

첫째 줄에 세 정수 $n$, $m$, $k$가 주어진다. 각각 정류장의 수, 버스 좌석의 수, 안톤을 제외한 승객의 수이다 ($2 \le n \le 10^9$, $1 \le m \le 2\cdot10^5$, $0 \le k \le 2\cdot10^5$).

다음 $k$개 줄에 두 수 $a\_i$와 $b\_i$가 주어진다. $i$번째 승객이 $a\_i$번째 정류장에서 타서 $b\_i$번째 정류장에서 내린다는 뜻이다 ($1 \le a\_i < b\_i \le n$).

한 정류장에서 여러 명이 버스에 타면 입력에 나온 순서대로 탄다.

한 줄에 두 수를 출력한다. 안톤 위에 서서 견제하는 시간의 합의 최솟값(분)과, 그 값을 위해 안톤이 앉아야 할 좌석 번호이다. 그러한 좌석이 여러 개면 출입구에 가장 가까운 것을 출력한다.