Алиса и Боб известны своей любовью к передаче сообщений друг другу. В этот раз у них есть корневое дерево, где Боб находится в корне, а во всех остальных вершинах находится по одной копии Алисы. Корневая вершина имеет номер 0, а остальные пронумерованы от 1 до n.
В некоторые моменты времени некоторая из копий Алисы отправляет Бобу сообщение и хочет получить на него ответ. Назовём такую копию инициатором. Процесс отправки сообщения проходит следующим образом:
- Инициатор посылает сообщение человеку, стоящему в вершине, являющейся предком вершины инициатора, и начинает ждать ответа.
- Когда какая-то из копий Алисы получает сообщение от кого-либо из вершин-потомков, она посылает это сообщение в вершину-предка и начинает ждать ответа.
- Когда Боб получает сообщение от кого-то стоящего в непосредственном ребёнке корня, он сразу отправляет в эту вершину ответ.
- Когда какая-либо из копий Алисы (не инициатор) получает ответ, которого она ожидает, она немедленно отправляет его в ту дочернюю вершину, из которой пришёл запрос.
- Когда инициатор получает ожидаемый ответ, она становится свободной и никому ничего не посылает.
- Есть особый случай: никакая копия Алисы не может одновременно ждать ответа на два сообщения, поэтому если какая-то копия получает сообщение, когда она уже ждёт ответа на другое сообщение, то она просто отклоняет запрос, отправляя его вершине, которая его прислала. Далее копии Алисы обрабатывают этот ответ так же, как если бы он пришёл от Боба.
- Передача сообщения родительской вершине или ответа ребёнку происходит мгновенно, но сообщение или ответ доходит до получателя всегда через 1 секунду.
Если какая-то из копий Алисы получает несколько сообщений из вершин-потомков одновременно, и в этот момент данная копия не занята ожиданием ответа, то она обрабатывает сообщение, посланное инициатором с минимальным номером, а все остальные отклоняет. Если какая-либо из копий Алисы получает одновременно сообщение от потомка и ответ, которого она ожидает, то считается, что она успевает сначала обработать ответ, а затем в ту же секунду обработать пришедшие сообщения как обычно.
Вам даны моменты времени, в которые копии Алисы становятся инициаторами и отправляют сообщения Бобу. Для каждого сообщения найдите момент времени, когда инициатор получит ответ (от Боба или от какой-то из копий Алисы).
Можете считать, что если какая-то из Алис хочет отправить сообщение (то есть стать инициатором) в момент ожидания ответа, она сама немедленно отклоняет это сообщение и получает ответ сама от себя за нулевое время.
Выходные данные
Выведите m целых чисел, i-е из которых должно быть равно моменту времени, в который инициатор i-го сообщения получит ответ.
Примечание
В первом примере первое сообщение инициируется в момент времени 6, достигает Боба в момент времени 10, а инициатор получает ответ в момент времени 14. Второе сообщение достигает вершины 2 в момент времени 11. В это время копия Алисы во второй вершине все еще ждет ответа на первое сообщение, поэтому отклоняет второе. Ответ достигает инициатора в момент времени 13. Третье сообщение вообще никому не отправляется, т. к. в момент времени 11 Алиса в вершине 5 ждет ответа на второе сообщение.
Во втором примере первое сообщение достигает Боба, а второе отклоняется Алисой в вершине 1, т. к. приоритет имеет сообщение, отправленное инициатором с меньшим номером.
В третьем примере первое и третье сообщение достигнут Боба, а второе будет отклонено Алисой в вершине 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
0 1 2 3 2 5
4 6
6 9
5 11
|
14 13 11
|
|
2
|
3 2
0 1 1
2 1
3 1
|
5 3
|
|
3
|
8 3
0 1 1 2 3 3 4 5
6 1
8 2
4 5
|
7 6 11
|