시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 199 46 35 28.000%

문제

작곡가 철수는 피보나치 수열을 이용하여 만든 피아노 곡을 우연히 유튜브에서 보게 되었다. 피보나치 수열이란 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+bjxcL3N1Yj4gKFx1YmFhOFx1YjRlMCBuICZnZTsgMVx1YzVkMCBcdWIzMDBcdWQ1NzQpXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjZTFcdWM3NDAgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjNzkwXHViOWFjIFx1YzIyYlx1Yzc5MFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVhYzc0XHViYzE4XHVjNzQ0IFx1YjIwY1x1YjdlY1x1YzExYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM4NGNcdWIyZTQuPGJyIFwvPlxyXG5cdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNWY0XHVjNzU4IFx1Y2NhYiA4XHVhYzFjIFx1ZDU2ZFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHVhY2UxXHVjNzQ0IFx1YjljY1x1YjRlMFx1YjJlNFx1YmE3NCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjNzRcdWJjMThcdWM3NDQgXHVjZDFkIDEwXHViYzg4IFx1YjIwNFx1Yjk3NFx1YWM4YyBcdWI0MjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj4xICZyYXJyOyAxICZyYXJyOyAyICZyYXJyOyAzICZyYXJyOyA1ICZyYXJyOyA4ICZyYXJyOyAxICZyYXJyOyAzICZyYXJyOyAyICZyYXJyOyAxPFwvcD5cclxuXHJcbjxwPlx1Y2NhMFx1YzIxOFx1YjI5NCBcdWM3OTBcdWMyZTBcdWIzYzQgXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHViY2Y0XHVhZTMwXHViODVjIFx1YjljOFx1Yzc0Y1x1YmEzOVx1YzVjOFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NDAgXHViMTA4XHViYjM0IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWM5OWRcdWFjMDBcdWQ1NzRcdWMxMWMsIFx1YjM2N1x1YzE0OFx1YzVkMCBcdWM1N2RcdWQ1NWMgXHVjY2EwXHVjMjE4XHVhYzAwIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YWUzMFx1YzVkMFx1YjI5NCBcdWM1YjRcdWI4MjRcdWM2ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1Yjc5OFx1YzExYyBcdWNjYTBcdWMyMThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzg3MFx1YWUwOCBcdWJjMTRcdWFmYjhcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWNjYTBcdWMyMThcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzIxOCBNXHVjNzQ0IFx1YzgxNVx1ZDU1YyBcdWQ2YzQsIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzAxIFx1ZDU2ZFx1Yzc0NCBNXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI4NWMgPGVtPlx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWMyMThcdWM1ZjQ8XC9lbT4gXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCwgXHVhZGY4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjNzkwXHViOWFjIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWMwYzggXHVkNTNjXHVjNTQ0XHViMTc4IFx1YWNlMVx1Yzc0NCBcdWM0ZjBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IE09MTBcdWM3N2MgXHViNTRjLCA8ZW0+XHVjMGM4XHViODVjXHVjNmI0IFx1YzIxOFx1YzVmNCZuYnNwOzxcL2VtPlx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj57MSwgMSwgMiwgMywgNSwgOCwgMywgMSwgJmhlbGxpcDt9PFwvcD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYyBcdWNjYTBcdWMyMThcdWIyOTQgMSAmcmFycjsxICZyYXJyOyAyICZyYXJyOyAzICZyYXJyOyA1ICZyYXJyOyA4ICZyYXJyOyAzICZyYXJyOyAxICZyYXJyOyA0Jm5ic3A7JnJhcnI7ICZoZWxsaXA7IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjNzRcdWJjMThcdWM3NDQgXHViMjA0XHViOTc0XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjLCBcdWNjYTBcdWMyMThcdWIyOTQgXHVjNWI0XHViNWE0IE5cdWM1ZDAgXHViMzAwXHVkNTc0IE5cdWJjODhcdWM5ZjhcdWI4NWMgXHViMjA0XHViOTc0XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWFjNzRcdWJjMThcdWM3NTggXHViYzg4XHVkNjM4KGkuZS4gPGVtPlx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWMyMThcdWM1ZjQmbmJzcDs8XC9lbT5cdWM3NTggTlx1YmM4OFx1YzlmOCBcdWQ1NmQpXHVhYzAwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+UVx1YWMxY1x1Yzc1OCBOXHVjNzc0IFx1YzljOFx1Yzc1OFx1Yjg1YyZuYnNwO1x1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5YzhcdWM3NThcdWM1ZDAmbmJzcDtcdWIzMDBcdWQ1NzQgTlx1YmM4OFx1YzlmOFx1Yjg1YyBcdWIyMDRcdWI5NzRcdWFjOGMgXHViNDE4XHViMjk0IFx1YWM3NFx1YmMxOFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggUVx1YzY0MCBNXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzljOFx1Yzc1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQmbmJzcDtcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IE5cdWM1ZDAgXHViMzAwXHVkNTc0LCBOXHViYzg4XHVjOWY4XHViODVjIFx1YjIwNFx1Yjk3NFx1YWM4YyBcdWI0MThcdWIyOTQgXHVhYzc0XHViYzE4XHVjNzU4IFx1YmM4OFx1ZDYzOChcdWMwYzhcdWI4NWNcdWM2YjQgXHVjMjE4XHVjNWY0XHVjNzU4IDxlbT5OPFwvZW0+Jm5ic3A7XHViYzg4XHVjOWY4IFx1ZDU2ZClcdWI5N2MgXHVjNzg1XHViODI1XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDFkIFFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyZuYnNwOzEwPHN1cD4xNTxcL3N1cD48XC9saT5cclxuXHQ8bGk+MiAmbGU7IE0gJmxlOyAxLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgUSAmbGU7IDEwMCwwMDAmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE3ODQwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlib25hY2NpIHNvbmciLCJkZXNjcmlwdGlvbiI6IjxwPkVsc2EsIGEgY29tcG9zZXIsIGhhcHBlbmVkIHRvIGxpc3RlbiBhIHBpYW5vIHNvbmcgbWFkZSB1c2luZyB0aGUgRmlib25hY2NpIHNlcXVlbmNlLiBGaWJvbmFjY2kgc2VxdWVuY2Uge2Y8c3ViPm48XC9zdWI+fSBpcyBkZWZpbmVkIGJ5IGZvbGxvd2luZyByZWN1cnJlbmNlIHJlbGF0aW9uOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmY8c3ViPjE8XC9zdWI+Jm5ic3A7PSAxLCZuYnNwO2Y8c3ViPjI8XC9zdWI+Jm5ic3A7PSAxLDxcL2xpPlxyXG5cdDxsaT5hbmQgZm9yIGV2ZXJ5IG4mbmJzcDsmZ2U7IDEsJm5ic3A7ZjxzdWI+bisyPFwvc3ViPiZuYnNwOz0gZjxzdWI+bisxPFwvc3ViPiZuYnNwOysgZjxzdWI+bjxcL3N1Yj4uPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIHNvbmcgd2FzIG1hZGUgYnkgcHJlc3NpbmcgdGhlIGtleXMgY29ycmVzcG9uZGluZyZuYnNwO3RvIGVhY2ggZGlnaXQgaW4gdGhlIEZpYm9uYWNjaSBzZXF1ZW5jZS4gSWYgeW91IHVzZSB0aGUgZmlyc3QgZWlnaHQgZW50cmllcyBvZiB0aGUgRmlib25hY2NpIHNlcXVlbmNlIHRvIG1ha2UgYSBzb25nLCB5b3Ugd2lsbCBwcmVzcyB0aGUgMTAga2V5cyBpbiB0b3RhbCwgYXMgYmVsb3cuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjEgJnJhcnI7IDEgJnJhcnI7IDIgJnJhcnI7IDMgJnJhcnI7IDUgJnJhcnI7IDggJnJhcnI7IDEgJnJhcnI7IDMgJnJhcnI7IDIgJnJhcnI7IDE8XC9wPlxyXG5cclxuPHA+RWxzYSB0cmllZCZuYnNwO3RvIGNvbXBvc2UgcGlhbm8gc29uZyB1c2luZyB0aGlzIG1ldGhvZC4mbmJzcDtUaGUgRmlib25hY2NpIHNlcXVlbmNlLCBob3dldmVyLCBpbmNyZWFzZWQgc28gcXVpY2tseSB0aGF0IGl0IHdhcyBkaWZmaWN1bHQgdG8gY2FsY3VsYXRlLjxcL3A+XHJcblxyXG48cD5TbyBFbHNhJm5ic3A7ZGVjaWRlZCB0byBjaGFuZ2UgdGhlIG1ldGhvZCBhIGxpdHRsZS4gU2hlIGNyZWF0ZWQgYSBuZXcgc2VxdWVuY2Ugd2l0aCB0aGUgcmVtYWluZGVyIG9mIHRoZSBGaWJvbmFjY2kgc2VxdWVuY2UsIGRpdmlkZWQgYnkgc29tZSBwb3NpdGl2ZSBpbnRlZ2VyIE0uIFNoZSYjMzk7cyBnb2luZyB0byBjb21wb3NlIGEgbmV3IHBpYW5vIHNvbmcgdXNpbmcgZWFjaCBkaWdpdCBvZiB0aGUgbmV3IHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgTSA9IDEwLCBuZXcgc2VxdWVuY2UgaXM6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPnsxLCAxLCAyLCAzLCA1LCA4LCAzLCAxLCAuLi59LDxcL3A+XHJcblxyXG48cD50aGVyZWZvcmUsIHNoZSZuYnNwO3dpbGwgcHJlc3Mga2V5IGluIG9yZGVyIG9mJm5ic3A7MSAmcmFycjsgMSAmcmFycjsgMiAmcmFycjsgMyAmcmFycjsgNSAmcmFycjsgOCAmcmFycjsgMyAmcmFycjsgMSAmcmFycjsgNCZuYnNwOyZyYXJyOyAmaGVsbGlwOyAuPFwvcD5cclxuXHJcbjxwPkZvciBmaXhlZCBNLCBzaGUgd2FudHMgdG8gZGVhbCB3aXRoIGZvbGxvd2luZyBxdWVyeTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5mb3IgZ2l2ZW4gTiwgcHJpbnQgTi10aCBlbnRyeSBvZiB0aGUgbmV3IHNlcXVlbmNlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlNoZSBuZWVkcyB5b3VyIGhlbHAgdG8gZGVhbCB3aXRoIHF1ZXJpZXMuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGRlYWxzIHdpdGggcXVlcmllcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lLCB0d28gaW50ZWdlcnMgUSBhbmQgTSBhcmUgZ2l2ZW4uIFEgaXMgdGhlIG51bWJlciBvZiBxdWVyaWVzLjxcL3A+XHJcblxyXG48cD5JbiBlYWNoIG9mIGZvbGxvd2luZyBRIGxpbmVzLCBhbiBpbnRlZ2VyIE4sIHJlcHJlc2VudGluZyB0aGUgcXVlcnkgaXMgZ2l2ZW4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggMSZuYnNwOyZsZTsgaSZuYnNwOyZsZTsgTiwgaW4gdGhlJm5ic3A7aS10aCBsaW5lLCBvdXRwdXQgdGhlIGFuc3dlciBvZiB0aGUgaS10aCBxdWVyeS4gTm90ZSB0aGF0IHRoZSBhbnN3ZXIgb2YgdGhlIHF1ZXJ5IGlzIE4tdGggZW50cnkgb2YgbmV3IHNlcXVlbmNlLCB3aGVyZSBOIGlzIHRoZSBpbnRlZ2VyIGdpdmVuIGFzIGlucHV0IG9mIHF1ZXJ5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4yJm5ic3A7JmxlOyBNJm5ic3A7JmxlOyAxLDAwMDxcL2xpPlxyXG5cdDxsaT4xJm5ic3A7JmxlOyBOJm5ic3A7JmxlOyAxMDxzdXA+MTU8XC9zdXA+PFwvbGk+XHJcblx0PGxpPjEmbmJzcDsmbGU7IFEmbmJzcDsmbGU7IDEwMCwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==