Guild Apprentice Abandonment Audit

EasyHash setFilteringSet operationsMembership2 sample tests6 hidden tests

The Cartographers' Guild keeps a roster of apprentices. Each apprentice has a unique badge number, a monthly stipend, and the badge number of the mentor they were assigned when they joined (or a special marker showing that no mentor was ever assigned). Over the years many original mentors have left the guild for good, meaning their badge number no longer belongs to anyone currently on the roster. Guild leadership wants to flag every apprentice who is both underpaid — stipend strictly below a chosen guild minimum — and effectively unsupervised because their assigned mentor's badge number does not belong to any apprentice currently on the roster. An apprentice who was never assigned a mentor at all must never be flagged, no matter their stipend.

Given the roster and the guild minimum stipend, list the badge numbers of every apprentice who should be flagged.

Input format

Line 1: two integers n and T — the number of apprentices and the guild minimum stipend. Each of the next n lines contains three integers badge_i stipend_i mentor_i — apprentice i's badge number, monthly stipend, and mentor's badge number, or -1 if no mentor was assigned.

Output format

Print the flagged badge numbers, in ascending order, space-separated on one line. Print an empty line if no apprentice is flagged.

Constraints

1 <= n <= 2000
All badge_i are distinct, 1 <= badge_i <= 10^9
0 <= stipend_i <= 10^6
0 <= T <= 10^6
mentor_i = -1, or 1 <= mentor_i <= 10^9 (mentor_i need not equal any badge_i on the roster)

Examples

Example 1

Input

5 30000
101 60000 -1
102 25000 -1
103 15000 101
104 40000 199
105 20000 199

Expected

Explanation

Apprentices 101 and 102 have no mentor (-1), so they are never flagged. Apprentice 103's mentor (101) is still on the roster, so 103 is not flagged. Apprentice 104's mentor (199) has left the guild, but 104's stipend (40000) is not below 30000, so 104 is not flagged. Apprentice 105's mentor (199) has also left, and 105's stipend (20000) is below 30000, so 105 is flagged. Output: 105.

Example 2

Input

4 50000
201 10000 -1
202 45000 999
203 60000 999
204 20000 201

Expected

Explanation

Apprentice 201 has no mentor, so it is never flagged. Apprentice 202's mentor (999) is absent from the roster and its stipend (45000) is below 50000, so 202 is flagged. Apprentice 203's mentor (999) is also absent, but its stipend (60000) is not below 50000, so 203 is not flagged. Apprentice 204's mentor (201) is present on the roster, so 204 is not flagged. Output: 202.

Ready to solve this?