아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Aunts

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

요약
이웃한 칸의 높이 차가 정확히 1인 A x B 격자에서 (칸, 높이) 주장이 주어질 때, 높이 배정을 불가능하게 만드는 첫 번째 주장의 번호를 찾는다.
난이도

보통10점 중 7점

유형
수학, 그래프, BFS
정답자
아직 제출이 없습니다

문제

The organizing comittee of this contest is made from a bunch of slackers who's rather do anything than prepare a contest. As a result of this, NN of them reported that they have to bring some medicine to their aunt, so that they can get away without doing anything. All of their aunts live within a A×BA\times B matrix. They all report their absence to Dzoni, who takes a note of the cell that their aunt's house is located as well as the altitude it's located in. Dzoni doesn't know the actual altitudes, but he knows that in every two adjacent cells in the matrix, the absolute difference of their altitudes is exaclty 1. Having this in mind, after every claim made by a member of the organizing comittee he tries to reconstruct all the altitudes, meaning that he will check if its possible to assign each cell with an altitude so that all of the reports are true. If after some report, Dzoni is unable to reconstruct the altitudes (and since it's Dzoni, if it's possible, he'll be able to do it), it's obvious that the organizing comittee member that just made the report said something really stupid. Your job is to find the member who said something really stupid.

입력

In the first line of the input there are three integers NN, AA and BB denoting the number of comittee members (N≤105N\leq10^5), the number of rows and the number of columns of the matrix (A,B≤109A,B\leq10^9).

In each of the following NN lines, there are three integers R_iR\_i, C_iC\_i and H_iH\_i denoting the row, column (R_i≤A,C_i≤BR\_i\le A, C\_i\le B) and altitude (1≤H_i≤1081 \le H\_i \le 10^8) of the ii-th organizing comittee's alleged aunt's house.

출력

In the first and only line write the index of the comittee member who said something really stupid (comittee members are indexed from 11). If such a member doesn't exist, print "bravo komisijo" (meaning "congratulations, ogranizing comittee" in Serbian) without the quotation marks.

예제1

  1. 예제 1

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