Under construction

Still being built. Things may change

Sheep Cloning

Time limit1sMemory limit128 MB

Summary
Design a minimum-length sequence of ENTER and CLONE commands so every cloning machine's sheep count reaches its exact target capacity via prime multiplications shared across machines under a per-command size limit.
Level

Hard8 of 10

Topics
Greedy, Number theory, Math, Simulation
Solved
No attempts yet

Problem

Sanggeun wants to increase the number of sheep using several cloning machines. Initially, each machine contains exactly one sheep.

Each cloning machine has a keyboard, and a prime number p can be entered into it. Suppose a machine currently contains K sheep and p is entered on that machine. When its clone button is pressed, the number of sheep in that machine becomes p*K.

Each machine has a maximum capacity and cannot contain more sheep than that capacity. Sanggeun wants every machine to reach its given maximum capacity exactly. Sheep cannot be removed during cloning.

Sanggeun places one assistant in front of each machine and announces two kinds of commands to all assistants.

  • ENTER p: tells every assistant to enter the prime number p into their own machine.
  • CLONE a1, a2, ..., ak: tells the assistants in front of machines a1, a2, ..., ak to press the clone button. The machine numbers in one command must all be distinct so that no assistant presses twice in the same command. Also, one CLONE command may contain at most M numbers.

Print a sequence of commands that maximizes the number of sheep in every machine while using the minimum possible number of commands. If several minimum-length sequences are possible, print any one of them.

Input

The first line contains the number of cloning machines N. (1 <= N <= 50)

The second line contains the maximum capacity of each machine. Each capacity is a positive integer less than 1,000,000,000.

The third line contains M, the maximum number of machine numbers that may be spoken in one CLONE command. (1 <= M <= N)

Output

Print one command per line. The number of printed commands must be minimum, and if multiple minimum command sequences satisfy the requirements, any one of them may be printed.

Examples2

  1. Example 1

    Input
    3
2 3 6
2
    Expected output
    ENTER 2
CLONE 1 3
ENTER 3
CLONE 2 3

  2. Example 2

    Input
    5
25 25 30 25 25
3
    Expected output
    ENTER 2
CLONE 3
ENTER 5
CLONE 1 2 3
CLONE 5 4 1
CLONE 2 4 5
ENTER 3
CLONE 3