Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BFN4 - Piotruś Szyfrantem

Piotruś, z powodu swoich zamiłowań do rozwiązywania zagadek, został poproszony przez kolegów ze szkolnej tajnej organizacji "Klub Vernama" o rozszyfrowanie przekazu zawierającego najprawdopodobniej informacje o tajnej akcji konkurencyjnego stowarzyszenia "Miłośnicy Vigenera". Piotruś doskonale znał metodę szyfrowania przez nich stosowaną (czegóż nie znał Piotruś?). Wiadomości są zapisywane literami A, B, ..., Z (26 znaków), które są interpretowane odpowiednio jako liczby całkowite: 0,1, ..., 25. Sekretny klucz potrzebny do transmisji wiadomości jest znany zarówno osobie nadającej, jak i odbierającej i składa się z n liczb k1, k2,...,kn. Używając klucza, i-ta litera xi niezaszyfrowanej wiadomości x jest zaszyfrowana do postaci i-tej liczby zakodowanej wiadomości y, zgodnie z poniższym schematem:yi =(xi+k1+ ((i-1) mod n)) mod 26.

Piotruś próbuje odgadnąć zawartość wiadomości przesłanej przez członków "Miłośników Vigenera". Szczęśliwym zbiegiem okoliczności, udało się przechwycić wiadomość oryginalną i zaszyfrowaną (odpowiednio x oraz y). Niestety, w trakcie przechwytywania wiadomości, nastąpiła awaria sieci komputerowej i część z przesyłanych wiadomości x oraz y uległa nieodwracalnemu zniszczeniu. Ale czy rzeczywiście? I to jest zadanie dla Piotrusia! Musi zrekonstruować jak największą część wiadomości x, jak to tylko możliwe.

Wejście

W pierwszej linii na wejściu znajduje się pojedyncza liczba t <= 200 określająca liczbę testów. Następnie podane sa kolejne zestawy.

W każdym zestawie danych wejściowych, pierwsza linia zawiera jedną liczbę m , która ogranicza z góry długość klucza (1 <= n <= m <= 100000). Druga linia zawiera oryginalną wiadomość x, wreszcie trzecia linia zawiera zaszyfrowaną wiadomość y. Wiadomość złożone są ze znaków 'A'-'Z' (interpretowane jako liczby z przedziału 0-25) i gwiazdki '*' (oznaczającej pojedynczy znak nieczytelny z powodu zniszczenia przekazu). Całkowita długość pliku wejściowego nie przekracza 2MB.

Wyjście

Dla każdego testu należy wypisać jedną linię zawierającą oryginalną wiadomość x, gwiazdkami '*' w miejscach wyłącznie tych znaków, które nie mogą zostać rozszyfrowane.

Przykład

Wejście:
4
1
A*X*C
**CM*
4
*B***A
AAAAAA
6
*B***A
AAAAAA
4
*AA*******
AAAAAAAAAA

Wyjście:
A*XHC
*BA*BA
*B***A
*AA**A****

Uwaga: duże rozmiary plików wejścia/wyjścia, należy starannie przemyśleć wybór języka. Limit czasu działania programu jest dobrany restrykcyjnie.


Dodane przez:mima
Data dodania:2005-05-08
Limit czasu wykonania programu:17s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:autor: Konrad Piwakowski
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.