Implement Map Sum Pair

Ninja has to implement a data structure called ‘MapSum’. Ninja has to implement two functions and one constructor.

1) MapSum(): Ninja has to initialize the ‘MapSum’.
2) insert(‘KEY’, ‘VAL’): Ninja has to insert this key-value pair in this ‘MapSum’.
3) sum(‘PREFIX’): Ninja has to find the sum of all values whose prefix of the keys is equal to ‘PREFIX’

Note :

During insertion, In the ‘MapSum’ if a ‘KEY’ is already present in the ‘MapSum’ then replace it with the new one.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ which denotes how many times the functions(as discussed above) we call.

The next “N” lines contain the string and key-value pair or a string, the first one is the name of the function and the second one is a ‘key-value’ or ‘PREFIX’.

Output Format :

For each test case, complete all the functions as we discussed above.

Output for every test case will be printed in a separate line.

Note :

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 50
2 <= ‘N’ <= 10000
1 <= |‘KEY’|, |‘PREFIX’| <= 50
1 <= ‘VAL’ <= 1000

Where |‘KEY’| and |’PREFIX’| denotes the length of the string ‘KEY’ and ‘PREFIX’. ‘VAL’ denotes the value of the key-value pair.

Time limit: 1 sec