You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.
Implement the BrowserHistory class:

BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
void visit(string url) Visits url from the current page. It clears up all the forward history.
string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

 
Example:
Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(2);                   // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

 
Constraints:

1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage and url consist of  '.' or lower case English letters.
At most 5000 calls will be made to visit, back, and forward.

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Starter code: class BrowserHistory:
    def __init__(self, homepage: str):
    def visit(self, url: str) -> None:
    def back(self, steps: int) -> str:
    def forward(self, steps: int) -> str:
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

Solutions:
class BrowserHistory:

	def __init__(self, homepage: str):
		self.hashM = {}
		(self.maxIndex, self.currIndex) = (0, 0)
		self.hashM[self.currIndex] = homepage

	def visit(self, url: str) -> None:
		self.hashM[self.currIndex + 1] = url
		self.currIndex = self.currIndex + 1
		self.maxIndex = self.currIndex
		return url

	def back(self, steps: int) -> str:
		if self.currIndex - steps < 0:
			self.currIndex = 0
		else:
			self.currIndex = self.currIndex - steps
		return self.hashM[self.currIndex]

	def forward(self, steps: int) -> str:
		if self.currIndex + steps > self.maxIndex:
			self.currIndex = self.maxIndex
		else:
			self.currIndex = self.currIndex + steps
		return self.hashM[self.currIndex]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.l = [homepage]
		self.cur = 0
		self.max = 0

	def visit(self, url: str) -> None:
		self.cur += 1
		if self.cur == len(self.l):
			self.l.append(url)
		else:
			self.l[self.cur] = url
		self.max = self.cur

	def back(self, steps: int) -> str:
		self.cur -= steps
		if self.cur < 0:
			self.cur = 0
		return self.l[self.cur]

	def forward(self, steps: int) -> str:
		self.cur += steps
		if self.cur > self.max:
			self.cur = self.max
		return self.l[self.cur]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = [homepage]
		self.idx = 0

	def visit(self, url: str) -> None:
		for _ in range(len(self.history) - 1 - self.idx):
			self.history.pop()
		self.history.append(url)
		self.idx += 1

	def back(self, steps: int) -> str:
		self.idx = max(0, self.idx - steps)
		return self.history[self.idx]

	def forward(self, steps: int) -> str:
		self.idx = min(len(self.history) - 1, self.idx + steps)
		return self.history[self.idx]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = [homepage]
		self.index = 0

	def visit(self, url: str) -> None:
		while len(self.history) > self.index + 1:
			print(self.history.pop())
		self.history.append(url)
		self.index += 1

	def back(self, steps: int) -> str:
		self.index = max(0, self.index - steps)
		return self.history[self.index]

	def forward(self, steps: int) -> str:
		self.index = min(len(self.history) - 1, self.index + steps)
		return self.history[self.index]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.home = homepage
		self.history = [homepage] + [0 for _ in range(5000)]
		self.curr_ind = 0
		self.top = 0

	def visit(self, url: str) -> None:
		self.history[self.curr_ind + 1] = url
		self.curr_ind += 1
		self.top = self.curr_ind

	def back(self, steps: int) -> str:
		self.curr_ind = max(0, self.curr_ind - steps)
		return self.history[self.curr_ind]

	def forward(self, steps: int) -> str:
		self.curr_ind = min(self.top, self.curr_ind + steps)
		return self.history[self.curr_ind]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.currentIndex = 0
		self.maxIndex = 0
		self.history = {self.currentIndex: homepage}

	def visit(self, url: str) -> None:
		self.currentIndex += 1
		self.history[self.currentIndex] = url
		self.maxIndex = self.currentIndex

	def back(self, steps: int) -> str:
		self.currentIndex -= steps
		self.currentIndex = 0 if self.currentIndex < 0 else self.currentIndex
		return self.history[self.currentIndex]

	def forward(self, steps: int) -> str:
		self.currentIndex += steps
		self.currentIndex = self.maxIndex if self.currentIndex > self.maxIndex else self.currentIndex
		return self.history[self.currentIndex]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.pages = [homepage]
		self.curr = 0

	def visit(self, url: str) -> None:
		self.pages = self.pages[:self.curr + 1]
		self.pages.append(url)
		self.curr = len(self.pages) - 1
		print(self.pages)

	def back(self, steps: int) -> str:
		if self.curr - steps < 0:
			self.curr = 0
			return self.pages[0]
		else:
			self.curr = self.curr - steps
			return self.pages[self.curr]

	def forward(self, steps: int) -> str:
		if self.curr + steps >= len(self.pages):
			self.curr = len(self.pages) - 1
			return self.pages[-1]
		else:
			self.curr = self.curr + steps
			return self.pages[self.curr]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = [homepage]
		self.i = 0

	def visit(self, url: str) -> None:
		self.history = self.history[0:self.i + 1]
		self.history.append(url)
		self.i += 1

	def back(self, steps: int) -> str:
		if self.i >= steps:
			for _ in range(steps):
				self.i -= 1
			return self.history[self.i]
		else:
			self.i = 0
			return self.history[self.i]

	def forward(self, steps: int) -> str:
		if len(self.history) - self.i - 1 >= steps:
			for _ in range(steps):
				self.i += 1
			return self.history[self.i]
		else:
			self.i = len(self.history) - 1
			return self.history[self.i]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.stack = [homepage]
		self.stack_position = 0

	def visit(self, url: str) -> None:
		self.stack_position += 1
		print('You are in "{}". Visit "{}"'.format(self.stack[-1], url))
		while self.stack_position < len(self.stack):
			self.stack.pop()
		self.stack.append(url)

	def back(self, steps: int) -> str:
		self.stack_position = max(0, self.stack_position - steps)
		if self.stack_position == 0:
			print('cant go any more back')
		return self.stack[self.stack_position]

	def forward(self, steps: int) -> str:
		self.stack_position = min(len(self.stack) - 1, self.stack_position + steps)
		if self.stack_position == len(self.stack) - 1:
			print('cant go any more forwards')
		return self.stack[self.stack_position]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.arr = [homepage]
		self.cur = 0
		self.f = 0

	def visit(self, url: str) -> None:
		self.arr = self.arr[:self.cur + 1]
		self.arr.append(url)
		self.cur += 1
		self.f = 0

	def back(self, steps: int) -> str:
		if steps > self.cur:
			self.cur = 0
			self.f = len(self.arr) - 1
		else:
			self.cur -= steps
			self.f += steps
		return self.arr[self.cur]

	def forward(self, steps: int) -> str:
		if steps > self.f:
			self.cur = len(self.arr) - 1
			self.f = 0
		else:
			self.cur += steps
			self.f -= steps
		return self.arr[self.cur]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = [homepage]
		self.pointer = 0

	def visit(self, url: str) -> None:
		if self.pointer < len(self.history) - 1:
			del self.history[self.pointer + 1:]
		self.history.append(url)
		self.pointer = len(self.history) - 1

	def back(self, steps: int) -> str:
		length = min(steps, self.pointer)
		self.pointer -= length
		return self.history[self.pointer]

	def forward(self, steps: int) -> str:
		length = min(steps, len(self.history) - 1 - self.pointer)
		self.pointer += length
		return self.history[self.pointer]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.prev = [homepage]
		self.future = []

	def visit(self, url: str) -> None:
		self.prev.append(url)
		self.future = []

	def back(self, steps: int) -> str:
		size = len(self.prev) - 1
		for _ in range(min(steps, size)):
			self.future.append(self.prev.pop())
		return self.prev[-1]

	def forward(self, steps: int) -> str:
		size = len(self.future)
		for _ in range(min(steps, size)):
			self.prev.append(self.future.pop())
		return self.prev[-1]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = LinkedList(homepage, None, None)
		self.curr_page = self.history

	def visit(self, url: str) -> None:
		new_page = LinkedList(url, self.curr_page, None)
		self.curr_page.next = new_page
		self.curr_page = new_page

	def back(self, steps: int) -> str:
		num_steps = 0
		temp = self.curr_page
		while num_steps < steps and temp.prev != None:
			temp = temp.prev
			num_steps += 1
		self.curr_page = temp
		return temp.val

	def forward(self, steps: int) -> str:
		num_steps = 0
		temp = self.curr_page
		while num_steps < steps and temp.__next__ != None:
			temp = temp.__next__
			num_steps += 1
		self.curr_page = temp
		return temp.val

