Browser History

In a design question you build a small data structure and run a list of operations on it. The operations are given as text, one per string, and you return the answers of the operations that produce one. Think about which operations must be fast and choose the data structure for them.

A browser starts on homepage. Operations: "visit url" goes to a new page (all pages ahead in the history are forgotten); "back k" goes back up to k pages (as far as the first page); "forward k" goes forward up to k pages (as far as the last page). Return the current page after each back and each forward, in order. visit has no result.

For homepage = "a" and ["visit b", "visit c", "back 1", "back 5", "forward 1", "visit d", "forward 3"] the answer is ["b", "a", "b", "d"].

Examples

Example 1

Input:

run_browser_history('a', ['visit b', 'visit c', 'back 1', 'back 5', 'forward 1', 'visit d', 'forward 3'])

Output:

['b', 'a', 'b', 'd']

Example 2

Input:

run_browser_history('a', ['back 1'])

Output:

['a']

Constraints

• 0 <= len(ops) <= 100000
• Pages are words without spaces; 1 <= k <= 100.