시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 235 75 59 48.760%

문제

세 소수 p1, p2, p3을 이용해서 해밍 수열 H(p1, p2, p3), i = 1... 을 정의할 수 있다.

해밍 수열 H(p1, p2, p3)은 소인수가 p1, p2, p3로만 이루어진 자연수의 오름 차순 목록이다.

예를 들어, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, ... 이고, 5번째 수는 6이다.

입력

첫째 줄에 p1, p2, p3, i가 주어진다. 네 정수는 1018보다 작다.

출력

H(p1, p2, p3)의 i번째 수를 출력한다. 출력하는 수는 1018보다 작다.

예제 입력 1

7 13 19 100

예제 출력 1

26590291
W3sicHJvYmxlbV9pZCI6Ijc4NjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NzRcdWJjMGQgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzggXHVjMThjXHVjMjE4IHA8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgcDxzdWI+MzxcL3N1Yj5cdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDU3NFx1YmMwZCBcdWMyMThcdWM1ZjQgSChwPHN1Yj4xPFwvc3ViPiwgcDxzdWI+MjxcL3N1Yj4sIHA8c3ViPjM8XC9zdWI+KSwgaSA9IDEuLi4gXHVjNzQ0IFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NzRcdWJjMGQgXHVjMjE4XHVjNWY0IEgocDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCBwPHN1Yj4zPFwvc3ViPilcdWM3NDAgXHVjMThjXHVjNzc4XHVjMjE4XHVhYzAwIHA8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgcDxzdWI+MzxcL3N1Yj5cdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWM2MjRcdWI5ODQgXHVjYzI4XHVjMjFjIFx1YmFhOVx1Yjg1ZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgSCgyLCAzLCA1KSA9IDIsIDMsIDQsIDUsIDYsIDgsIDksIDEwLCAxMiwgMTUsIDE2LCAxOCwgMjAsIDI0LCAyNSwgMjcsIC4uLiBcdWM3NzRcdWFjZTAsIDVcdWJjODhcdWM5ZjggXHVjMjE4XHViMjk0IDZcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIHA8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgcDxzdWI+MzxcL3N1Yj4sIGlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIxMjQgXHVjODE1XHVjMjE4XHViMjk0IDEwPHN1cD4xODxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkgocDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCBwPHN1Yj4zPFwvc3ViPilcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMjE4XHViMjk0IDEwPHN1cD4xODxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc4NjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIYW1taW5nIFByb2JsZW0iLCJkZXNjcmlwdGlvbiI6IjxwPkZvciBlYWNoIHRocmVlIHByaW1lIG51bWJlcnMgcDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+IGFuZCBwPHN1Yj4zPFwvc3ViPiwgbGV0JiMzOTtzIGRlZmluZSBIYW1taW5nIHNlcXVlbmNlIEhpKHA8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgcDxzdWI+MzxcL3N1Yj4pLCBpID0gMSxcdTAwODUgYXMgY29udGFpbmluZyBpbiBpbmNyZWFzaW5nIG9yZGVyIGFsbCB0aGUgbmF0dXJhbCBudW1iZXJzIHdob3NlIG9ubHkgcHJpbWUgZGl2aXNvcnMgYXJlIHA8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiBvciBwPHN1Yj4zPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIEgoMiwgMywgNSkgPSAyLCAzLCA0LCA1LCA2LCA4LCA5LCAxMCwgMTIsIDE1LCAxNiwgMTgsIDIwLCAyNCwgMjUsIDI3LC4uLjxcL3A+XHJcblxyXG48cD5TbyBIPHN1Yj41PFwvc3ViPigyLCAzLCA1KT02LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIHNpbmdsZSBsaW5lIG9mIGlucHV0IGZpbGUgdGhlcmUgYXJlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBwPHN1Yj4xPFwvc3ViPiBwPHN1Yj4yPFwvc3ViPiBwPHN1Yj4zPFwvc3ViPiBpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZmlsZSBtdXN0IGNvbnRhaW4gdGhlIHNpbmdsZSBpbnRlZ2VyIC0gSDxzdWI+aTxcL3N1Yj4ocDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCBwPHN1Yj4zPFwvc3ViPikuIEFsbCBudW1iZXJzIGluIGlucHV0IGFuZCBvdXRwdXQgYXJlIGxlc3MgdGhhbiAxMDxzdXA+MTg8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==