시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 28 6 6 46.154%

문제

현수는 새로운 게임을 만들고 있다. 이 게임은 어드벤쳐 게임으로 해적과 원숭이가 등장한다. 게임을 해본 사람들의 말에 의하면 엄청나게 재밌다고 한다.

이 게임은 다양한 랜덤 요소를 포함하고 있다. 따라서, 현수는 랜덤 함수 생성기를 이용하려고 한다. 랜덤 함수 생성기는 줄여서 RNG라고 쓴다.

각 RNG는 다음과 같은 식을 사용한다. x가 이전 랜덤 숫자 일때, y는 아래 식으로 구할 수 있다.

y = ax2 + bx + c (mod 2n)

a, b, c, n은 정수이다.

현수는 게임을 테스트 하기 위하고 있다. 현수는 게임을 중단시키고 디버그 콘솔을 볼 수 있다. 디버그 콘솔에는 현재 생성된 랜덤 숫자 하나가 나타나 있다. 하지만, 현수는 프로그램을 역추적해 그 전의 랜덤 숫자를 알아내려고 한다.

현재 랜덤 숫자(y)의 값과 a, b, c, n이 주어졌을 때, 이전 랜덤 숫자(x)를 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.

  • 첫째 줄에 다섯개의 정수 y, a, b, c, n이 주어진다. (0 ≤ y, a, b, c < 2n, 1 ≤ n ≤ 31)

출력

각 테스트 케이스에 대해서, 이전 랜덤 숫자 x를 출력한다. (0 ≤ x < 2n) 만약, 가능한 x가 없거나, 두 개 이상 존재한다면 "No unique solution"을 출력한다.

예제 입력 1

4
26 2 1 5 5
10 1 0 0 4
1 1 1 1 4
3 14 15 92 7

예제 출력 1

3
No unique solution
No unique solution
55

힌트

