만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이모들

시간 제한7초메모리 제한128 MB

요약
인접한 칸의 고도 차가 정확히 1인 A×B 격자에서, 처음으로 모든 보고를 만족시킬 수 없게 만드는 위원의 번호를 찾습니다.
난이도

보통10점 중 6점

유형
수학, 정렬, 구현
정답자
아직 제출이 없습니다

문제

이 대회의 운영위원회는 대회 준비보다 다른 무엇이든 하고 싶어 하는 게으른 사람들로 구성되어 있다. 그중 NN명이 이모에게 약을 가져다 드려야 한다고 보고하고, 그 핑계로 작업을 빠지려 한다. 이모들은 모두 A×BA\times B 크기의 격자 안에 살고 있다. 각 위원은 Dzoni에게 불참을 알리고, Dzoni는 이모 집이 있는 칸과 그 집의 고도를 기록한다.

Dzoni는 실제 고도를 모르지만, 격자에서 인접한 두 칸의 고도 차이의 절댓값이 정확히 1이라는 것은 알고 있다. 보고가 들어올 때마다 Dzoni는 지금까지의 모든 보고가 참이 되도록 각 칸에 고도를 배정할 수 있는지 확인한다. 배정할 수 없으면(배정이 가능하다면 Dzoni는 반드시 찾아낸다), 방금 보고한 위원이 엉뚱한 말을 한 것이다. 그 위원을 찾아라.

입력

첫째 줄에 세 정수 NN, AA, BB가 주어진다. NN은 위원의 수(N≤105N \le 10^5)이고, AA와 BB는 격자의 행 수와 열 수이다(A,B≤109A, B \le 10^9).

이어지는 NN개의 줄에는 세 정수 RiR_i, CiC_i, HiH_i가 주어진다. 이는 ii번째 위원이 행 RiR_i, 열 CiC_i에 있는 집의 고도가 HiH_i라고 주장한다는 뜻이다. 여기서 Ri≤AR_i \le A, Ci≤BC_i \le B, 1≤Hi≤1081 \le H_i \le 10^8이다.

출력

엉뚱한 말을 한 위원의 번호를 1부터 세어 출력한다. 그런 위원이 없으면 bravo komisijo(세르비아어로 '운영위원회 여러분, 축하합니다'라는 뜻)를 출력한다.

예제1

  1. 예제 1

    입력
    4 3 5
    1 2 1
    2 1 3
    2 5 21
    2 2 8
    
    예상 출력
    3