Иногда вспоминаешь старого друга и начинаешь вспоминать все, что с ним связано. Хорошо, что есть социальные сети: они хранят вашу переписку с самого знакомства, и можно с легкостью прочитать, о чем же вы спорили 10 лет назад.
Формально, ваша переписка — упорядоченная по времени последовательность сообщений, пронумерованных от 1 до n, где n — общее количество сообщений в переписке.
Каждое сообщение может содержать ссылку на более раннее сообщение, на которое оно является ответом. При открытии сообщения с номером x или при переходе по ссылке на сообщение с номером x диалог показывается так, что видны k сообщений до этого сообщения, само сообщение x и k сообщений после этого сообщения. Если до или после текущего сообщения было менее k сообщений, то все они отображаются.
Изучая старую переписку, вы всегда читаете все сообщения, показанные на экране, а затем переходите по ссылке в текущем сообщении x (в которое пришли по ссылке), если такая есть, и читаете дальше.
Определите количество различных сообщений, которые вы прочтете, если начинать читать переписку, открыв диалог на сообщении t, для каждого t от 1 до n. Считайте ответ для каждого случая независимо. Если начинать читать с сообщения номер x, то на экране изначально показаны k сообщений до сообщения x, само сообщение x и k сообщений после. Сообщения, прочитанные несколько раз, считаются за одно.
Выходные данные
Выведите n целых чисел, где i-е число должно быть равно количеству различных сообщений, которые можно прочитать, если начинать читать с i-го сообщения и переходить по ссылкам до тех пор, пока это возможно.
Примечание
Если начинать с шестого сообщения в первом примере, то вы прочитаете шестое сообщение, затем второе, затем первое и закончите, т. к. из первого сообщения нет ссылки.
Если начинать с шестого сообщения во втором примере, то вы сначала прочтете пятое, шестое и седьмое сообщение, затем перейдете по ссылке в пятое сообщение и прочтете четвертое, пятое и шестое сообщение, затем перейдете по ссылке в четвертое сообщение и прочитаете третье, четвертое и пятое сообщение, наконец, перейдете по ссылке в третье сообщение и прочитаете второе, третье и четвертое сообщение. Больше переходить по ссылкам вы не будете, так как из третьего сообщения ссылки нет. Итого вы прочтете все сообщения со второго по седьмое, таких шесть.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 0
0 1 1 2 3 2
|
1 2 2 3 3 3
|
|
2
|
10 1
0 1 0 3 4 5 2 3 7 0
|
2 3 3 4 5 6 6 6 8 2
|
|
3
|
2 2
0 1
|
2 2
|