시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 6 | 6 | 6 | 100.000% |
It’s time to put your hacking skills to the test! You’ve been called upon to help crack enemy codes in the current war on... something or another. Anyway, the point is that you have discovered the encryption technique used by the enemy; it is quite simple, and proceeds as follows. Note that all strings contain only uppercase letters of the alphabet.
As an example, consider the encryption of the string “STANFORD” using the key “ACM”:
STA NFORD + ACM SVMFA ---------- SVM FAAWD
Knowing this, you are well on your way to being able to read the enemy’s communications. Luckily, you also have several pairs of plaintexts and ciphertexts which your team recovered, all of which are known to be encrypted with the same key. Help find the key that the enemy is using.
The input consists of multiple test cases. Each test case begins with a line containing a single integer N, 1 ≤ N ≤ 100, the number of plaintext and ciphertext pairs you will receive. The next N lines each contain two strings P and C, the plaintext and ciphertext, respectively. P and C will contain only uppercase letters (A-Z) and have the same length (at most 100 characters). The input terminates with a line with N = 0.
For each test case, print a single line that contains the shortest possible key or “Impossible” (quotes added for clarity) if no possible key could have produced all of the encryptions.
1 A B 3 STANFORD SVMFAAWD AVOWIENR AXAWFEJW VAMRI VCYMK 3 ABCDEFGHIJKLMNOPQRSTUVWXYZ AAAAAAAAAAAAAAAAAAAAAAAAAA Y Y Z Z 2 A B B A 0
B ACM AZYXWVUTSRQPONMLKJIHGFEDCB Impossible