A boardwalk runs a summer-long fleet of numbered concession stands. Whenever the boardwalk operator changes a stand's listed price, the change is written into a log entry containing the stand's id, the new price, and the day number on which the change takes effect. A stand keeps the boardwalk's default opening price of 10 for every day up to and including the day before its first recorded change. Given the full log and a single query day, report the price that was actually in effect at every stand that appears anywhere in the log, on that query day: the price fixed by that stand's most recent change on or before the query day, or 10 if none of its changes happened on or before that day.

Input format

• The first line contains two integers n and q: the number of log entries and the query day.
• Each of the next n lines contains three integers standId, newPrice, and day, describing one log entry: on day day, stand standId's price became newPrice. No two log entries share the same (standId, day) pair.

Output format

Print one line per distinct standId that appears anywhere in the log, in strictly increasing order of standId. Each line contains the standId followed by a single space and its price on day q.

Constraints

• 1 <= n <= 2 * 10^4
• 1 <= standId <= 10^4
• 1 <= newPrice <= 10^4
• 1 <= day <= 10^4
• 1 <= q <= 10^4

3 4
1 20 2
1 15 4
2 30 1

1 15
2 30

2 1
5 40 3
5 25 5

5 10