BB84

Interview

Time limit1sMemory limit1024 MB

Summary

Given each qubit's basis and value from both sides, build the shared key from positions where the bases match, or print htg! if any matched position disagrees.

Level: Easy2 of 10
Topics: Implementation, String
Solved: No attempts yet

Problem

BB84 is a quantum key distribution protocol proposed in 1984 by Charles Bennett and Gilles Brassard.

Jeonghun wants to send a key to Ian using the BB84 protocol. The key is a string of length $N$ made of 0 and 1. Taegyun may be eavesdropping on the network, so the work must stop if eavesdropping is detected.

Jeonghun implements each digit of the key as a quantum state called a qubit. Each qubit is prepared in one of two bases, V or H. If a qubit is measured in the same basis used to prepare it, the key value it represents can be read exactly. If it is measured in the other basis, 0 or 1 comes out at random. For example, if the first digit of the key is 0 and Jeonghun prepares the first qubit in basis V, Ian always gets 0 when he measures it in basis V. In basis H, he gets 0 or 1 at random.

Jeonghun chooses a basis at random for each qubit he sends. Ian also chooses a basis at random and measures each qubit. Then they compare the positions where they chose the same basis. Jeonghun collects the key values at those positions, and Ian collects his measured values at those positions, and each of them builds a new key.

If the communication went normally, the two new keys match exactly. Taegyun can eavesdrop by measuring each qubit in a random basis, then preparing a new qubit in a random basis and sending it to Ian. In that case, the two new keys very likely do not match.

Given Jeonghun's basis choices and sent key, and Ian's basis choices and measured values, decide whether Taegyun certainly eavesdropped. If he did not, or if it cannot be known, find the new key that the two of them built.

Input

The first line contains $N$ .

The second line contains a string of length $N$ made of V and H, which is Jeonghun's basis choices.

The third line contains a string of length $N$ made of 0 and 1, which is the key Jeonghun sent.

The fourth line contains a string of length $N$ made of V and H, which is Ian's basis choices.

The fifth line contains a string of length $N$ made of 0 and 1, which is Ian's qubit measurement values.

Output

If Taegyun did not eavesdrop, or if it cannot be known, print the new key built by Jeonghun and Ian on the first line. If Taegyun certainly eavesdropped, print htg! on the first line.

Constraints

$1 \le N \le 200\,000$
The length of the new key built by Jeonghun and Ian is at least $1$ .

Examples2

Example 1

Input

8
HHVHVVHV
00100110
HVHHHVVV
01100100

Expected output

Example 2
Input
```
4
HHVH
0101
VHVV
1001
```
Expected output
```
htg!
```