Do you know the company Just Ordinary Inventions? The business of this company is to create "just ordinary inventions."

JOI-kun is playing the latest game developed by Just Ordinary Inventions.

This game involves exploring a dungeon consisting of several rooms and several paths. A path connects two distinct rooms in the dungeon and is traversable in both directions. For any two distinct rooms, there is at most one path connecting them, and there are no paths where both ends are the same room. Furthermore, it is known that any two rooms in the dungeon can be reached from each other by using some number of paths. Each room is very similar to the others, and rooms with the same number of outgoing paths cannot be distinguished from each other just by looking at the appearance of the room.

In this game, to assist with exploration, each room is equipped with a mark and a pedestal. The paths leading out of a room can be counted as the 1st, 2nd, ... path based on the mark. The structure of the dungeon does not change during the game. Therefore, if you move from the same room using the same numbered path, you will always arrive at the same room. The pedestal is decorated with one gem whose color can be changed by the player. The color of the gem is one of color 1, color 2, ..., color $X$, and the color of the gem in each room at the start of the game is color 1. The color of the gem will not change unless the player operates it.

JOI-kun realized that if the structure of this dungeon, i.e., how the rooms are connected by paths, were known, this game could be easily cleared. However, no matter how much JOI-kun tried, he could not determine the structure of the dungeon. Therefore, you have decided to write a program to determine the structure of the dungeon on behalf of JOI-kun.

Task

Create a program that explores the dungeon and determines its structure. However, since JOI-kun did not want the structure of the dungeon to be completely revealed, the program must not answer the structure of the dungeon directly, but instead must answer the value of "how many pairs of rooms are there that can be reached using a minimum of exactly $i$ paths" (pairs where the order of rooms is swapped are considered the same pair) for each integer $i$ from 1 to $R$.

To explore the dungeon, you are provided with a library that performs the following actions:

• Know how many paths lead out from the current room.
• Know the color of the gem decorated on the pedestal in the current room.
• Change the color of the gem decorated on the pedestal in the current room to a specified color (you can also specify the same color as the current one). After that, choose one path leading out from the room and move to another room using that path.
• Know which number path the last used path was among the paths leading out from the current room.

Implementation Details

You must write one program that implements the method for JOI-kun to answer. The program must include dungeon2.h.

The program must implement the following routine:

• void Inspect(int R)
  • This routine is called exactly once at the beginning.
  • The argument $R$ indicates that you must answer the value of "how many pairs of rooms are there that can be reached using a minimum of exactly $i$ paths" for each integer $i$ from 1 to $R$.

Also, you must call the following routine to answer the questions:

• void Answer(int D, int A)
  • The arguments $D$ and $A$ indicate that you are answering that "there are $A$ pairs of rooms that can be reached using a minimum of exactly $D$ paths" in this call.

However, the call to Answer must satisfy the following conditions: $D$ must be an integer between 1 and $R$. If this is not satisfied, it will be judged as Incorrect [1]. Answer must not be called more than once with the same argument $D$. If this is not satisfied, it will be judged as Incorrect [2]. Answer must be called exactly $R$ times. If this is not satisfied, it will be judged as Incorrect [3]. $A$ must be the number of pairs of rooms that can be reached using a minimum of exactly $D$ paths. If this is not satisfied, it will be judged as Incorrect [4].

If a call to Answer is judged as incorrect, the subsequent program may not be executed.

In addition, you can call the following routines in your program:

• void Move(int I, int C)
  • The argument $I$ is the number of the path the player chooses to move. Immediately after this call, the player moves to another room using the $I$-th path leading out from the current room.
  • The argument $C$ indicates that the color of the gem decorated on the pedestal in the current room is changed to color $C$ before moving to the room.

However, the call to Move must satisfy the following conditions: The argument $I$ must be an integer between 1 and $K$, where $K$ is the number of paths leading out from the room where the player is currently located. If this is not satisfied, it will be judged as Incorrect [5]. The argument $C$ must be an integer between 1 and $X$, where $X$ is the number of types of gem colors. The value of $X$ is determined for each subtask. If this is not satisfied, it will be judged as Incorrect [6]. * Move must not be called more than 1,500,000 times. If it is called more, it will be judged as Incorrect [7].

• int NumberOfRoads()

  • This function returns the number of paths leading out from the room where the player is currently located.

• int LastRoad()

  • This function returns which number path the last used path was among the paths leading out from the current room. However, if this function is called before Move is called even once, it returns -1.

• int Color()

  • This function returns the color of the gem decorated on the pedestal in the room where the player is currently located.

After the routine Inspect is called, the answer is judged.

You are free to implement other routines for internal use or to declare global variables. However, your submission must not interact with standard input/standard output or any other files in any way.

Compilation and Execution

A sample grader is provided in the archive that can be downloaded from the contest site. This archive also contains a sample of the file you must submit.

The sample grader consists of a single file, grader.c or grader.cpp. To test your program, execute the following commands:

• For C: gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm
• For C++: g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

If compilation is successful, an executable named grader is generated.

Note that the actual grader used for evaluation is different from the sample grader. The sample grader runs as a single process, reading input from standard input and writing results to standard output.

Constraints

All input data satisfies the following conditions: $2 \le N \le 200$ $3 \le X \le 100$ $1 \le R \le 200$ $1 \le D_i \le N - 1$ ($1 \le i \le N$) $1 \le T_{ij} \le N$ and $T_{ij} \neq i$ ($1 \le i \le N, 1 \le j \le D_i$) $T_{i1}, T_{i2}, \dots, T_{iD_i}$ ($1 \le i \le N$) are distinct. For each $i, j$ ($1 \le i \le N, 1 \le j \le D_i$), there exists $k$ ($1 \le k \le D_{T_{ij}}$) such that $T_{T_{ij}k} = i$. Any two rooms can be reached from each other by using some number of paths.

Subtasks

In the following, let $N$ be the number of rooms and $M$ be the number of paths in the dungeon in the input data.

Subtask 1 [17 points]

The following conditions are satisfied: $N \le 50$ $M \le 100$ * $X = 100$

Subtask 2 [27 points]

The following conditions are satisfied: $N \le 50$ $M \le 100$ * $X = 3$

Subtask 3 [56 points]

• $X = 3$ is satisfied.

In this subtask, the score is determined as follows: Let $L$ be the maximum value of the following for all test cases in this subtask: $\frac{C}{M}$, where $C$ is the number of calls to Move. In this case, the score for this subtask is: If $L \le 14$, 56 points. If $14 < L \le 32$, $\lfloor 70 - L \rfloor$ points. If $32 < L \le 64$, $\lfloor 54 - \frac{L}{2} \rfloor$ points. * If $64 < L$, 0 points.

Here, $\lfloor x \rfloor$ represents the largest integer not exceeding $x$.

Examples

Input 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Output 1

Inspect(3)
NumberOfRoads() -> 1
LastRoad() -> -1
Move(1,2)
Color() -> 1
LastRoad() -> 1
NumberOfRoads() -> 3
Move(1,3)
Color() -> 2
Answer(1,4)
Answer(2,2)
Answer(3,0)

Note

The function calls in this example are not necessarily meaningful calls.