406707: GYM102503 D Union Found

Lolo Generoso owns the Sibuyas Unlimited Cookie Company, a company that mass-produces cookies for sale. His son, also the chief engineer of the company, made a mistake in the designs of one of the cookie machines in one of the cookie factories, causing it to produce lots of cookies: so many cookies, in fact, that they couldn't sell it all and had to give some away for Christmas. To make up for the financial losses, Lolo Generoso decided to reduce the wages of the company's employees. Sir Richard the Knight, Sir Poorard the Merchant, Sir Coward the Brave, Sir Alucard the Mage, and other employees of the Sibuyas Unlimited Cookie Company got unhappy about this and decided to found a union, the Frustrated Union of Cookie Cutters, to demand better working conditions.

Negotiations between the Frustrated Union of Cookie Cutters and the Sibuyas Unlimited Cookie Company don't always go well. Sometimes, instead of ending peacefully, Sir Richard and friends would demonstrate their frustrations violently, vandalizing parts of Sibuyas Unlimited Cookie Company factory premises. After a series of demonstrations, the cookie machine mysteriously broke. Lolo Generoso wants to find out who to blame. None of the members of the Frustrated Union of Cookie Cutters would betray each other and name who should be responsible. Lolo Generoso, therefore, hired an investigator to figure out.

Sir Guard the Guard is the Sibuyas Unlimited Cookie Company factory security guard. He has a logbook of people going into and out of the factory premises. Whenever a violent demonstration occurs, he also notes it in his logbook. As part of the investigation, the investigator wants to ask some questions about certain events in the log. Specifically, any time there is a demonstration, she wants to know how many people there are inside the premises. In between certain events in the log, she also wants to know whether or not some employee is inside the premises.

Here's what we know about Sir Guard's logbook:

• Whenever someone enters the premises, he writes a line with a plus (+) symbol followed by either their title followed by their name (for example, "Sir Richard") or their nickname (for example "the Knight").
• Whenever someone leaves the premises, he writes a line with a minus (-) symbol followed by either their title followed by their name or their nickname.
• Whenever there is a demonstration, he writes UNION on a line in the logbook.

Sir Guard the Guard is always on-guard, so the logbook never contains any mistakes or inconsistencies.

The investigator inserts some instructions in between the lines of Sir Guard's logbook. They are of the form FIND $$$x$$$, where $$$x$$$ is the title followed by the name or the nickname of an employee whose presence needs to be determined. She then gives the edited logbook to you. The Sibuyas Unlimited Cookie Company employs lots of cookie cutters, so she doesn't want to obtain the needed info herself. Of course, you must write a program to do this for her. Ninong Generoso is watching and may give you more cookies this Christmas if you help them out.

By the way, we know the following about the employees of the Sibuyas Unlimited Cookie Company:

• All of their titles are one of the following: Sir, Madam, Miss, Honorable, Heneral, Ginoong, Ginang, Binibining, Lolo, Lola, Ninong, Ninang, Darth.
• All of their names are single words only. Names only contain English letters, and always begin with a capital letter followed by any number of small letters.
• All of their nicknames are single words only. Nicknames only contain English letters, and always begin with a capital letter followed by any number of small letters.
• No two employees have the same name.
• No two employees have the same nickname.

The input begins with a list of employees of the Sibuyas Unlimited Cookie Company. Each of these lines is of the form Title Name the Nickname, where Title, Name, and Nickname are the title, name, and nickname of an employee respectively.

This is followed by a line containing ---------- (ten dashes) denoting the end of the list.

Following this are the lines written in Sir Guard's logbook, including the investigator's edits. The lines are given in chronological order. Each of these lines is one of the following forms:

• "+ Title Name" (without the quotes) indicating that the employee with the corresponding title and name entered the premises;
• "+ the Nickname" (without the quotes) indicating that the employee with the corresponding nickname entered the premises;
• "- Title Name" (without the quotes) indicating that the employee with the corresponding title and name left the premises;
• "- the Nickname" (without the quotes) indicating that the employee with the corresponding nickname left the premises;
• "UNION" (without the quotes) indicating that the Frustrated Union of Cookie Cutters made a violent demonstration;
• "FIND Title Name" (without the quotes) indicating that the investigator wants to know if the employee with the corresponding title and name is inside the premises or not at that specific point in time;
• "FIND the Nickname" (without the quotes) indicating that the investigator wants to know if the employee with the corresponding nickname is inside the premises or not at that specific point in time.

