시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 40 11 2 9.524%

문제

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≤10)가 주어진다. 다음 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

힌트

W3sicHJvYmxlbV9pZCI6IjIwNjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjFcdWQ1NThcdWFlMzAgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5OaWxzXHVjNjQwIE1pa2FlbFx1Yzc0MCBcdWFjZjFcdWQ1NThcdWFlMzAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgSygxJmxlO0smbGU7NilcdWFjMWNcdWM3NTggXHVjZTc0XHViNGRjXHVjNjQwIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVjMmU0XHVjMjE4IFgoMSZsdDtYJmx0OzEwLDAwMClcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YzljNFx1ZDU4OVx1YjQxY1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2U3NFx1YjRkY1x1YzVkMFx1YjI5NCAwLjkgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzJlNFx1YzIxOFx1YWMwMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHVhY2UwLCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1Yzc3NCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVkNTY4XHVhZWQ4IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTcwIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVhYzAxIFx1ZDEzNFx1YzVkMFx1YzExYyBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzQwIFx1ZDU1YyBcdWM3YTVcdWM3NTggXHVjZTc0XHViNGRjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViYTc0IFx1YWRmOCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWMyZTRcdWMyMThcdWI5N2MgWFx1YzVkMCBcdWFjZjFcdWQ1NzRcdWMxMWMgXHVjMGM4XHViODVjXHVjNmI0IFhcdWI5N2MgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhZGY4XHViN2VjXHViYTc0IFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjMGFjXHViNzhjXHViM2M0IFx1ZDU1YyBcdWM3YTVcdWM3NTggXHVjZTc0XHViNGRjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YWNlMCwgXHVhZGY4IFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YzJlNFx1YzIxOFx1Yjk3YyBcdWM3NzRcdWM4MDQgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBYXHVjNWQwIFx1YWNmMVx1ZDU1OFx1YWNlMCwgXHViNjEwIFx1YzBjOFx1Yjg1Y1x1YzZiNCBYXHViOTdjIFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NjAgXHViNTRjXHVjNWQwXHViMjk0IEtcdWFjMWNcdWM3NTggXHVjZTc0XHViNGRjIFx1YzkxMVx1YzVkMFx1YzExYyBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkNTU4XHViMDk4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1Yzc3NFx1YzgwNCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHViNDE4XHVjNWM4XHViMzU4IFx1Y2U3NFx1YjRkY1x1YjNjNCBcdWM1YmNcdWI5YzhcdWI0ZTBcdWM5YzAgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NzQgXHVjOWM0XHVkNTg5XHViNDE4XHViYTc0LCBcdWMyZTRcdWMyMTggWFx1Yzc1OCBcdWFjMTJcdWM3NzQgXHVjODEwXHVjODEwIFx1YzkwNFx1YzViNFx1YjRlNFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgWFx1Yjk3YyBcdWM5MDRcdWM1ZWMgXHViMDk4XHVhYzAwXHViMmU0XHVhYzAwLCBcdWJhM2NcdWM4MDAgWFx1YWMwMCAxIFx1Yzc3NFx1ZDU1OFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHViOWNjXHViNGRjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzJiOVx1Yzc5MFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIE5pbHNcdWFjMDAgXHViYTNjXHVjODAwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHViYWE4XHViNDUwIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDAgXHVjNzc1XHVjMjE5XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYyBcdWNkNWNcdWMxMjBcdWM3NDQgXHViMmU0XHVkNTc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5YzRcdWQ1ODlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMmI5XHVjNzkwXHViOTdjIFx1YWMwMFx1YjgyNFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbjxwPlx1YzJlNFx1YzIxOCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVkNTU4XHViMmU0IFx1YmNmNFx1YmE3NCBcdWM2MjRcdWNjMjgocm91bmRpbmctZXJyb3IpXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWNjNDRcdWM4MTBcdWM3NDQgXHVkNTYwIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViYjM4XHVjODFjXHVhYzAwIFx1YzBkZFx1YWUzMFx1YjI5NCBcdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzk4OSwgXHVjNzg1XHViODI1IFx1YWMxMlx1Yzc0NCBcdWJiZjhcdWMxMzhcdWQ1NThcdWFjOGMgXHVjODcwXHVjODA4XHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWIyZjVcdWM3NzQgXHViYzE0XHViMDBjXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjNDRcdWM4MTAgXHViMzcwXHVjNzc0XHVkMTMwXHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEmbGU7VCZsZTsxMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmEzY1x1YzgwMCBcdWMyZTRcdWMyMTggWFx1YzY0MCBcdWM4MTVcdWMyMTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWFjMDEgXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyZTRcdWMyMThcdWI0ZTRcdWM3NzQgS1x1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMyZTRcdWMyMThcdWI0ZTRcdWM3NDAgXHVjNzIwXHVkNmE4IFx1YzIyYlx1Yzc5MFx1YWMwMCA2XHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWMyYjlcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjA2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZ1bm55IEdhbWVzIiwiZGVzY3JpcHRpb24iOiI8cD5OaWxzIGFuZCBNaWthZWwgYXJlIGludGVyZ2FsYXhpYWwgXHVmYjAxZ2h0ZXJzLiBOb3cgdGhleSBhcmUgY29tcGV0aW5nIGZvciB0aGUgcGxhbmV0IFRlbGx1cy4gVGhlIHNpemUgb2YgdGhpcyBzbWFsbCBhbmQgdW5pbXBvcnRhbnQgcGxhbmV0IGlzIDEgJmx0OyBYICZsdDsgMTAwMDAgZ29icy4gVGhlIHByb2JsZW0gaXMgdGhhdCB0aGVpciBwb2NrZXRzIG9ubHkgaGF2ZSByb29tIGZvciBvbmUgZ29iLCBzbyB0aGV5IGhhdmUgdG8gcmVkdWNlIHRoZSBzaXplIG9mIHRoZSBwbGFuZXQuIFRoZXkgaGF2ZSBhdmFpbGFibGUgMSAmbGU7IEsgJmxlOyA2IEZBQ1RPUi13ZWFwb25zIGNoYXJhY3Rlcml6ZWQgYnkgbnVtYmVycyBGPHN1Yj4xPFwvc3ViPiwgRjxzdWI+MjxcL3N1Yj4sIC4gLiAuICwgRjxzdWI+azxcL3N1Yj4sIGFsbCBsZXNzIHRoYW4gMC45LiBBcyBpcyBjb21tb25seSBrbm93biwgYSBGQUNUT1Itd2VhcG9uIHdpbGwgYmxvdyBvZmYgcGFydCBvZiB0aGUgcGxhbmV0LCB0aHVzIHJlZHVjaW5nIHRoZSBwbGFuZXQgdG8gYSBmcmFjdGlvbiBvZiBpdHMgc2l6ZSwgZ2l2ZW4gYnkgdGhlIGNoYXJhY3RlcmlzdGljLiBUaHVzLCB3aXRoIGUuZy4gRjxzdWI+MTxcL3N1Yj4gPSAwLjUgYW4gYXBwbGljYXRpb24gb2YgdGhlIFx1ZmIwMXJzdCB3ZWFwb24gd2lsbCBoYWxmIHRoZSBzaXplIG9mIHRoZSBwbGFuZXQuIFRoZSBcdWZiMDFnaHRlciB3aG8gcmVkdWNlcyB0aGUgc2l6ZSB0byBsZXNzIHRoYW4sIG9yIGVxdWFsIHRvLCAxIGdvYiBjYW4gdGFrZSB0aGUgcGxhbmV0IGhvbWUgd2l0aCBoaW0uIFRoZXkgdGFrZSB0dXJucyBhdHRhY2tpbmcgdGhlIHBsYW5ldCB3aXRoIGFueSB3ZWFwb24uIElmIE5pbHMgc3RhcnRzLCB3aG8gd2lsbCB3aW4gdGhlIHBsYW5ldD8gQXNzdW1lIHRoYXQgYm90aCBOaWxzIGFuZCBNaWthZWwgYXJlIG9tbmlzY2llbnQgYW5kIGFsd2F5cyBtYWtlIGEgd2lubmluZyBtb3ZlIGlmIHRoZXJlIGlzIG9uZS48XC9wPlxyXG5cclxuPHA+VGVjaG5pY2FsIG5vdGU6IFRvIGVhc2UgdGhlIHByb2JsZW0gb2Ygcm91bmRpbmcgZXJyb3JzLCB0aGVyZSB3aWxsIGJlIG5vIGVkZ2UgY2FzZXMgd2hlcmUgYW4gaW5cdWZiMDFuaXRlc2ltYWwgcGVydHVyYmF0aW9uIG9mIHRoZSBpbnB1dCB2YWx1ZXMgd291bGQgY2F1c2UgYSBkaWZmZXJlbnQgYW5zd2VyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGlzIE4gJmxlOyAxMDAsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnNpc3RzIG9mIFgsIEsgYW5kIHRoZW4gdGhlIEsgbnVtYmVycyBGPHN1Yj4xPFwvc3ViPiwgRjxzdWI+MjxcL3N1Yj4sIC4gLiAuICwgRjxzdWI+azxcL3N1Yj4sIGhhdmluZyBubyBtb3JlIHRoYW4gNiBkZWNpbWFsczxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJvZHVjZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgbmFtZSBvZiB0aGUgd2lubmVyIChlaXRoZXIgTmlscyBvciBNaWthZWwpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==