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

문제

정수론 중간고사를 마치고 집으로 돌아온 상근이는 패닉에 빠졌다. 유일하게 공부를 하지 않은 것이 오일러 피 함수(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)\))

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, $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
W3sicHJvYmxlbV9pZCI6IjQ5MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMyMThcdWI4NjAgXHVjMmViXHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMThcdWI4NjAgXHVjOTExXHVhYzA0XHVhY2UwXHVjMGFjXHViOTdjIFx1YjljOFx1Y2U1OFx1YWNlMCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQzMjhcdWIyYzlcdWM1ZDAgXHViZTYwXHVjODRjXHViMmU0LiBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVhY2Y1XHViZDgwXHViOTdjIFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhYzgzXHVjNzc0IFx1YzYyNFx1Yzc3Y1x1YjdlYyBcdWQ1M2MgXHVkNTY4XHVjMjE4KEV1bGVyJiMzOTtzIHRvdGllbnQgZnVuY3Rpb24sIFxcKFxcdmFycGhpIFxcKSlcdWM2MDBcdWIyOTRcdWIzNzAsIFx1YWRmOCBcdWQ1NjhcdWMyMThcdWM1ZDAgXHVhZDAwXHVkNTVjIFx1YmIzOFx1YzgxY1x1YjljYyBcdWIwOThcdWM2NTRcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMTA4XHViYjM0IFx1YzViNVx1YzZiOFx1ZDU4OFx1YWNlMCwgXHVjOWMxXHVjODExIFRvdGllbnQgXHVkNTY4XHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOFx1Yjg2MFx1YzVkMFx1YzExYyBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzU4IFx1YzE4Y1x1Yzc3OFx1YzIxOFx1YjI5NCBcdWFkZjggXHVjODE1XHVjMjE4XHViOTdjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWM1YzZcdWM3NzQgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMThjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgJG4gXFxnZSAyJFx1YzVkMFx1YzExYyBcdWQ1NjhcdWMyMTggJEYobikkXHVjNzQ0IFx1YWNmMVx1Yzc3NCAkbiRcdWM3NzQgXHViNDE4XHViMjk0IFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMThjXHVjMjE4XHVjNzU4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICRGKDgpJm5ic3A7PSBcXGxsIDIsMiwyIFxcZ2ckLCAkRig2MCkgPSBcXGxsIDIsMiwzLDUgXFxnZyQsICRGKDcxKSA9IFxcbGwgNzEgXFxnZyQgXHVjNzc0XHViMmU0LiAkTyhuKSRcdWM3NDAgJEYobikkXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgJE8oOCkgPSAzJCwgJE8oNjApID0gNCQsICRPKDcxKSA9IDEkIFx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXFwocChuKVxcKVx1Yzc0NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwocChuKSA9IFxcYmVnaW57Y2FzZXN9IDAgJmFtcDsgXFx0ZXh0e2lmIH0gbiA9IDEgXFxcXCAtMSAmYW1wOyBcXHRleHR7aWYgfSBuIFxcdGV4dHsgaXMgYSBwcmltZSBudW1iZXJ9IFxcXFwgTyhuKSAmYW1wOyBcXHRleHQge290aGVyd2lzZX0gXFxlbmR7Y2FzZXN9XFwpPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWQ0NWNcdWM1ZDBcdWIyOTQgXFwocChuKVxcKVx1Yzc1OCBcdWNjYWIgMjBcdWFjMWMgXHVhYzEyXHVjNzc0IFx1YjA5OFx1YzY0MFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWQgdGQtY2VudGVyIHRoLWNlbnRlclwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPiRuJDxcL3RoPlxyXG5cdFx0XHQ8dGg+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+XHJcblxyXG48cD4kYSBcXGxlIGIkXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkYSRcdWM2NDAgJGIkXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBUb3RpZW50IFx1ZDU2OFx1YzIxOFx1Yzc3OCBcXChcXHZhcnBoaShhLGIpXFwpXHViOTdjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cXChcXHZhcnBoaSAoYSxiKT0gKCBcXHN1bSBfeyBrPWEgfV57IGIgfXsgcChrKSB9ICZuYnNwOykgJm5ic3A7LSAoYi1hKzEpXFwpPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFxcKFxcdmFycGhpKDEsNCkgPSAtNFxcKSwgXFwoXFx2YXJwaGkoMTYsMTYpID0gM1xcKSwgXFwoXFx2YXJwaGkoOCwxMikgPSA0XFwpIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVhYzA0ICRbTCwgVV0kXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzEyXHVjNzQ0IFx1YWMxNlx1YjI5NCBcXChcXHZhcnBoaVxcKVx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCAkTCBcXGxlIFUkXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkTCRcdWFjZmMgJFUkXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXFwoXFx2YXJwaGkoYSxiKVxcKSAoJEwgXFxsZSBhIFxcbGUgYiBcXGxlIFUkKSBcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YWQ2Y1x1YWMwNCAkWzEsMjBdJFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFxcKFxcdmFycGhpXFwpXHViMjk0IDdcdWM3NzRcdWIyZTQuIChcXChcXHZhcnBoaSg4LDE2KVxcKSk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCAkTCRcdWFjZmMgJFUkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxIFxcbGUgTCBcXGxlIFUgJmx0OyAxLDAwMCwwMDAkKTxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAkLTEkXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YzhmY1x1YzViNFx1YzljNCBcdWFkNmNcdWFjMDQgJFtMLCBVXSRcdWM1ZDBcdWMxMWMgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcXChcXHZhcnBoaVxcKSBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQ5MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKb2hubnkgSGF0ZXMgTnVtYmVyIFRoZW9yeSIsImRlc2NyaXB0aW9uIjoiPHA+Sm9obm55IGhhdGVzIE51bWJlciBUaGVvcnkhIEFjdHVhbGx5LCBiYWNrIGluIDIwMDIsIHdlIGNhbWUgdG8ga25vdyB0aGF0IEpvaG5ueSBjb3VsZG4mcnNxdW87dCBjb3VudCBhbmQgaW4gMjAwNSB3ZSBrbmV3IHRoYXQgSm9obm55IGNvdWxkbiZyc3F1bzt0IHlldCBhZGQuIChCdXQgd2UgZGlkIGtub3cgaW4gMjAwMyB0aGF0IEpvaG5ueSB3YXMgc3RyZWV0IHNtYXJ0IGVub3VnaCB0byBzb2x2ZSBkaVx1ZmIwM2N1bHQgZ3JhcGggcHJvYmxlbXMhKSBXaHkgSm9obm55IGRlY2lkZWQgdG8gc3R1ZHkgTnVtYmVyIFRoZW9yeSBpcyBpbmNvbXByZWhlbnNpYmxlIHRvIHVzLjxcL3A+XHJcblxyXG48cD5Bbnlob3csIGJhY2sgdG8gSm9obm55LiBKb2hubnkganVzdCBmYWlsZWQgaGlzIGNvbXByZWhlbnNpdmUgZXhhbSBhbmQgdGhhdCB3YXMgYWxsIGJlY2F1c2Ugb2YgRXVsZXImcnNxdW87cyBUb3RpZW50IGZ1bmN0aW9uIChcXChcXHZhcnBoaVxcKSkuIEpvaG5ueSBpcyBzbyBhbmdyeSB0aGF0IGhlIGRlY2lkZXMgdG8gY3JlYXRlIGhpcyBvd24gVG90aWVudCBmdW5jdGlvbi4gSGVyZSZyc3F1bztzIGhvdyBoZSBkZXNjcmliZWQgaXQgdG8gaGlzIGFkdmlzb3I6PFwvcD5cclxuXHJcbjxwPkluIG51bWJlciB0aGVvcnksIHRoZSBwcmltZSBmYWN0b3JzIG9mIGEgcG9zaXRpdmUgaW50ZWdlciBhcmUgdGhlIHByaW1lIG51bWJlcnMgdGhhdCBkaXZpZGUgaW50byB0aGF0IGludGVnZXIgZXhhY3RseSwgd2l0aG91dCBsZWF2aW5nIGEgcmVtYWluZGVyLiBKb2hubnkgZGVcdWZiMDFuZXMgZnVuY3Rpb24gRihuKSwgZm9yICRuIFxcZ2UgMiQsIHRvIGJlIHRoZSBub24tZGVjcmVhc2luZyBsaXN0IG9mIHByaW1lIG51bWJlcnMgd2hvc2UgcHJvZHVjdCBpcyAkbiQuIEZvciBleGFtcGxlLCAkRig4KSZuYnNwOz0gXFxsbCAyLDIsMiBcXGdnJCwgJEYoNjApID0gXFxsbCAyLDIsMyw1IFxcZ2ckLCBhbmQgJEYoNzEpID0gXFxsbCA3MSBcXGdnJFx1MDAwNSAoJDcxJCBpcyBhIHByaW1lLikgTGV0ICRPKG4pJCBiZSB0aGUgbGVuZ3RoIG9mIHRoZSBsaXN0ICRGKG4pJCAoaS5lLiBpdHMgb3JkaW5hbC4pIEZvciBleGFtcGxlLCAkTyg4KSA9IDMkLCAkTyg2MCkgPSA0JCwgYW5kICRPKDcxKSA9IDEkLiBKb2hubnkgYWxzbyBkZVx1ZmIwMW5lcyBmdW5jdGlvbiBcXChwKG4pXFwpIG92ZXIgcG9zaXRpdmUgaW50ZWdlcnMgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+XFwocChuKSA9IFxcYmVnaW57Y2FzZXN9IDAgJmFtcDsgXFx0ZXh0e2lmIH0gbiA9IDEgXFxcXCAtMSAmYW1wOyBcXHRleHR7aWYgfSBuIFxcdGV4dHsgaXMgYSBwcmltZSBudW1iZXJ9IFxcXFwgTyhuKSAmYW1wOyBcXHRleHQge290aGVyd2lzZX0gXFxlbmR7Y2FzZXN9XFwpPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgdGFibGUgaWxsdXN0cmF0ZXMgXFwocChuKVxcKSBmb3IgdGhlIFx1ZmIwMXJzdCB0d2VudHkgcG9zaXRpdmUgaW50ZWdlcnM6PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkIHRkLWNlbnRlciB0aC1jZW50ZXJcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4kbiQ8XC90aD5cclxuXHRcdFx0PHRoPiQxJDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDIkPFwvdGg+XHJcblx0XHRcdDx0aD4kMyQ8XC90aD5cclxuXHRcdFx0PHRoPiQ0JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDUkPFwvdGg+XHJcblx0XHRcdDx0aD4kNiQ8XC90aD5cclxuXHRcdFx0PHRoPiQ3JDxcL3RoPlxyXG5cdFx0XHQ8dGg+JDgkPFwvdGg+XHJcblx0XHRcdDx0aD4kOSQ8XC90aD5cclxuXHRcdFx0PHRoPiQxMCQ8XC90aD5cclxuXHRcdFx0PHRoPiQxMSQ8XC90aD5cclxuXHRcdFx0PHRoPiQxMiQ8XC90aD5cclxuXHRcdFx0PHRoPiQxMyQ8XC90aD5cclxuXHRcdFx0PHRoPiQxNCQ8XC90aD5cclxuXHRcdFx0PHRoPiQxNSQ8XC90aD5cclxuXHRcdFx0PHRoPiQxNiQ8XC90aD5cclxuXHRcdFx0PHRoPiQxNyQ8XC90aD5cclxuXHRcdFx0PHRoPiQxOCQ8XC90aD5cclxuXHRcdFx0PHRoPiQxOSQ8XC90aD5cclxuXHRcdFx0PHRoPiQyMCQ8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPiRwKG4pJDxcL3RoPlxyXG5cdFx0XHQ8dGQ+JDAkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMiQ8XC90ZD5cclxuXHRcdFx0PHRkPiQtMSQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JC0xJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDMkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMiQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JC0xJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDMkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMiQ8XC90ZD5cclxuXHRcdFx0PHRkPiQyJDxcL3RkPlxyXG5cdFx0XHQ8dGQ+JDQkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kLTEkPFwvdGQ+XHJcblx0XHRcdDx0ZD4kMyQ8XC90ZD5cclxuXHRcdFx0PHRkPiQtMSQ8XC90ZD5cclxuXHRcdFx0PHRkPiQzJDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+R2l2ZW4gdHdvIHBvc2l0aXZlIGludGVnZXJzICRhJCBhbmQgJGIkIHdoZXJlICRhIFxcbGUgYiQsIEpvaG5ueSBkZVx1ZmIwMW5lcyBoaXMgdmVyeSBvd24gVG90aWVudCBmdW5jdGlvbiBcXChcXHZhcnBoaShhLGIpXFwpIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxwPlxcKFxcdmFycGhpIChhLGIpPSAoIFxcc3VtIF97IGs9YSB9XnsgYiB9eyBwKGspIH0gJm5ic3A7KSAmbmJzcDstIChiLWErMSlcXCk8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIFxcKFxcdmFycGhpKDEsNCkgPSAtNFxcKSwgXFwoXFx2YXJwaGkoMTYsMTYpID0gM1xcKSwgYW5kIFxcKFxcdmFycGhpKDgsMTIpID0gNFxcKS48XC9wPlxyXG5cclxuPHA+Rm9yIGhpcyBkaXNzZXJ0YXRpb24sIEpvaG5ueSBuZWVkcyBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBtYXhpbWFsIFxcKFxcdmFycGhpXFwpIHdpdGhpbiBhIGdpdmVuIHJhbmdlICRbTCwgVV0kLiBJbiBvdGhlciB3b3JkcywgZ2l2ZW4gdHdvIHBvc2l0aXZlIGludGVnZXJzICRMJCwgJFUkIHN1Y2ggdGhhdCAkTCBcXGxlIFUkLCB0aGUgcHJvZ3JhbSBtdXN0IFx1ZmIwMW5kIHRoZSBtYXhpbXVtIFxcKFxcdmFycGhpKGEsIGIpXFwpIHdoZXJlICRMIFxcbGUgYSBcXGxlIGIgXFxsZSBVJC4gRm9yIGV4YW1wbGUsIHRoZSBtYXhpbWFsIFxcKFxcdmFycGhpXFwpIHdpdGhpbiB0aGUgcmFuZ2UgJFsxLDIwXSQgaXMgJDckICh3aGljaCBpcyBcXChcXHZhcnBoaSg4LDE2KVxcKS4pPFwvcD5cclxuXHJcbjxwPldyaXRlIHRoZSBwcm9ncmFtIEpvaG5ueSBuZWVkcyE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIHRlc3RlZCBvbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBzcGVjaVx1ZmIwMWVkIG9uIGEgc2luZ2xlIGxpbmUuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpXHVmYjAxZWQgdXNpbmcgdHdvIHBvc2l0aXZlIGludGVnZXJzICRMJCBhbmQgJFUkIHNlcGFyYXRlZCBieSBvbmUgb3IgbW9yZSBzcGFjZXMsIGFuZCBzYXRpc2Z5aW5nIHRoZSBmb2xsb3dpbmcgcHJvcGVydHk6ICQxIFxcbGUgTCBcXGxlIFUgJmx0OyAxLDAwMCwwMDAkLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSB0ZXN0IGNhc2VzIGlzIGluZGljYXRlZCBieSBhIGxpbmUgbWFkZSBvZiB0d28gJC0xJCZyc3F1bztzLiBUaGF0IGxhc3QgbGluZSBpcyBpcyBub3QgcGFydCBvZiB0aGUgdGVzdCBjYXNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgcmVzdWx0IG9uIGEgc2luZ2xlIGxpbmUgdXNpbmcgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjxwcmU+XHJcbmsuIHJlc3VsdDxcL3ByZT5cclxuXHJcbjxwPldoZXJlIGsgaXMgdGhlIHRlc3QgY2FzZSBudW1iZXIgKHN0YXJ0aW5nIGF0IDEsKSBhbmQgcmVzdWx0IGlzIHRoZSBtYXhpbWFsIFxcKFxcdmFycGhpXFwpIHRoYXQgY2FuIGJlIGZvdW5kIHdpdGhpbiB0aGUgcmFuZ2UgJFtMLCBVXSQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

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