409829: GYM103800 F Ginger's treasure
Description
Although Ginger is the king of the algorithm world, Ginger's performance in Tivat has been disappointing. Because Ginger devotes all his time to the algorithm, the abyss gets hung up every issue. Now that Ginger needs you to help him maximize the strength of his lineup, can you help Ginger go further in the abyss?
Ginger's treasure trove contains numerous weapons, which are placed in weapon slots for easy selection. Each weapon has its own attack power, and due to some restrictions, Ginger can only choose $$$k$$$ from the weapons. You need to help Ginger to maximize the product of these weapons.
InputThe first line contains a string $$$s$$$ $$$(1 \le |s| \le 2 \times 10 ^ 6)$$$ indicating all weapons, $$$|s|$$$ denotes the size of the string.
The string contains the attack power of all weapons $$$x_i$$$ $$$(-10 ^ 9 \le x_i \le 10 ^ 9)$$$, the weapons are separated by several "|". Each weapon is numbered starting at $$$1$$$ in the order in which it appears in the string.
The second line is the number of choices $$$k$$$. Guarantee that $$$k$$$ is less than or equal to the number of weapons, and $$$1 \le k$$$.
OutputPrint the $$$k$$$ selected weapon in ascending order separated by spaces, representing the number of the selected weapon. If there are multiple solutions, output the answer with the smallest lexicographical order.
ExamplesInput|12|31|-12|1| 1Output
2Input
|||1|||31||-12|12| 2Output
2 4Input
||13|13||13|13 3Output
1 2 3