시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB212896342.857%

문제

정수론 중간고사를 마치고 집으로 돌아온 상근이는 패닉에 빠졌다. 유일하게 공부를 하지 않은 것이 오일러 피 함수(Euler's totient function, \(\varphi \))였는데, 그 함수에 관한 문제만 나왔기 때문이다. 상근이는 너무 억울했고, 직접 Totient 함수를 만들기로 했다.

정수론에서 양의 정수의 소인수는 그 정수를 나머지 없이 나눌 수 있는 소수이다. 상근이는 $n \ge 2$에서 함수 $F(n)$을 곱이 $n$이 되는 감소하지 않는 소수의 리스트로 정의했다. 예를 들어, $F(8) = \ll 2,2,2 \gg$, $F(60) = \ll 2,2,3,5 \gg$, $F(71) = \ll 71 \gg$ 이다. $O(n)$은 $F(n)$의 길이이다. 예를 들어, $O(8) = 3$, $O(60) = 4$, $O(71) = 1$ 이 된다. 마지막으로, 양의 정수에 대해서 \(p(n)\)을 다음과 같이 정의했다.

\(p(n) = \begin{cases} 0 & \text{if } n = 1 \\ -1 & \text{if } n \text{ is a prime number} \\ O(n) & \text {otherwise} \end{cases}\)

아래 표에는 \(p(n)\)의 첫 20개 값이 나와있다.

$n$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$ $13$ $14$ $15$ $16$ $17$ $18$ $19$ $20$
$p(n)$ $0$ $-1$ $-1$ $2$ $-1$ $2$ $-1$ $3$ $2$ $2$ $-1$ $3$ $-1$ $2$ $2$ $4$ $-1$ $3$ $-1$ $3$

$a \le b$를 만족하는 두 양의 정수 $a$와 $b$에 대해서, 상근이는 자신의 Totient 함수인 \(\varphi(a,b)\)를 다음과 같이 정의했다.

\(\varphi (a,b)= ( \sum _{ k=a }^{ b }{ p(k) } ) - (b-a+1)\)

예를 들어, \(\varphi(1,4) = -4\), \(\varphi(16,16) = 3\), \(\varphi(8,12) = 4\) 이다.

구간 $[L, U]$가 주어졌을 때, 가장 큰 값을 갖는 \(\varphi\)를 찾는 프로그램을 작성하시오.

즉, $L \le U$를 만족하는 두 양의 정수 $L$과 $U$가 주어졌을 때, 가장 큰 \(\varphi(a,b)\) ($L \le a \le b \le U$) 를 찾는 프로그램을 작성하시오. 예를 들어, 구간 $[1,20]$에서 가장 큰 \(\varphi\)는 7이다. (\(\varphi(8,16)\))

입력

입력은 7,000개 이하의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, $L$과 $U$가 주어진다. ($1 \le L \le U < 1,000,000$)

입력의 마지막 줄에는 $-1$이 두 개 주어진다.

출력

각 테스트 케이스마다 주어진 구간 $[L, U]$에서 찾을 수 있는 가장 큰 \(\varphi\) 값을 출력한다.

예제 입력 1

1 5
1 20
10 20
900000 901000
-1 -1

예제 출력 1

1. 1
2. 7
3. 5
4. 2551
W3sicHJvYmxlbV9pZCI6IjQ5MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMyMThcdWI4NjAgXHVjMmViXHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMThcdWI4NjAgXHVjOTExXHVhYzA0XHVhY2UwXHVjMGFjXHViOTdjIFx1YjljOFx1Y2U1OFx1YWNlMCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQzMjhcdWIyYzlcdWM1ZDAgXHViZTYwXHVjODRjXHViMmU0LiBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVhY2Y1XHViZDgwXHViOTdjIFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhYzgzXHVjNzc0IFx1YzYyNFx1Yzc3Y1x1YjdlYyBcdWQ1M2MgXHVkNTY4XHVjMjE4KEV1bGVyJiMzOTtzIHRvdGllbnQgZnVuY3Rpb24sIFxcKFxcdmFycGhpIFxcKSlcdWM2MDBcdWIyOTRcdWIzNzAsIFx1YWRmOCBcdWQ1NjhcdWMyMThcdWM1ZDAgXHVhZDAwXHVkNTVjIFx1YmIzOFx1YzgxY1x1YjljYyBcdWIwOThcdWM2NTRcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMTA4XHViYjM0IFx1YzViNVx1YzZiOFx1ZDU4OFx1YWNlMCwgXHVjOWMxXHVjODExIFRvdGllbnQgXHVkNTY4XHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOFx1Yjg2MFx1YzVkMFx1YzExYyBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzU4IFx1YzE4Y1x1Yzc3OFx1YzIxOFx1YjI5NCBcdWFkZjggXHVjODE1XHVjMjE4XHViOTdjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWM1YzZcdWM3NzQgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMThjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgJG4gXFxnZSAyJFx1YzVkMFx1YzExYyBcdWQ1NjhcdWMyMTggJEYobikkXHVjNzQ0IFx1YWNmMVx1Yzc3NCAkbiRcdWM3NzQgXHViNDE4XHViMjk0IFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMThjXHVjMjE4XHVjNzU4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICRGKDgpID0gXFxsbCAyLDIsMiBcXGdnJCwgJEYoNjApID0gXFxsbCAyLDIsMyw1IFxcZ2ckLCAkRig3MSkgPSBcXGxsIDcxIFxcZ2ckIFx1Yzc3NFx1YjJlNC4gJE8obikkXHVjNzQwICRGKG4pJFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICRPKDgpID0gMyQsICRPKDYwKSA9IDQkLCAkTyg3MSkgPSAxJCBcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFxcKHAobilcXClcdWM3NDQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxcKHAobikgPSBcXGJlZ2lue2Nhc2VzfSAwICZhbXA7IFxcdGV4dHtpZiB9IG4gPSAxIFxcXFwgLTEgJmFtcDsgXFx0ZXh0e2lmIH0gbiBcXHRleHR7IGlzIGEgcHJpbWUgbnVtYmVyfSBcXFxcIE8obikgJmFtcDsgXFx0ZXh0IHtvdGhlcndpc2V9IFxcZW5ke2Nhc2VzfVxcKTxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVkNDVjXHVjNWQwXHViMjk0IFxcKHAobilcXClcdWM3NTggXHVjY2FiIDIwXHVhYzFjIFx1YWMxMlx1Yzc3NCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkIHRkLWNlbnRlciB0aC1jZW50ZXJcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4kbiQ8XC90aD5cclxuXHRcdFx0PHRoPiQxJDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDIkPFwvdGg+XHJcblx0XHRcdDx0aD4kMyQ8XC90aD5cclxuXHRcdFx0PHRoPiQ0JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDUkPFwvdGg+XHJcblx0XHRcdDx0aD4kNiQ8XC90aD5cclxuXHRcdFx0PHRoPiQ3JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDgkPFwvdGg+XHJcblx0XHRcdDx0aD4kOSQ8XC90aD5cclxuXHRcdFx0PHRoPiQxMCQ8XC90aD5cclxuXHRcdFx0PHRoPiQxMSQ8XC90aD5cclxuXHRcdFx0PHRoPiQxMiQ8XC90aD5cclxuXHRcdFx0PHRoPiQxMyQ8XC90aD5cclxuXHRcdFx0PHRoPiQxNCQ8XC90aD5cclxuXHRcdFx0PHRoPiQxNSQ8XC90aD5cclxuXHRcdFx0PHRoPiQxNiQ8XC90aD5cclxuXHRcdFx0PHRoPiQxNyQ8XC90aD5cclxuXHRcdFx0PHRoPiQxOCQ8XC90aD5cclxuXHRcdFx0PHRoPiQxOSQ8XC90aD5cclxuXHRcdFx0PHRoPiQyMCQ8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPiRwKG4pJDxcL3RoPlxyXG5cdFx0XHQ8dGQ+JDAkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMiQ8XC90ZD5cclxuXHRcdFx0PHRkPiQtMSQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JC0xJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDMkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMiQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JC0xJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDMkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMiQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDQkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMyQ8XC90ZD5cclxuXHRcdFx0PHRkPiQtMSQ8XC90ZD5cclxuXHRcdFx0PHRkPiQzJDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+JGEgXFxsZSBiJFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJGEkXHVjNjQwICRiJFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggVG90aWVudCBcdWQ1NjhcdWMyMThcdWM3NzggXFwoXFx2YXJwaGkoYSxiKVxcKVx1Yjk3YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwoXFx2YXJwaGkgKGEsYik9ICggXFxzdW0gX3sgaz1hIH1eeyBiIH17IHAoaykgfSAgKSAgLSAoYi1hKzEpXFwpPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFxcKFxcdmFycGhpKDEsNCkgPSAtNFxcKSwgXFwoXFx2YXJwaGkoMTYsMTYpID0gM1xcKSwgXFwoXFx2YXJwaGkoOCwxMikgPSA0XFwpIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVhYzA0ICRbTCwgVV0kXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzEyXHVjNzQ0IFx1YWMxNlx1YjI5NCBcXChcXHZhcnBoaVxcKVx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCAkTCBcXGxlIFUkXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkTCRcdWFjZmMgJFUkXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXFwoXFx2YXJwaGkoYSxiKVxcKSAoJEwgXFxsZSBhIFxcbGUgYiBcXGxlIFUkKSBcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YWQ2Y1x1YWMwNCAkWzEsMjBdJFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFxcKFxcdmFycGhpXFwpXHViMjk0IDdcdWM3NzRcdWIyZTQuIChcXChcXHZhcnBoaSg4LDE2KVxcKSk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCA3LDAwMFx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsICRMJFx1YWNmYyAkVSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDEgXFxsZSBMIFxcbGUgVSAmbHQ7IDEsMDAwLDAwMCQpPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0ICQtMSRcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWQ2Y1x1YWMwNCAkW0wsIFVdJFx1YzVkMFx1YzExYyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFxcKFxcdmFycGhpXFwpIFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDkyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkpvaG5ueSBIYXRlcyBOdW1iZXIgVGhlb3J5IiwiZGVzY3JpcHRpb24iOiI8cD5Kb2hubnkgaGF0ZXMgTnVtYmVyIFRoZW9yeSEgQWN0dWFsbHksIGJhY2sgaW4gMjAwMiwgd2UgY2FtZSB0byBrbm93IHRoYXQgSm9obm55IGNvdWxkbiZyc3F1bzt0IGNvdW50IGFuZCBpbiAyMDA1IHdlIGtuZXcgdGhhdCBKb2hubnkgY291bGRuJnJzcXVvO3QgeWV0IGFkZC4gKEJ1dCB3ZSBkaWQga25vdyBpbiAyMDAzIHRoYXQgSm9obm55IHdhcyBzdHJlZXQgc21hcnQgZW5vdWdoIHRvIHNvbHZlIGRpXHVmYjAzY3VsdCBncmFwaCBwcm9ibGVtcyEpIFdoeSBKb2hubnkgZGVjaWRlZCB0byBzdHVkeSBOdW1iZXIgVGhlb3J5IGlzIGluY29tcHJlaGVuc2libGUgdG8gdXMuPFwvcD5cclxuXHJcbjxwPkFueWhvdywgYmFjayB0byBKb2hubnkuIEpvaG5ueSBqdXN0IGZhaWxlZCBoaXMgY29tcHJlaGVuc2l2ZSBleGFtIGFuZCB0aGF0IHdhcyBhbGwgYmVjYXVzZSBvZiBFdWxlciZyc3F1bztzIFRvdGllbnQgZnVuY3Rpb24gKFxcKFxcdmFycGhpXFwpKS4gSm9obm55IGlzIHNvIGFuZ3J5IHRoYXQgaGUgZGVjaWRlcyB0byBjcmVhdGUgaGlzIG93biBUb3RpZW50IGZ1bmN0aW9uLiBIZXJlJnJzcXVvO3MgaG93IGhlIGRlc2NyaWJlZCBpdCB0byBoaXMgYWR2aXNvcjo8XC9wPlxyXG5cclxuPHA+SW4gbnVtYmVyIHRoZW9yeSwgdGhlIHByaW1lIGZhY3RvcnMgb2YgYSBwb3NpdGl2ZSBpbnRlZ2VyIGFyZSB0aGUgcHJpbWUgbnVtYmVycyB0aGF0IGRpdmlkZSBpbnRvIHRoYXQgaW50ZWdlciBleGFjdGx5LCB3aXRob3V0IGxlYXZpbmcgYSByZW1haW5kZXIuIEpvaG5ueSBkZVx1ZmIwMW5lcyBmdW5jdGlvbiBGKG4pLCBmb3IgJG4gXFxnZSAyJCwgdG8gYmUgdGhlIG5vbi1kZWNyZWFzaW5nIGxpc3Qgb2YgcHJpbWUgbnVtYmVycyB3aG9zZSBwcm9kdWN0IGlzICRuJC4gRm9yIGV4YW1wbGUsICRGKDgpJm5ic3A7PSBcXGxsIDIsMiwyIFxcZ2ckLCAkRig2MCkgPSBcXGxsIDIsMiwzLDUgXFxnZyQsIGFuZCAkRig3MSkgPSBcXGxsIDcxIFxcZ2ckXHUwMDA1ICgkNzEkIGlzIGEgcHJpbWUuKSBMZXQgJE8obikkIGJlIHRoZSBsZW5ndGggb2YgdGhlIGxpc3QgJEYobikkIChpLmUuIGl0cyBvcmRpbmFsLikgRm9yIGV4YW1wbGUsICRPKDgpID0gMyQsICRPKDYwKSA9IDQkLCBhbmQgJE8oNzEpID0gMSQuIEpvaG5ueSBhbHNvIGRlXHVmYjAxbmVzIGZ1bmN0aW9uIFxcKHAobilcXCkgb3ZlciBwb3NpdGl2ZSBpbnRlZ2VycyBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD5cXChwKG4pID0gXFxiZWdpbntjYXNlc30gMCAmYW1wOyBcXHRleHR7aWYgfSBuID0gMSBcXFxcIC0xICZhbXA7IFxcdGV4dHtpZiB9IG4gXFx0ZXh0eyBpcyBhIHByaW1lIG51bWJlcn0gXFxcXCBPKG4pICZhbXA7IFxcdGV4dCB7b3RoZXJ3aXNlfSBcXGVuZHtjYXNlc31cXCk8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyB0YWJsZSBpbGx1c3RyYXRlcyBcXChwKG4pXFwpIGZvciB0aGUgXHVmYjAxcnN0IHR3ZW50eSBwb3NpdGl2ZSBpbnRlZ2Vyczo8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWQgdGQtY2VudGVyIHRoLWNlbnRlclwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPiRuJDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDEkPFwvdGg+XHJcblx0XHRcdDx0aD4kMiQ8XC90aD5cclxuXHRcdFx0PHRoPiQzJDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDQkPFwvdGg+XHJcblx0XHRcdDx0aD4kNSQ8XC90aD5cclxuXHRcdFx0PHRoPiQ2JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDckPFwvdGg+XHJcblx0XHRcdDx0aD4kOCQ8XC90aD5cclxuXHRcdFx0PHRoPiQ5JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDEwJDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDExJDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDEyJDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDEzJDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDE0JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDE1JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDE2JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDE3JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDE4JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDE5JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDIwJDxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+JHAobikkPFwvdGg+XHJcblx0XHRcdDx0ZD4kMCQ8XC90ZD5cclxuXHRcdFx0PHRkPiQtMSQ8XC90ZD5cclxuXHRcdFx0PHRkPiQtMSQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JC0xJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDIkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMyQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDIkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMyQ8XC90ZD5cclxuXHRcdFx0PHRkPiQtMSQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDIkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kNCQ8XC90ZD5cclxuXHRcdFx0PHRkPiQtMSQ8XC90ZD5cclxuXHRcdFx0PHRkPiQzJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JC0xJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDMkPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5HaXZlbiB0d28gcG9zaXRpdmUgaW50ZWdlcnMgJGEkIGFuZCAkYiQgd2hlcmUgJGEgXFxsZSBiJCwgSm9obm55IGRlXHVmYjAxbmVzIGhpcyB2ZXJ5IG93biBUb3RpZW50IGZ1bmN0aW9uIFxcKFxcdmFycGhpKGEsYilcXCkgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+XFwoXFx2YXJwaGkgKGEsYik9ICggXFxzdW0gX3sgaz1hIH1eeyBiIH17IHAoaykgfSAmbmJzcDspICZuYnNwOy0gKGItYSsxKVxcKTxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgXFwoXFx2YXJwaGkoMSw0KSA9IC00XFwpLCBcXChcXHZhcnBoaSgxNiwxNikgPSAzXFwpLCBhbmQgXFwoXFx2YXJwaGkoOCwxMikgPSA0XFwpLjxcL3A+XHJcblxyXG48cD5Gb3IgaGlzIGRpc3NlcnRhdGlvbiwgSm9obm55IG5lZWRzIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIG1heGltYWwgXFwoXFx2YXJwaGlcXCkgd2l0aGluIGEgZ2l2ZW4gcmFuZ2UgJFtMLCBVXSQuIEluIG90aGVyIHdvcmRzLCBnaXZlbiB0d28gcG9zaXRpdmUgaW50ZWdlcnMgJEwkLCAkVSQgc3VjaCB0aGF0ICRMIFxcbGUgVSQsIHRoZSBwcm9ncmFtIG11c3QgXHVmYjAxbmQgdGhlIG1heGltdW0gXFwoXFx2YXJwaGkoYSwgYilcXCkgd2hlcmUgJEwgXFxsZSBhIFxcbGUgYiBcXGxlIFUkLiBGb3IgZXhhbXBsZSwgdGhlIG1heGltYWwgXFwoXFx2YXJwaGlcXCkgd2l0aGluIHRoZSByYW5nZSAkWzEsMjBdJCBpcyAkNyQgKHdoaWNoIGlzIFxcKFxcdmFycGhpKDgsMTYpXFwpLik8XC9wPlxyXG5cclxuPHA+V3JpdGUgdGhlIHByb2dyYW0gSm9obm55IG5lZWRzITxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIGF0IG1vc3QgNzAwMCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBzcGVjaVx1ZmIwMWVkIG9uIGEgc2luZ2xlIGxpbmUuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpXHVmYjAxZWQgdXNpbmcgdHdvIHBvc2l0aXZlIGludGVnZXJzICRMJCBhbmQgJFUkIHNlcGFyYXRlZCBieSBvbmUgb3IgbW9yZSBzcGFjZXMsIGFuZCBzYXRpc2Z5aW5nIHRoZSBmb2xsb3dpbmcgcHJvcGVydHk6ICQxIFxcbGUgTCBcXGxlIFUgJmx0OyAxLDAwMCwwMDAkLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSB0ZXN0IGNhc2VzIGlzIGluZGljYXRlZCBieSBhIGxpbmUgbWFkZSBvZiB0d28gJC0xJCZyc3F1bztzLiBUaGF0IGxhc3QgbGluZSBpcyBpcyBub3QgcGFydCBvZiB0aGUgdGVzdCBjYXNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgcmVzdWx0IG9uIGEgc2luZ2xlIGxpbmUgdXNpbmcgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjxwcmU+XHJcbmsuIHJlc3VsdDxcL3ByZT5cclxuXHJcbjxwPldoZXJlIGsgaXMgdGhlIHRlc3QgY2FzZSBudW1iZXIgKHN0YXJ0aW5nIGF0IDEsKSBhbmQgcmVzdWx0IGlzIHRoZSBtYXhpbWFsIFxcKFxcdmFycGhpXFwpIHRoYXQgY2FuIGJlIGZvdW5kIHdpdGhpbiB0aGUgcmFuZ2UgJFtMLCBVXSQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2006 Arab Collegiate Programming Contest F번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: corea