Задачі
Постійні біти
Постійні біти
Компания WhatNext створює генератори послідовностей, які, як вони сподіваються, будуть видавати довільні послідовності \textbf{16}-бітових беззнакових цілих чисел в інтервалі \textbf{0--65535}. Послідовність задається цілими числами \textbf{A}, \textbf{B}, \textbf{C} і \textbf{S}, де \textbf{1 }≤ \textbf{A }< \textbf{32768}, \textbf{0} ≤ \textbf{B} < \textbf{65536}, \textbf{2} ≤ \textbf{C} < \textbf{65536} и\textbf{0} ≤ \textbf{S} < \textbf{C}. \textbf{S} - перший елемент послідовності, а кожен наступний елемент отримується з поаереднього. Якщо \textbf{X} - деякий елемент послідовності, то наступним буде елемент
\textbf{(A*X + B) \% C}
де '\textbf{\%}' позначає залишок від ділення. Хоча кожен елемент послідовності є \textbf{16}-бітним беззнаковим цілим числом, меншим \textbf{65536}, проміжний результат \textbf{A*X + B} може бути більшим. Тому обчислення потрібно виконувати у \textbf{32}-бітових цілих числах, а не в \textbf{16}-бітових для отримання правильного результату.
Деякі значення параметрів генеують кращі послідовності, ніж інші. Найбільш поганими послідовностями у компанії WhatNext є ті, у яки є один або декілька бітів, які ніколи не змінюються. Біт, яки ніколи не змінюється в усій послідовності, називається постійним. В ідеалі послідовність не повинна мати постійний біт. Вам потрібно протестувати послідовність і визначити, які біти в ній є постійними.
Наприклад, дуже поганим буде вибір \textbf{A = 2}, \textbf{B = 5}, \textbf{C = 18} і \textbf{S = 3}. Він генерує послідовність \textbf{3}, \textbf{(2*3+5)\%18 = 11}, \textbf{(2*11+5)\%18 = 9}, \textbf{(2*9+5)\%18 = 5}, \textbf{(2*5+5)\%18 = 15}, \textbf{(2*15+5)\%18 = 17}, потім \textbf{(2*17+5)\%18 = 3} знову і так далі. Послідовність повторяється через кожні шість членів:
Останній рядок вказує позиції, у яких біти завжди залишаються \textbf{0}, завжди \textbf{1}, або приймають обидва значення. Відмітимо, що \textbf{12} з \textbf{16} біт є постійними. Гарні випадкові послідовності не мають постійних бітів, але зворотнє твердження не вірне. Наприклад, послідовність отримана значеннями \textbf{A = 1}, \textbf{B = 1}, \textbf{C = 64000} і \textbf{S = 0} не має постійних бітів, проте не є випадковою: вона лише рахує від \textbf{0} до \textbf{63999} і повторюється. Послідовність не обов'язково повинна повторюватись з першого елемента послвдовноств: значення \textbf{A = 2}, \textbf{B = 0}, \textbf{C = 16} в \textbf{S = 2} генерують послідовність \textbf{2}, \textbf{4}, \textbf{8}, \textbf{0}, \textbf{0}, \textbf{0}, \textbf{...} .
\InputFile
Вхідні дані містять від одного до шістнадцяти тестів, які завершуються рядком з одного \textbf{0}. Кожен тест складається з єдиного рядка, який містить цілі числа \textbf{A}, \textbf{B}, \textbf{C} і \textbf{S} у десятковому запису, відокремлені пропуском.
\OutputFile
Для кожного тесту вивести один рядок, який містить \textbf{16} символів '\textbf{1}', '\textbf{0}' або '\textbf{?}' для кожного з \textbf{16} біт у порядку з найбільш значимого. '\textbf{1}' позначає, що відповідний біт завжди дорівнює \textbf{1}, '\textbf{0}' позначає що відповідний біт завжди дорівнює \textbf{0}, а '\textbf{?}' позначає те, що біт у послідовності може приймати значення як \textbf{0}, так і \textbf{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???