W3sicHJvYmxlbV9pZCI6IjU0MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJSTkciLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDYwNFx1YzIxOFx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHVjNWI0XHViNGRjXHViY2E0XHVjY2QwIFx1YWM4Y1x1Yzc4NFx1YzczY1x1Yjg1YyBcdWQ1NzRcdWM4MDFcdWFjZmMgXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU3NFx1YmNmOCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHViOWQwXHVjNWQwIFx1Yzc1OFx1ZDU1OFx1YmE3NCBcdWM1YzRcdWNjYWRcdWIwOThcdWFjOGMgXHVjN2FjXHViYzBjXHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWIyZTRcdWM1OTFcdWQ1NWMgXHViNzljXHViMzY0IFx1YzY5NFx1YzE4Y1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1ZDYwNFx1YzIxOFx1YjI5NCBcdWI3OWNcdWIzNjQgXHVkNTY4XHVjMjE4IFx1YzBkZFx1YzEzMVx1YWUzMFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI3OWNcdWIzNjQgXHVkNTY4XHVjMjE4IFx1YzBkZFx1YzEzMVx1YWUzMFx1YjI5NCBcdWM5MDRcdWM1ZWNcdWMxMWMgUk5HXHViNzdjXHVhY2UwIFx1YzRmNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFJOR1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzJkZFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIHhcdWFjMDAgXHVjNzc0XHVjODA0IFx1Yjc5Y1x1YjM2NCBcdWMyMmJcdWM3OTAgXHVjNzdjXHViNTRjLCB5XHViMjk0IFx1YzU0NFx1Yjc5OCBcdWMyZGRcdWM3M2NcdWI4NWMgXHVhZDZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPnkgPSBheDxzdXA+MjxcL3N1cD4gKyBieCArIGMgKG1vZCAyPHN1cD5uPFwvc3VwPik8XC9wPlxyXG5cclxuPHA+YSwgYiwgYywgblx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzIxOFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ2MDRcdWMyMThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzkxMVx1YjJlOFx1YzJkY1x1ZDBhNFx1YWNlMCBcdWI1MTRcdWJjODRcdWFkZjggXHVjZjU4XHVjMTk0XHVjNzQ0IFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI1MTRcdWJjODRcdWFkZjggXHVjZjU4XHVjMTk0XHVjNWQwXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWMwZGRcdWMxMzFcdWI0MWMgXHViNzljXHViMzY0IFx1YzIyYlx1Yzc5MCBcdWQ1NThcdWIwOThcdWFjMDAgXHViMDk4XHVkMGMwXHViMDk4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWQ2MDRcdWMyMThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1YzVlZFx1Y2Q5NFx1YzgwMVx1ZDU3NCBcdWFkZjggXHVjODA0XHVjNzU4IFx1Yjc5Y1x1YjM2NCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjN2FjIFx1Yjc5Y1x1YjM2NCBcdWMyMmJcdWM3OTAoeSlcdWM3NTggXHVhYzEyXHVhY2ZjIGEsIGIsIGMsIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHVjODA0IFx1Yjc5Y1x1YjM2NCBcdWMyMmJcdWM3OTAoeClcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU0XHVjMTJmXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCB5LCBhLCBiLCBjLCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyB5LCBhLCBiLCBjICZsdDsgMjxzdXA+bjxcL3N1cD4sIDEgJmxlOyBuICZsZTsgMzEpPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc3NFx1YzgwNCBcdWI3OWNcdWIzNjQgXHVjMjJiXHVjNzkwIHhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoMCAmbGU7IHggJmx0OyAyPHN1cD5uPFwvc3VwPikgXHViOWNjXHVjNTdkLCBcdWFjMDBcdWIyYTVcdWQ1NWMgeFx1YWMwMCBcdWM1YzZcdWFjNzBcdWIwOTgsIFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCAmcXVvdDtObyB1bmlxdWUgc29sdXRpb24mcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU0MzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSTkcgaW4gUmV2ZXJzZSIsImRlc2NyaXB0aW9uIjoiPHA+VG9tIGlzIG1ha2luZyBhIG5ldyBjb21wdXRlciBnYW1lLiBJdCYjMzk7cyBhbiBhZHZlbnR1cmUgZ2FtZSBmZWF0dXJpbmcgYm90aCBuaW5qYXMgYW5kIHBpcmF0ZXM7IGZ1biBndWFyYW50ZWVkITxcL3A+XHJcblxyXG48cD5WYXJpb3VzIGVsZW1lbnRzIG9mIHRoZSBnYW1lIGNvbnRhaW4gYSByYW5kb20gZmFjdG9yLiBUaGVyZWZvcmUsIHRoZSBnYW1lIG1ha2VzIHVzZSBvZiB2YXJpb3VzIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9ycywgb3IgUk5HIGZvciBzaG9ydC4gRWFjaCBSTkcgdXNlcyB0aGUgZm9sbG93aW5nIGZvcm11bGE6IGxldCB4IGJlIHRoZSBwcmV2aW91cyByYW5kb20gbnVtYmVyLiBUaGUgbmV4dCBudW1iZXIgeSBpcyB0aGVuIGdpdmVuIGJ5OjxcL3A+XHJcblxyXG48cD55ID0gYXg8c3VwPjI8XC9zdXA+Jm5ic3A7KyBieCArIGMgKG1vZCAyPHN1cD5uPFwvc3VwPik8XC9wPlxyXG5cclxuPHA+d2hlcmUgYSwgYiwgYyBhbmQgbiBhcmUgc29tZSBpbnRlZ2VyIHBhcmFtZXRlcnMuPFwvcD5cclxuXHJcbjxwPkZvciB0aGUgcHVycG9zZSBvZiB0ZXN0aW5nIHRoZSBnYW1lLCBUb20gY2FuIGludGVycnVwdCB0aGUgZ2FtZSBhbmQgY29uc3VsdCBkZWJ1ZyBvdXRwdXQuIFNvbWUgb2YgdGhlIHZhbHVhYmxlIHBpZWNlcyBvZiBpbmZvcm1hdGlvbiBhcmUgdGhlIGxhc3QgdmFsdWVzIHRoZSBSTkdzIGhhdmUgcHJvZHVjZWQuIEhvd2V2ZXIsIFRvbSBvZnRlbiB3aXNoZXMgdG8gYmFja3RyYWNrIGhpcyBwcm9ncmFtLCBhbmQgZm9yIHRoYXQgaGUgbmVlZHMgdG8gZmlndXJlIG91dCB3aGF0IHRoZSBwcmV2aW91cyB2YWx1ZXMgb2YgdGhlIFJOR3Mgd2VyZS4gU28gaW4gc2hvcnQsIGdpdmVuIHRoZSBwYXJhbWV0ZXJzIG9mIGEgY2VydGFpbiBSTkcgYW5kIHRoZSBjdXJyZW50IG51bWJlciB5LCBoZSB3YW50cyB0byBrbm93IHdoYXQgdGhlIHByZXZpb3VzIG51bWJlciB4IHdhcy4gQ2FuIHlvdSBoZWxwIGhpbT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBjYXNlIGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHZlIGludGVnZXJzIHksIGEsIGIsIGMgYW5kIG4sIHNhdGlzZnlpbmcgMCAmbGU7IHksIGEsIGIsIGMgJmx0OyAyPHN1cD5uPFwvc3VwPiZuYnNwO2FuZCZuYnNwOzEgJmxlOyBuICZsZTsgMzE6IHRoZSBsYXN0IHZhbHVlIG9mIHRoZSBSTkcgYW5kIGl0cyBmb3VyIHBhcmFtZXRlcnMsIHJlc3BlY3RpdmVseS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgaW4gdGhlIGlucHV0LCB0aGUgb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyIG9uIGEgc2luZ2xlIGxpbmU6IHRoZSBwcmV2aW91cyB2YWx1ZSB4IG9mIHRoZSBSTkcgKDAgJmxlOyB4ICZsdDsgMjxzdXA+bjxcL3N1cD4pLiBJZiB0aGVyZSBpcyBubyBzdWNoIG51bWJlciwgb3IgbW9yZSB0aGFuIG9uZSBzdWNoIG51bWJlciwgdGhlIG91dHB1dCBzaG91bGQgYmUgJnF1b3Q7Tm8gdW5pcXVlIHNvbHV0aW9uJnF1b3Q7ICh3aXRob3V0IHRoZSBxdW90YXRpb24gbWFya3MpIG9uIGEgc2luZ2xlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d