비제네르 암호 분석

비제네르(Vigenère) 암호는 반복되는 키로 메시지를 암호화한다. 평문과 키는 모두 대문자 알파벳 ${A, B, \ldots, Z}$ 로 이루어진 문자열이며, 각 글자를 $A = 0, B = 1, \ldots, Z = 25$ 로 대응시킨다. 평문 $P$ 와 키 $Q$ 가 주어지면, 암호문 $C$ 는 $P$ 와 길이가 같고 다음과 같이 정의된다.

$$C_i = (P_i + Q_{i \bmod |Q|}) \bmod 26$$

결과를 다시 글자로 읽으며, 키 $Q$ 는 메시지 전체를 덮을 때까지 반복된다. 복호화는 그 역으로 $P_i = (C_i - Q_{i \bmod |Q|}) \bmod 26$ 이다.

비밀 조직인 아마추어 암호 해독 운동(Amateur Codebreakers Movement, ACM)은 은행 강도 일당이 다시 범행을 저지르려 한다고 강하게 의심하고 있다. 하지만 목표 은행의 이름도, 정확한 날짜와 시각도 알지 못한다. ACM 은 강도들과 도주 차량 운전자가 주고받는 메시지를 도청할 수 있지만, 모든 메시지는 비제네르 암호로 암호화되어 있다.

당신의 임무는 이 암호를 해독하는 것이다. 원래 평문에 나타날 가능성이 매우 높은 두 단어, 이른바 크립(crib) 이 주어진다. (이렇게 추측한 단어들은 예컨대 유명한 에니그마(Enigma) 기계를 해독할 때 결정적인 역할을 했다.)

입력은 여러 개의 테스트 인스턴스로 이루어진다. 각 인스턴스는 네 줄로 구성된다.

• 첫째 줄에는 고려할 최대 키 길이인 정수 $K$ 가 주어지며 $1 \le K \le 100$ 이다.
• 둘째 줄과 셋째 줄에는 크립 $W_1$ 과 $W_2$ 가 주어지며 $1 \le K \le |W_i| \le 100$ 이다.
• 넷째 줄에는 암호문 $C$ 가 주어지며 $1 \le |C| \le 100000$ 이다.

두 크립 $W_1, W_2$ 와 암호문 $C$ 는 모두 대문자 알파벳 ${A, B, C, \ldots, Z}$ 로만 이루어진다. 입력은 $0$ 하나만 있는 줄로 끝난다.

각 인스턴스에 대해, 다음 조건을 모두 만족하는 서로 다른 평문의 개수를 구하라.

• 길이가 $1 \le |Q| \le K$ 인 어떤 비제네르 키 $Q$ 로 평문을 암호화하면 주어진 암호문 $C$ 와 정확히 같아진다.
• 평문 안에서 두 크립 $W_1$ 과 $W_2$ 가 서로 겹치지 않는 위치에 나타난다. 즉, $W_1$ 의 어떤 출현과 $W_2$ 의 어떤 출현이 차지하는 글자 구간이 서로 겹치지 않는다.

각 인스턴스마다 한 줄씩 출력한다.

• 그러한 평문이 정확히 하나뿐이면, 그 평문을 추가 공백 없이 출력한다.
• 그러한 평문이 둘 이상이면 ambiguous 를 출력한다.
• 그러한 평문이 하나도 없으면 impossible 을 출력한다.