Money Transfer - Shopee Code League 2022 - Qualification Round HackerEarth

SeaMoney has a feature to transfer money between users. Let’s imagine a simple scenario.

$N$ usernames—consisting of lowercase Latin characters—each starts with a balance $b$. Amongst them, $T$ transactions happened, where user $u_a$ transfers $x$ amount of money to $u_b$. If $x$ is larger than the $u_a$’s balance when the transaction happens, the transaction is automatically rejected.

Output the final balance of each user.

Input

The first line contains two numbers $N$ and $T\left(1\le N,T\le 1000\right)$. Each of the next $N$ following lines contain username $u_i$ $\left(1\le |u_i|\le 10\right)$ and integer $b_i\left(1\le b_i\le 10^9\right)$, denoting the balance of user $u_i$. Following that are $T$ lines, each containing two usernames $u_a$ and $u_b$ $\left(u_a\ne u_b\right)$ followed by an integer $x\left(1\le x\le 10^9\right)$, denoting the amount of money transferred from $u_a$ to $u_b$ .

Output

Output the balance of all users in alphabetical order.

Input

3 4
amir 10
brenda 10
charlie 10
amir brenda 5
brenda charlie 5
charlie amir 20
charlie amir 7

Output

amir 12
brenda 10
charlie 8

Time Limit: 1.0 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme: Score is assigned when all the testcases pass.

Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic