시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 327 151 124 52.542%

문제

집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {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이다. 또한, 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어진다.

출력

각각의 테스트 케이스마다, 입력으로 주어진 위치에 해당하는 순열을 공백없이 출력한다. 만약, 해당하는 순열이 없는 경우에는 "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+biBpIGUgYjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMjJiXHVjNzkwXHVjNjQwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjOWQxXHVkNTY5XHVhY2ZjIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjOWQxXHVkNTY5XHVjNzU4IFx1YzIxY1x1YzVmNCBcdWM5MTEgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMyMmJcdWM3OTBcdWM2NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTBcdWM3NzRcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVjMGFjXHVjODA0XHVjMjFjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzVjNlx1Yzc3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O05vIHBlcm11dGF0aW9uJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NzQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGVybXV0YXRpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5BIHBlcm11dGF0aW9uIG9mIGEgc2V0IGlzIGp1c3QgYW4gYXJyYW5nZW1lbnQgb2YgYWxsIHRoZSBkaXN0aW5jdCBlbGVtZW50cyBvZiB0aGUgc2V0LiBGb3IgZXhhbXBsZSwgYWxsIHRoZSBwZXJtdXRhdGlvbnMgb2YgdGhlIHNldCB7IDIsIDMsIDV9IGFyZSBnaXZlbiBiZWxvdy48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT4yIDMgNTxcL2xpPlxyXG5cdDxsaT4yIDUgMzxcL2xpPlxyXG5cdDxsaT4zIDIgNTxcL2xpPlxyXG5cdDxsaT4zIDUgMjxcL2xpPlxyXG5cdDxsaT41IDIgMzxcL2xpPlxyXG5cdDxsaT41IDMgMjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPklmIGVhY2ggcGVybXV0YXRpb24gaXMgcmVnYXJkZWQgYXMgYSBudW1iZXIsIHRoZSBwZXJtdXRhdGlvbnMgaW4gdGhlIGFib3ZlIGxpc3QgYXJlIGFycmFuZ2VkIGluIGluY3JlYXNpbmcgbWFnbml0dWRlLiBUaGUgcGVybXV0YXRpb25zIGFyZSBzYWlkIHRvIGJlIGxpc3RlZCBpbiBsZXhpY29ncmFwaGljIG9yZGVyLiBOb3RlIHRoYXQgdGhlIHBlcm11dGF0aW9uIGluIHBvc2l0aW9uIDQgaXMgMyA1IDIgd2hpbGUgdGhlIHBlcm11dGF0aW9uIGluIHRoZSBsYXN0IHBvc2l0aW9uLCB3aGljaCBpcyA2LCBpcyA1IDMgMi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGFub3RoZXIgZXhhbXBsZSwgYWxsIHRoZSBwZXJtdXRhdGlvbnMgb2YgdGhlIHNldCB7IGIsIGUsIGksIG4gfSBhcmUgbGlzdGVkIGluIHRhYnVsYXIgZm9ybSBiZWxvdy48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5iIGUgaSBuPFwvbGk+XHJcblx0PGxpPmIgZSBuIGk8XC9saT5cclxuXHQ8bGk+YiBpIGUgbjxcL2xpPlxyXG5cdDxsaT5iIGkgbiBlPFwvbGk+XHJcblx0PGxpPmIgbiBlIGk8XC9saT5cclxuXHQ8bGk+YiBuIGkgZTxcL2xpPlxyXG5cdDxsaT5lIGIgaSBuPFwvbGk+XHJcblx0PGxpPmUgYiBuIGk8XC9saT5cclxuXHQ8bGk+ZSBpIGIgbjxcL2xpPlxyXG5cdDxsaT5lIGkgbiBiPFwvbGk+XHJcblx0PGxpPmUgbiBiIGkmbmJzcDs8XC9saT5cclxuXHQ8bGk+ZSBuIGkgYjxcL2xpPlxyXG5cdDxsaT5pIGIgZSBuPFwvbGk+XHJcblx0PGxpPmkgYiBuIGU8XC9saT5cclxuXHQ8bGk+aSBlIGIgbjxcL2xpPlxyXG5cdDxsaT5pIGUgbiBiPFwvbGk+XHJcblx0PGxpPmkgbiBiIGU8XC9saT5cclxuXHQ8bGk+aSBuIGUgYjxcL2xpPlxyXG5cdDxsaT5uIGIgZSBpPFwvbGk+XHJcblx0PGxpPm4gYiBpIGU8XC9saT5cclxuXHQ8bGk+biBlIGIgaTxcL2xpPlxyXG5cdDxsaT5uIGUgaSBiPFwvbGk+XHJcblx0PGxpPm4gaSBiIGU8XC9saT5cclxuXHQ8bGk+biBpIGUgYjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlRoZSBwZXJtdXRhdGlvbnMgaGVyZSBhcmUgbGlzdGVkIGluIGRpY3Rpb25hcnkgb3JkZXIsIHdoaWNoIGlzIGp1c3QgYW5vdGhlciB3YXkgb2YgZGVzY3JpYmluZyBsZXhpY29ncmFwaGljIG9yZGVyLiBOb3RlIHRoYXQgdGhlIHBlcm11dGF0aW9uIGluIHBvc2l0aW9uIDQgaXMgYiBpIG4gZSB3aGlsZSB0aGUgcGVybXV0YXRpb24gaW4gcG9zaXRpb24gMjAgaXMgbiBiIGkgZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBzZXQgb2YgZGlzdGluY3QgZGlnaXRzIG9yIGxldHRlcnMsIHlvdXIgdGFzayBpcyB0byBkZXRlcm1pbmUgdGhlIHBlcm11dGF0aW9uIG9mIHRoZSBzZXQgaW4gYSBnaXZlbiBwb3NpdGlvbiB3aGVuIHRoZSBwZXJtdXRhdGlvbnMgYXJlIGFzc3VtZWQgdG8gYmUgbGlzdGVkIGluIGxleGljb2dyYXBoaWMgb3JkZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Ygb25lIG9yIG1vcmUgaW5wdXQgbGluZXMuIEVhY2ggaW5wdXQgbGluZSBjb25zaXN0cyBvZiBhIHN0cmluZyB0aGF0IGlzIGNvbXBvc2VkIGVpdGhlciBlbnRpcmVseSBvZiBkaXN0aW5jdCBsZXR0ZXJzIG9yIGVudGlyZWx5IG9mIGRpc3RpbmN0IGRpZ2l0cy4gVGhlIGxldHRlcnMgb3IgZGlnaXRzIGFyZSBhbHJlYWR5IGFycmFuZ2VkIGluIG9yZGVyLiBUaGUgbGVuZ3RoIG9mIHRoZSBzdHJpbmcgaXMgYXQgbW9zdCAxMCBhbmQgaXMgZm9sbG93ZWQgYnkgYSBzcGFjZSBhbmQgYSBudW1iZXIgdGhhdCBnaXZlcyB0aGUgcG9zaXRpb24gb2YgdGhlIHJlcXVpcmVkIHBlcm11dGF0aW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgY29uc2lzdHMgb2Ygb25lIG9yIG1vcmUgbGluZXMuIEVhY2ggb3V0cHV0IGxpbmUgY29uc2lzdHMgb2YgdGhlIGdpdmVuIGlucHV0IGZvbGxvd2VkIGJ5IHRoZSBlcXVhbCBzaWduIGFuZCBmb2xsb3dlZCBieSB0aGUgcGVybXV0YXRpb24gaW4gdGhlIHJlcXVpcmVkIHBvc2l0aW9uLiBJZiB0aGUgZ2l2ZW4gcG9zaXRpb24gaXMgYmV5b25kIHRoZSB0b3RhbCBudW1iZXIgb2YgcGVybXV0YXRpb25zLCB0aGVuIHRoZSBvdXRwdXQgc2hvdWxkIGluZGljYXRlICZsZHF1bztObyBwZXJtdXRhdGlvbiZyZHF1bzsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d