The Tariff Board at Greyford Bridge

The stone toll-board at Greyford Bridge is pinned with decrees, top to bottom, oldest first. Every morning the keeper works down the queue of travellers and names a price for each one. You are given the board and the queue.

Input

rules — a list of board entries in the order they are pinned (the first is topmost). Each entry is a plain object (a dict in Python) and is one of two things:

• A revocation: its only key is "revoke", holding a tag string. It cancels every tariff pinned above it (earlier in the list) whose tag equals that string. Tariffs with that tag pinned below it are unaffected. A revocation never prices anybody itself.
• A tariff: keys "tag" (string), "guild" (string), "road" (string), "cargo" (string), "priority" (an integer, possibly negative) and "toll" (a non-negative integer, or the string "bar"). "guild" and "cargo" are each either a name or "*". "road" is either "*" or a path of one or more non-empty segments joined by /. Tags need not be unique.

travellers — a list of objects with keys "guild", "road" and "cargo". Each value is a non-empty string and never "*"; the road is a path of segments joined by /.

Matching. A surviving tariff matches a traveller when all three hold:

• its guild is "*" or equals the traveller's guild;
• its cargo is "*" or equals the traveller's cargo;
• its road is "*", or equals the traveller's road, or the traveller's road begins with the tariff's road followed by /.

Precedence. Among the surviving tariffs that match a traveller, the winner is the one that comes out ahead on the first of these tests that distinguishes them:

1. higher "priority"; 2. greater road depth — the number of segments in the tariff's road, with "*" counting as depth 0; 3. a named guild ahead of "*"; 4. a named cargo ahead of "*"; 5. pinned lower on the board (later in rules). This settles every remaining tie.

Return a list of integers, one per traveller in queue order: the winning tariff's toll, or -1 if the winning tariff's toll is "bar", or 0 if no surviving tariff matches that traveller.