Problem F
Key Management
Languages
en
is
Now that Arnar has a new beefy computer, it is very important we run everything related to the contests on it! Everything will be so much faster and better!
However, with great power comes great responsibility, so it is more important than ever to make sure only those with permission to run certain commands can do so on the computer. To this end, the plan is to set up a key system to manage all that.
The computer has some users, initially only the user ADMIN. The computer also has some keys, initially only the key ADMINKEY. Finally the computer has different commands it can execute. Initially these are the commands addUser, addKey, addCommand, linkKey, deleteUser, deleteKey, deleteCommand and unlinkKey.
Each key is connected to some (possibly zero) users, and those users have the permissions those keys grant them. Each key is also connected to some (possibly zero) commands. All the users connected to that key can then perform all connected commands. Initially the key ADMINKEY is connected to the user ADMIN and all the commands given above.
Each command takes some number of inputs (possibly zero), all inputs are strings. The following table describes the commands listed above.
|
Name of command |
Number of inputs |
Description of inputs |
|
addUser |
1 |
Valid user name |
|
addKey |
1 |
Valid key name |
|
addCommand |
2 |
Valid command name, number $0 \leq x \leq 8$. |
|
linkKey |
3 |
Key name, valid command or user, USER or COMMAND |
|
deleteUser |
1 |
User name |
|
deleteKey |
1 |
Key name |
|
deleteCommand |
1 |
Command name |
|
unlinkKey |
3 |
Key name, valid command or user, USER or COMMAND |
The command addUser creates a new user with the given name, addKey doing the same for a key. The command addCommand adds a new command with the given name and the given number of inputs. These commands are invalid if the users, keys or commands already exist. The addCommand command is also invalid if the second argument is anything other than an integer between $0$ and $8$, inclusive on both ends. New keys, users and commands have no connections to other keys, users or commands. For linkKey the second input must be a user if the third input is USER or a command if the third input is COMMAND. All other third inputs make the command invalid. The second input makes the command invalid if the corresponding user or command does not exist. Similarly the command is invalid if the given key does not exist, or if the key and user or command are already linked.
The delete operations are similar except they delete a user, key or command. If the user, key or command do not exist, the command is invalid. The command unlinkKey works like linkKey except it removes a link between a key and a user or command, being invalid if that link is not already present.
Valid user names may not contain spaces nor any special characters, only upper and lower case letters. Their length can not be greater than $16$ characters. Anything else makes the name invalid. Similarly the key names may only contain upper case letters and at most $10$ of them. Command names may contain special characters but not spaces and may be at most $20$ characters.
All commands created with addCommand will not do anything in our system, so their inputs do not have to be validated. Thus they are always valid as long as they receive the correct number of inputs and are performed by a user that exists. Any commands performed by a non-existent user are invalid. Similarly attempting to perform a non-existent command is invalid.
The only thing missing is a program maintaining all these keys and commands! This program needs to reject all invalid commands and then reject all commands performed by users that do not have permission to perform them.
Input
The first line of input contains a positive integer $1 \leq n \leq 1\, 000$, the number of commands to follow. Each command is on its own line.
All names, inputs and other data in the commands will contain only ASCII characters and no spaces. Thus each line can be split into words. The first word on the line will be a user name, the user performing the command. The second word will be the command they want to perform. Finally the other words on the line are the inputs to the command.
The input will contain at most $100\, 000$ characters. They will all be non-whitespace printable ASCII characters, spaces or newlines.
Output
For each command print INVALID if the command is invalid. Otherwise if it is valid but the user does not have the permission to perform the command instead print FORBIDDEN. If everything is acceptable instead print ACCEPTED.
| Sample Input 1 | Sample Output 1 |
|---|---|
22 ADMIN addUser Arnar Arnar addUser Atli ADMIN addUser Konrad ADMIN linkKey ADMINKEY Konrad USER Konrad addUser Atli Konrad addCommand verifyproblem 1 Konrad addKey KFFIKEY Konrad linkKey KFFIKEY Arnar USER Konrad linkKey KFFIKEY verifyproblem COMMAND Arnar verifyproblem keymanagement Konrad deleteCommand addKey Konrad deleteCommand addKey Konrad unlinkKey ADMINKEY deleteKey COMMAND ADMIN deleteKey KFFIKEY ADMIN verifyproblem ADMIN verifyproblem factorialencoding lkeys ADMIN deleteUser ADMIN ADMIN deleteUser Konrad Konrad addCommand verylongcommandthatisnotallowed Konrad addUser hey! Konrad addKey newkey Konrad unlinkKey ADMINKEY addUser command |
ACCEPTED FORBIDDEN ACCEPTED ACCEPTED ACCEPTED ACCEPTED ACCEPTED ACCEPTED ACCEPTED ACCEPTED ACCEPTED INVALID ACCEPTED FORBIDDEN INVALID INVALID ACCEPTED INVALID INVALID INVALID INVALID INVALID |
