문제
평화로운 삶을 살던 하이히는 어느 날 갑자기 바이비의 새로운 요세푸스 게임에 참가하게 되었다! 새로운 요세푸스 게임은 다음과 같이 진행된다.
- 게임이 시작하기 전, 양의 정수 $M$이 정해진다.
- 1ドル$번 참가자부터 $N$번 참가자까지 시계 방향으로 차례로 원을 그리며 앉는다.
- 시작할 때는 화살표를 $N$번 참가자를 가리키도록 놓는다.
- 이후 모든 사람이 탈락할 때까지 다음 과정을 반복한다.
- 1ドル$ 이상 $M$ 이하의 정수 $K$가 정해진다. 이 수는 이전과 같을 수도, 다를 수도 있다.
- 화살표를 시계 방향으로 $K$번 돌린다. 이때, 탈락한 참가자의 자리는 건너뛴다.
- 이후 화살표가 가리키는 참가자가 탈락한다. 이로 인해 화살표가 돌아가지는 않는다.
예로, 다음은 $N = 7,ドル $M = 10$일 때 가능한 새로운 요세푸스 게임의 진행 과정이다.
원래라면 어디에 있어야 탈락하지 않고 끝까지 남을 수 있을지 궁금해하는 것이 일반적이지만, 호기심에 가득 찬 하이히는 사람들이 탈락한 순서가 주어질 때 $K$가 최소 몇 번 달라졌는지 구해보기로 했다!
출력
첫째 줄에 게임이 진행되면서 $K$가 최소 몇 번 달라졌는지 출력한다. $K$를 처음 정하는 것은 $K$가 달라지는 것으로 세지 않는다.
W3sicHJvYmxlbV9pZCI6IjM0MTM0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiW1ldIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM2OTRcdWMxMzhcdWQ0NzhcdWMyYTQgXHViYjM4XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzYzlcdWQ2NTRcdWI4NWNcdWM2YjQgXHVjMGI2XHVjNzQ0IFx1YzBiNFx1YjM1OCBcdWQ1NThcdWM3NzRcdWQ3ODhcdWIyOTQgXHVjNWI0XHViMjkwIFx1YjBhMCBcdWFjMTFcdWM3OTBcdWFlMzAgXHViYzE0XHVjNzc0XHViZTQ0XHVjNzU4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM2OTRcdWMxMzhcdWQ0NzhcdWMyYTQgXHVhYzhjXHVjNzg0XHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQhIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM2OTRcdWMxMzhcdWQ0NzhcdWMyYTQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjODA0LCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4ICRNJFx1Yzc3NCBcdWM4MTVcdWQ1NzRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiQxJFx1YmM4OCBcdWNjMzhcdWFjMDBcdWM3OTBcdWJkODBcdWQxMzAgJE4kXHViYzg4IFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YWU0Y1x1YzljMCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWM2ZDBcdWM3NDQgXHVhZGY4XHViOWFjXHViYTcwIFx1YzU0OVx1YjI5NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMmRjXHVjNzkxXHVkNTYwIFx1YjU0Y1x1YjI5NCBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWI5N2MgJE4kXHViYzg4IFx1Y2MzOFx1YWMwMFx1Yzc5MFx1Yjk3YyBcdWFjMDBcdWI5YWNcdWQwYTRcdWIzYzRcdWI4NWQgXHViMTkzXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWQ2YzQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWQwYzhcdWI3N2RcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YjJlNFx1Yzc0YyBcdWFjZmNcdWM4MTVcdWM3NDQgXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT4kMSQgXHVjNzc0XHVjMGMxICRNJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4ICRLJFx1YWMwMCBcdWM4MTVcdWQ1NzRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWIyOTQgXHVjNzc0XHVjODA0XHVhY2ZjIFx1YWMxOVx1Yzc0NCBcdWMyMThcdWIzYzQsIFx1YjJlNFx1Yjk3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdFx0PGxpPlx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1Yjk3YyBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjICRLJFx1YmM4OCBcdWIzY2NcdWI5YjBcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVkMGM4XHViNzdkXHVkNTVjIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1Yzc1OCBcdWM3OTBcdWI5YWNcdWIyOTQgXHVhYzc0XHViMTA4XHViNmY0XHViMmU0LjxcL2xpPlxyXG5cdFx0PGxpPlx1Yzc3NFx1ZDZjNCBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWFjMDAgXHVhYzAwXHViOWFjXHVkMGE0XHViMjk0IFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YWMwMCBcdWQwYzhcdWI3N2RcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1Yjg1YyBcdWM3NzhcdWQ1NzQgXHVkNjU0XHVjMGI0XHVkNDVjXHVhYzAwIFx1YjNjY1x1YzU0NFx1YWMwMFx1YzljMFx1YjI5NCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNjA4XHViODVjLCBcdWIyZTRcdWM3NGNcdWM3NDAgJE4gPSA3JCwgJE0gPSAxMCRcdWM3N2MgXHViNTRjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjNjk0XHVjMTM4XHVkNDc4XHVjMmE0IFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWM5YzRcdWQ1ODkgXHVhY2ZjXHVjODE1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2UxOTNhZmM2LTM2NTYtNGY2OS1hZTI0LTZkNWVkMDg4MzBiYVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNzk3cHg7IG1heC13aWR0aDogMTAwJVwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2ZDBcdWI3OThcdWI3N2NcdWJhNzQgXHVjNWI0XHViNTE0XHVjNWQwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQwYzhcdWI3N2RcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YjA1ZFx1YWU0Y1x1YzljMCBcdWIwYThcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1Yzc3Y1x1YmMxOFx1YzgwMVx1Yzc3NFx1YzljMFx1YjljYywgXHVkNjM4XHVhZTMwXHVjMmVjXHVjNWQwIFx1YWMwMFx1YjRkZCBcdWNjMmMgXHVkNTU4XHVjNzc0XHVkNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWQwYzhcdWI3N2RcdWQ1NWMgXHVjMjFjXHVjMTFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgJEskXHVhYzAwIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYzg4IFx1YjJlY1x1Yjc3Y1x1Yzg0Y1x1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0ITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVjMjE4ICROJFx1YWNmYyBcdWM4MTVcdWQ1NzRcdWM5YzBcdWIyOTQgXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMiAkTSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMVxcbGUgTlxcbGUgMjAwXFwsIDAwMDskICQxXFxsZSBNXFxsZSAxMF45KSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4ICRBXzEsQV8yLFxcbGRvdHMgLEFfTiRcdWM3NzQgXHVkMGM4XHViNzdkXHVkNTVjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxXFxsZSBBX2lcXGxlIE47JCAkQV9pXFxuZXEgQV9qXFx0ZXh0eyBpZmYgfSBpXFxuZXEgaikkPFwvcD5cclxuXHJcbjxwPlx1YzJlNFx1YzgxY1x1Yjg1YyBcdWNjMzhcdWFjMDBcdWM3OTBcdWFjMDAgXHVkNTc0XHViMmY5IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWQwYzhcdWI3N2RcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3ODVcdWI4MjVcdWI5Y2NcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YzljNFx1ZDU4OVx1YjQxOFx1YmE3NFx1YzExYyAkSyRcdWFjMDAgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHViMmVjXHViNzdjXHVjODRjXHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJEskXHViOTdjIFx1Y2M5OFx1Yzc0YyBcdWM4MTVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwICRLJFx1YWMwMCBcdWIyZWNcdWI3N2NcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YzEzOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzQxMzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJbWV0gWWV0IEFub3RoZXIgSm9zZXBodXMgUHJvYmxlbSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIG1pZHN0IG9mIGhpcyBwZWFjZWZ1bCBsaWZlLCBIaWh5ZSB3YXMgc3VkZGVubHkgZm9yY2VkIHRvIHBhcnRpY2lwYXRlIGluIEJpYnllJnJzcXVvO3MgeWV0IGFub3RoZXIgSm9zZXBodXMgZ2FtZSEgVGhpcyBuZXcgSm9zZXBodXMgZ2FtZSZyc3F1bztzIHJ1bGVzIGFyZSBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkJlZm9yZSB0aGUgZ2FtZSBiZWdpbnMsIGEgcGFyYW1ldGVyICRNJCBpcyBzZXQgdG8gYSBwb3NpdGl2ZSBpbnRlZ2VyIHZhbHVlLjxcL2xpPlxyXG5cdDxsaT5UaGUgcGFydGljaXBhbnRzIHNpdCBpbiBhIGNpcmNsZSBpbiBhIGNsb2Nrd2lzZSBvcmRlciBzdGFydGluZyBmcm9tIHBhcnRpY2lwYW50IG51bWJlciAkMSQgdG8gcGFydGljaXBhbnQgbnVtYmVyICROJC48XC9saT5cclxuXHQ8bGk+V2hlbiB0aGUgZ2FtZSBzdGFydHMsIHRoZSBhcnJvdyBpcyBzZXQgdG8gcG9pbnQgYXQgcGFydGljaXBhbnQgJE4kLjxcL2xpPlxyXG5cdDxsaT5UaGVuLCB0aGUgZm9sbG93aW5nIHByb2Nlc3MgaXMgcmVwZWF0ZWQgdW50aWwgYWxsIHBhcnRpY2lwYW50cyBhcmUgZWxpbWluYXRlZC5cclxuXHQ8dWw+XHJcblx0XHQ8bGk+QW4gaW50ZWdlciAkSyQgZ3JlYXRlciB0aGFuIG9yIGVxdWFsIHRvICQxJCBhbmQgbGVzcyB0aGFuIG9yIGVxdWFsIHRvICRNJCBpcyBjaG9zZW4uIFRoaXMgdmFsdWUgbWF5IG9yIG1heSBub3QgYmUgZGlmZmVyIGJldHdlZW4gaXRlcmF0aW9ucy48XC9saT5cclxuXHRcdDxsaT5UaGUgYXJyb3cgaXMgcm90YXRlZCBjbG9ja3dpc2UgJEskIHRpbWVzLiBFbGltaW5hdGVkIHBhcnRpY2lwYW50cyZyc3F1bzsgc2VhdHMgYXJlIHNraXBwZWQuPFwvbGk+XHJcblx0XHQ8bGk+VGhlIHBhcnRpY2lwYW50IHRoZSBhcnJvdyBwb2ludHMgYXQgaXMgZWxpbWluYXRlZC4gVGhpcyBhY3Rpb24gZG9lcyBub3QgcmVzdWx0IGluIHJvdGF0aW5nIHRoZSBhcnJvdy48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIGZvbGxvd2luZyBpcyBhbiBleGFtcGxlIG9mIGEgcG9zc2libGUgc2NlbmFyaW8gZm9yIHRoaXMgbmV3IEpvc2VwaHVzIGdhbWUgd2hlbiAkTiA9IDckLCBhbmQgJE0gPSAxMCQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZTE5M2FmYzYtMzY1Ni00ZjY5LWFlMjQtNmQ1ZWQwODgzMGJhXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA3OTdweDsgbWF4LXdpZHRoOiAxMDAlXCIgXC8+PFwvcD5cclxuXHJcbjxwPk5vcm1hbGx5LCBvbmUgd291bGQgYmUgY3VyaW91cyB3aGVyZSB0aGV5IHNob3VsZCBiZSBpbiBvcmRlciB0byBzdXJ2aXZlIHRpbGwgdGhlIGVuZC4gSG93ZXZlciwgSGloeWUgd2FudHMgdG8gZmluZCBvdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHRpbWVzICRLJCBjb3VsZCBoYXZlIGJlZW4gY2hhbmdlZCBiZXR3ZWVuIGl0ZXJhdGlvbnMgZ2l2ZW4gdGhlIG9yZGVyIGluIHdoaWNoIHRoZSBwbGF5ZXJzIHdlcmUgZWxpbWluYXRlZCE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgcGFydGljaXBhbnRzICROJCwgYW5kIHRoZSBtYXhpbXVtIHZhbHVlIHdoaWNoIGNhbiBiZSBjaG9zZW4gJE0kLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gJCgxXFxsZSBOXFxsZSAyMDBcXCwgMDAwOyQgJDFcXGxlIE1cXGxlIDEwXjkpJDxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIG51bWJlcnMgYmVsb25naW5nIHRvIHRoZSBwYXJ0aWNpcGFudHMgJEFfMSxBXzIsXFxsZG90cyAsQV9OJCBpbiB0aGUgb3JkZXIgdGhlIHBhcnRpY2lwYW50cyB3ZXJlIGVsaW1pbmF0ZWQuICQoMVxcbGUgQV9pXFxsZSBOOyQgJEFfaVxcbmVxIEFfalxcdGV4dHsgaWZmIH0gaVxcbmVxIGopJDxcL3A+XHJcblxyXG48cD5Pbmx5IGlucHV0IGRhdGEgdGhhdCBhbGxvd3MgcGFydGljaXBhbnRzIHRvIGJlIGVsaW1pbmF0ZWQgaW4gdGhlIGdpdmVuIG9yZGVyIGlzIHByb3ZpZGVkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBtaW5pbXVtIG51bWJlciBvZiB0aW1lcyAkSyQgY291bGQgaGF2ZSBiZWVuIGNoYW5nZWQgYmV0d2VlbiBpdGVyYXRpb25zLiBDaG9vc2luZyAkSyQgZm9yIHRoZSBmaXJzdCB0aW1lIHdoZW4gdGhlIGdhbWUgc3RhcnRzIGRvZXMgbm90IGNvdW50IGFzICRLJCBjaGFuZ2luZy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d