HHEMANT - Help Hemant Verma

Steganography is a method of cryptography where a message or entire document can be hidden inside of another file or image which shows no evidence that there is data hidden in it. Typically, the message or document to be sent is first encrypted and compressed, and then combined with an existing file in the bits that are less significant.

Hemant Verma is a secret agent who wants to send some classified information to his head office , the amount of data is very large , he needs your help to encode the message into image . You will be given an "image" and you will encode a given message into it and return the new image. The returned image should be in the same format as the original image.

The image will be in the format of a string of various lines where each three digits represent a number from 0 to 255, inclusive (leading zeros will be added as necessary), which is a pixel value in the image. You will also be given a  message which contains the message you would like to encode into the image.

You will first encode the message into numbers representing the characters in the message - spaces will be 0, 'A'-'Z' will be 1-26, 'a'-'z' will be 27-52, '0'-'9' will be 53-62, and 63 will be used for any space after the message. All these numbers can be represented in binary with 6 digits. You will put each pair of bits (representing a number between 0 and 3) into the lowest two bits of the values in the image. For each character, you will put in the lowest two bits, then the middle two, then the highest two, and then continue to the next character. You will put them in the lowest two bits of the first pixel on the first row, then the second pixel on the first row, and so on until you get to the end of the first row, then the first pixel on the second row, and so on. Once you are out of characters, continue substituting the lowest two bits of each pixel value as if the current character were represented by number 63.

Input

First line contain T representing number of test case , for each test case first line contain message  then follow N the number of lines for image then following N line contain image.


0 < Length(message) < 1000
0 < T, N < 10000

Output

For each test case output the image in same format as input.

Example

Input:
2
hi
1
255123212001201222
hi
2
255123212
001201222

Output:
254120214003200222
254120214
003200222

Added by:Hemant Verma
Date:2009-07-28
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Modified Topcoder Problem

hide comments
2010-06-24 00:07:18 刘启鹏
bad problem, expression is not clear!
2010-04-26 18:17:17 Aditya A R
are the no of chars in each line,a multiple of three?
2009-07-29 13:22:05 Ajay Nair
Wow !! That definitely helped , just a matter of ingnoring the inputs other than a-z, A-Z, 0-9.
Thanks
2009-07-29 09:51:17 Robert Gerbicz
Yes, and in the message description there are also invalid characters, other than space, a-z, A-Z, 0-9.
2009-07-29 07:23:57 amaroq
@Ajay Nair:
1 - Yes
2 - No

The input contains other characters besides letters, digits, space and newline. You have to ignore them to get accepted. Maybe it's just return characters (DOS line breaks) or also other rubbish; I don't know.
2009-07-29 02:34:39 Ajay Nair
2 queries :
1-please confirm if length multiple of 3
2-will the message exceed the image required to encode ?
2009-07-28 17:34:23 Jorge Bernadas
No FameOfLight, there are lines whose length is not a multiple of three. I managed to pass the problem by just ignoring them when making the substitution.

Last edit: 2009-07-28 17:34:46
2009-07-28 14:05:49 Hemant Verma
the characters in the message - spaces will be 0, 'A'-'Z' will be 1-26, 'a'-'z' will be 27-52, '0'-'9' will be 53-62, and 63 will be used for any space after the message.

Robert Gerbiz , You haven't taken the fact of space equal to 0 into account . Also the Length are prefectly divisible by 3
Write mail to me if problem still presist

Last edit: 2009-07-28 14:15:16
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.