시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB5213416.667%

문제

Nils와 Mikael은 곱하기 게임을 하고 있다. 이 게임은 K(1 ≤ K ≤ 6)개의 카드와 한 개의 실수 X(1 < X < 10,000)를 가지고 진행된다. 각각의 카드에는 0.9 이하의 양의 실수가 적혀 있고, 두 사람은 이 카드를 함께 사용하게 된다.

게임은 두 사람이 번갈아가며 진행하는데, 각 턴에서 각 사람은 한 장의 카드를 선택할 수 있다. 카드를 선택하면 그 카드에 적혀 있는 실수를 X에 곱해서 새로운 X를 얻게 된다. 그러면 그 다음 사람도 한 장의 카드를 선택하고, 그 카드에 적혀 있는 실수를 이전 단계에서 만들어진 X에 곱하고, 또 새로운 X를 얻게 된다. 카드를 선택할 때에는 K개의 카드 중에서 반드시 하나를 선택해야 하며, 이전 단계에서 사용되었던 카드도 얼마든지 선택할 수 있다.

이와 같이 게임이 진행되면, 실수 X의 값이 점점 줄어들게 된다. 이와 같이 X를 줄여 나가다가, 먼저 X가 1 이하가 되도록 만드는 사람이 이 게임의 승자가 된다.

게임은 Nils가 먼저 시작하게 된다. 두 사람은 모두 이 게임에 익숙하기 때문에, 각 단계에서 최선을 다해 게임을 진행하게 된다. 이러한 상황에서 이 게임의 승자를 가려내는 프로그램을 작성하시오.

실수 연산을 하다 보면 오차(rounding-error)가 발생할 수 있는데, 채점을 할 때에는 이러한 문제가 생기는 입력 데이터는 사용하지 않는다. 즉, 입력 값을 미세하게 조절했을 때 답이 바뀌는 경우는 입력으로 주어지지 않는다.

입력

첫째 줄에 채점 데이터의 개수 T(1 ≤ T ≤ 55)가 주어진다. 다음 T개의 줄에는 각 데이터가 주어진다. 먼저 실수 X와 정수 K가 주어지고, 다음에는 각 카드에 적혀있는 실수들이 K개 주어진다. 각 실수들은 유효 숫자가 6개를 넘지 않는다.

출력

각각의 데이터에 대해 승자를 출력한다.

예제 입력 1

4
6 2 0.25 0.5
10 2 0.25 0.5
29.29 4 0.3 0.7 0.43 0.54
29.30 4 0.3 0.7 0.43 0.54

예제 출력 1

