Вы — Большая Рыба, и вы управляете огромной страной.

В этой стране много городов, а между ними проложено много рек. После тщательного наблюдения выяснилось, что из каждого города вытекает одна река, которая либо впадает в море, либо течет в другой город. Поскольку вода всегда течет вниз, циклов из рек не существует, и вы обнаружили, что существует только одна река, впадающая в море.

В какой-то момент времени над определенным городом может начаться сильный ливень. Поток реки, вытекающей из этого города, резко увеличится, и поток рек, вытекающих из всех городов, расположенных ниже по течению, также резко возрастет.

Для города, над которым идет ливень, нет хороших способов защиты, но в каждом городе, расположенном ниже по течению, можно подготовиться к одной из впадающих в него рек. Если город подготовился к одной из впадающих в него рек, он может избежать огромного ущерба, вызванного резким увеличением потока этой реки.

В самом начале вы можете приказать каждому городу подготовиться к одной из впадающих в него рек (конечно, можно не делать никакой подготовки). В процессе последующих ливней, из-за нехватки времени, вы можете отдавать только экстренные приказы. Существует два типа экстренных приказов:

1. Приказать городу отменить подготовку к впадающей в него реке.
2. Приказать городу подготовиться к одной из впадающих в него рек.

Из-за ограничений человеческих ресурсов вы не можете позволить городу подготовиться к двум рекам одновременно. Поэтому, если вы хотите, чтобы город, который уже подготовился к одной реке, подготовился к другой, вы должны сначала отменить его текущую подготовку.

Сейчас последовательно происходит $q$ ливней. Перед каждым ливнем вы можете наблюдать, над каким городом он произойдет. Перед каждым ливнем вы можете отдать несколько экстренных приказов, чтобы избежать огромного ущерба для городов ниже по течению, а после ливня вы можете отдать несколько экстренных приказов, чтобы подготовиться к будущим событиям. Конечно, вы хотите, чтобы количество отданных экстренных приказов было минимальным. Сможете ли вы найти эффективный способ?

Задание

Вам необходимо реализовать две функции для выполнения задач:

• init(n, father):
  • Эта функция будет вызвана в самом начале выполнения задачи, ровно один раз. Она предоставит вам некоторую информацию о стране, и вам нужно вернуть начальную подготовку для каждого города.
  • n — количество городов, города пронумерованы от $1$ до $n$.
  • father — массив длины $n - 1$ с индексами $[0 \dots n-2]$, где $father_i$ — номер города, в который впадает река из города $i + 2$. Город $1$ — это город, река из которого впадает в море. Гарантируется, что $father_i < i + 2$.
  • Верните массив длины $n$, представляющий начальную подготовку каждого города. $i$-й элемент массива (индексация с 1) означает, что город $i$ подготовился к реке, приходящей из этого города. Если значение равно $0$, это означает, что никакой подготовки не сделано.
• solve(x):
  • Эта функция может вызываться многократно после вызова init, указывая, что ливень надвигается на город $x$. Вам нужно использовать функцию set для отдачи экстренных приказов, чтобы избежать огромного ущерба для городов ниже по течению.
  • Вы должны гарантировать, что количество вызовов функции set внутри этой функции не превышает $60$.
  • В этой функции вы должны вызвать функцию wait ровно один раз. Команды, отданные до вызова wait, будут выполнены до начала ливня, а команды, отданные после вызова wait, будут выполнены после ливня.

Для реализации solve вы можете вызывать следующие две функции:

• set(x, p):
  • Можно вызывать только внутри функции solve. Означает, что город $x$ должен подготовиться к реке, вытекающей из города $p$. Если $p$ равно $0$, это означает, что город $x$ отменяет подготовку к впадающей в него реке.
  • За один вызов solve можно вызвать не более $60$ раз.
  • Запрещено вызывать внутри функции init.
• wait():
  • Вызывается ровно один раз при каждом вызове solve. Означает, что вы завершили подготовку перед ливнем. При вызове необходимо гарантировать, что к этому моменту все города ниже по течению от города, над которым идет ливень, подготовились к впадающим в них рекам.
  • После вызова этой функции можно продолжать отдавать команды для подготовки к следующему ливню.
  • Запрещено вызывать внутри функции init.

Обратите внимание: город либо не делает никакой подготовки, либо готовится к одной из впадающих в него рек.

Если ваши действия недопустимы или не соответствуют требованиям, за этот тест вы немедленно получите $0$ баллов.

Если что-то осталось неясным, обратитесь к примерам и скачиваемым файлам с тестирующей системой, в которых содержатся примеры программ.

Детали реализации

Данная задача поддерживает только язык C++.

Вы должны отправить один исходный файл, реализующий функции init и solve, следуя указанным именам и интерфейсам. Вам необходимо подключить заголовочный файл river.h.

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

Информация об интерфейсах функций set и wait:

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

Примеры

Пример 1 Входные данные

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

Пример 1 Выходные данные

2 6
ok you are right!

Примечание к примеру 1

Это сообщение выводится после успешного выполнения всех операций. Первое целое число — это максимальное количество вызовов set за один раунд, второе — общее количество вызовов set.

Подзадачи

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

Вы не можете вызывать более $60$ команд за один раунд.

Если вы не выполните задание в рамках установленных ограничений по времени и памяти, вы получите $0$ баллов.

В противном случае, пусть $x$ — максимальное количество вызовов set в каждом solve ($\max$). Тогда ваш балл рассчитывается по формуле:

$$ 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} $$

Вашим итоговым баллом будет минимальный балл среди всех тестовых случаев.

Если количество вызовов set в каждом solve не превышает $60$ и все операции корректны:

Гарантируется, что время работы интерактора не превышает $1\,\mathrm{s}$.

Гарантируется, что использование памяти интерактором не превышает $10\,\mathrm{MB}$.