You are Big Fish, and you manage a vast country.

There are many cities in this country, and many rivers between them. Careful observation reveals that every city has exactly one river flowing out of it, either into the sea or into another city. Since water always flows to lower elevations, there are no cycles formed by the rivers, and you find that there is only one river that flows into the sea.

At any given moment, a rainstorm may occur over a city. The river flowing out of this city will surge, and the rivers flowing out of all cities downstream will also surge.

There is no good way to prevent damage at the city where the rainstorm occurs, but in every city downstream, they can prepare for one of the rivers flowing into them. If a city is prepared for a river flowing into it, it can avoid the massive damage caused by that river surging.

Initially, you can order each city to prepare for one of the rivers flowing into it (or choose not to prepare at all). Because time is tight before and after each rainstorm, you can only issue a limited number of emergency orders. There are two types of emergency orders:

1. Order a city to cancel its preparation for a river flowing into it.
2. Order a city to prepare for a specific river flowing into it.

Due to human resource constraints, you cannot have a city prepared for two rivers simultaneously. Therefore, if you want a city that is already prepared for one river to prepare for another, you must first cancel its current preparation.

Now, $q$ rainstorms arrive one after another. You can observe which city a rainstorm will hit before it happens. Before each rainstorm, you can issue some emergency orders to prevent downstream cities from suffering massive damage, and you can also issue some emergency orders after the rainstorm to prepare for future events. Naturally, you want to issue as few emergency orders as possible. Can you find an efficient method?

Task

You need to implement two functions to complete the task:

• init(n, father):
  • This function will be called once at the beginning of the task. It provides information about the country, and you need to provide the initial preparations for each city.
  • n is the number of cities, numbered $1$ to $n$.
  • father is an array of length $n - 1$ with indices $[0 \dots n-2]$, where $father_i$ is the index of the city that the river from city $i + 2$ flows into. The river from city $1$ flows into the sea. It is guaranteed that $father_i < i + 2$.
  • Return an array of length $n$ representing the initial preparation for each city. The $(i-1)$-th number represents the city that city $i$ is prepared for; if it is $0$, it means no preparation is made.
• solve(x):
  • This function may be called multiple times after init. It indicates that a rainstorm is about to hit city $x$. You need to use the set function to issue emergency orders to prevent massive damage to downstream cities.
  • You must ensure that the set function is called no more than $60$ times within this function.
  • You should call the wait function exactly once in this function. Commands issued before calling wait will be executed before the rainstorm arrives, and commands issued after wait will be executed after the rainstorm.

You can call the following two functions to implement solve:

• set(x, p):
  • Can only be called within the solve function. It orders city $x$ to prepare for the river flowing from city $p$. If $p$ is $0$, it means city $x$ cancels its current preparation.
  • Can be called at most $60$ times per solve.
  • Forbidden to be called in the init function.
• wait():
  • Must be called exactly once per solve. It indicates that you have completed the preparations before the rainstorm. When called, you must ensure that all cities downstream of the rainstorm-affected city are prepared for the river flowing into them.
  • You can continue to perform operations after this function is called to prepare for the next rainstorm.
  • Forbidden to be called in the init function.

Note: A city either makes no preparation or prepares for exactly one river flowing into it.

If your operations are illegal or do not meet the requirements, the test case will immediately receive $0$ points.

If there are any unclear points, see the sample and the grader download, which includes sample programs.

Implementation Details

This problem only supports the C++ language.

You must submit a single source file implementing the init and solve functions as described above, following the naming and interface conventions. You must include the header file river.h.

std::vector<int> init(int n, std::vector<int> father);
void solve(int x);

The interfaces for set and wait are as follows:

void set(int x, int p);
void wait();

Sample Grader

The provided sample grader will read a tree and all operations in the following format:

The first line contains two positive integers $n, q$, representing the number of nodes and the number of queries.

The second line contains $n-1$ integers representing the father array.

The next $q$ lines each contain an integer $x$, representing a call to solve(x).

Input 1

8 8
1 1 3 3 4 5 3
7
1
1
7
3
6
5
1

Output 1

2 6
ok you are right!

Note 1

This is the information provided after successfully completing all operations. The first integer represents the maximum number of set calls in a single round, and the second is the total number of set calls.

Subtasks

$1 \leq n \leq 50000$, $1 \leq q \leq 500000$.

You cannot call the set command more than $60$ times in one round.

If you do not complete the task within the specified time and memory limits, you will receive $0$ points.

Otherwise, let $x$ be the maximum number of set calls in each solve ($\max$). Your score will be:

$$ f \left( x \right) = \begin{cases} 0 & 60 \lt x \\ 100 - 18 \times \sqrt{x - 35} & 36 \leq x \leq 60 \\ 100 & \operatorname{otherwise} \end{cases} $$

Your final score will be the minimum score across all test cases.

If the number of set calls in each solve does not exceed $60$ and all operations are legal:

The grader is guaranteed to run within $1\,\mathrm{s}$.

The grader is guaranteed to use no more than $10\,\mathrm{MB}$ of memory.