시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB109923916321.252%

문제

작곡가 철수는 피보나치 수열을 이용하여 만든 피아노 곡을 우연히 유튜브에서 보게 되었다. 피보나치 수열이란 f1 = 1, f2 = 1, fn+2 = fn+1 + fn (모든 n ≥ 1에 대해)을 만족하는 수열이다.

이 곡은 피보나치 수열의 각 자리 숫자에 해당하는 건반을 눌러서 만들어졌다. 피보나치 수열의 첫 8개 항을 사용해 곡을 만든다면, 다음과 같이 건반을 총 10번 누르게 될 것이다.

1 → 1 → 2 → 3 → 5 → 8 → 1 → 3 → 2 → 1

철수는 자신도 이 방법을 사용해 보기로 마음먹었다. 그런데 피보나치 수열은 너무 빠르게 증가해서, 덧셈에 약한 철수가 계산하기에는 어려웠다.

그래서 철수는 방법을 조금 바꾸기로 했다. 철수는 어떤 수 M을 정한 후, 피보나치 수열의 각 항을 M으로 나눈 나머지를 구하고, 각 수의 각 자리 숫자로 새로운 수열 을 만들어 이에 따라 피아노 곡을 쓰려고 한다.

예를 들어 M=10일 때, 새로운 수열 은 다음과 같다.

{1, 1, 2, 3, 5, 8, 3, 1, …}

따라서 철수는 1 →1 → 2 → 3 → 5 → 8 → 3 → 1 → 4 → … 순으로 건반을 누르게 된다.

이때, 철수는 어떤 N에 대해 N번째로 누르게 되는 건반의 번호(i.e. 새로운 수열 의 N번째 항)가 궁금해졌다.

Q개의 N이 질의로 주어졌을 때, 각각의 질의에 대해 N번째로 누르게 되는 건반의 번호를 출력하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 정수 Q와 M이 공백을 사이에 두고 주어진다.

두 번째 줄부터 Q개의 줄에 각각의 질의를 나타내는 정수 N이 주어진다.

출력

각각의 N에 대해, N번째로 누르게 되는 건반의 번호(새로운 수열의 N 번째 항)를 입력에 주어진 순서대로 총 Q개의 줄에 출력한다.

제한

  • 1 ≤ N ≤ 1015
  • 2 ≤ M ≤ 1,000
  • 1 ≤ Q ≤ 100,000

예제 입력 1

2 10
5
8

예제 출력 1

