고정 비트

WhatNext Software는 0부터 65535까지 범위의 16비트 부호 없는 정수를 무작위에 가깝게 생성하는 수열 생성기를 만든다. 하나의 수열은 정수 $A$, $B$, $C$, $S$로 정의되며, $1 \le A < 32768$, $0 \le B < 65536$, $2 \le C < 65536$, $0 \le S < C$를 만족한다. $S$는 수열의 첫 번째 원소(시드)이고, 이후의 각 원소는 바로 앞 원소로부터 생성된다. $X$가 수열의 한 원소이면, 다음 원소는

$$(A \cdot X + B) \bmod C$$

이다. 여기서 $\bmod$는 나머지 연산이다. 수열의 모든 원소는 65536보다 작은 16비트 부호 없는 정수이지만, 중간 계산값 $A \cdot X + B$는 더 커질 수 있으므로, 정확한 결과를 위해 16비트가 아닌 32비트 정수로 계산해야 한다.

어떤 매개변수 값은 다른 값보다 더 좋은 수열을 만든다. 가장 좋지 않은 수열은 하나 이상의 비트가 전혀 바뀌지 않는 수열이다. 수열 전체에서 값이 절대 바뀌지 않는 비트를 고정 비트(persistent bit)라고 한다. 이상적인 수열에는 고정 비트가 하나도 없다. 여러분의 임무는 주어진 수열을 조사하여 어떤 비트가 고정 비트인지 판별하는 것이다.

예를 들어 $A = 2$, $B = 5$, $C = 18$, $S = 3$은 특히 나쁜 선택이다. 이 값은 수열 3, $(2 \cdot 3 + 5) \bmod 18 = 11$, $(2 \cdot 11 + 5) \bmod 18 = 9$, $(2 \cdot 9 + 5) \bmod 18 = 5$, $(2 \cdot 5 + 5) \bmod 18 = 15$, $(2 \cdot 15 + 5) \bmod 18 = 17$을 만들고, 그다음 $(2 \cdot 17 + 5) \bmod 18 = 3$이 되어 처음으로 돌아간다. 따라서 수열은 같은 여섯 값을 계속 반복한다:

표의 마지막 줄은 각 비트 위치가 항상 0인지, 항상 1인지, 아니면 두 값을 모두 가지는지를 나타낸다. 16개 비트 중 12개가 고정 비트임에 유의하라. (좋은 무작위 수열에는 고정 비트가 없지만, 그 역은 반드시 성립하지 않는다. 예를 들어 $A = 1$, $B = 1$, $C = 64000$, $S = 0$으로 정의되는 수열에는 고정 비트가 없지만 무작위도 아니다. 단지 0부터 63999까지 세다가 반복할 뿐이다.) 수열이 반드시 시드로 되돌아올 필요는 없다. $A = 2$, $B = 0$, $C = 16$, $S = 2$이면 수열은 2, 4, 8, 0, 0, 0, ...으로 진행한다.

입력은 1개부터 16개까지의 데이터셋과, 그 뒤에 0만 적힌 한 줄로 이루어진다. 각 데이터셋은 한 줄에 정수 $A$, $B$, $C$, $S$의 값이 하나의 공백으로 구분되어 주어진다.

각 데이터셋마다 한 줄씩 출력한다. 각 줄은 16개의 문자로 이루어지며, 16개 비트 각각에 대해 '1', '0', '?' 중 하나를 최상위 비트부터 순서대로 출력한다. '1'은 해당 비트가 항상 1임을, '0'은 항상 0임을, '?'는 해당 비트가 수열에서 0과 1의 값을 모두 가짐을 뜻한다.