Prefix-scoped store: hints, no solution

Simulate a key-value store that groups keys by prefix. Keys are strings of lowercase letters, digits and colons, and values are non-negative integers. Operations arrive as three parallel arrays: ops holds the operation name, keys holds its key or prefix, and values holds the value, which matters only for set.

Process the operations in order and return one integer per operation. Set stores the value under the key and returns 1 if the key was new or 0 if it replaced a value. Get returns the stored value or -1. CountPrefix returns how many stored keys start with the given text, and a key equal to it counts. DeletePrefix removes every stored key that starts with the given text and returns how many were removed.

Examples

Input

ops = ["set", "set", "set", "countPrefix", "get", "deletePrefix", "countPrefix"], keys = ["user:1", "user:2", "order:1", "user:", "user:2", "user:", "user:"], values = [10, 20, 30, 0, 0, 0, 0]

Output

[1, 1, 1, 2, 20, 2, 0]

Note

Three keys are set; two start with user:, the get finds 20, and deleting the prefix removes two keys and leaves none under it.

Input

ops = ["set", "set", "get", "countPrefix"], keys = ["a", "a", "a", "a"], values = [1, 2, 0, 0]

Output

[1, 0, 2, 1]

Note

The second set replaces the first, so it returns 0 and the get sees 2; one key is stored.

Input

ops = ["deletePrefix", "get"], keys = ["x", "x"], values = [0, 0]

Output

[0, -1]

Note

Deleting from an empty store removes nothing and the get finds no value.

Constraints

• 1 <= ops.length <= 60000, and keys and values have the same length
• ops[i] is one of set, get, countPrefix, deletePrefix
• Keys and prefixes have 1 to 12 characters (lowercase letters, digits, colons); 0 <= values[i] <= 1000000

Hint 1: a nudge

Two operations ask about all keys that share a beginning. What would you need to remember about each possible beginning so that neither counting nor deleting has to look at every key?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing