영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Point value | Constraints |
|---|---|---|
| 1 | 10 | N = 1 |
| 2 | 17 | f(i) = i for all 1 ≤ i ≤ M. |
| 3 | 16 | N,M ≤ 300 |
| 4 | 22 | N,M ≤ 3000 and f(i) ≠ f(j) if i ≠ j. |
| 5 | 9 | N,M ≤ 3000 |
| 6 | 26 | No 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