Постійні біти
Компания WhatNext створює генератори послідовностей, які, як вони сподіваються, будуть видавати довільні послідовності 16-бітових беззнакових цілих чисел в інтервалі 0–65535. Послідовність задається цілими числами A, B, C і S, де 1 ≤ A < 32768, 0 ≤ B < 65536, 2 ≤ C < 65536 и0 ≤ S < 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.