class LinkedList:

	def __init__(self, val, prev, next):
		self.val = val
		self.prev = prev
		self.next = next


class BrowserHistory:

	def __init__(self, homepage: str):
		self.pointer = 0
		self.histlen = 1
		self.history = [homepage]

	def visit(self, url: str) -> None:
		self.history = self.history[:self.pointer + 1] + [url]
		self.pointer += 1
		self.histlen = len(self.history)

	def back(self, steps: int) -> str:
		self.pointer = max(self.pointer - steps, 0)
		return self.history[self.pointer]

	def forward(self, steps: int) -> str:
		self.pointer = min(self.pointer + steps, self.histlen - 1)
		return self.history[self.pointer]


class Node:

	def __init__(self, url: str):
		self.url = url
		self.next = None
		self.prev = None

class BrowserHistory:

	def __init__(self, homepage: str):
		self.head = Node(homepage)
		self.current_node = self.head

	def visit(self, url: str) -> None:
		new_node = Node(url)
		self.current_node.next = new_node
		new_node.prev = self.current_node
		self.current_node = self.current_node.__next__

	def back(self, steps: int) -> str:
		for i in range(steps):
			if self.current_node == self.head:
				break
			else:
				self.current_node = self.current_node.prev
		return self.current_node.url

	def forward(self, steps: int) -> str:
		for i in range(steps):
			if self.current_node.__next__ is None:
				break
			else:
				self.current_node = self.current_node.__next__
		return self.current_node.url


