서스펜스!

Jan과 Tereza는 이웃한 두 건물에 살고 있으며, 두 사람의 아파트는 서로 마주 보고 있다. 두 사람은 학교 과학 프로젝트로 밧줄, 끈, 판지를 사용해 두 건물을 잇는 소형 현수교를 만들려고 한다. 길이가 같은 밧줄 두 개가 주 케이블을 이루며, 각각 두 사람의 창문 아래쪽에 고정된다. 다리의 판지 바닥은 주 케이블에 묶인 여러 끈으로 지지된다. 수평인 다리 바닥은 밧줄의 가장 낮은 점보다 정확히 1미터 아래에 있다. 미관상 다리 바닥은 두 학생의 창문 중 더 낮은 창문의 아래쪽 가장자리보다 적어도 2미터 아래에 있어야 한다. 물리 법칙에 따라 각 현수 밧줄은 포물선을 이룬다.

Jan과 Tereza는 이 모형 다리 위를 걸을 계획은 없지만, 심각한 문제가 하나 있다. 두 아파트 주민 중에는 고양이를 기르는 사람도 있고 새를 기르는 사람도 있다. 두 사람은 자신들의 다리가 고양이가 새에게 닿을 수 있는 경로가 되지 않기를 바란다. Jan과 Tereza는 고양이가 0.5미터 높이로 뛰어오르지 못하며, 3미터 아래로 뛰어내리지도 않는다는 것을 관찰했다. 따라서 다리 바닥이 고양이 창문의 아래쪽보다 적어도 0.5미터 위에 있거나, 고양이 창문의 아래쪽보다 적어도 3미터 아래에 있으면 고양이는 다리 위로 뛰어오르지 않는다. 마찬가지로, 다리 위로 성공적으로 뛰어오른 고양이는 다리 바닥이 새 창문의 아래쪽보다 적어도 0.5미터 아래에 있거나, 새 창문의 아래쪽보다 적어도 3미터 위에 있으면 새 창문에 닿을 수 없다. 고양이는 새에게 닿는 것만 신경 쓰며, 집으로 돌아가는 것은 걱정하지 않는다.

아래 그림은 Jan의 아파트(J)와 Tereza의 아파트(T)를 보여 준다. 밧줄은 두 사람의 창문 아래쪽을 잇고, 판지 바닥은 밧줄의 가장 낮은 점보다 1미터 아래에 있다. 2층에 있는 고양이는 다리를 이용해 2층에 있는 새에게 닿을 수 있다.

두 건물의 어떤 새도 위험에 빠뜨리지 않는 다리를 만들기 위해 각 케이블에 필요한 밧줄의 길이를 구하는 프로그램을 작성해야 한다.

프로그램의 입력은 두 건물 사이의 거리(미터), Jan과 Tereza의 층 번호(각 건물의 가장 낮은 층, 즉 1층을 1로 센다), Jan의 층까지 모든 층에 사는 애완동물의 종류, Tereza의 층까지 모든 층에 사는 애완동물의 종류이다. 프로그램은 두 건물 사이에 다리를 매달 수 있는 가장 긴 케이블의 길이를 구해야 한다. 이 다리는 어떤 고양이도 다리를 통해 새에게 닿게 해서는 안 된다. 다리 바닥은 지면에서 적어도 1미터 위에 있어야 하고, 현수 케이블의 가장 낮은 점보다 정확히 1미터 아래에 있어야 한다. 또한 Jan과 Tereza의 두 창문 중 더 낮은 창문보다 적어도 2미터 아래에 있어야 한다. 건물의 모든 방은 정확히 3미터 높이이고, 모든 창문은 정확히 1.5미터 높이이며, 각 창문의 아래쪽은 각 방의 바닥보다 정확히 1미터 위에 있다.

입력은 여러 테스트 케이스로 이루어지며, 각 케이스는 세 줄이다. 첫 줄에는 Jan의 층과 Tereza의 층을 나타내는 두 양의 정수 j와 t(2 ≤ j, t ≤ 25), 그리고 두 건물 사이의 거리를 미터 단위로 나타내는 실수 d(1 ≤ d ≤ 25)가 주어진다. 둘째 줄에는 공백으로 구분된 j개의 대문자 ℓ1, ℓ2, ..., ℓj가 주어진다. Jan의 건물 k층에 새가 살면 ℓk는 B, 고양이가 살면 C, 둘 다 없으면 N이다. 셋째 줄에도 같은 정보를 나타내는 t개의 대문자가 Tereza의 건물 층에 대해 주어진다. 마지막 케이스 뒤에는 세 개의 0이 있는 줄이 이어진다.

각 케이스에 대해 케이스 번호(1, 2, ...)와 가장 큰 값 c를 출력한다. c는 길이가 각각 c인 두 케이블로 Jan과 Tereza의 창문 아래쪽 가장자리에서 다리를 매달 수 있고, 다리 바닥이 케이블의 가장 낮은 점보다 1미터 아래에 있으며, 지면에서 적어도 1미터 위에 있고, Jan과 Tereza의 두 창문 중 더 낮은 창문보다 적어도 2미터 아래에 있으며, 어떤 고양이도 새에게 닿지 못하게 하는 값이다. 길이는 소수점 아래 셋째 자리까지 반올림한다. 그러한 다리를 만들 수 없으면 impossible을 출력한다. 연속한 케이스 사이에는 빈 줄을 하나 출력한다.