Electronic Document Security

Interview

Time limit1sMemory limit128 MB

Summary

Process a log of ACL +, -, = entries in order and print the final rights for each entity, merging entities with identical rights.

Level: Medium4 of 10
Topics: Implementation, Simulation, Hash map, Sorting
Solved: No attempts yet

Problem

The Tyrell corporation uses a state-of-the-art electronic document system that controls every aspect of document creation, viewing, editing, and distribution. Document security is handled through access control lists (ACLs). An ACL defines the set of entities that may access a document, and for each entity it defines the set of rights that entity holds.

Entities are denoted by uppercase letters; an entity might be a single individual or an entire division.
Rights are denoted by lowercase letters; for example, a is append, d is delete, e is edit, and r is read.

A document's ACL is stored with the document, but a separate ACL log is also kept on a dedicated log server. Every document begins with an empty ACL, which grants no rights to anyone. Each time a document's ACL changes, a new entry is appended to its log.

Every entry has the form ExR, where E is a nonempty set of entities, R is a nonempty set of rights, and x is one of +, -, or =.

E+R grants every right in R to every entity in E.
E-R removes every right in R from every entity in E.
E=R sets every entity in E to have exactly the rights in R and no others.

An entry may be redundant — granting a right an entity already has, or removing a right it does not have. A log is a list of such entries separated by commas, ordered from oldest to most recent. Entries apply cumulatively, and when they conflict the more recent entry takes precedence.

Periodically the Tyrell corporation runs a security check: it uses the log to compute each document's current ACL and compares it with the ACL actually stored with the document. A mismatch indicates a security breach. Write a program that, given an ACL log, computes the current ACL.

Input

The input consists of one or more ACL logs. Each log is 3 to 79 characters long and appears on a line by itself, followed by a line containing only # that marks the end of the input. Each log follows the format defined above and contains no whitespace.

Output

For each log, output a single line: first the log number (logs are numbered sequentially starting from one), then a colon, then the current ACL in the format below.

The output contains no spaces.
Entities are listed in alphabetical order.
Each entity's rights are listed in alphabetical order.
An entity with no current rights is not listed (even if it appeared in a log entry), so an ACL may be empty.
If two or more consecutive entities have exactly the same rights, those rights are printed only once, after the list of those entities.

Examples4

Example 1

Input

MC-p,SC+c
YB=rde,B-dq,AYM+e
GQ+tju,GH-ju,AQ-z,Q=t,QG-t
JBL=fwa,H+wf,LD-fz,BJ-a,P=aw
#

Expected output

1:CSc
2:AeBerMeYder
3:
4:BHJfwLPaw

Example 2
Input
```
A+r
#
```
Expected output
```
1:Ar
```
Example 3
Input
```
A+r,A-r
#
```
Expected output
```
1:
```
Example 4
Input
```
ABC=xyz
#
```
Expected output
```
1:ABCxyz
```