class BrowserHistory:

	def __init__(self, homepage: str):
		self.list = []
		self.list.append(homepage)
		self.currentIndex = 0

	def visit(self, url: str) -> None:
		self.currentIndex += 1
		while self.currentIndex < len(self.list):
			self.list.pop()
		self.list.append(url)

	def forward(self, steps: int) -> str:
		self.currentIndex = min(self.currentIndex + steps, len(self.list) - 1)
		return self.list[self.currentIndex]

	def back(self, steps: int) -> str:
		self.currentIndex = max(self.currentIndex - steps, 0)
		return self.list[self.currentIndex]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.fwd = []
		self.bck = [homepage]
		self.lastback = homepage

	def visit(self, url: str) -> None:
		self.bck.append(url)
		self.lastback = url
		self.fwd = []

	def back(self, steps: int) -> str:
		el = None
		while steps and len(self.bck) > 1:
			self.fwd.append(self.bck.pop())
			steps -= 1
		return self.bck[-1]

	def forward(self, steps: int) -> str:
		el = None
		while steps and self.fwd:
			self.bck.append(self.fwd.pop())
			steps -= 1
		return self.bck[-1]


class BrowserHistory:

	def __init__(self, homepage):
		self.history = [homepage]
		self.curr = 0
		self.bound = 0

	def visit(self, url):
		self.curr += 1
		if self.curr == len(self.history):
			self.history.append(url)
		else:
			self.history[self.curr] = url
		self.bound = self.curr

	def back(self, steps):
		self.curr = max(self.curr - steps, 0)
		return self.history[self.curr]

	def forward(self, steps):
		self.curr = min(self.curr + steps, self.bound)
		return self.history[self.curr]


class ListNode:

	def __init__(self, x):
		self.val = x
		self.next = None
		self.prev = None

class BrowserHistory:

	def __init__(self, homepage: str):
		self.root = ListNode(homepage)

	def visit(self, url: str) -> None:
		node = ListNode(url)
		node.prev = self.root
		self.root.next = node
		self.root = self.root.__next__

	def back(self, steps: int) -> str:
		while self.root.prev and steps:
			self.root = self.root.prev
			steps -= 1
		return self.root.val

	def forward(self, steps: int) -> str:
		while self.root.__next__ and steps:
			self.root = self.root.__next__
			steps -= 1
		return self.root.val


