Pearls and Converter#10301
The Pearls are a peaceful and ancient race that almost went extinct due to humanity's fault, with their remnants drifting in space. Upon arriving at Alpha, the Pearls met Valerian and Lorelin and received a pearl converter.
The converter is a cute creature that produces pearls of different colors. To start the spaceship's engine, the Pearls need a set of pearls of different colors. The converter produces one pearl per second. For the engine to work efficiently, each set must satisfy the condition: for any pair of pearls in the set, the time difference between their appearance must not exceed seconds. Each pearl can only belong to one set.
The converter created pearls and got tired. Help the Pearls determine the maximum possible number of pearl sets they can form from the pearls they received.
The first line contains three integers , , — the number of pearls created by the converter; the maximum time interval between the appearance of any pair of pearls in a set; and the number of different pearl colors respectively (1 \le m \le n \le 10^5, 1 \le k \le 10^5).
The next line contains integers a_{i} — the color of the -th pearl that appeared (1 \le a_i \le k).
In the first line, output a single number — the maximum possible number of pearl sets that the Pearls can form from the available pearls.
In the next lines, output integers d_{ij} — the indices of the pearls that belong to the -th set (1 \le d_{ij} \le n).
If there are multiple correct answers, output any of them.
Example 1
Example 2
Example 3
This problem contains five subtasks. Additional constraints apply to the subtasks as listed below. To receive points for a subtask, you must pass all tests of that subtask, as well as all tests of all required subtasks. The required subtask numbers are also indicated in the table.
( points): n = m, n \le 1000;
( points): k = 2, n \le 1000;
( points): k \le 10, n \le 1000;
( points): n \le 1000;
( points): full constraints.