Problem A
Hårgalåten
Languages
en
sv
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, \dots , 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), \dots , 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 \leq N,M \leq 3 \cdot 10^5$), the number of musicians and measures.
The second line contains $N$ integers $X_1, X_2, \dots , X_ N$ ($1 \leq X_ i \leq M$), the measure that each musician should play at second $1$.
The third line contains $M$ integers $f(1), f(2), \dots , f(M)$ ($1 \leq f(i) \leq 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, \dots , 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 \leq i \leq M$. |
$3$ |
$16$ |
$N,M \leq 300$ |
$4$ |
$22$ |
$N,M \leq 3000$ and $f(i) \neq f(j)$ if $i \neq j$. |
$5$ |
$9$ |
$N,M \leq 3000$ |
$6$ |
$26$ |
No additional constraints. |
Sample Input 1 | Sample Output 1 |
---|---|
1 4 4 2 3 1 1 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
4 5 5 4 3 2 2 3 4 5 1 |
17 16 15 14 |
Sample Input 3 | Sample Output 3 |
---|---|
3 4 1 4 1 2 3 2 4 |
-1 |
Sample Input 4 | Sample Output 4 |
---|---|
2 2 1 2 1 2 |
2 2 |