Единственное отличие между простой и сложной версиями — ограничения.
Есть \(n\) детей, каждый из которых читает уникальную книгу. В конце каждого дня \(i\)-й ребёнок отдаёт свою книгу \(p_i\)-му ребёнку (в случае, когда \(i = p_i\) ребенок отдает свою книгу самому себе). Гарантируется, что все значения \(p_i\) — различные целые числа от \(1\) до \(n\) (то есть \(p\) — перестановка). Последовательность \(p\) не меняется изо дня в день, она фиксированная.
Например, если \(n=6\) и \(p=[4, 6, 1, 3, 5, 2]\), то в конце первого дня книга \(1\)-го ребёнка будет у \(4\)-го ребёнка, книга \(2\)-го ребёнка будет у \(6\)-го ребёнка и так далее. В конце второго дня книга \(1\)-го ребёнка будет у \(3\)-го ребёнка, книга \(2\)-го ребёнка будет у \(2\)-го ребёнка и так далее.
Перед вами стоит задача — для каждого \(i\) от \(1\) до \(n\) определить число дней, через которое книга \(i\)-го ребёнка вернётся обратно к нему в первый раз.
Предположим что \(p = [5, 1, 2, 4, 3]\). Книга \(1\)-го ребёнка будет передана следующим детям:
- после \(1\)-го дня она будет у \(5\)-го ребёнка,
- после \(2\)-го дня она будет у \(3\)-го ребёнка,
- после \(3\)-го дня она будет у \(2\)-го ребёнка,
- после \(4\)-го дня она будет у \(1\)-го ребёнка.
Таким образом, после четвертого дня книга первого ребёнка вернётся к своему владельцу. Книга четвёртого ребёнка вернётся к нему в первый раз сразу после первого дня.
Вы должны ответить на \(q\) независимых запросов.
Выходные данные
Для каждого запроса выведите ответ на него: \(n\) целых чисел \(a_1, a_2, \dots, a_n\), где \(a_i\) — номер дня, в конце которого книга \(i\)-го ребёнка вернётся к нему в первый раз в этом запросе.