5
1
W3sicHJvYmxlbV9pZCI6IjE3ODQwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1Yzc0Y1x1YzU0NSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzkxXHVhY2UxXHVhYzAwIFx1Y2NhMFx1YzIxOFx1YjI5NCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWI5Y2NcdWI0ZTAgXHVkNTNjXHVjNTQ0XHViMTc4IFx1YWNlMVx1Yzc0NCBcdWM2YjBcdWM1ZjBcdWQ3ODggXHVjNzIwXHVkMjljXHViZTBjXHVjNWQwXHVjMTFjIFx1YmNmNFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3ODAgZjxzdWI+MTxcL3N1Yj4gPSAxLCBmPHN1Yj4yPFwvc3ViPiA9IDEsIGY8c3ViPm4rMjxcL3N1Yj4gPSBmPHN1Yj5uKzE8XC9zdWI+ICsgZjxzdWI+bjxcL3N1Yj4gKFx1YmFhOFx1YjRlMCBuICZnZTsgMVx1YzVkMCBcdWIzMDBcdWQ1NzQpXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjZTFcdWM3NDAgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjNzkwXHViOWFjIFx1YzIyYlx1Yzc5MFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVhYzc0XHViYzE4XHVjNzQ0IFx1YjIwY1x1YjdlY1x1YzExYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM4NGNcdWIyZTQuIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjY2FiIDhcdWFjMWMgXHVkNTZkXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NCBcdWFjZTFcdWM3NDQgXHViOWNjXHViNGUwXHViMmU0XHViYTc0LCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWM3NFx1YmMxOFx1Yzc0NCBcdWNkMWQgMTBcdWJjODggXHViMjA0XHViOTc0XHVhYzhjIFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjEgJnJhcnI7IDEgJnJhcnI7IDIgJnJhcnI7IDMgJnJhcnI7IDUgJnJhcnI7IDggJnJhcnI7IDEgJnJhcnI7IDMgJnJhcnI7IDIgJnJhcnI7IDE8XC9wPlxyXG5cclxuPHA+XHVjY2EwXHVjMjE4XHViMjk0IFx1Yzc5MFx1YzJlMFx1YjNjNCBcdWM3NzQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NCBcdWJjZjRcdWFlMzBcdWI4NWMgXHViOWM4XHVjNzRjXHViYTM5XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWIxMDhcdWJiMzQgXHViZTYwXHViOTc0XHVhYzhjIFx1Yzk5ZFx1YWMwMFx1ZDU3NFx1YzExYywgXHViMzY3XHVjMTQ4XHVjNWQwIFx1YzU3ZFx1ZDU1YyBcdWNjYTBcdWMyMThcdWFjMDAgXHVhY2M0XHVjMGIwXHVkNTU4XHVhZTMwXHVjNWQwXHViMjk0IFx1YzViNFx1YjgyNFx1YzZlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViNzk4XHVjMTFjIFx1Y2NhMFx1YzIxOFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjODcwXHVhZTA4IFx1YmMxNFx1YWZiOFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1Y2NhMFx1YzIxOFx1YjI5NCBcdWM1YjRcdWI1YTQgXHVjMjE4IE1cdWM3NDQgXHVjODE1XHVkNTVjIFx1ZDZjNCwgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVkNTZkXHVjNzQ0IE1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWFjZTAsIFx1YWMwMSBcdWMyMThcdWM3NTggXHVhYzAxIFx1Yzc5MFx1YjlhYyBcdWMyMmJcdWM3OTBcdWI4NWMgPGVtPlx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWMyMThcdWM1ZjQ8XC9lbT4gXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNCBcdWM3NzRcdWM1ZDAgXHViNTMwXHViNzdjIFx1ZDUzY1x1YzU0NFx1YjE3OCBcdWFjZTFcdWM3NDQgXHVjNGYwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBNPTEwXHVjNzdjIFx1YjU0YywgPGVtPlx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWMyMThcdWM1ZjQgPFwvZW0+XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPnsxLCAxLCAyLCAzLCA1LCA4LCAzLCAxLCAmaGVsbGlwO308XC9wPlxyXG5cclxuPHA+XHViNTMwXHViNzdjXHVjMTFjIFx1Y2NhMFx1YzIxOFx1YjI5NCAxICZyYXJyOzEgJnJhcnI7IDIgJnJhcnI7IDMgJnJhcnI7IDUgJnJhcnI7IDggJnJhcnI7IDMgJnJhcnI7IDEgJnJhcnI7IDQgJnJhcnI7ICZoZWxsaXA7IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjNzRcdWJjMThcdWM3NDQgXHViMjA0XHViOTc0XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjLCBcdWNjYTBcdWMyMThcdWIyOTQgXHVjNWI0XHViNWE0IE5cdWM1ZDAgXHViMzAwXHVkNTc0IE5cdWJjODhcdWM5ZjhcdWI4NWMgXHViMjA0XHViOTc0XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWFjNzRcdWJjMThcdWM3NTggXHViYzg4XHVkNjM4KGkuZS4gPGVtPlx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWMyMThcdWM1ZjQgPFwvZW0+XHVjNzU4IE5cdWJjODhcdWM5ZjggXHVkNTZkKVx1YWMwMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlFcdWFjMWNcdWM3NTggTlx1Yzc3NCBcdWM5YzhcdWM3NThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzljOFx1Yzc1OFx1YzVkMCBcdWIzMDBcdWQ1NzQgTlx1YmM4OFx1YzlmOFx1Yjg1YyBcdWIyMDRcdWI5NzRcdWFjOGMgXHViNDE4XHViMjk0IFx1YWM3NFx1YmMxOFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggUVx1YzY0MCBNXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzljOFx1Yzc1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBOXHVjNWQwIFx1YjMwMFx1ZDU3NCwgTlx1YmM4OFx1YzlmOFx1Yjg1YyBcdWIyMDRcdWI5NzRcdWFjOGMgXHViNDE4XHViMjk0IFx1YWM3NFx1YmMxOFx1Yzc1OCBcdWJjODhcdWQ2MzgoXHVjMGM4XHViODVjXHVjNmI0IFx1YzIxOFx1YzVmNFx1Yzc1OCA8ZW0+TjxcL2VtPiBcdWJjODhcdWM5ZjggXHVkNTZkKVx1Yjk3YyBcdWM3ODVcdWI4MjVcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkMWQgUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDEwPHN1cD4xNTxcL3N1cD48XC9saT5cclxuXHQ8bGk+MiAmbGU7IE0gJmxlOyAxLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgUSAmbGU7IDEwMCwwMDAgPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNzg0MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpYm9uYWNjaSBzb25nIiwiZGVzY3JpcHRpb24iOiI8cD5FbHNhLCBhIGNvbXBvc2VyLCBoYXBwZW5lZCB0byBsaXN0ZW4gYSBwaWFubyBzb25nIG1hZGUgdXNpbmcgdGhlIEZpYm9uYWNjaSBzZXF1ZW5jZS4gRmlib25hY2NpIHNlcXVlbmNlIHtmPHN1Yj5uPFwvc3ViPn0gaXMgZGVmaW5lZCBieSBmb2xsb3dpbmcgcmVjdXJyZW5jZSByZWxhdGlvbjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5mPHN1Yj4xPFwvc3ViPiZuYnNwOz0gMSwmbmJzcDtmPHN1Yj4yPFwvc3ViPiZuYnNwOz0gMSw8XC9saT5cclxuXHQ8bGk+YW5kIGZvciBldmVyeSBuJm5ic3A7JmdlOyAxLCZuYnNwO2Y8c3ViPm4rMjxcL3N1Yj4mbmJzcDs9IGY8c3ViPm4rMTxcL3N1Yj4mbmJzcDsrIGY8c3ViPm48XC9zdWI+LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBzb25nIHdhcyBtYWRlIGJ5IHByZXNzaW5nIHRoZSBrZXlzIGNvcnJlc3BvbmRpbmcmbmJzcDt0byBlYWNoIGRpZ2l0IGluIHRoZSBGaWJvbmFjY2kgc2VxdWVuY2UuIElmIHlvdSB1c2UgdGhlIGZpcnN0IGVpZ2h0IGVudHJpZXMgb2YgdGhlIEZpYm9uYWNjaSBzZXF1ZW5jZSB0byBtYWtlIGEgc29uZywgeW91IHdpbGwgcHJlc3MgdGhlIDEwIGtleXMgaW4gdG90YWwsIGFzIGJlbG93LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4xICZyYXJyOyAxICZyYXJyOyAyICZyYXJyOyAzICZyYXJyOyA1ICZyYXJyOyA4ICZyYXJyOyAxICZyYXJyOyAzICZyYXJyOyAyICZyYXJyOyAxPFwvcD5cclxuXHJcbjxwPkVsc2EgdHJpZWQmbmJzcDt0byBjb21wb3NlIHBpYW5vIHNvbmcgdXNpbmcgdGhpcyBtZXRob2QuJm5ic3A7VGhlIEZpYm9uYWNjaSBzZXF1ZW5jZSwgaG93ZXZlciwgaW5jcmVhc2VkIHNvIHF1aWNrbHkgdGhhdCBpdCB3YXMgZGlmZmljdWx0IHRvIGNhbGN1bGF0ZS48XC9wPlxyXG5cclxuPHA+U28gRWxzYSZuYnNwO2RlY2lkZWQgdG8gY2hhbmdlIHRoZSBtZXRob2QgYSBsaXR0bGUuIFNoZSBjcmVhdGVkIGEgbmV3IHNlcXVlbmNlIHdpdGggdGhlIHJlbWFpbmRlciBvZiB0aGUgRmlib25hY2NpIHNlcXVlbmNlLCBkaXZpZGVkIGJ5IHNvbWUgcG9zaXRpdmUgaW50ZWdlciBNLiBTaGUmIzM5O3MgZ29pbmcgdG8gY29tcG9zZSBhIG5ldyBwaWFubyBzb25nIHVzaW5nIGVhY2ggZGlnaXQgb2YgdGhlIG5ldyBzZXF1ZW5jZS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIE0gPSAxMCwgbmV3IHNlcXVlbmNlIGlzOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj57MSwgMSwgMiwgMywgNSwgOCwgMywgMSwgLi4ufSw8XC9wPlxyXG5cclxuPHA+dGhlcmVmb3JlLCBzaGUmbmJzcDt3aWxsIHByZXNzIGtleSBpbiBvcmRlciBvZiZuYnNwOzEgJnJhcnI7IDEgJnJhcnI7IDIgJnJhcnI7IDMgJnJhcnI7IDUgJnJhcnI7IDggJnJhcnI7IDMgJnJhcnI7IDEgJnJhcnI7IDQmbmJzcDsmcmFycjsgJmhlbGxpcDsgLjxcL3A+XHJcblxyXG48cD5Gb3IgZml4ZWQgTSwgc2hlIHdhbnRzIHRvIGRlYWwgd2l0aCBmb2xsb3dpbmcgcXVlcnk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Zm9yIGdpdmVuIE4sIHByaW50IE4tdGggZW50cnkgb2YgdGhlIG5ldyBzZXF1ZW5jZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5TaGUgbmVlZHMgeW91ciBoZWxwIHRvIGRlYWwgd2l0aCBxdWVyaWVzLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBkZWFscyB3aXRoIHF1ZXJpZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSwgdHdvIGludGVnZXJzIFEgYW5kIE0gYXJlIGdpdmVuLiBRIGlzIHRoZSBudW1iZXIgb2YgcXVlcmllcy48XC9wPlxyXG5cclxuPHA+SW4gZWFjaCBvZiBmb2xsb3dpbmcgUSBsaW5lcywgYW4gaW50ZWdlciBOLCByZXByZXNlbnRpbmcgdGhlIHF1ZXJ5IGlzIGdpdmVuLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIDEmbmJzcDsmbGU7IGkmbmJzcDsmbGU7IE4sIGluIHRoZSZuYnNwO2ktdGggbGluZSwgb3V0cHV0IHRoZSBhbnN3ZXIgb2YgdGhlIGktdGggcXVlcnkuIE5vdGUgdGhhdCB0aGUgYW5zd2VyIG9mIHRoZSBxdWVyeSBpcyBOLXRoIGVudHJ5IG9mIG5ldyBzZXF1ZW5jZSwgd2hlcmUgTiBpcyB0aGUgaW50ZWdlciBnaXZlbiBhcyBpbnB1dCBvZiBxdWVyeS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjImbmJzcDsmbGU7IE0mbmJzcDsmbGU7IDEsMDAwPFwvbGk+XHJcblx0PGxpPjEmbmJzcDsmbGU7IE4mbmJzcDsmbGU7IDEwPHN1cD4xNTxcL3N1cD48XC9saT5cclxuXHQ8bGk+MSZuYnNwOyZsZTsgUSZuYnNwOyZsZTsgMTAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn1d