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

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

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

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

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

Repovive

Net Balance Finder - MAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG05. Net Balance Finder

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Given a list of $n$ debt records between team members, where each record consists of a borrower name, a lender name, and an integer amount, compute each person's net balance defined as:

$\text{net balance} = \text{total amount lent} - \text{total amount borrowed}$

Return the names of all people who have the smallest (most negative) net balance, sorted alphabetically and separated by spaces.

If nobody has a negative net balance, output: Nobody has a negative balance

Constraints

$1 \le n \le 10^5$
$1 \le \text{amount} \le 10^6$
Names are lowercase alphabetic strings of length $1$ to $20$
Borrower and lender in each record are different people

Input

\begin{array}{l} n \\ \text{borrower}_0 \quad \text{lender}_0 \quad \text{amount}_0 \\ \text{borrower}_1 \quad \text{lender}_1 \quad \text{amount}_1 \\ \vdots \\ \text{borrower}_{n-1} \quad \text{lender}_{n-1} \quad \text{amount}_{n-1} \end{array}

Output

$\text{name}_0 \quad \text{name}_1 \quad \cdots$

$\texttt{Nobody has a negative balance}$

Samples

Input

6
alex blake 2
blake alex 2
casey alex 5
blake casey 7
alex blake 4
alex casey 4

Explanation

Record 1: alex borrows $2$ from blake. Record 2: blake borrows $2$ from alex. Record 3: casey borrows $5$ from alex. Record 4: blake borrows $7$ from casey. Record 5: alex borrows $4$ from blake. Record 6: alex borrows $4$ from casey.

alex: total lent $= 2 + 5 = 7$ , total borrowed $= 2 + 4 + 4 = 10$ , net $= 7 - 10 = -3$ . blake: total lent $= 2 + 4 = 6$ , total borrowed $= 2 + 7 = 9$ , net $= 6 - 9 = -3$ . casey: total lent $= 7 + 4 = 11$ , total borrowed $= 5$ , net $= 11 - 5 = 6$ .

Minimum balance is $-3$ , shared by alex and blake. Output sorted alphabetically: alex blake.

Output

alex blake

Input

2
alice bob 5
bob alice 5

Explanation

alice: total lent $= 5$ , total borrowed $= 5$ , net $= 0$ . bob: total lent $= 5$ , total borrowed $= 5$ , net $= 0$ .

No one has a negative balance. Output: Nobody has a negative balance.

Output

Nobody has a negative balance

Input

2
dan eve 10
fay eve 10

Explanation

dan: borrowed $10$ , lent nothing, net $= 0 - 10 = -10$ . fay: borrowed $10$ , lent nothing, net $= 0 - 10 = -10$ . eve: borrowed nothing, lent $10 + 10 = 20$ , net $= 20$ .

Minimum balance is $-10$ , shared by dan and fay. Output sorted: dan fay.

Output

dan fay

$\text{net balance} = \text{total amount lent} - \text{total amount borrowed}$

Return the names of all people who have the smallest (most negative) net balance, sorted alphabetically and separated by spaces.

If nobody has a negative net balance, output: Nobody has a negative balance

Constraints

$1 \le n \le 10^5$
$1 \le \text{amount} \le 10^6$
Names are lowercase alphabetic strings of length $1$ to $20$
Borrower and lender in each record are different people

\begin{array}{l} n \\ \text{borrower}_0 \quad \text{lender}_0 \quad \text{amount}_0 \\ \text{borrower}_1 \quad \text{lender}_1 \quad \text{amount}_1 \\ \vdots \\ \text{borrower}_{n-1} \quad \text{lender}_{n-1} \quad \text{amount}_{n-1} \end{array}

$\text{name}_0 \quad \text{name}_1 \quad \cdots$

$\texttt{Nobody has a negative balance}$

Minimum balance is $-3$ , shared by alex and blake. Output sorted alphabetically: alex blake.

alice: total lent $= 5$ , total borrowed $= 5$ , net $= 0$ . bob: total lent $= 5$ , total borrowed $= 5$ , net $= 0$ .

No one has a negative balance. Output: Nobody has a negative balance.

dan: borrowed $10$ , lent nothing, net $= 0 - 10 = -10$ . fay: borrowed $10$ , lent nothing, net $= 0 - 10 = -10$ . eve: borrowed nothing, lent $10 + 10 = 20$ , net $= 20$ .

Minimum balance is $-10$ , shared by dan and fay. Output sorted: dan fay.