#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/03

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/03

Repovive

High-Volume Account Filter - MAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG03. High-Volume Account Filter

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Given a list of transaction logs, where each log contains a sender ID, a recipient ID, and a transaction amount, find all user IDs that have a number of transactions greater than or equal to a given threshold.

A transaction involves two users — the sender and the recipient. Each transaction increments the count of both the sender and the recipient. However, if the sender and recipient are the same user (a self-transaction), it only counts as one transaction for that user.

Return the qualifying user IDs sorted in ascending numeric order.

If no user meets the threshold, output an empty line.

Constraints

$1 \le n \le 10^5$
$1 \le threshold \le n$
User IDs are numeric strings
$1 \le amount \le 10^5$

Input

\begin{array}{l} n \quad t \\ s_0 \quad r_0 \quad a_0 \\ s_1 \quad r_1 \quad a_1 \\ \vdots \\ s_{n-1} \quad r_{n-1} \quad a_{n-1} \end{array}

Output

$u_0 \quad u_1 \quad \cdots \quad u_{m-1}$

Samples

Input

Explanation

Transaction counts: user 1 appears in 3 transactions (as sender twice, recipient once). User 2 appears in 2 transactions. User 3 appears in 3 transactions. With threshold $= 2$ , users 1, 2, and 3 all qualify. Output sorted: 1 2 3.

Output

1 2 3

Input

Explanation

User 1: self-transaction counts as 1, plus 2 more = 3 total. User 2: appears in 2 transactions. User 3: appears in 2 transactions. User 4: appears in 2 transactions. Only user 1 meets threshold $= 3$ . Output: 1.

Output

Input

2 2
10 20 100
30 40 200

Explanation

Each user appears in exactly 1 transaction. No user has count $\ge 2$ . Output is empty.

Output

Return the qualifying user IDs sorted in ascending numeric order.

If no user meets the threshold, output an empty line.

Constraints

$1 \le n \le 10^5$
$1 \le threshold \le n$
User IDs are numeric strings
$1 \le amount \le 10^5$

\begin{array}{l} n \quad t \\ s_0 \quad r_0 \quad a_0 \\ s_1 \quad r_1 \quad a_1 \\ \vdots \\ s_{n-1} \quad r_{n-1} \quad a_{n-1} \end{array}

$u_0 \quad u_1 \quad \cdots \quad u_{m-1}$

Each user appears in exactly 1 transaction. No user has count $\ge 2$ . Output is empty.