01204212/Zooma 1

Back to 01204212

This task is motivated by Zuma, a video game by PopCap Games.

In this version of the game, there is a sequence of n colored balls that moves toward an exit. You can shoot another m colored balls into the sequence. Balls do not disappear in this version.

Find out the final sequence of the balls.

The balls in the original sequence are numbered from 1 to n. The balls that you shoot are numbered from n+1 to n+m.

Game play example

Consider the case where n=5 and m=4. The original sequence has balls with these colors:

        1     2     3     4     5
        G     B     G     Y     Y

You have 3 balls numbered as this:

        6     7     8     9
        R     G     B     G

If you shoot your first ball to the location after ball 3, the sequence becomes

        1     2     3     *6*     4     5
        G     B     G     *R*     Y     Y

If you shoot your second ball to the location after ball 1, the sequence becomes

        1     *7*     2     3     6     4     5
        G     *G*     B     G     R     Y     Y

If you shoot your third ball to the location after ball 6, the sequence becomes

        1     7     2     3     6     *8*     4     5
        G     G     B     G     R     *B*     Y     Y

If you shoot your forth ball to the location after ball 5, the sequence becomes

        1     7     2     3     6     8     4     5     *9*
        G     G     B     G     R     B     Y     Y     *G*

and this is the final sequence.

Note: In this version, the colors of the balls are not relevant because balls do not disappear. In next versions of the task (see Zooma 2 and Zooma 3), there are rules about the disappearance of consecutive balls with the same color.

Input

• First line: n and m
• Next n lines:
• Next m lines:

Next challenge

Check out Zooma 2.