The employees have decided to kill some time by creating some unique backstories for some of the critters in your park.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Objective

Give practice with Tries in C.

 

Story

The employees have decided to kill some time by creating some unique backstories for some of the critters in your park.   Partly due to their solitary nature there is not a more rich, diverse, and mysterious set of characters than that of your orangutans. To help distinguish between the different orangutans each one gets a name. Due to the escapades that the orangutans get into their names can change from day to day. This dynamic element makes keeping track of the storylines tricky. The employees like to feed their favorite orangutans mangos as a treat.

 

Due to certain great ape weight issues, you are concerned that your employees may be over feeding some orangutans and underfeeding others. Luckily, your employees track the orangutans that get fed. Unluckily, your employees write the name of the orangutan at the time of the feeding.

 

You have decided to embrace the nonsense that is an inconsistent and changing naming convention, but you have forced your employees to write down when an orangutan changes its name. You will focus on asking at particular times how many mangos have been eaten by the orangutans whose name begins with a particular letter sequence.

 

Problem

Given a list of name changes and feedings, determine the number of mangos eaten by the orangutans with a particular name prefix.

 

Input

Input will begin with a line containing 2 integers, n and e (1 ≤ n ≤ 500,000; 1 ≤ e ≤ 500,000), representing the number of orangutans and the number of events. The following e lines each contain a single event description. An event description will be one of the following three,

● 1 n a - which represents a feeding, where n is the name of the orangutan at the time of the feeding

and a represents the amount of mangos given to the orangutan. (1 ≤ a ≤ 100)

● 2 o n - which represents a name change, where o represents the old name of the orangutan and n

represents the new name.

● 3 p - which represents an inquiry as to the number of mangos eaten by orangutans whose name starts with the sequence of characters p.

 

Each name and character sequence will contain at most 20 characters. All names will be strictly uppercase Latin characters (‘A’ through ‘Z’). No name will contain whitespace. No orangutan will change their name to an already existing name.

 

Assume that no orangutan has eaten prior to the given events

 

 

Output

For each input event that represents an inquiry print the number of mangos eaten by orangutans whose name starts with the given input character sequence.

 

Sample Input Sample Output

10 6 8

1 BOB 5 0

1 BETTY 3 5

3 B

3 ALICE

2 BETTY ALICE

3 B

4 8 4

1 WILLIAM 4 25

1 WILL 6

3 WILLI

1 WILLIAN 9

1 WILLY 10

2 WILL MATT

1 WILLIAN 2

3 WILL

 

Explanation

Case 1

There are 10 orangutans, but we only ever hear about 2 of them (initially BOB and BETTY). Additionally there is

 

First Event

BOB gets fed 5 mangos.

 

Second Event

BETTY gets fed 3 mangos.

 

Third Event

We want to know how many mangos have been given to orangutans whose name starts with B. Both BOB who received 5 mangos and BETTY who received 3 mangos have a name that starts with the letter

B. Because of this the total mangos given is 8.

 

Fourth Event

We want to know how many mangos have been given to orangutans whose name starts with ALICE. We do not know of any orangutans with names that start with ALICE that have been given a mango. For this reason the answer is 0.

 

 

Fifth Event

BETTY is changing their name to ALICE. This means that “BETTY” has eaten 0 mangos and ALICE has eaten 3.

 

Sixth Event

We want to know how many mangos have been given to orangutans whose name starts with B. BOB who received 5 mangos has a name that starts with the letter B, but since BETTY is no longer BETTY we don’t count them. Because of this the total mangos given is 5.

 

Case 2

There are 4 orangutans and 8 events.

 

First Event

WILLIAM gets 4 mangos.

 

Name WILLIAM ??? ??? ???

Mangos 4 0 0 0

 

Second Event

WILL gets 6 mangos

 

Name WILLIAM WILL ??? ???

Mangos 4 6 0 0

 

Third Event

We want to know how many mangos orangutans whose names start with WILLI got. In this case only WILLIAM meets the criteria. They got 4 mangos.

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of