Let us observe two consecutive chameleons moving to the right and are located at coordinates ~x_1~ and ~x_2~, and a chameleon at the coordinate ~x_L~ moving to the left. Between the collision with two chameleons moving to the right, he will pass ~\dfrac{x_2+x_L}{2}-\dfrac{x_1+x_L}{2} = \dfrac{x_2-x_1}{2}~ meters. We can see that the distance traveled doesn't depend on the coordinate of the chameleon moving to the left.

The task is further solved using dynamic programming. Let ~f(i, c)~ be an array of length ~K~ that denotes the distance traveled in each color a chameleon colored in ~c~ moving to the left will take in consecutive collisions if it had just collided with a chameleon ~i~ moving to the right. Using the aforementioned statement, we can easily calculate the value of function ~f~.

Finally, for each chameleon moving to the left, we calculate:

1. distance traveled until the first collision;
2. distance traveled between consecutive collisions (calculated using ~f~);
3. distance traveled from the last collision to the end

The time complexity of this algorithm is ~\mathcal O(NK^2)~.