class BrowserHistory:

	def __init__(self, homepage: str):
		self.forwardA = []
		self.backward = [homepage]

	def visit(self, url: str) -> None:
		self.backward.append(url)
		self.forwardA = []

	def forward(self, steps: int) -> str:
		i = 0
		while len(self.forwardA) != 0 and i < steps:
			i += 1
			item = self.forwardA.pop()
			self.backward.append(item)
		return self.backward[-1]

	def back(self, steps: int) -> str:
		i = 0
		while len(self.backward) > 1 and i < steps:
			item = self.backward.pop()
			self.forwardA.append(item)
			i += 1
		return self.backward[-1]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.curr = homepage
		self.backw = []
		self.forw = []

	def visit(self, url: str) -> None:
		self.backw.append(self.curr)
		self.forw = []
		self.curr = url

	def back(self, steps: int) -> str:
		for _ in range(steps):
			if not self.backw:
				break
			self.forw.append(self.curr)
			self.curr = self.backw.pop()
		return self.curr

	def forward(self, steps: int) -> str:
		for _ in range(steps):
			if not self.forw:
				break
			self.backw.append(self.curr)
			self.curr = self.forw.pop()
		return self.curr


class BrowserHistory:

	def __init__(self, homepage: str):
		self.before = [homepage]
		self.after = []

	def visit(self, url: str) -> None:
		self.before.append(url)
		self.after = []

	def back(self, steps: int) -> str:
		while steps > 0 and len(self.before) > 1:
			self.after.append(self.before[-1])
			self.before.pop()
			steps -= 1
		return self.before[-1]

	def forward(self, steps: int) -> str:
		while steps > 0 and self.after:
			self.before.append(self.after[-1])
			self.after.pop()
			steps -= 1
		return self.before[-1]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.backwardStack = [homepage]
		self.forwardStack = []

	def visit(self, url: str) -> None:
		self.backwardStack.append(url)
		self.forwardStack.clear()

	def back(self, steps: int) -> str:
		while len(self.backwardStack) >= 2 and steps > 0:
			top = self.backwardStack.pop()
			self.forwardStack.append(top)
			steps -= 1
		return self.backwardStack[-1]

	def forward(self, steps: int) -> str:
		while steps > 0 and len(self.forwardStack) > 0:
			top = self.forwardStack.pop()
			self.backwardStack.append(top)
			steps -= 1
		return self.backwardStack[-1]


class Node:

	def __init__(self, data):
		self.next = None
		self.prev = None
		self.data = data

class BrowserHistory:

	def __init__(self, homepage: str):
		self.head = Node(homepage)
		self.head.next = None
		self.head.prev = None
		self.curr = self.head

	def visit(self, url: str) -> None:
		node = Node(url)
		self.curr.next = node
		node.prev = self.curr
		self.curr = node

	def back(self, steps: int) -> str:
		count = 0
		while count < steps and self.curr.prev != None:
			self.curr = self.curr.prev
			count += 1
		return self.curr.data

	def forward(self, steps: int) -> str:
		count = 0
		while count < steps and self.curr.__next__ != None:
			self.curr = self.curr.__next__
			count += 1
		return self.curr.data


class BrowserHistory:

	def __init__(self, homepage: str):
		self.urls = []
		self.urls.append(homepage)
		self.i = 0
		self.bound = 0

	def visit(self, url: str) -> None:
		self.urls.append(url)
		self.i += 1
		if self.i == len(self.urls):
			self.urls.append(url)
		else:
			self.urls[self.i] = url
		self.bound = self.i

	def back(self, steps: int) -> str:
		self.i = max(0, self.i - steps)
		return self.urls[self.i]

	def forward(self, steps: int) -> str:
		self.i = min(self.bound, self.i + steps)
		return self.urls[self.i]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = [homepage]
		self.forward_pages = []

	def visit(self, url):
		self.history.append(url)
		self.forward_pages = []

	def back(self, steps):
		while steps > 0 and len(self.history) > 1:
			self.forward_pages.append(self.history.pop())
			steps -= 1
		return self.history[-1]

	def forward(self, steps):
		while steps > 0 and self.forward_pages:
			self.history.append(self.forward_pages.pop())
			steps -= 1
		return self.history[-1]


class BiLinkedNode:

	def __init__(self, val: str):
		self.val = val
		self.next = None
		self.prev = None

