메시지

Aisha와 Basma는 서로 편지를 주고받는 두 친구이다. Aisha에게는 길이가 $S$인 비트 열(0 또는 1) 메시지 $M$이 있고, 이를 Basma에게 보내려 한다. Aisha는 패킷을 보내는 방식으로 Basma와 통신한다. 패킷은 인덱스 0부터 30까지 붙은 31비트 열이다. Aisha는 여러 개의 패킷을 보내 메시지 $M$을 Basma에게 전한다.

Cleopatra가 Aisha와 Basma의 통신을 장악하였고, 패킷을 오염(taint)시킬 수 있다. Cleopatra는 각 패킷에서 정확히 15개 인덱스의 비트를 수정할 수 있다. 길이 31인 배열 $C$가 있으며, 각 원소는 0 또는 1이고 의미는 다음과 같다.

• $C[i] = 1$: 인덱스 $i$의 비트를 Cleopatra가 바꿀 수 있다. 이 인덱스들이 Cleopatra의 통제 대상이다.
• $C[i] = 0$: 인덱스 $i$의 비트를 Cleopatra가 바꿀 수 없다.

$C$에는 1이 정확히 15개, 0이 정확히 16개 있다. 통제 대상 인덱스 집합은 모든 패킷에서 같다. Aisha는 통제 대상인 15개 인덱스를 정확히 안다. Basma는 15개 인덱스가 통제 대상이라는 사실만 알고, 어느 인덱스인지는 모른다.

Aisha가 보내는 패킷(원본 패킷)을 $A$, Basma가 받는 패킷(오염된 패킷)을 $B$라 하자. $0 \le i < 31$인 각 $i$에 대해 다음이 성립한다.

• $C[i] = 0$이면 $B[i] = A[i]$이다.
• $C[i] = 1$이면 $B[i]$의 값은 Cleopatra가 정한다.

Aisha는 패킷을 보낼 때마다 오염된 패킷이 무엇인지 바로 알게 된다. Aisha가 모든 패킷을 보내고 나면, Basma는 보낸 순서대로 오염된 패킷을 모두 받아 원본 메시지 $M$을 복원해야 한다.

두 개의 절차를 구현해야 한다. 첫 번째 절차는 Aisha의 동작으로, $M$과 $C$를 받아 메시지를 실어 나를 패킷들을 보낸다. 두 번째 절차는 Basma의 동작으로, 오염된 패킷들을 받아 $M$을 복원한다.

• $1 \le S \le 1024$
• $C$는 정확히 31개의 원소를 가지며, 그중 16개는 0, 15개는 1이다.