Account Prefix Balance Sum Log

A ledger maps string keys to integer values. Process q operations in order:

• SET k v - set the value of key k to v, replacing any previous value of that key.
• SUM p - report the sum of the values of all keys that currently have p as a prefix (a key is a prefix of itself). If no key has that prefix, the sum is 0.

Keys consist of lowercase English letters only; values are integers.

Input format

Line 1: an integer q. Each of the next q lines: SET k v or SUM p.

Output format

For each SUM operation, in order, print a line with the requested total.

Constraints

• 1 <= q <= 50000
• Each key/prefix has length 1..20, lowercase letters.
• -1000000 <= v <= 1000000