eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Постоянные биты

Постоянные биты

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Компания WhatNext создает генераторы последовательностей, которые, как они надеются, будут выдавать произвольные последовательности 16-битовых беззнаковых целых чисел в интервале 0–65535. Последовательность задается целыми числами A, B, C и S, где 1 A < 32768, 0B < 65536, 2C < 65536 и 0S < C. S - первый элемент последовательности, а каждый следующий элемент получается из предыдущего. Если X - некоторый элемент последовательности, то следующим будет элемент

(A*X + B) % C

где '%' обозначает остаток от деления. Хотя каждый элемент последовательности является 16-битным беззнаковым целым числом, меньшим 65536, промежуточный результат A*X + B может быть большим. Поэтому вычисления следует производить в 32-битовых целых числах, а не в 16-битовых для получения правильного результата.

Некоторые значения параметров генерируют лучшие последовательности, чем другие. Наиболее плохими последовательностями в компании WhatNext являются те, в которых имеется один или несколько никогда не изменяющихся бит. Бит, который никогда не изменяется во всей последовательности, называется постоянным. В идеале последовательность не должна иметь постоянный бит. Вам следует протестировать последовательность и определить, какие биты в ней являются постоянными.

Например, очень плохим будет выбор A = 2, B = 5, C = 18 и S = 3. Он генерирует последовательность 3, (2*3+5)%18 = 11, (2*11+5)%18 = 9, (2*9+5)%18 = 5, (2*5+5)%18 = 15, (2*15+5)%18 = 17, затем (2*17+5)%18 = 3 снова и так далее. Последовательность повторяется через каждые шесть членов:

Последняя строка указывает позиции, в которых биты всегда остаются 0, всегда 1, или принимают оба значения. Заметим, что 12 из 16 бит являются постоянными. Хорошие случайные последовательности не имеют постоянных бит, но обратное утверждение не верно. Например, последовательность полученная значениями A = 1, B = 1, C = 64000 и S = 0 не имеет постоянных бит, однако не является случайной: она лишь считает от 0 до 63999 и повторяется. Последовательность не обязательно должна повторяться с первого элемента последовательности: значения A = 2, B = 0, C = 16 и S = 2 генерируют последовательность 2, 4, 8, 0, 0, 0, ... .

Входные данные

Входные данные содержат от одного до шестнадцати тестов, завершающихся строкой из одного 0. Каждый тест состоит из единственной строки, содержащей целые числа A, B, C и S в десятичной записи, разделенные пробелом.

Выходные данные

Для каждого теста вывести одну строку, содержащую 16 символов '1', '0' или '?' для каждого из 16 бит в порядке с наиболее значимого. '1' означает, что соответствующий бит всегда равен 1, '0' означает что соответствующий бит всегда равен 0, а '?' означает то что бит в последовательности может принимать значения как 0, так и 1.

Пример

Входные данные #1
2 5 18 3
1 1 64000 0
2 0 16 2
256 85 32768 21845
1 4097 32776 248
0
Выходные данные #1
00000000000????1
????????????????
000000000000???0
0101010101010101
0???000011111???
Источник ACM Mid-Central Regional Programming Contest 2007