The last line of input contains END denoting the end of the logbook. This line should not be processed.

For every entry in the logbook containing UNION, print a line containing the number of employees inside the premises at that specific point in time. For every entry in the logbook containing FIND Title Name or FIND the Nickname, print a line containing FOUND if the mentioned employee is inside the premises at that specific point in time, or the integer 404 if not found. Print the answers in chronological order.

Each name and nickname is at least one and at most $$$13$$$ characters long.

Names and nicknames only contain English letters, and always begin with a capital letter followed by any number of small letters.

Each title is one of the following: Sir, Madam, Miss, Honorable, Heneral, Ginoong, Ginang, Binibining, Lolo, Lola, Ninong, Ninang, Darth.

No two employees have the same name.

No two employees have the same nickname.

It is guaranteed that the logbook only contains titles, names, and nicknames of legitimate employees. That is, the titles, names, and nicknames appearing in the logbook all appear in the list of employees of the Sibuyas Unlimited Cookie Company.

Let $$$e$$$ denote the number of employees, and $$$n$$$ denote the number of lines in the logbook.

Subtask 1 (45 points):

$$$1 \le n \le 50$$$

$$$1 \le e \le 50$$$

Subtask 2 (22 points):

$$$1 \le n \le 8000$$$

$$$1 \le e \le 8000$$$

Subtask 3 (33 points):

$$$1 \le n \le 10^5$$$

$$$1 \le e \le 10^5$$$

Sir Richard the Knight
Sir Poorard the Merchant
Sir Coward the Brave
Sir Alucard the Mage
Sir Strongard the Weak
Sir Weakard the Mighty
Sir Cheapard the Extravagant
Sir Goodard the Cruel
Sir Forward the Backward
Sir Standard the Unusual
Sir Bernard the Frozen
Sir Seculard the Pious
Sir Niggard the Generous
Sir Donard the Duck
----------
+ Sir Richard
+ the Merchant
FIND the Knight
UNION
- the Knight
FIND Sir Richard
+ the Duck
- Sir Poorard
FIND the Duck
FIND Sir Donard
- Sir Donard
END

FOUND
2
404
FOUND
FOUND

Honorable Jejeman the Honorable
Honorable Rodrix the Thirtieth
Heneral Luna the General
Heneral Heneroso the Specific
Lolo Generoso the Brandy
Ninong Generous the Lostcookie
Heneral Grievous the Grieving
Sir Jabba the Hutt
Madam Pizza the Hut
Sir Chew the Baka
Darth Plagueis the Wise
Darth Aegis the Band
Miss Taylor the Swift
Sir Freddie the Mercurial
Sir Shia the Buff
Sir Pew the Pie
Miss Ter the Jay
Binibining Pilipinas the Pageant
Madam Damin the Madamdamin
Madam Sibuyas the Onion
Lola Ynidora the Odorous
Sir Plato the Contemplator
Miss Gora the Explorer
Honorable Ben the Solver
Darth Eric the Tester
----------
+ Lolo Generoso
UNION
FIND the Wise
FIND the Swift
FIND the Onion
- Lolo Generoso
UNION
+ Lolo Generoso
UNION
UNION
- Lolo Generoso
UNION
UNION
UNION
END

1
404
404
404
0
1
1
0
0
0

Darth Josh the Incider
Darth Andrew the Android
Darth Carl the Smooth
Sir Martin the Martian
Sir Cisco the Router
Sir Robin the Hood
Sir Robbin the Bank
Sir Tim the Mol
Madam Tonette the Lawyer
Sir Guessmo the Fortuneteller
Sir Kevin the Spacey
Honorable Marte the President
Sir Vernon the Master
Binibining Sara the Bukalangloob
Ginoong Jingdong the Jengdung
Sir Jabba the Wookiee
----------
FIND Ginoong Jingdong
END

404