الى العباقرة فقط

هنا توجد كل المواضيع المتعلقة بالخوارزميات الرياضية و الحاسوبية

المشرف: Mu_Nizar

الى العباقرة فقط

مشاركة غير مقروءةبواسطة ITbreaker » الأربعاء ديسمبر 05, 2012 10:53 am

بتحداكون بهي الخوارزمية ورجونا حبايب ٪#{_}#٪


The Bytelandian Cryptographer has been requested by the BBFO to put forward an ecryption scheme which would allow the BBFO to communicate with its foreign associates. After some intensive studies, he has decided upon the Vigenére cipher. Messages written using 26 upper case characters of the Latin alphabet: A, B, ..., Z which are interpreted as integers 0,1, ..., 25 respectively. The secret cypher for transmitting a message is known to both sides and consists of n integers k1, k2,...,kn. Using this cypher, the i-th number xi of the input message x is encrypted to the form of the i-th number of the output message y, as follows:
yi =(xi+k1+ ((i-1) mod n)) mod 26.

You are trying to find out the content of a message transmitted by the BBFO. By a lucky stroke of fortune, your spys managed to intercept the message in both its plaintext and encrypted form (x and y respectively). Unfortunately, during their dramatic escape the files they were carrying where pierced by bullets and fragments of messages x and y were inadvertantly lost. Or were they? It is your task to reconstruct as much of message x as you possibly can.

Input

The first line of input contains a single integer t<=200 denoting the number of test cases. t test case descriptions follow.

For each test case, the first line contains one integer m which is some upper bound on the length of the cypher (1<=n<=m<=100000). The second line of input contains the original message x, while the third line contains the encrypted message y. The messages are expressed using characters 'A'-'Z' (interpreted as integers 0-25) and '*' (denoting a single character illegible due to damage). The total length of the input file is not more than 2MB.

Output

For each test case output a single line containing the original message x, with asterisks '*' in place of only those characters whose value cannot be determined.

Example

Input:
4
1
A*X*C
**CM*
4
*B***A
AAAAAA
6
*B***A
AAAAAA
4
*AA*******
AAAAAAAAAA

Output:
A*XHC
*BA*BA
*B***A
*AA**A****
بعمق الألم الصارخ
قفزة نحو الحياة
وإن كان الموت هو المصير
أليس في الموت حياة؟
صورة العضو الشخصية
ITbreaker
عضو جديد
عضو جديد
 
مشاركات: 52
اشترك في: الأربعاء سبتمبر 29, 2010 5:03 pm
مكان: banded with shellc99.c100.sniper...serverHotevil..
الجتس: ذكر
الشهادة الثانوية: سورية
الجامعة: جامعة دمشق
الكلية: الهندسة المعلوماتية
المرحلة الدراسية: السنة الثانية

العودة إلى منتدى الخوارزميات العام

الموجودون الآن

المستخدمون المتصفحون لهذا المنتدى: لا يوجد أعضاء مسجلين متصلين و 1 زائر

cron