Chef and Codes
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Once upon a time chef decided to learn encodings. And, obviously, he started with the easiest one (well, actually the easiest after Caesar cypher) – substitution cypher.
But very soon Chef got bored with encoding/decoding, so he started thinking how to hack this cypher.
He already knows some algorithm, which is not always correct,
but it’s sufficient for now. Here is its description.
Imagine we know frequency sequence of English letters (this means, that letters are sorted by their frequency of appearing in English texts, in ascending order).
And let’s find frequency sequence of cyphered letters (if some of them appear equal number of times, then first in frequency sequence will be lower letter between them).
Now, using this two frequency sequences we can recover plain text. Just substitute cyphered letter with origin one, if they are at same positions in sequences.
Now, Chef has frequency sequence of English letters and cypher text. And he asks you to recover plain text. Please, help him.
In first line number T is given - number of test cases. Then T test cases follow. Each test case consists of two lines - frequency sequence and encrypted text.
For each test case you should output decrypted with the given frequency sequence text. Please note, that the case of letters should be preserved.
- 1 ≤ T ≤ 1000;
- Length of frequency sequence is always 26;
- 1 ≤ length of the text ≤ 150000;
- 1 ≤ sum lengths of all texts ≤ 150000.
- Frequency sequence consists of all lowercase English letters. Text consists of any characters.
Input: 3 qwrtyuipasdfgjkzxcvbnmheol dummy! bfgjklmopqrstuwxzhvnicdyea abcd b efgd hbi! qwrtyuipasdfgjkzxcvbnmheol Dummy! Output: hello! have a nice day! Hello!
|Tags||cakewalk, dec13, programming, witalij_hq|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.