Russian ACM ICPC competitors form a strange and miraculous community, and Ural ACMers — even more so. A newbie can’t even begin to understand strange laws and patterns, according to which everything in this community works. The Guardian of Traditions Alexander manages not only to understand everything about Ural ACM, but also to discover new patterns.

One of his points of interest lately is searching for dependencies between the distribution of places at the Ural Federal University Championship and the team’s rank at the ACM ICPC World Finals, given that the team qualifies for them.

Alexander has already made huge progress in his research. It is well-known that every year n teams participate in UrFU Championship and each one of them gets an id number from 1 to n (the competition is held only once a year). Once upon a time upon completion of another UrFU Championship Alexander wrote down a sequence of teams’ ids, so that the id on i-th position belonged to the team that took i-th place at the Championship. Alexander quickly noticed that his sequence was just a permutation of integers from 1 to n. Since then, he began writing down such permutations after every UrFU Championship and started looking for interesting patterns in them.

For a long time he had no success, but then a turning year has come. This year Alexander wrote down the permutation p: p(1), p(2), p(3),…,p(n). After that the following pattern has emerged: if in some year the team k took i-th place, then the next year i-th place would be taken by a team p(k). For the last m years now (including the turning year) the UrFU Championship results confirm that pattern.

ACM ICPC Finals are coming soon, and Alexander wants very badly to predict the results of this competition. In addition to discovering this new pattern, he managed to find the Characteristic Vector q. He believes that if permutations corresponding to last m years were placed into a matrix A, so that the first line described the results of the turning year UrFU Championship, the next line — the results for the next year and so on, and vector q were multiplied by this matrix, the resulting vector would help make an accurate prediction for team UrFU at the upcoming Finals.

Calculate the product of q and A for Alexander, please.

The first line contains two integers m and n (2 ≤ m, n ≤ 5 × 10⁴).

The second line contains n integers p(1), p(2), …, p(n) (1 ≤ p(i) ≤ n, p(i) differ for different i) — elements of permutation p.

In the third line the components of the Characteristic Vector q are given: m integers q₁, q₂, …, q_m (0 ≤ q_i ≤ 10⁹).

In a single line output n integers separated by spaces — components of the resulting vector q× A.