Web Navigation

Interview

Time limit1sMemory limit128 MB

Summary

Simulate browser back and forward navigation using two stacks, printing the current URL after each command.

Level: Easy3 of 10
Topics: Stack, Simulation, Implementation
Solved: No attempts yet

Problem

Standard web browsers provide features to move backward and forward through the pages you have recently visited. One way to implement these features is to use two stacks that keep track of the pages reachable by moving backward and forward. In this problem you have to implement this behavior.

Your program must support the following commands:

BACK: Push the current page on top of the forward stack. Then pop the page on top of the backward stack and make it the new current page. If the backward stack is empty, the command is ignored.
FORWARD: Push the current page on top of the backward stack. Then pop the page on top of the forward stack and make it the new current page. If the forward stack is empty, the command is ignored.
VISIT <url>: Push the current page on top of the backward stack, and make the given URL the new current page. The forward stack is emptied.
QUIT: Quit the browser.

Assume that the browser initially loads the page at the URL http://www.acm.org/.

Input

The first line of input contains a single positive integer giving the number of test cases that follow. This line is followed by a blank line, and there is also a blank line between two consecutive test cases.

Each test case is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all uppercase. URLs contain no whitespace and have at most 70 characters. You may assume that no test case requires more than 100 elements in either stack at any time. Each test case ends with the QUIT command.

Output

For each test case, produce output as described below. The outputs of two consecutive test cases are separated by a blank line.

For each command other than QUIT, print the URL of the current page after the command is executed, provided the command is not ignored. Otherwise print Ignored. Each command's output is printed on its own line. The QUIT command produces no output.

Examples3

Example 1

Input

1

VISIT http://acm.ashland.edu/
VISIT http://acm.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT http://www.ibm.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT

Expected output

http://acm.ashland.edu/
http://acm.baylor.edu/acmicpc/
http://acm.ashland.edu/
http://www.acm.org/
Ignored
http://acm.ashland.edu/
http://www.ibm.com/
http://acm.ashland.edu/
http://www.acm.org/
http://acm.ashland.edu/
http://www.ibm.com/
Ignored

Example 2
Input
```
1

BACK
FORWARD
QUIT
```
Expected output
```
Ignored
Ignored
```

Example 3

Input

1

VISIT http://a.com/
BACK
FORWARD
QUIT

Expected output

http://a.com/
http://www.acm.org/
http://a.com/