Description

Before falling into a coma, Susan experienced $m$ days of memories. Starting from the first day, Susan has a base memory value $x$. The memory for the $i$-th day ($1 \le i \le m$) is $x + i - 1$. These $m$ days of memories are concatenated in order to form a sequence of length $m$.

In her dreams, this memory sequence is repeated $k$ times in order. Afterward, to awaken Susan, Luvia intervenes in the dream, inserting foreign memories not belonging to Susan. The final result is a sequence $a_1, a_2, \ldots, a_n$ of length $n$.

Given this sequence and $k$, Luvia wants to determine the maximum possible value of $m$ for every possible base memory $x$ where $1 \le x \le V$. If no valid memory sequence exists for a particular $x$, output $0$.

Input Format

• The first line contains three integers $n$, $k$, $V$, as described.
• The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, representing the final sequence.

Output Format

Output one line containing $V$ integers, where the $i$-th integer represents the maximum possible $m$ when $x = i$.

9 2 5
2 1 3 4 5 2 3 2 4

0 3 2 1 0

30 3 8
3 4 5 5 1 2 8 4 5 3 6 4 5 7 5 6 6 7 6 8 7 1 8 2 3 2 7 3 7 8

0 2 1 2 1 2 2 1

Hint

Sample Explanation #1

For $x = 2$ and $m = 3$, Susan's memory sequence is 2 3 4. Repeating $k = 2$ times gives 2 3 4 2 3 4. After inserting values between positions $1$ and $2$, $3$ and $4$, and $5$ and $6$, the sequence matches the original input.

Similarly, sequences like 2, 3, 4, 2 3, and 3 4 are all valid.

Data Range

This problem uses subtasks with bundled testing.

• Subtask 1 (13 pts): $n \le 100$.
• Subtask 2 (21 pts): $n \le 3000$.
• Subtask 3 (23 pts): $n \le 3 \times 10^4$.
• Subtask 4 (25 pts): $n \le 5 \times 10^5$.
• Subtask 5 (18 pts): No additional constraints.

For all data: $1 \le k \le n \le 2 \times 10^6$, $1 \le a_i \le V \le n$.

Translation by DeepSeek R1