32344번 - 유물 발굴

문제

홍익대학교 운동장은 $R$행 $C$열 크기의 격자 모양이다. 이런 홍익대학교 운동장에서 학계를 뒤흔들만한 유물의 조각들이 발견되었다. 하지만 한 번에 여러 유물을 발굴하는 것은 불가능하다. 따라서, 유물의 예상 크기를 조사해서 예상 크기가 가장 큰 유물을 먼저 발굴하려고 한다. 만약 그런 유물이 여러 개라면, 번호가 가장 작은 것을 먼저 발굴하려고 한다.

조각은 1ドル \times 1$ 크기이고, 같은 위치에 여러 조각이 존재할 수 있다. 유물의 예상 크기는 해당 유물의 조각들을 한번에 묶을 수 있는 가장 작은 직사각형의 크기이다. 직사각형의 모든 변은 운동장과 평행해야 한다.

가장 먼저 발굴하는 유물의 번호와 예상 크기를 알아내보자!

입력

첫째 줄에 홍익대학교 운동장의 세로 길이를 나타내는 정수 $R,ドル 가로 길이를 나타내는 정수 $C$가 공백으로 구분되어 주어진다. $(1 \leq R, C \leq 100,000円)$

둘째 줄에 조각의 개수 정수 $N$이 주어진다. $(1 \leq N \leq 100,000円)$

셋째 줄부터 $N$개의 줄에 걸쳐 정수 $a_i,ドル $v_i,ドル $h_i$가 공백으로 구분되어 주어진다. $(1 \leq a_i \leq N;$ 1ドル \leq v_i \leq R; 1 \leq h_i \leq C)$ 이는 $a_i$번 유물의 조각이 $v_i$행 $h_i$열에 존재함을 의미한다.

출력

첫째 줄에 가장 먼저 발굴하는 유물의 번호와 예상 크기를 공백으로 구분하여 출력한다.

제한

힌트