Hi Friends! Hopefully my own solution to this is correct. However don't hesitate to report if you suspect checker behaves wrong - and sorry for inconvenience!
We have seen a couple of ways to generate random numbers already (or rather "pseudo-random") - one of them
Neumann's which was virtually first practical random generator, and
LCG which is still widely used in standard libraries of many
languages (e.g. C++, Java).
Both of them are known to be of poor in many regards. Methods based on shift register are gaining popularity
nowadays (particularly used in many JavaScript implementations). Let's look at one of the simplest of them.
For simplicity, let's generate 4-bit random values. Every step has 3 operations:
0-th and 1-st) and xor them to get single bit3-rd)Let's "run" this process manually, starting with value 1:
value: xor lowest bits shift right inject new bit
0001 (0^1 = 1) _000 1000
1000 (0^0 = 0) _100 0100
0100 (0^0 = 0) _010 0010
0010 (1^0 = 0) _001 1001
Continue this until numbers start to repeat:
1001 => 1100 => 0110 => 1011 => 0101 => 1010 =>
=> 1101 => 1110 => 1111 => 0111 => 0011 => 0001
Great, we got 15 possible values - in decimal the sequence looks like:
1 8 4 2 9 12 6 11 5 10 13 14 15 7 3 1 ...
Obviously, 0 couldn't be included as it will loop immediately to itself.
Now, extending this algorithm, we can work with values of N digits and build sequences of 2**N - 1 numbers.
Also we are not restricted to picking just two lowest digits for xoring. As larger example, try th 8-bit
values, picking bits in positions 0, 1, 3, 5 for xoring (i.e. bits forming "mask" 00101011).
Result of xoring obviously do not depend on order, but simply on whether number of bits set to 1 among
those picked (masked) is odd (result is 1) or even (result is 0).
00000001 => 10000000 => 01000000 => 00100000 => 10010000 => 01001000 => 10100100 => 11010010 ...
Try continuing this and see how many different values we get. Hopefully all 255 (except zero).
So our "shift register random generator" is defined by number of bits N in the "register" holding current
value - and M - bit mask, telling which bits are selected for xoring on every iteration.
It is easy to see that not any mask M is equally good. For example, with 4-bit version we can try
mask M=5 (i.e. 0101 - picking 0-th and 2-nd bits):
0001 => 1000 => 0100 => 1010 => 0101 => 0010 => 0001
it doesn't iterate through all 15 values, coming to repeat too soon! Let's call good mask such M
which allows iteting over all 2**N - 1 values.
So, given N and M we... don't ask you to write the code for generating random sequence :)
Instead just tell, please, whether M is "good" for given N and if not - which smallest possible mask
above M is "good".
Input gives amount of test-cases in the first line.
Next lines contain one test-case each, in form N M.
Answer should for every testcase just repeat M if it is "good" for given N, otherwise suggest nearest
larger M1 > M which makes "good mask".
Example:
input:
3
6 35
8 141
10 202
answer:
39 141 215