eolymp
bolt
Try our new interface for solving problems
Məsələlər

RNG in Reverse

RNG in Reverse

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Tom is making a new computer game. It's an adventure game featuring both ninjas and pirates; fun guaranteed!

Various elements of the game contain a random factor. Therefore, the game makes use of various random number generators, or RNG for short. Each RNG uses the following formula: let x be the previous random number. The next number y is then given by:

y = ax^2+ bx + c (mod 2^n)

where a, b, c and n are some integer parameters.

For the purpose of testing the game, Tom can interrupt the game and consult debug output. Some of the valuable pieces of information are the last values the RNGs have produced. However, Tom often wishes to backtrack his program, and for that he needs to figure out what the previous values of the RNGs were. So in short, given the parameters of a certain RNG and the current number y, he wants to know what the previous number x was. Can you help him?

Giriş verilənləri

The first line contains a single number: the number of test cases to follow. Each test case has the following format:

  • One line with five integers y, a, b, c and n (0 y, a, b, c < 2^n, 1 n 31): the last value of the RNG and its four parameters, respectively.

Çıxış verilənləri

For every test case print one integer on a single line: the previous value x of the RNG (0 x < 2^n). If there is no such number, or more than one such number, the output should be "No unique solution" (without the quotation marks) on a single line.

Nümunə

Giriş verilənləri #1
4
26 2 1 5 5
10 1 0 0 4
1 1 1 1 4
3 14 15 92 7
Çıxış verilənləri #1
3
No unique solution
No unique solution
55
Mənbə 2011 Benelux Algorithm Programming Contest, Preliminaries, Problem B