class BrowserHistory:

	def __init__(self, homepage: str):
		self.currPage = BiLinkedNode(homepage)
		self.browseListLen = 1
		self.currPageIdx = 0

	def visit(self, url: str) -> None:
		newPage = BiLinkedNode(url)
		newPage.prev = self.currPage
		self.currPage.next = newPage
		self.currPage = newPage
		self.currPageIdx += 1
		self.browseListLen = self.currPageIdx + 1

	def back(self, steps: int) -> str:
		while self.currPageIdx > 0 and steps > 0:
			self.currPage = self.currPage.prev
			self.currPageIdx -= 1
			steps -= 1
		return self.currPage.val

	def forward(self, steps: int) -> str:
		while self.currPageIdx < self.browseListLen - 1 and steps > 0:
			self.currPage = self.currPage.__next__
			self.currPageIdx += 1
			steps -= 1
		return self.currPage.val


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = []
		self.forwardHistory = []
		self.curr = homepage

	def visit(self, url: str) -> None:
		self.history.append(self.curr)
		self.curr = url
		self.forwardHistory = []

	def back(self, steps: int) -> str:
		if not self.history:
			return self.curr
		left = steps
		url = None
		while left and self.history:
			url = self.history.pop()
			left -= 1
			self.forwardHistory.append(self.curr)
			self.curr = url
		return url

	def forward(self, steps: int) -> str:
		if not self.forwardHistory:
			return self.curr
		left = steps
		url = None
		while left and self.forwardHistory:
			url = self.forwardHistory.pop()
			left -= 1
			self.history.append(self.curr)
			self.curr = url
		return url


class BrowserHistory:

	def __init__(self, homepage: str):
		self.list1 = [homepage]
		self.currentInd = 0

	def visit(self, url: str) -> None:
		newList = self.list1[0:self.currentInd + 1]
		newList.append(url)
		self.currentInd += 1
		self.list1 = newList
		print((self.list1, self.currentInd))

	def back(self, steps: int) -> str:
		while self.currentInd > 0 and steps > 0:
			self.currentInd -= 1
			steps -= 1
		return self.list1[self.currentInd]

	def forward(self, steps: int) -> str:
		while self.currentInd < len(self.list1) - 1 and steps > 0:
			self.currentInd += 1
			steps -= 1
		print((self.list1[self.currentInd], self.currentInd))
		return self.list1[self.currentInd]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.curIndex = 0
		self.history = [homepage]

	def visit(self, url: str) -> None:
		self.history = self.history[:self.curIndex + 1]
		self.history.append(url)
		self.curIndex += 1

	def back(self, steps: int) -> str:
		self.curIndex = max(0, self.curIndex - steps)
		return self.history[self.curIndex]

	def forward(self, steps: int) -> str:
		self.curIndex = min(len(self.history) - 1, self.curIndex + steps)
		return self.history[self.curIndex]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.back_stack = []
		self.front_stack = []
		self.curr = homepage

	def visit(self, url: str) -> None:
		self.front_stack = []
		self.back_stack.append(self.curr)
		self.curr = url

	def back(self, steps: int) -> str:
		for i in range(steps):
			if len(self.back_stack) == 0:
				return self.curr
			ans = self.back_stack.pop()
			self.front_stack.append(self.curr)
			self.curr = ans
		return ans

	def forward(self, steps: int) -> str:
		for i in range(steps):
			if len(self.front_stack) == 0:
				return self.curr
			ans = self.front_stack.pop()
			self.back_stack.append(self.curr)
			self.curr = ans
		return ans


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = []
		self.future = []
		self.history.append(homepage)

	def visit(self, url: str) -> None:
		self.history.append(url)
		self.future = []

	def back(self, steps: int) -> str:
		while steps > 0 and len(self.history) > 1:
			self.future.append(self.history[-1])
			self.history.pop()
			steps -= 1
		return self.history[-1]

	def forward(self, steps: int) -> str:
		while steps > 0 and len(self.future) > 0:
			self.history.append(self.future[-1])
			self.future.pop()
			steps -= 1
		return self.history[-1]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history_ = [homepage]
		self.count_ = 1

	def visit(self, url: str) -> None:
		self.history_ = self.history_[:self.count_]
		self.history_.append(url)
		self.count_ += 1

	def back(self, steps: int) -> str:
		if steps < self.count_:
			self.count_ -= steps
			return self.history_[self.count_ - 1]
		else:
			self.count_ = 1
			return self.history_[self.count_ - 1]

	def forward(self, steps: int) -> str:
		if steps <= len(self.history_) - self.count_:
			self.count_ += steps
			return self.history_[self.count_ - 1]
		else:
			self.count_ = len(self.history_)
			return self.history_[-1]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.ls = []
		self.ls.append(homepage)
		self.hm = {}
		self.cur = 0

	def visit(self, url: str) -> None:
		self.ls = self.ls[:self.cur + 1]
		self.ls.append(url)
		self.cur = len(self.ls) - 1

	def back(self, steps: int) -> str:
		if steps > self.cur:
			self.cur = 0
			return self.ls[0]
		self.cur -= steps
		return self.ls[self.cur]

	def forward(self, steps: int) -> str:
		if steps > len(self.ls) - self.cur - 1:
			self.cur = len(self.ls) - 1
			return self.ls[self.cur]
		self.cur += steps
		return self.ls[self.cur]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.ls = [homepage]
		self.cur = 0

	def visit(self, url: str) -> None:
		last = len(self.ls) - 1
		while last != self.cur:
			self.ls.pop()
			last -= 1
		self.ls.append(url)
		self.cur = len(self.ls) - 1

	def back(self, steps: int) -> str:
		while steps != 0 and self.cur > 0:
			self.cur -= 1
			steps -= 1
		return self.ls[self.cur]

	def forward(self, steps: int) -> str:
		while steps != 0 and self.cur < len(self.ls) - 1:
			self.cur += 1
			steps -= 1
		return self.ls[self.cur]


