N knights gathered at the King Arthur’s round table. Each of them has several goblets near him. It is possible that knights have different number of goblets. The goblets are brought (and also carried away) by a servant who can carry only two goblets at a time (one for each hand). When the servant comes he can either bring two goblets, or carry them away. Note that he can serve exactly two knights that sit at a fixed distance K from each other.
For example, if K=1 then the knights who sit side by side are served.
By the end of the feast each of the knights should have an equal predefined number of goblets near him. The number of the times the servant has to come must be minimized.
Your task is to write a program, which plans the servant’s work during the feast.
2 <= N <= 1000
1 <= K <= N-1
Initial and final number of goblets near each knight is not greater than 1000 and it is always non-negative.
The total number of servant’s visits is not greater than 30000.
The first number contains three numbers separated with white-space.
N – the number of knights,
K – “arm-span” of the servant,
F – the final number of goblets each of the knights must have by the end of the feast.
The following N numbers separated with spaces or EOL characters describe the initial number of goblets near each knight. It is assumed that the knights are numbered in a cyclic manner, i.e. the first knight sits after the N-th one.
If it is impossible to reach the goal, write “–1” (without quotes) to the output. If the solution exists then the first line must contain a single integer M – the number of the servant’s visits. The following M lines must carry triples: two numbers (the numbers of knights being served) and “+” (plus) character if the goblets are brought or “–” (minus) if they are carried away. The data on each of these lines must be separated with a white-space character.
3 1 4
1 2 3
1 2 +
1 2 +
3 1 +
Problem Author: © Sergey G. Volchenkov, 2003(firstname.lastname@example.org); Vladimir N. Pinaev, 2003(email@example.com; http://www.pic200x.chat.ru); Michael Y. Kopachev, 2003 (firstname.lastname@example.org).
Problem Source: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003