Persistent Bits

Time limit1sMemory limit128 MB

Summary

Starting from a seed S, repeatedly apply (A*X+B) mod C and report, for each of the 16 bit positions, whether it is always 1, always 0, or varies.

Level: Medium4 of 10
Topics: Bit manipulation, Simulation, Hash map
Solved: No attempts yet

Problem

WhatNext Software builds sequence generators that they hope will produce fairly random sequences of 16-bit unsigned integers in the range 0 to 65535. A sequence is specified by integers $A$ , $B$ , $C$ , and $S$ , where $1 \le A < 32768$ , $0 \le B < 65536$ , $2 \le C < 65536$ , and $0 \le S < C$ . $S$ is the first element (the seed) of the sequence, and each later element is generated from the previous one. If $X$ is an element of the sequence, then the next element is

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

where $\bmod$ is the remainder operation. Although every element of the sequence is a 16-bit unsigned integer less than 65536, the intermediate result $A \cdot X + B$ may be larger, so the calculation should use a 32-bit integer rather than a 16-bit one to stay accurate.

Some parameter values produce better sequences than others. The most embarrassing sequences are those that never change one or more bits. A bit that never changes throughout the sequence is called persistent. Ideally a sequence has no persistent bits. Your job is to examine a sequence and determine which bits are persistent.

For example, $A = 2$ , $B = 5$ , $C = 18$ , $S = 3$ is a particularly bad choice. It produces the sequence 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$ , and then $(2 \cdot 17 + 5) \bmod 18 = 3$ again, returning to the start. So the sequence repeats the same six values over and over:

Decimal	16-Bit Binary
3	0000000000000011
11	0000000000001011
9	0000000000001001
5	0000000000000101
15	0000000000001111
17	0000000000010001
overall	00000000000????1

The last row of the table shows which bit positions are always 0, always 1, or take on both values in the sequence. Note that 12 of the 16 bits are persistent. (Good random sequences have no persistent bits, but the converse is not necessarily true: the sequence defined by $A = 1$ , $B = 1$ , $C = 64000$ , $S = 0$ has no persistent bits, yet it is not random either — it simply counts from 0 to 63999 before repeating.) A sequence need not return to its seed: with $A = 2$ , $B = 0$ , $C = 16$ , $S = 2$ the sequence goes 2, 4, 8, 0, 0, 0, ....

Input

The input contains from one to sixteen datasets, followed by a line containing only 0. Each dataset is a single line containing decimal integer values for $A$ , $B$ , $C$ , and $S$ , separated by single blanks.

Output

Print one line of output for each dataset. Each line contains 16 characters — either '1', '0', or '?' for each of the 16 bits in order, most significant bit first. '1' means the corresponding bit is always 1, '0' means it is always 0, and '?' means the bit takes on both 0 and 1 in the sequence.

Examples5

Example 1

Input

2 5 18 3
1 1 64000 0
2 0 16 2
256 85 32768 21845
1 4097 32776 248
0

Expected output

00000000000????1
????????????????
000000000000???0
0101010101010101
0???000011111???

Example 2
Input
```
2 5 18 3
0
```
Expected output
```
00000000000????1
```
Example 3
Input
```
1 1 64000 0
0
```
Expected output
```
????????????????
```
Example 4
Input
```
2 0 16 2
0
```
Expected output
```
000000000000???0
```
Example 5
Input
```
256 85 32768 21845
0
```
Expected output
```
0101010101010101
```