题目背景

这是一道 IO 交互题。

题目描述

Indiana Jones has stuck in the Uniform Cave. There are many round chambers in the cave, and all of them are indistinguishable from each other. Each chamber has the same number of one-way passages evenly distributed along the chamber’s wall. Passages are indistinguishable from each other, too. The Cave is magical. All passages lead to other chambers or to the same one. However, the last passage, after all passages are visited, leads to the treasure. Even the exact number of chambers is a mystery. It is known that each chamber is reachable from each other chamber using the passages.

Dr. Jones noticed that each chamber has a stone in the center. He decided to use these stones to mark chambers and passages. A stone can be placed to the left or to the right of one of the passages. When Indiana Jones enters the chamber all that he can observe is the location of the stone in the chamber. He can move the stone to the desired location and take any passage leading out of the chamber.

Your task is to help Indiana Jones to visit every passage in the Uniform Cave and find the treasure.

输入格式

First, the testing system writes the integer m — the number of passages in each chamber ($2 \leq m \le 20$).

Dr. Jones enters the chamber and sees, in the next line, where the stone is placed: either in the “center” of the chamber or to the “left”, or to the “right” of some passage. On the first visit to the chamber, the stone is in the center.

Your solution shall output his actions: the number and the side of the passage to place the stone to, and the number of the passage to take. Both numbers are relative to the passage marked by the stone, counting clockwise from 0 to m − 1. If the stone is in the center of the chamber, the origin is random.

For example, “3 left 1” tells that Dr. Jones moves the stone three passages clockwise and places it to the left of the passage, then he takes the passage to the right of the initial stone position.

After each move testing system tells either the location of the stone in the next chamber or “treasure”, if Indiana Jones had found it. The testing system writes “treasure” when all the passages are visited.

If Dr. Jones does not find the treasure room after 20 000 passages are taken, he starves to death, and your solution receives the “Wrong Answer” outcome. You also receive this outcome if your solution terminates before all passages are taken.

The total number of chambers in the cave is unknown, but you may assume that it does not exceed 20, and that each chamber is reachable from every other chamber.

题目大意

现在在一个洞穴里寻宝。这个洞穴有 $n$ 个房间。房间是不可区分的。每个房间都引出 $m$ 个单向道路，终点可以是自己也可以是其它房间。这些单向道路的入口均匀地分布在房间的墙壁上，且每条单向道路也是不可区分的。保证整个有向图是强连通的。你一开始在某一个房间，如果遍历了所有的边，就能找到宝藏。

每个房间有一个石子，这也是你区分房间和道路的唯一工具。一开始石子是在这个房间的某一个通道的入口前，并且是放在中央的。你每到一个房间，可以选择将石子移动到某个通道前，把它放在通道左边或者右边（不能是中间），然后再从某个通道走出去。你不可以把石子带出房间。你并没有携带过多的食物，所以如果你走了超过 $20000$ 条边，你就会因为食物耗尽而饿死。你要在规定步数之内找到宝藏。

输入格式

共 $m$ 行，每行一个字符串，表示该房间内石头被放置的位置为某个通道的 $"center"$，$"left"$ 或 $"right"$。当第一次到达一个墓室时，石头处在中间(center)。

输出格式

每行一个非负整数 $st$，表示将石头放在原所在位置顺时针方向第 $st$ 个通道入口；一个字符串，表示将它放在该通道入口 $dir$ 的位置（$"center"$，$"left"$ 或 $"right"$）；一个非负整数 $pa$ ，表示从石子的原来位置顺时针方向第 $pa$ 个通道走出。

通道顺时针从 $0$ 到 $m−1$ 编号。如果石头一开始是在中间（$center$），它会位于随机一个通道入口处。

每走一步，评测机会返回该房间的石头的位置或者 $"treasure"$ （如果您找到了宝藏且所有的通道都被走过时，就会反馈 $"treasure"$ ）。

举个栗子：3 left 1 表示将石头顺时针移动了 $3$ 个通道，并将其放置在该通道的左侧，然后走向最初石头所在位置的右侧的通道。

你最多可以进行 $20000$ 次操作。

2
center
left
center
left
right
treasure

0 left 0
1 left 1
1 right 0
0 left 0
1 right 0

提示

Dr. Jones enters the example cave and sees that the stone in the first chamber is in the center. He marks the chamber by placing the stone to the left of some passage and takes it. He sees the chamber where the stone is to the left of the passage, so he is in the first chamber again. He moves the stone clockwise and takes the passage marked by it. This passage leads to the second chamber. He marks it by placing the stone to the right of some passage and takes another one. He is in the first chamber again, so he returns to the second chamber and takes the remaining passage. This passage leads to the treasure.