Under construction

Still being built. Things may change

Aunts

Time limit7sMemory limit128 MB

Summary
Given altitude reports on an A by B grid where adjacent cells differ by exactly 1, find the first report that makes a consistent assignment impossible.
Level

Medium6 of 10

Topics
Math, Sorting, Implementation
Solved
No attempts yet

Problem

The organizing committee of this contest is made up of slackers who would rather do anything than prepare the contest. NN of them reported that they have to bring medicine to their aunt, so they can skip the work. All of the aunts live in an A×BA\times B grid. Each member reports their absence to Dzoni, who records the cell where the aunt's house is located and the altitude of that house.

Dzoni does not know the actual altitudes, but he knows that for any two adjacent cells in the grid, the absolute difference of their altitudes is exactly 1. After each report, Dzoni checks whether he can assign an altitude to every cell so that all reports so far are true. If he cannot (and if an assignment exists, he will always find one), the committee member who made the latest report said something really stupid. Find that member.

Input

The first line contains three integers NN, AA, and BB, where NN is the number of committee members (N≤105N \le 10^5), and AA and BB are the number of rows and columns of the grid (A,B≤109A, B \le 10^9).

Each of the following NN lines contains three integers RiR_i, CiC_i, and HiH_i, meaning the ii-th member claims that the house at row RiR_i and column CiC_i has altitude HiH_i. Here Ri≤AR_i \le A, Ci≤BC_i \le B, and 1≤Hi≤1081 \le H_i \le 10^8.

Output

Print the index of the member who said something really stupid, counting members from 1. If no such member exists, print bravo komisijo (Serbian for "congratulations, organizing committee").

Examples1

  1. Example 1

    Input
    4 3 5
    1 2 1
    2 1 3
    2 5 21
    2 2 8
    
    Expected output
    3