RLCIPHER - Robert Langdon & Cipher

no tags 

Robert and Sienna are running, with Florence police catching up fast. They make a swift left, and found a shallow alley, with a strange looking metal gate at the end. Their only way out: open the gate.

The gate has a horizontal bar, with N sections on it. Each section has an input portal, and a number written below that portal. They have to enter correct number at each portal to open the gate.

The hint given below the portals:

Take out three, take out four,
Below the voids, take no more.
Tire your brain, let the blood flow,
Plunge it deepest, let it go.

Robert figured: For each section, keep subtracting 3 or 4 from the number written in that section, until the number becomes negative. Try to get the smallest number possible using these operations. Then enter the number in that portal.

They entered the numbers and quickly got in. Can you guess what they answered?

Input

First line contains T, number of test cases. Then each test case contains two lines.

First line of each test case contains N, the number of sections on the horizontal bar.

Second line contains N space separated numbers, containing the numbers on the N sections.

Output

For each testcase, output one line of N space separated number, containing the numbers that must be entered in the portals to get the gate open.

Sample

Input
2
3
0 2 1
4
3 2 1 -1

Output
-4 -2 -3
-4 -2 -3 -1

Constraints

1 <= T<= 1000

1 <= N<= 100000

Sum of all N's in a test file will not exceed 105.

Each number in each section is between -109 to +109 inclusive.


hide comments
mayank09_19: 2020-09-25 09:10:52

while giving the output make sure to leave a gap between values.....costed me 2 wa

sagar_zhcet: 2017-06-23 15:03:16

easiest problem i had ever solved

vengatesh15: 2017-03-06 14:27:43

solution in O(1)

Bhumit: 2016-09-12 11:05:14

O(1)
AC in 2nd go :)

Piyush Kumar: 2016-07-01 20:43:04

It's strange, I didn't follow the output format and still got AC! What a day :) !

Dushyant Singh: 2015-07-29 17:39:11

After solving this problem, i am sherlocked. :-)

:.Mohib.:: 2015-07-25 21:19:04

Really enjoyed it's thinking part....!! Beautiful problem... :)

Ankit Mittal: 2014-01-28 20:07:23

@ admin here are we supposed to give answers after the whole test case or along with the number scanned?
RE Doesn't matter

Last edit: 2014-01-28 21:58:47
Rohan Phadke: 2014-01-26 00:02:25

@Piyush Kumar- please could you check solution ID 10941030? am getting correct answer for all inputs but i think the output(spaces and new line) is getting me WA! :( thanx in advance..
RE: Output format is clearly stated. If you think that is the problem, do it correctly and resubmit!

Last edit: 2014-01-26 12:01:19

Added by:Piyush Kumar
Date:2014-01-15
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IIT Bombay Coding GC