BB84

BB84 프로토콜은 1984년 찰스 베넷(Charles Bennett)과 질 브라사드(Gilles Brassard)가 제안한 양자 키 분배 방식이다.

정훈이는 BB84 프로토콜로 이안이에게 키를 보내려고 한다. 키는 0과 1로 이루어진 길이 $N$인 문자열이다. 태균이가 통신망을 도청할 위험이 있어서, 도청이 감지되면 작업을 중단해야 한다.

정훈이는 키의 각 자리를 양자 상태인 '큐비트'로 구현한다. 각 큐비트는 기저 V 또는 기저 H 중 하나로 생성된다. 큐비트를 만들 때 쓴 기저와 같은 기저로 측정하면 그 큐비트가 나타내는 키 값을 정확히 얻을 수 있다. 다른 기저로 측정하면 0 또는 1이 무작위로 나온다. 예를 들어 키의 첫 번째 자리가 0이고 정훈이가 첫 번째 큐비트를 기저 V로 만들었다면, 이안이가 기저 V로 측정할 때는 반드시 0이 나오지만, 기저 H로 측정하면 0이나 1이 무작위로 나온다.

정훈이는 키의 각 자리에 해당하는 큐비트를 만들 때 기저를 임의로 골라 전송한다. 이안이도 기저를 임의로 골라 큐비트를 측정한다. 그런 다음 두 사람은 같은 기저를 고른 자리를 확인하고, 정훈이는 그 자리의 키 값을, 이안이는 그 자리의 측정값을 모아 각각 '새로운 키'를 만든다.

정상적으로 통신이 이루어졌다면 두 사람의 '새로운 키'는 완전히 일치한다. 하지만 태균이는 각 큐비트를 임의의 기저로 측정한 뒤, 다시 임의의 기저로 큐비트를 만들어 이안이에게 보내는 방식으로 도청할 수 있다. 이 경우 두 사람의 '새로운 키'는 높은 확률로 일치하지 않는다.

정훈이의 기저 선택과 전송한 키, 이안이의 기저 선택과 측정값이 주어졌을 때, 태균이가 도청한 것이 확실한지 판단하고, 도청하지 않았거나 도청 여부를 알 수 없다면 두 사람이 만든 '새로운 키'를 구하여라.

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에 V와 H로 이루어진 길이 $N$의 문자열이 주어진다. 이는 정훈이의 기저 선택이다.

세 번째 줄에 0과 1로 이루어진 길이 $N$의 문자열이 주어진다. 이는 정훈이가 전송한 키다.

네 번째 줄에 V와 H로 이루어진 길이 $N$의 문자열이 주어진다. 이는 이안이의 기저 선택이다.

다섯 번째 줄에 0과 1로 이루어진 길이 $N$의 문자열이 주어진다. 이는 이안이의 큐비트 측정값이다.

태균이가 도청하지 않았거나 도청 여부를 알 수 없다면 첫 번째 줄에 정훈이와 이안이가 만든 '새로운 키'를 출력한다. 태균이가 도청한 것이 확실하다면 첫 번째 줄에 htg!를 출력한다.

• $1 \le N \le 200\,000$
• 정훈이와 이안이가 만든 '새로운 키'의 길이는 1 이상이다.