시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 441 190 158 47.164%

문제

집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다.

  1. 2 3 5
  2. 2 5 3
  3. 3 2 5
  4. 3 5 2
  5. 5 2 3
  6. 5 3 2

각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다.

{b,e,i,n}으로 만들 수 있는 순열은 다음과 같다.

  1. b e i n
  2. b e n i
  3. b i e n
  4. b i n e
  5. b n e i
  6. b n i e
  7. e b i n
  8. e b n i
  9. e i b n
  10. e i n b
  11. e n b i 
  12. e n i b
  13. i b e n
  14. i b n e
  15. i e b n
  16. i e n b
  17. i n b e
  18. i n e b
  19. n b e i
  20. n b i e
  21. n e b i
  22. n e i b
  23. n i b e
  24. n i e b

서로 다른 숫자와 문자로 이루어진 집합과 위치가 주어졌을 때, 그 집합의 순열 중 주어진 위치의 순열을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어지며, 이 값은 3,628,800보다 작거나 같은 자연수이다.

출력

각각의 테스트 케이스마다, 입력으로 주어진 위치에 해당하는 순열을 공백없이 출력한다. 만약, 해당하는 순열이 없는 경우에는 "No permutation"을 출력한다.

예제 입력 1

235 4
bein 20
123456 700
mnpqr 130
tuvwxyz 4000

예제 출력 1