class BrowserHistory:

	def __init__(self, homepage: str):
		self.l = [homepage]
		self.curr = 0

	def visit(self, url: str) -> None:
		if self.curr == len(self.l) - 1:
			self.l.append(url)
			self.curr += 1
		else:
			while self.curr < len(self.l) - 1:
				self.l.pop()
			self.l.append(url)
			self.curr += 1

	def back(self, steps: int) -> str:
		if self.curr - steps < 0:
			self.curr = 0
			return self.l[0]
		self.curr -= steps
		return self.l[self.curr]

	def forward(self, steps: int) -> str:
		if self.curr + steps >= len(self.l):
			self.curr = len(self.l) - 1
			return self.l[-1]
		self.curr += steps
		return self.l[self.curr]


from collections import deque

class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = deque()
		self.future = deque()
		self.history.append(homepage)

	def visit(self, url: str) -> None:
		self.history.append(url)
		if self.future:
			self.future = deque()

	def back(self, steps: int) -> str:
		for i in range(steps):
			if len(self.history) > 1:
				self.future.append(self.history.pop())
		return self.history[-1]

	def forward(self, steps: int) -> str:
		for i in range(steps):
			if self.future:
				self.history.append(self.future.pop())
		return self.history[-1]


class BrowserHistory:
	curr = None
	backHistory = 0
	forwardHistory = 0

	def __init__(self, homepage: str):
		self.curr = Node(homepage)

	def visit(self, url: str) -> None:
		self.forwardHistory = 0
		self.curr.next = Node(url)
		self.curr.next.prev = self.curr
		self.backHistory += 1
		self.curr = self.curr.__next__

	def back(self, steps: int) -> str:
		while steps > 0 and self.curr.prev:
			self.curr = self.curr.prev
			self.forwardHistory += 1
			self.backHistory -= 1
			steps -= 1
		return self.curr.url

	def forward(self, steps: int) -> str:
		while steps > 0 and self.curr.__next__:
			self.curr = self.curr.__next__
			self.forwardHistory -= 1
			self.backHistory += 1
			steps -= 1
		return self.curr.url

class Node:
	url = None
	prev = None
	next = None

	def __init__(self, url: str):
		self.url = url
		self.prev = None
		self.next = None


class BrowserHistory:

	def __init__(self, homepage: str):
		self.history = [homepage]
		self.current = 0

	def visit(self, url: str) -> None:
		self.history = self.history[:self.current + 1]
		self.history.append(url)
		self.current = len(self.history) - 1

	def back(self, steps: int) -> str:
		ex = max(self.current - steps, 0)
		self.current = ex
		return self.history[ex]

	def forward(self, steps: int) -> str:
		if self.current + steps < len(self.history) - 1:
			self.current += steps
		else:
			self.current = len(self.history) - 1
		return self.history[self.current]