IGOR - Helping Igor

Dr Samuel has been working in one of his grim (and useless) experiments in order to take control of the humanity.

Recently, he has been working in a hypnotic bomb, and he plans to launch it in the center of the city. Once it falls, all the inhabitants will be under his control, due to the properties of its principal element, the Samuelanium.

Amusingly, the Doctor himself created this element, and he does not know its behavior! He has commanded Igor, his faithful sidekick (and slave) to describe it.

Samuelanium’s behavior is pretty strange. According to Igor’s Notes:

-Its atoms are only composed by electrons and protons and it has a chain-like shape.

-On its sides there are two strange portals. They can suck the proton-electron chain in only one direction. Once a particle enters in a portal, it comes back from the other portal with its charge changed.

-If the first particle in the chain is a proton, the charge of the last particle changes.

For example, suppose we have the chain "+-+".

As you can see, the first particle is a proton, so the last particle must change its charge, becoming "+--". Then, the chain is sucked by the left portal. The proton comes out from the right portal, having changed it charge, becoming "---"(as an electron). This occurs in one second.

So, if the chain is represented as "+-+" at time 0, it will be represented as "---" at time 1.

Doctor Samuel wants to know the state of this chain, having passed some seconds from its initial state.

Unfortunately, Igor is exhausted. Can you help Igor and (ironically) help Doctor Samuel to control the humanity and conquer the whole world?

Input

Your program will be tested with t experiments.

Every experiment begins with two integers, n and k. n represents the length of the Samuelanium chain, and k represents the number of queries that Samuel demands.

Next, there will be a string of length n, composed only of '+' and '-'. '+' represents a proton, and '-' an electron. This chain represents its initial state (time 0).

You must assume that the portal that sucks the chain is on the left side.

Then, there will be k lines, with an integer ki, representing the time query you have been asked for.

Output

For each test case you must print one line containing "Experiment #i:", being i the ith case you are analyzing.

Then, k strings, representing the chain in a given moment.

Remember, protons are represented with '+' and electrons with '-', and there are no neutrons.

Example

Input:
1
3 4
+-+
0
1
2
4

Output: Experiment #1: +-+ --- --+ +++

Constraints

1<=t<=15

1<=n<=14

10<=k<=1000

0<=ki<=10^9


Added by:Samuel Nacache
Date:2013-07-29
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2013-07-31 05:03:19 RAJDEEP GUPTA
@Miguel Oliveira : Thanks for the explanation. :)
2013-07-30 15:19:07 Vaibhav Yenamandra
There is an easy way to do this and a hard way, think carefully what this resembles :)
2013-07-30 15:00:33 Miguel Oliveira
@Rajdeep, the chain is sucked to the left "---" => "--" and the first atom ('-') moves to the right while changing its charge: "--" and "+" = "--+"
2013-07-30 11:47:48 RAJDEEP GUPTA
Can someone please explain the 2nd case? How is --- changed to --+ after 2 seconds?

Last edit: 2013-07-30 12:02:33
2013-07-30 07:07:28 Karan Chauhan
Great problem !
Learnt a lot of optimization :D
2013-07-30 05:27:38 Rocker3011
nice question, it takes some implementation, but it has a nice logic behind it :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.