Three Ways to Tidy a Tool Tray

A workshop tray holds tools in a row, listed in tray from the front. Picking up the tool at position p (the front is position 1) costs p seconds of searching. After each pick-up the tool goes back into the row, and the workshop is testing three rules for where it goes:

• front: the tool is put at the front of the row;
• swap: the tool swaps places with the tool just in front of it (a tool already at the front stays there);
• count: every tool has a use count, starting at 0. After the pick-up the tool's count goes up by one and it moves forward past every tool directly in front of it whose count is strictly smaller; it stops behind the first tool whose count is equal or larger.

Every rule starts from the same tray order and serves the same requests (tool names, all in the tray). Return a tuple of the total search time under each rule: (front, swap, count).

Examples

Input:  tray = ["pen", "ruler", "glue", "tape"], requests = ["tape", "tape", "glue", "tape"]
Output: (11, 13, 10)
Explanation: front costs 4 + 1 + 4 + 2. swap costs 4 + 3 + 4 + 2.
count: tape (4) moves to the front; tape (1); glue (4) now has count 1 and passes pen and
ruler (count 0) but not tape (count 2); tape (1). Total 10.

Input:  tray = ["saw"], requests = ["saw", "saw"]
Output: (2, 2, 2)

Constraints

• 1 <= len(tray) <= 300, tool names are distinct strings
• 0 <= len(requests) <= 2 * 10**4, every request names a tool in tray

Goals

• Simulate three online rules that reorder a list after every access
• Keep a position map in step with swaps
• Maintain a list sorted by use count and insert an item at the right place