You have been imprisoned by an evil, but stupid alien overlord. You told them it was a trap. It's not your fault. IT'S NOT YOUR FAULT.

You can pass notes containing information to other prisoners to coordinate your escape. You want to use an algorithm that can be easily deciphered by your fellow prisoners, in between torture sessions of forced “Buffy the Vampire Slayer” marathons. But you also want the notes to remain unreadable to evil alien overlord and his minions should the notes be discovered.

Therefore, you choose to implement a simple Caesar cypher given the following rule:

When the characters in the document are sorted by frequency, then by ASCII code (case sensitive), each character is replaced by the character in the same position in the reversely sorted set. Make a single character frequency lookup for ENTIRE file.

Given an arbitrary body of text as input, produce the appropriate output based on the cypher.

The first line of the input will contain a count of all the remaining lines, the remaining line are all part of the text to be encrypted.

Note: The ¶ symbol in the examples below represents a newline character. You may also ignore (strip/pop off) the first line of the input. It was added for languages that have difficulty (or lack of ability) detecting EOF.

Also note that the newlines in the input text are treated as any other character and are encoded with the rest of the text. Note in particular that the last line of output may not end with a newline character. THIS IS WHITESPACE SENSITIVE.

The sample input contains no whitespace characters at the end of a line unless marked with ¶ symbol at which point there is a newline character.

Examples

Input 1:
1¶
Aliens are dumb¶

Output 1:
 mn¶
ibAud¶
Aralse

Input 2:
1¶
Mississippi

Output 2:
spMMpMMpiip

Input 3:
2¶
Missi¶
ssippi

Output 3:
iM¶
¶
Ms¶
¶
MppM