루미 알고리즘

#1584다이아Hårgalåten

PO 2024 훈련 캠프코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Hårgalåten is a Swedish folk song that tells the story of how the devil makes a group of youths dance until they die. Tom likes Hårgalåten and has therefore written an arrangement for his orchestra to play. To fit with the theme of the lyrics, Tom has composed the arrangement in such a way that anyone can get stuck forever if they start at the wrong place.

The orchestra consists of N musicians arranged in a circle, where musician 1 is to the left of musician 2, who is to the left of musician 3, and so on. Note that the musician to the right of musician N is musician 1. The arrangement consists of M measures numbered from 1 to M. Initially, there is a list of integers X_1, X_2, …, X_N, where X_i indicates the measure that musician i should start playing. Playing one measure takes one second, and everyone plays simultaneously. After musician i finishes playing measure X_i, they look at the measure played by the musician to their right (i.e., X_{i+1}). Then, musician i plays the measure f(X_{i+1}), where f(1), f(2), …, f(M) is a given function. This process repeats over and over again.

In other words, if musician i played measure x at second t, and the musician to the right played measure y at second t, musician i will play measure f(y) at second t+1.

The song ends when all musicians have played all measures at least once. Your task is to determine, for each musician, when they have played all different measures in the song at least once. It may happen that some musicians never play all measures, in which case the orchestra will have to play indefinitely.

Input

The first line of input contains the integers N and M (1 ≤ N,M ≤ 3 · 10^5), the number of musicians and measures.

The second line contains N integers X_1, X_2, …, X_N (1 ≤ X_i ≤ M), the measure that each musician should play at second 1.

The third line contains M integers f(1), f(2), …, f(M) (1 ≤ f(i) ≤ M), the function that determines which measures the musicians should play.

Output

If some musician will never play all measures, output -1. Otherwise, output N integers t_1, t_2, …, t_N, where t_i is the number of seconds it takes for musician i to have played each measure at least once.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

GroupPoint valueConstraints
110N = 1
217f(i) = i for all 1 ≤ i ≤ M.
316N,M ≤ 300
422N,M ≤ 3000 and f(i) ≠ f(j) if i ≠ j.
59N,M ≤ 3000
626No additional constraints.

예제

예제 1

입력
1 4
4
2 3 1 1
출력
4 

예제 2

입력
4 5
5 4 3 2
2 3 4 5 1
출력
17 16 15 14 

예제 3

입력
3 4
1 4 1
2 3 2 4
출력
-1

예제 4

입력
2 2
1 2
1 2
출력
2 2 

출처 표기

출처: Programmeringsolympiaden 2024년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.