IGOR - Helping Igor

no tags 

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


hide comments
nadstratosfer: 2018-11-27 01:30:22

AC with a Py2 solution in fraction of time limit so if yours TLE, the approach is wrong. My program doesn't use any defensive input technique either so the testfiles are clean. Sweet little puzzle! Also try ICODER if you enjoyed this.

procrastinator: 2015-08-25 06:55:50

forgot to print "Experiment %d:". Code failed at 8th judge :P

eightnoteight: 2014-12-08 13:36:37

is there is anything wrong with the testcases? my python solution is getting runtime error with the 8th testcase, please help me #13100778

mohsin mohammad: 2014-08-07 12:57:35

yeah do it in first attempt..........
think on test cases very keenly

Jashan Goyal: 2013-12-28 23:35:28

Has it got any solution in python??mine TLE after good optimization also..

AB: 2013-08-25 10:53:19

@samuel pls check submission id #9909631.....i think my code works fine
still getting WA

Last edit: 2013-08-25 11:09:35
satya hemanth: 2013-08-11 14:27:16

@Samuel: getting WA again and again.please check Submission Id#9820206
RE: Check your output format carefully
@Samuel: Thanx :-)

Last edit: 2013-08-13 02:50:08
shadoww: 2013-08-02 06:21:57

@Samuel , what to do when n = 1, and s = "+" ???
Found it :)

Last edit: 2013-08-02 09:06:25
Samuel Nacache: 2013-07-31 20:02:54

@Akash you have made a wrong assumption in your approach. Try with the chain "----" and you will figure it out ;)

Akash: 2013-07-31 19:49:44

Edit: Yep, it is incorrect. Think about this:
If the chain cycle begun at 0 and ended at 21, it must repeat at 31? You must fix that issue :)
--Thanx @Samuel..found my mistake..was just taking wrong assumption for chain cycle..:)

Last edit: 2013-08-01 18:14:53

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