Turn on the lights, close the doors!

This is an interactive problem.

In a new quest gaining popularity in city N, the player must escape a maze of an unknown number of rooms. Each room has some doors, one light bulb, and two switches. The first switch in each room turns the light on and off and can be used any number of times. The second switch can be activated only once. It locks all doors leading out of the room right after the player passes through one of them, after which the room becomes unreachable.

Initially all rooms are open, and some of them have their lights on. The goal is to turn on the lights in all rooms and to lock all rooms except one (any one). The problem would be simple if the player could leave marks in the rooms, but the quest rules forbid this. When the player enters a room, the player sees only the number of doors in that room, whether the light is on, and the door through which the player just entered. The player always sees the doors in the same order and numbers them the same way.

The player can perform the following actions:

• Turn on the light in the room where the player currently is.
• Turn off the light in the room where the player currently is.
• Try to pass through one of the doors. The attempt succeeds if the room on the other side is not locked. Passing through a door can also activate the locking of the room being left.
• End the game, if the player believes that all rooms except the current one are locked and the lights are on in every room.

The program first receives whether the light in the starting room is on, the number of doors in that room, and the number 0 (the player did not enter this room through any door).

It is guaranteed that the number of rooms is at most 50 and the number of doors is at most 100. Each door connects two rooms and is counted once. It is also guaranteed that every room can be reached from every other room through the doors, and that no pair of rooms is connected by more than one door.

The maze format in the sample tests is as follows: the first line gives the number of rooms and doors, then the initial light state of each room (1 if on, 0 if off), then the pairs of rooms joined by doors, and finally the starting room number. The first three tests show this structure, but it does not match the input your program actually receives. An example interaction is shown in the hints.

Your program must make at most $30\,000$ queries. Exceeding this limit gives the verdict Wrong Answer. Ending the game also counts as one query.

Flush the output buffer after every query: fflush(stdout) in C++, System.out.flush() in Java, stdout.flush() in Python, flush(output) in Pascal. For other languages, check the documentation.

A remark that the graph is a tree means that the maze has no cycle route of length greater than two that visits no room twice.

A remark that the graph is a cycle means that all rooms lie on one cycle route that visits no room twice.

Below is one possible interaction protocol for the first test. The left column is the checker's output, and the right column is a possible output of your program.

off 1 0
              turn on
              go 1 keep
off 1 1
              turn off
              turn on
              turn on
              go 1 lock
on 1 1
              go 1 lock
locked
              turn off
              turn on
              done