235 4 = 352
bein 20 = nbie
123456 700 = 651342
mnpqr 130 = No permutation
tuvwxyz 4000 = ywuxvzt
W3sicHJvYmxlbV9pZCI6Ijk3NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM3NzRcdWI3ODAgXHVjOWQxXHVkNTY5XHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNmQwXHVjMThjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCB7MiwzLDV9XHVjNzU4IFx1YzIxY1x1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPjIgMyA1PFwvbGk+XHJcblx0PGxpPjIgNSAzPFwvbGk+XHJcblx0PGxpPjMgMiA1PFwvbGk+XHJcblx0PGxpPjMgNSAyPFwvbGk+XHJcblx0PGxpPjUgMiAzPFwvbGk+XHJcblx0PGxpPjUgMyAyPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YzIxY1x1YzVmNFx1Yzc0MCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM3NDAgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzRmMFx1YzVlY1x1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjOTg5LCAzIDUgMlx1YjI5NCBcdWM3MDRcdWNlNTggNFx1YzVkMCBcdWM3ODhcdWFjZTAsIDUgMyAyXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWM3MDRcdWNlNThcdWM3NzggNlx1YzVkMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPntiLGUsaSxufVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5iIGUgaSBuPFwvbGk+XHJcblx0PGxpPmIgZSBuIGk8XC9saT5cclxuXHQ8bGk+YiBpIGUgbjxcL2xpPlxyXG5cdDxsaT5iIGkgbiBlPFwvbGk+XHJcblx0PGxpPmIgbiBlIGk8XC9saT5cclxuXHQ8bGk+YiBuIGkgZTxcL2xpPlxyXG5cdDxsaT5lIGIgaSBuPFwvbGk+XHJcblx0PGxpPmUgYiBuIGk8XC9saT5cclxuXHQ8bGk+ZSBpIGIgbjxcL2xpPlxyXG5cdDxsaT5lIGkgbiBiPFwvbGk+XHJcblx0PGxpPmUgbiBiIGkmbmJzcDs8XC9saT5cclxuXHQ8bGk+ZSBuIGkgYjxcL2xpPlxyXG5cdDxsaT5pIGIgZSBuPFwvbGk+XHJcblx0PGxpPmkgYiBuIGU8XC9saT5cclxuXHQ8bGk+aSBlIGIgbjxcL2xpPlxyXG5cdDxsaT5pIGUgbiBiPFwvbGk+XHJcblx0PGxpPmkgbiBiIGU8XC9saT5cclxuXHQ8bGk+aSBuIGUgYjxcL2xpPlxyXG5cdDxsaT5uIGIgZSBpPFwvbGk+XHJcblx0PGxpPm4gYiBpIGU8XC9saT5cclxuXHQ8bGk+biBlIGIgaTxcL2xpPlxyXG5cdDxsaT5uIGUgaSBiPFwvbGk+XHJcblx0PGxpPm4gaSBiIGU8XC9saT5cclxuXHQ8bGk+biBpIGUgYjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMjJiXHVjNzkwXHVjNjQwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjOWQxXHVkNTY5XHVhY2ZjIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjOWQxXHVkNTY5XHVjNzU4IFx1YzIxY1x1YzVmNCBcdWM5MTEgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMyMmJcdWM3OTBcdWM2NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTBcdWM3NzRcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVjMGFjXHVjODA0XHVjMjFjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzQgXHVhYzEyXHVjNzQwIDMsNjI4LDgwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWFjZjVcdWJjMzFcdWM1YzZcdWM3NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtObyBwZXJtdXRhdGlvbiZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTc0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBlcm11dGF0aW9ucyIsImRlc2NyaXB0aW9uIjoiPHA+QSBwZXJtdXRhdGlvbiBvZiBhIHNldCBpcyBqdXN0IGFuIGFycmFuZ2VtZW50IG9mIGFsbCB0aGUgZGlzdGluY3QgZWxlbWVudHMgb2YgdGhlIHNldC4gRm9yIGV4YW1wbGUsIGFsbCB0aGUgcGVybXV0YXRpb25zIG9mIHRoZSBzZXQgeyAyLCAzLCA1fSBhcmUgZ2l2ZW4gYmVsb3cuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+MiAzIDU8XC9saT5cclxuXHQ8bGk+MiA1IDM8XC9saT5cclxuXHQ8bGk+MyAyIDU8XC9saT5cclxuXHQ8bGk+MyA1IDI8XC9saT5cclxuXHQ8bGk+NSAyIDM8XC9saT5cclxuXHQ8bGk+NSAzIDI8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5JZiBlYWNoIHBlcm11dGF0aW9uIGlzIHJlZ2FyZGVkIGFzIGEgbnVtYmVyLCB0aGUgcGVybXV0YXRpb25zIGluIHRoZSBhYm92ZSBsaXN0IGFyZSBhcnJhbmdlZCBpbiBpbmNyZWFzaW5nIG1hZ25pdHVkZS4gVGhlIHBlcm11dGF0aW9ucyBhcmUgc2FpZCB0byBiZSBsaXN0ZWQgaW4gbGV4aWNvZ3JhcGhpYyBvcmRlci4gTm90ZSB0aGF0IHRoZSBwZXJtdXRhdGlvbiBpbiBwb3NpdGlvbiA0IGlzIDMgNSAyIHdoaWxlIHRoZSBwZXJtdXRhdGlvbiBpbiB0aGUgbGFzdCBwb3NpdGlvbiwgd2hpY2ggaXMgNiwgaXMgNSAzIDIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBhbm90aGVyIGV4YW1wbGUsIGFsbCB0aGUgcGVybXV0YXRpb25zIG9mIHRoZSBzZXQgeyBiLCBlLCBpLCBuIH0gYXJlIGxpc3RlZCBpbiB0YWJ1bGFyIGZvcm0gYmVsb3cuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+YiBlIGkgbjxcL2xpPlxyXG5cdDxsaT5iIGUgbiBpPFwvbGk+XHJcblx0PGxpPmIgaSBlIG48XC9saT5cclxuXHQ8bGk+YiBpIG4gZTxcL2xpPlxyXG5cdDxsaT5iIG4gZSBpPFwvbGk+XHJcblx0PGxpPmIgbiBpIGU8XC9saT5cclxuXHQ8bGk+ZSBiIGkgbjxcL2xpPlxyXG5cdDxsaT5lIGIgbiBpPFwvbGk+XHJcblx0PGxpPmUgaSBiIG48XC9saT5cclxuXHQ8bGk+ZSBpIG4gYjxcL2xpPlxyXG5cdDxsaT5lIG4gYiBpJm5ic3A7PFwvbGk+XHJcblx0PGxpPmUgbiBpIGI8XC9saT5cclxuXHQ8bGk+aSBiIGUgbjxcL2xpPlxyXG5cdDxsaT5pIGIgbiBlPFwvbGk+XHJcblx0PGxpPmkgZSBiIG48XC9saT5cclxuXHQ8bGk+aSBlIG4gYjxcL2xpPlxyXG5cdDxsaT5pIG4gYiBlPFwvbGk+XHJcblx0PGxpPmkgbiBlIGI8XC9saT5cclxuXHQ8bGk+biBiIGUgaTxcL2xpPlxyXG5cdDxsaT5uIGIgaSBlPFwvbGk+XHJcblx0PGxpPm4gZSBiIGk8XC9saT5cclxuXHQ8bGk+biBlIGkgYjxcL2xpPlxyXG5cdDxsaT5uIGkgYiBlPFwvbGk+XHJcblx0PGxpPm4gaSBlIGI8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UaGUgcGVybXV0YXRpb25zIGhlcmUgYXJlIGxpc3RlZCBpbiBkaWN0aW9uYXJ5IG9yZGVyLCB3aGljaCBpcyBqdXN0IGFub3RoZXIgd2F5IG9mIGRlc2NyaWJpbmcgbGV4aWNvZ3JhcGhpYyBvcmRlci4gTm90ZSB0aGF0IHRoZSBwZXJtdXRhdGlvbiBpbiBwb3NpdGlvbiA0IGlzIGIgaSBuIGUgd2hpbGUgdGhlIHBlcm11dGF0aW9uIGluIHBvc2l0aW9uIDIwIGlzIG4gYiBpIGUuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgc2V0IG9mIGRpc3RpbmN0IGRpZ2l0cyBvciBsZXR0ZXJzLCB5b3VyIHRhc2sgaXMgdG8gZGV0ZXJtaW5lIHRoZSBwZXJtdXRhdGlvbiBvZiB0aGUgc2V0IGluIGEgZ2l2ZW4gcG9zaXRpb24gd2hlbiB0aGUgcGVybXV0YXRpb25zIGFyZSBhc3N1bWVkIHRvIGJlIGxpc3RlZCBpbiBsZXhpY29ncmFwaGljIG9yZGVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG9uZSBvciBtb3JlIGlucHV0IGxpbmVzLiBFYWNoIGlucHV0IGxpbmUgY29uc2lzdHMgb2YgYSBzdHJpbmcgdGhhdCBpcyBjb21wb3NlZCBlaXRoZXIgZW50aXJlbHkgb2YgZGlzdGluY3QgbGV0dGVycyBvciBlbnRpcmVseSBvZiBkaXN0aW5jdCBkaWdpdHMuIFRoZSBsZXR0ZXJzIG9yIGRpZ2l0cyBhcmUgYWxyZWFkeSBhcnJhbmdlZCBpbiBvcmRlci4gVGhlIGxlbmd0aCBvZiB0aGUgc3RyaW5nIGlzIGF0IG1vc3QgMTAgYW5kIGlzIGZvbGxvd2VkIGJ5IGEgc3BhY2UgYW5kIGEgbnVtYmVyIHRoYXQgZ2l2ZXMgdGhlIHBvc2l0aW9uIG9mIHRoZSByZXF1aXJlZCBwZXJtdXRhdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGNvbnNpc3RzIG9mIG9uZSBvciBtb3JlIGxpbmVzLiBFYWNoIG91dHB1dCBsaW5lIGNvbnNpc3RzIG9mIHRoZSBnaXZlbiBpbnB1dCBmb2xsb3dlZCBieSB0aGUgZXF1YWwgc2lnbiBhbmQgZm9sbG93ZWQgYnkgdGhlIHBlcm11dGF0aW9uIGluIHRoZSByZXF1aXJlZCBwb3NpdGlvbi4gSWYgdGhlIGdpdmVuIHBvc2l0aW9uIGlzIGJleW9uZCB0aGUgdG90YWwgbnVtYmVyIG9mIHBlcm11dGF0aW9ucywgdGhlbiB0aGUgb3V0cHV0IHNob3VsZCBpbmRpY2F0ZSAmbGRxdW87Tm8gcGVybXV0YXRpb24mcmRxdW87LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==