Mikael
Nils
Nils
Mikael
W3sicHJvYmxlbV9pZCI6IjIwNjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjFcdWQ1NThcdWFlMzAgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5OaWxzXHVjNjQwIE1pa2FlbFx1Yzc0MCBcdWFjZjFcdWQ1NThcdWFlMzAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgSygxICZsZTsgSyAmbGU7IDYpXHVhYzFjXHVjNzU4IFx1Y2U3NFx1YjRkY1x1YzY0MCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YzJlNFx1YzIxOCBYKDEgJmx0OyBYICZsdDsgMTAsMDAwKVx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjZTc0XHViNGRjXHVjNWQwXHViMjk0IDAuOSBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzJlNFx1YzIxOFx1YWMwMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHVhY2UwLCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1Yzc3NCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVkNTY4XHVhZWQ4IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3MCBcdWM5YzRcdWQ1ODlcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YWMwMSBcdWQxMzRcdWM1ZDBcdWMxMWMgXHVhYzAxIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWQ1NWMgXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjZTc0XHViNGRjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YmE3NCBcdWFkZjggXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjMmU0XHVjMjE4XHViOTdjIFhcdWM1ZDAgXHVhY2YxXHVkNTc0XHVjMTFjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBYXHViOTdjIFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YmE3NCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzBhY1x1Yjc4Y1x1YjNjNCBcdWQ1NWMgXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjZTAsIFx1YWRmOCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWMyZTRcdWMyMThcdWI5N2MgXHVjNzc0XHVjODA0IFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzQgWFx1YzVkMCBcdWFjZjFcdWQ1NThcdWFjZTAsIFx1YjYxMCBcdWMwYzhcdWI4NWNcdWM2YjQgWFx1Yjk3YyBcdWM1YmJcdWFjOGMgXHViNDFjXHViMmU0LiBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YjU0Y1x1YzVkMFx1YjI5NCBLXHVhYzFjXHVjNzU4IFx1Y2U3NFx1YjRkYyBcdWM5MTFcdWM1ZDBcdWMxMWMgXHViYzE4XHViNGRjXHVjMmRjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWM3NzRcdWM4MDQgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YzBhY1x1YzZhOVx1YjQxOFx1YzVjOFx1YjM1OCBcdWNlNzRcdWI0ZGNcdWIzYzQgXHVjNWJjXHViOWM4XHViNGUwXHVjOWMwIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MThcdWJhNzQsIFx1YzJlNFx1YzIxOCBYXHVjNzU4IFx1YWMxMlx1Yzc3NCBcdWM4MTBcdWM4MTAgXHVjOTA0XHVjNWI0XHViNGU0XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBYXHViOTdjIFx1YzkwNFx1YzVlYyBcdWIwOThcdWFjMDBcdWIyZTRcdWFjMDAsIFx1YmEzY1x1YzgwMCBYXHVhYzAwIDEgXHVjNzc0XHVkNTU4XHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMmI5XHVjNzkwXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIE5pbHNcdWFjMDAgXHViYTNjXHVjODAwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHViYWE4XHViNDUwIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDAgXHVjNzc1XHVjMjE5XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYyBcdWNkNWNcdWMxMjBcdWM3NDQgXHViMmU0XHVkNTc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5YzRcdWQ1ODlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMmI5XHVjNzkwXHViOTdjIFx1YWMwMFx1YjgyNFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWMyZTRcdWMyMTggXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YjJlNCBcdWJjZjRcdWJhNzQgXHVjNjI0XHVjYzI4KHJvdW5kaW5nLWVycm9yKVx1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjYzQ0XHVjODEwXHVjNzQ0IFx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVjNzc0XHViN2VjXHVkNTVjIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWMwZGRcdWFlMzBcdWIyOTQgXHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM5ODksIFx1Yzc4NVx1YjgyNSBcdWFjMTJcdWM3NDQgXHViYmY4XHVjMTM4XHVkNTU4XHVhYzhjIFx1Yzg3MFx1YzgwOFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHViMmY1XHVjNzc0IFx1YmMxNFx1YjAwY1x1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2M0NFx1YzgxMCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSAmbGU7IFQgJmxlOyA1NSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmEzY1x1YzgwMCBcdWMyZTRcdWMyMTggWFx1YzY0MCBcdWM4MTVcdWMyMTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWFjMDEgXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyZTRcdWMyMThcdWI0ZTRcdWM3NzQgS1x1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMyZTRcdWMyMThcdWI0ZTRcdWM3NDAgXHVjNzIwXHVkNmE4IFx1YzIyYlx1Yzc5MFx1YWMwMCA2XHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjMmI5XHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnVubnkgR2FtZXMiLCJkZXNjcmlwdGlvbiI6IjxwPk5pbHMgYW5kIE1pa2FlbCBhcmUgaW50ZXJnYWxheGlhbCBcdWZiMDFnaHRlcnMuIE5vdyB0aGV5IGFyZSBjb21wZXRpbmcgZm9yIHRoZSBwbGFuZXQgVGVsbHVzLiBUaGUgc2l6ZSBvZiB0aGlzIHNtYWxsIGFuZCB1bmltcG9ydGFudCBwbGFuZXQgaXMgMSAmbHQ7IFggJmx0OyAxMDAwMCBnb2JzLiBUaGUgcHJvYmxlbSBpcyB0aGF0IHRoZWlyIHBvY2tldHMgb25seSBoYXZlIHJvb20gZm9yIG9uZSBnb2IsIHNvIHRoZXkgaGF2ZSB0byByZWR1Y2UgdGhlIHNpemUgb2YgdGhlIHBsYW5ldC4gVGhleSBoYXZlIGF2YWlsYWJsZSAxICZsZTsgSyAmbGU7IDYgRkFDVE9SLXdlYXBvbnMgY2hhcmFjdGVyaXplZCBieSBudW1iZXJzIEY8c3ViPjE8XC9zdWI+LCBGPHN1Yj4yPFwvc3ViPiwgLiAuIC4gLCBGPHN1Yj5rPFwvc3ViPiwgYWxsIGxlc3MgdGhhbiAwLjkuIEFzIGlzIGNvbW1vbmx5IGtub3duLCBhIEZBQ1RPUi13ZWFwb24gd2lsbCBibG93IG9mZiBwYXJ0IG9mIHRoZSBwbGFuZXQsIHRodXMgcmVkdWNpbmcgdGhlIHBsYW5ldCB0byBhIGZyYWN0aW9uIG9mIGl0cyBzaXplLCBnaXZlbiBieSB0aGUgY2hhcmFjdGVyaXN0aWMuIFRodXMsIHdpdGggZS5nLiBGPHN1Yj4xPFwvc3ViPiA9IDAuNSBhbiBhcHBsaWNhdGlvbiBvZiB0aGUgXHVmYjAxcnN0IHdlYXBvbiB3aWxsIGhhbGYgdGhlIHNpemUgb2YgdGhlIHBsYW5ldC4gVGhlIFx1ZmIwMWdodGVyIHdobyByZWR1Y2VzIHRoZSBzaXplIHRvIGxlc3MgdGhhbiwgb3IgZXF1YWwgdG8sIDEgZ29iIGNhbiB0YWtlIHRoZSBwbGFuZXQgaG9tZSB3aXRoIGhpbS4gVGhleSB0YWtlIHR1cm5zIGF0dGFja2luZyB0aGUgcGxhbmV0IHdpdGggYW55IHdlYXBvbi4gSWYgTmlscyBzdGFydHMsIHdobyB3aWxsIHdpbiB0aGUgcGxhbmV0PyBBc3N1bWUgdGhhdCBib3RoIE5pbHMgYW5kIE1pa2FlbCBhcmUgb21uaXNjaWVudCBhbmQgYWx3YXlzIG1ha2UgYSB3aW5uaW5nIG1vdmUgaWYgdGhlcmUgaXMgb25lLjxcL3A+XHJcblxyXG48cD5UZWNobmljYWwgbm90ZTogVG8gZWFzZSB0aGUgcHJvYmxlbSBvZiByb3VuZGluZyBlcnJvcnMsIHRoZXJlIHdpbGwgYmUgbm8gZWRnZSBjYXNlcyB3aGVyZSBhbiBpblx1ZmIwMW5pdGVzaW1hbCBwZXJ0dXJiYXRpb24gb2YgdGhlIGlucHV0IHZhbHVlcyB3b3VsZCBjYXVzZSBhIGRpZmZlcmVudCBhbnN3ZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgaXMgTiAmbGU7IDEwMCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29uc2lzdHMgb2YgWCwgSyBhbmQgdGhlbiB0aGUgSyBudW1iZXJzIEY8c3ViPjE8XC9zdWI+LCBGPHN1Yj4yPFwvc3ViPiwgLiAuIC4gLCBGPHN1Yj5rPFwvc3ViPiwgaGF2aW5nIG5vIG1vcmUgdGhhbiA2IGRlY2ltYWxzPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcm9kdWNlIG9uZSBsaW5lIG9mIG91dHB1dCB3aXRoIHRoZSBuYW1lIG9mIHRoZSB3aW5uZXIgKGVpdGhlciBOaWxzIG9yIE1pa2FlbCkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==