import java.io.*;
import java.util.*;
public class jobs {
// Maximum number of days (plus a safety margin) to accommodate job requests.
private static final int MAX_DAYS = (int) 1e6 + 5;
// totalDays: Total available days.
// numJobRequests: Total number of job requests.
// deadlineDuration: Extra days allowed after a job is requested.
private static int totalDays, numJobRequests, deadlineDuration;
// requestCountByDay[i] stores how many jobs are requested on day i.
private static int[] requestCountByDay = new int[MAX_DAYS];
/**
* Checks if a given daily machine capacity is sufficient to process all jobs
* within their deadlines.
*
* @param dailyMachineCapacity The number of jobs that can be processed per day.
* @return true if all jobs can be processed within totalDays and deadlines,
* false otherwise.
*/
private static boolean isScheduleFeasible(int dailyMachineCapacity) {
// Use a double-ended queue to track the deadlines of pending jobs.
Deque<Integer> deadlineQueue = new ArrayDeque<>();
// Simulate processing from day 1 to totalDays.
for (int currentDay = 1; currentDay <= totalDays; currentDay++) {
// If the job with the earliest deadline is already overdue (i.e., its deadline is before the current day),
// then the current capacity is not sufficient.
if (!deadlineQueue.isEmpty() && deadlineQueue.peekFirst() < currentDay) {
return false;
}
// For every job requested on the current day, add its deadline (currentDay + deadlineDuration)
// to the deadlineQueue.
for (int j = 0; j < requestCountByDay[currentDay]; j++) {
deadlineQueue.addLast(currentDay + deadlineDuration);
}
// Process (simulate) up to dailyMachineCapacity jobs on the current day.
// These represent the available machines processing the jobs.
for (int j = 0; j < dailyMachineCapacity; j++) {
// If there are no pending jobs, break out early.
if (deadlineQueue.isEmpty()) {
break;
}
// Remove the job with the earliest deadline from the queue (i.e., complete it).
deadlineQueue.pollFirst();
}
}
// After processing all days, if there are no pending jobs left,
// it means the given daily capacity successfully processed all jobs within their deadlines.
return deadlineQueue.isEmpty();
}
public static void main(String[] args) throws IOException {
// Set up input reading.
DataInputStream dataInput = new DataInputStream(System.in);
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(dataInput));
// The first input line contains totalDays, deadlineDuration, and numJobRequests.
StringTokenizer firstLine = new StringTokenizer(bufferedReader.readLine());
totalDays = Integer.parseInt(firstLine.nextToken());
deadlineDuration = Integer.parseInt(firstLine.nextToken());
numJobRequests = Integer.parseInt(firstLine.nextToken());
// The second input line contains the request day for each job.
// Initialize the requestCountByDay array to zero.
Arrays.fill(requestCountByDay, 0);
StringTokenizer secondLine = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < numJobRequests; i++) {
int requestDay = Integer.parseInt(secondLine.nextToken());
requestCountByDay[requestDay]++;
}
// Binary search to determine the minimum daily machine capacity (jobs processed per day)
// that allows all jobs to be completed within the allowed deadlines.
int left = 1, right = numJobRequests, optimalDailyCapacity = 0;
while (left <= right) {
int midCapacity = (left + right) >> 1;
if (isScheduleFeasible(midCapacity)) {
// If the schedule is feasible with the current capacity,
// try a smaller capacity (move the right bound).
right = midCapacity - 1;
optimalDailyCapacity = midCapacity;
} else {
// Otherwise, increase the capacity (move the left bound).
left = midCapacity + 1;
}
}
// Output the found minimum capacity required.
System.out.println(optimalDailyCapacity);
// The following prints an end-of-day marker (0) for each day,
// conforming to the problem's specified output format.
for (int day = 0; day < totalDays; day++) {
System.out.println(0);
}
}
}
