ACM — загадочный мир, а уж уральский ACM и подавно. Новичку не понять странных законов, по которым живёт этот мир, и сложно заметить взаимосвязи между событиями в нём. Хранитель традиций Александр не только понимает, что к чему в уральском ACM-е, но и ведёт масштабную исследовательскую деятельность по выявлению новых закономерностей.

В последнее время его интересует зависимость между распределением мест на Чемпионате УрФУ и тем, какое место займёт команда УрФУ на финале ACM ICPC, если на него попадёт.

В изучении этого вопроса Александр уже добился немалых успехов. Например, известно, что каждый год (Чемпионат УрФУ проводится строго раз в год) в соревновании принимает участие ровно n команд, и каждая из них получает уникальный порядковый номер от 1 до n. Как-то раз после завершения очередного Чемпионата УрФУ Александр выписал такую последовательность из n чисел, что на i-м месте в ней оказался порядковый номер команды, занявшей на чемпионате i-е место. Александр заметил, что выписанная последовательность — перестановка чисел от 1 до n. После этого он начал выписывать такую перестановку по итогу каждого Чемпионата УрФУ и стал изучать её свойства.

Долгое время зависимость между перестановками найти не удавалось, пока не наступил переломный год. В этот год по итогу Чемпионата УрФУ Александр получил перестановку p: p(1), p(2), p(3),…,p(n). В дальнейшем, в результатах чемпионата обнаружилась следующая закономерность: если в некотором году на i-м месте оказалась команда с номером k, то в следующем году на этом месте будет команда с номером p(k). С тех пор вот уже m лет (включая переломный год) результаты Чемпионата УрФУ подчиняются найденному Александром закону.

Совсем скоро финал ACM ICPC, и Александру жизненно необходимо предсказать его результат. Помимо выписанных перестановок за m последних лет, ему удалось найти Характеристический Вектор q. Он верит, что если эти m перестановок записать в матрицу A таким образом, что в первой строке матрицы окажется перестановка для результата переломного года, в следующей строке — перестановка для результата следующего за переломным года, и т. д., а затем умножить на эту матрицу вектор q, то итоговый вектор поможет определить результат команды УрФУ на предстоящем финале.

Найдите произведение вектора q на матрицу A.

В первой строке через пробел записаны два целых числа m и n (2 ≤ m, n ≤ 5 × 10⁴).

Во второй строке даны n целых чисел p(1), p(2), …, p(n) (1 ≤ p(i) ≤ n, p(i) различны для различных i) — элементы перестановки p.

В третьей строке даны m целых чисел q₁, q₂, …, q_m (0 ≤ q_i ≤ 10⁹) — элементы Характеристического Вектора q.

В единственной строке выведите n чисел через пробел — элементы вектора-произведения q× A.