Zhou Kangyang created human civilization.

In April 11451 A.D. human built cities on Mars. For each , there is a merchant in the city and a unidirectional road from the city to the city .

At the beginning of each year, the merchant in the city will go along the road to the city .

Let's call a city start to be bustling in the -th year iff the -th year is the earliest year in which there are at least merchants in the city.

Please tell me, in which year each city start to be bustling.

The first line contains two integers  ().

The second line contains  integers  ().

Print  integers, the -th of them is the number of the year in which city  start to be bustling. If a city will never be bustling, output '-1'.

3 2
1 3 2

-1 -1 -1

5 2
2 3 1 5 5

-1 -1 -1 -1 1

10 2
1 6 8 5 9 9 3 8 10 5

-1 -1 -1 -1 1 -1 -1 1 1 2