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

문제

세계적인 석유 재벌 "규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 7세"는 집 앞에 정원이 있다. 정원의 관리인은 그냥 홍태석이다. 이 석유 재벌은 앱등이 출신으로, 애플제품이면 모두 사모은다. 그의 집에는 아이팟 터치, 아이팟 나노, 아이폰, 맥북, 애플 티비, 아이패드 등등 전세계의 모든 애플 제품이 있다. 애플을 너무 좋아하기 때문에 정원에는 N개의 사과 나무가 있다.

홍태석은 나무에 비료를 주는 일과, 나무에 대한 통계를 내는 일 2가지만 한다. 다른 일은 해봤자 망치기 때문에, 전혀 하지 않는다.

나무에 비료를 주기 위해서 세계적인 비료 회사 "Telcontar"에서 만든 "BbuRiJaMaJaJaRam"을 사용한다. 이 비료를 나무에 뿌리면, 그 나무는 즉시 1cm 자란다. 이 비료는 병에 담겨져서 나오는데, 모든 병은 제한된 용량 Ci가 있다. 이 Ci는 몇 개의 나무에 비료를 뿌릴지에 쓰인다. 게다가 모든 병에는 나무의 최소 높이 Hi가 있다. 규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 79세는 가능하면 모든 트리를 크게 만들라고 그냥 홍태석에게 시켰다. 홍태석은 나무 중에 적어도 높이가 Hi 센치미터인 서로 다른 Ci개의 가장 작은 나무를 골라서 비료를 뿌린다.

통계를 낼 때는, 주어진 구간에 속하는 높이의 나무의 개수를 구하는 것이다. 세계적인 석유 재벌 규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 7세는 홍태석에게 일처리좀 빨리 하라고 강요했기 때문에, 홍태석은 결국 이 일을 대신하는 프로그램을 작성하기로 했다. 홍태석이 해야 하는 일의 목록이 주어졌을 때, 홍태석을 위해 통계를 구해주는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 N과 M이 있다. N은 나무의 개수이고, M은 홍태석이 해야 하는 일의 개수이다. 둘째 줄에는 각 나무의 처음 높이가 주어진다. 이 높이는 모두 1보다 크거나 같고, N보다 작거나 같은 정수이다. 다음 M개의 줄에는 홍태석이 해야 하는 일이 시간 순서대로 주어진다. 각각의 입력은 문자 Ti (홍태석이 해야 하는 일의 타입)로 시작된다. (Ti = F 또는 Ti = c)

만약, Ti = F라면, 두 개의 정수 Ci와 Hi가 주어진다. 이 줄이 의미하는 것은 홍태석이 높이가 적어도 Hi센치미터인 가장 작은 나무 Ci개를 골라서 "BbuRiJaMaJaJaRam" 비료를 뿌리는 것이다. 만약, 높이가 적어도 Hi센치미터인 나무의 개수가 Ci개 보다 작으면, 남은 비료는 버린다. (한 번 비료를 뿌릴 때면, 하나의 나무에 두번 뿌릴 수 없다.)

만약, Ti = C이면, mini와 maxi가 입력으로 주어진다. 이것은 홍태석이 통계를 내야 하는 개수이다. 나무의 높이 H가 mini와 maxi 사이에 있는 나무의 개수를 구하면 된다. (mini ≤ H ≤ maxi) (1 ≤ N, M ≤ 100,000, 1 ≤ Ci ≤ N, 0 ≤ Hi ≤ 1,000,000,000, 1 ≤ mini ≤ maxi ≤ 1,000,000,000)

출력

홍태석이 해야 하는 일의 타입이 C일때 마다, 해당하는 나무의 개수를 출력하면 된다.

예제 입력 1

5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5

예제 출력 1

3
0
5
W3sicHJvYmxlbV9pZCI6IjI0MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzhcdWFjYzRcdWM4MDFcdWM3NzggXHVjMTFkXHVjNzIwIFx1YzdhY1x1YmM4YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMTM4XHVhY2M0XHVjODAxXHVjNzc4IFx1YzExZFx1YzcyMCBcdWM3YWNcdWJjOGMgJnF1b3Q7XHVhZGRjXHVkNjA0IFx1Yzg3MCBcdWM1NTVcdWI0NTggXHVkMmYwXHVkMDZjXHViOWFjXHVkMmYwIFx1YzU0OFx1YjRkY1x1YjgwOFx1YzJhNCBcdWQ2YzRcdWMxMzhcdWM3NzggXHViOWFjXHVjNjI0XHViMTJjIFx1YzE5NFx1YjgwOFx1Yjk3NCBcdWMwYjRcdWI3N2MgXHViOWM4XHViOWFjXHVjNmIwIFx1YjQ1MFx1YzJhNCBcdWMwYjBcdWQyMmNcdWMyYTQgXHVkM2EwXHViOWFjXHVjMmE0IFx1YmU0OCBcdWM3OTBcdWM3NzRcdWI0ZGMgXHVjMjIwXHVkMGM0IFx1Y2U1Y1x1YjA5OFx1YzY1MyBcdWJjNDVcdWFjNzAgN1x1YzEzOCZxdW90O1x1YjI5NCBcdWM5ZDEgXHVjNTVlXHVjNWQwIFx1YzgxNVx1YzZkMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1YzZkMFx1Yzc1OCBcdWFkMDBcdWI5YWNcdWM3NzhcdWM3NDAgXHVhZGY4XHViMGU1IFx1ZDY0ZFx1ZDBkY1x1YzExZFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzExZFx1YzcyMCBcdWM3YWNcdWJjOGNcdWM3NDAgXHVjNTcxXHViNGYxXHVjNzc0IFx1Y2Q5Y1x1YzJlMFx1YzczY1x1Yjg1YywgXHVjNTYwXHVkNTBjXHVjODFjXHVkNDg4XHVjNzc0XHViYTc0IFx1YmFhOFx1YjQ1MCBcdWMwYWNcdWJhYThcdWM3NDBcdWIyZTQuIFx1YWRmOFx1Yzc1OCBcdWM5ZDFcdWM1ZDBcdWIyOTQgXHVjNTQ0XHVjNzc0XHVkMzFmIFx1ZDEzMFx1Y2U1OCwgXHVjNTQ0XHVjNzc0XHVkMzFmIFx1YjA5OFx1YjE3OCwgXHVjNTQ0XHVjNzc0XHVkM2YwLCBcdWI5ZTVcdWJkODEsIFx1YzU2MFx1ZDUwYyBcdWQyZjBcdWJlNDQsIFx1YzU0NFx1Yzc3NFx1ZDMyOFx1YjRkYyBcdWI0ZjFcdWI0ZjEgXHVjODA0XHVjMTM4XHVhY2M0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM1NjBcdWQ1MGMgXHVjODFjXHVkNDg4XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNTYwXHVkNTBjXHVjNzQ0IFx1YjEwOFx1YmIzNCBcdWM4OGJcdWM1NDRcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzgxNVx1YzZkMFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzBhY1x1YWNmYyBcdWIwOThcdWJiMzRcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2NGRcdWQwZGNcdWMxMWRcdWM3NDAgXHViMDk4XHViYjM0XHVjNWQwIFx1YmU0NFx1YjhjY1x1Yjk3YyBcdWM4ZmNcdWIyOTQgXHVjNzdjXHVhY2ZjLCBcdWIwOThcdWJiMzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1ZDFiNVx1YWNjNFx1Yjk3YyBcdWIwYjRcdWIyOTQgXHVjNzdjIDJcdWFjMDBcdWM5YzBcdWI5Y2MgXHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5NzggXHVjNzdjXHVjNzQwIFx1ZDU3NFx1YmQyNFx1Yzc5MCBcdWI5ZGRcdWNlNThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM4MDRcdWQ2MDAgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMDk4XHViYjM0XHVjNWQwIFx1YmU0NFx1YjhjY1x1Yjk3YyBcdWM4ZmNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzEzOFx1YWNjNFx1YzgwMVx1Yzc3OCBcdWJlNDRcdWI4Y2MgXHVkNjhjXHVjMGFjICZxdW90O1RlbGNvbnRhciZxdW90O1x1YzVkMFx1YzExYyBcdWI5Y2NcdWI0ZTAgJnF1b3Q7QmJ1UmlKYU1hSmFKYVJhbSZxdW90O1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWJlNDRcdWI4Y2NcdWI5N2MgXHViMDk4XHViYjM0XHVjNWQwIFx1YmZjY1x1YjlhY1x1YmE3NCwgXHVhZGY4IFx1YjA5OFx1YmIzNFx1YjI5NCBcdWM5ODlcdWMyZGMgMWNtIFx1Yzc5MFx1Yjc4MFx1YjJlNC4gXHVjNzc0IFx1YmU0NFx1YjhjY1x1YjI5NCBcdWJjZDFcdWM1ZDAgXHViMmY0XHVhY2E4XHVjODM4XHVjMTFjIFx1YjA5OFx1YzYyNFx1YjI5NFx1YjM3MCwgXHViYWE4XHViNGUwIFx1YmNkMVx1Yzc0MCBcdWM4MWNcdWQ1NWNcdWI0MWMgXHVjNmE5XHViN2M5IENpXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IEM8c3ViPmk8XC9zdWI+XHViMjk0IFx1YmE4NyBcdWFjMWNcdWM3NTggXHViMDk4XHViYjM0XHVjNWQwIFx1YmU0NFx1YjhjY1x1Yjk3YyBcdWJmY2NcdWI5YjRcdWM5YzBcdWM1ZDAgXHVjNGYwXHVjNzc4XHViMmU0LiBcdWFjOGNcdWIyZTRcdWFjMDAgXHViYWE4XHViNGUwIFx1YmNkMVx1YzVkMFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHVjZDVjXHVjMThjIFx1YjE5Mlx1Yzc3NCBIPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWRkY1x1ZDYwNCBcdWM4NzAgXHVjNTU1XHViNDU4IFx1ZDJmMFx1ZDA2Y1x1YjlhY1x1ZDJmMCBcdWM1NDhcdWI0ZGNcdWI4MDhcdWMyYTQgXHVkNmM0XHVjMTM4XHVjNzc4IFx1YjlhY1x1YzYyNFx1YjEyYyBcdWMxOTRcdWI4MDhcdWI5NzQgXHVjMGI0XHViNzdjIFx1YjljOFx1YjlhY1x1YzZiMCBcdWI0NTBcdWMyYTQgXHVjMGIwXHVkMjJjXHVjMmE0IFx1ZDNhMFx1YjlhY1x1YzJhNCBcdWJlNDggXHVjNzkwXHVjNzc0XHViNGRjIFx1YzIyMFx1ZDBjNCBcdWNlNWNcdWIwOThcdWM2NTMgXHViYzQ1XHVhYzcwIDc5XHVjMTM4XHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCBcdWJhYThcdWI0ZTAgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDA2Y1x1YWM4YyBcdWI5Y2NcdWI0ZTRcdWI3N2NcdWFjZTAgXHVhZGY4XHViMGU1IFx1ZDY0ZFx1ZDBkY1x1YzExZFx1YzVkMFx1YWM4YyBcdWMyZGNcdWNmMzBcdWIyZTQuIFx1ZDY0ZFx1ZDBkY1x1YzExZFx1Yzc0MCBcdWIwOThcdWJiMzQgXHVjOTExXHVjNWQwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWIxOTJcdWM3NzRcdWFjMDAgSDxzdWI+aTxcL3N1Yj4gXHVjMTNjXHVjZTU4XHViYmY4XHVkMTMwXHVjNzc4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggQzxzdWI+aTxcL3N1Yj5cdWFjMWNcdWM3NTggXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWIwOThcdWJiMzRcdWI5N2MgXHVhY2U4XHViNzdjXHVjMTFjIFx1YmU0NFx1YjhjY1x1Yjk3YyBcdWJmY2NcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDFiNVx1YWNjNFx1Yjk3YyBcdWIwYmMgXHViNTRjXHViMjk0LCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhZDZjXHVhYzA0XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHViMDk4XHViYjM0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWMxMzhcdWFjYzRcdWM4MDFcdWM3NzggXHVjMTFkXHVjNzIwIFx1YzdhY1x1YmM4YyBcdWFkZGNcdWQ2MDQgXHVjODcwIFx1YzU1NVx1YjQ1OCBcdWQyZjBcdWQwNmNcdWI5YWNcdWQyZjAgXHVjNTQ4XHViNGRjXHViODA4XHVjMmE0IFx1ZDZjNFx1YzEzOFx1Yzc3OCBcdWI5YWNcdWM2MjRcdWIxMmMgXHVjMTk0XHViODA4XHViOTc0IFx1YzBiNFx1Yjc3YyBcdWI5YzhcdWI5YWNcdWM2YjAgXHViNDUwXHVjMmE0IFx1YzBiMFx1ZDIyY1x1YzJhNCBcdWQzYTBcdWI5YWNcdWMyYTQgXHViZTQ4IFx1Yzc5MFx1Yzc3NFx1YjRkYyBcdWMyMjBcdWQwYzQgXHVjZTVjXHViMDk4XHVjNjUzIFx1YmM0NVx1YWM3MCA3XHVjMTM4XHViMjk0IFx1ZDY0ZFx1ZDBkY1x1YzExZFx1YzVkMFx1YWM4YyBcdWM3N2NcdWNjOThcdWI5YWNcdWM4ODAgXHViZTY4XHViOWFjIFx1ZDU1OFx1Yjc3Y1x1YWNlMCBcdWFjMTVcdWM2OTRcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ2NGRcdWQwZGNcdWMxMWRcdWM3NDAgXHVhY2IwXHVhZDZkIFx1Yzc3NCBcdWM3N2NcdWM3NDQgXHViMzAwXHVjMmUwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWQ2NGRcdWQwZGNcdWMxMWRcdWM3NzQgXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NTggXHViYWE5XHViODVkXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDY0ZFx1ZDBkY1x1YzExZFx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVkMWI1XHVhY2M0XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWNmYyBNXHVjNzc0IFx1Yzc4OFx1YjJlNC4gTlx1Yzc0MCBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHVhY2UwLCBNXHVjNzQwIFx1ZDY0ZFx1ZDBkY1x1YzExZFx1Yzc3NCBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWNjOThcdWM3NGMgXHViMTkyXHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0NTAgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNjRkXHVkMGRjXHVjMTFkXHVjNzc0IFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzc0IFx1YzJkY1x1YWMwNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNzg1XHViODI1XHVjNzQwIFx1YmIzOFx1Yzc5MCBUPHN1Yj5pPFwvc3ViPiAoXHVkNjRkXHVkMGRjXHVjMTFkXHVjNzc0IFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzU4IFx1ZDBjMFx1Yzc4NSlcdWI4NWMgXHVjMmRjXHVjNzkxXHViNDFjXHViMmU0LiAoVDxzdWI+aTxcL3N1Yj4gPSBGIFx1YjYxMFx1YjI5NCBUPHN1Yj5pPFwvc3ViPiA9IGMpPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgVDxzdWI+aTxcL3N1Yj4gPSBGXHViNzdjXHViYTc0LCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBDPHN1Yj5pPFwvc3ViPlx1YzY0MCBIPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM5MDRcdWM3NzQgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWQ2NGRcdWQwZGNcdWMxMWRcdWM3NzQgXHViMTkyXHVjNzc0XHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCBIPHN1Yj5pPFwvc3ViPlx1YzEzY1x1Y2U1OFx1YmJmOFx1ZDEzMFx1Yzc3OCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YjA5OFx1YmIzNCBDPHN1Yj5pPFwvc3ViPlx1YWMxY1x1Yjk3YyBcdWFjZThcdWI3N2NcdWMxMWMgJnF1b3Q7QmJ1UmlKYU1hSmFKYVJhbSZxdW90OyBcdWJlNDRcdWI4Y2NcdWI5N2MgXHViZmNjXHViOWFjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IEg8c3ViPmk8XC9zdWI+XHVjMTNjXHVjZTU4XHViYmY4XHVkMTMwXHVjNzc4IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgQzxzdWI+aTxcL3N1Yj5cdWFjMWMgXHViY2Y0XHViMmU0IFx1Yzc5MVx1YzczY1x1YmE3NCwgXHViMGE4XHVjNzQwIFx1YmU0NFx1YjhjY1x1YjI5NCBcdWJjODRcdWI5YjBcdWIyZTQuIChcdWQ1NWMgXHViYzg4IFx1YmU0NFx1YjhjY1x1Yjk3YyBcdWJmY2NcdWI5YjQgXHViNTRjXHViYTc0LCBcdWQ1NThcdWIwOThcdWM3NTggXHViMDk4XHViYjM0XHVjNWQwIFx1YjQ1MFx1YmM4OCBcdWJmY2NcdWI5YjQgXHVjMjE4IFx1YzVjNlx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgVDxzdWI+aTxcL3N1Yj4gPSBDXHVjNzc0XHViYTc0LCBtaW48c3ViPmk8XC9zdWI+XHVjNjQwIG1heDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQwIFx1ZDY0ZFx1ZDBkY1x1YzExZFx1Yzc3NCBcdWQxYjVcdWFjYzRcdWI5N2MgXHViMGI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWIxOTJcdWM3NzQgSFx1YWMwMCBtaW48c3ViPmk8XC9zdWI+XHVjNjQwIG1heDxzdWI+aTxcL3N1Yj4gXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIChtaW48c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyZuYnNwO0ggJmxlOyBtYXg8c3ViPmk8XC9zdWI+KSAoMSAmbGU7IE4sIE0gJmxlOyAxMDAsMDAwLCAxICZsZTsgQzxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IE4sIDAgJmxlOyBIPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgMSwwMDAsMDAwLDAwMCwgMSAmbGU7IG1pbjxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IG1heDxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNjRkXHVkMGRjXHVjMTFkXHVjNzc0IFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzU4IFx1ZDBjMFx1Yzc4NVx1Yzc3NCBDXHVjNzdjXHViNTRjIFx1YjljOFx1YjJlNCwgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNDI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3Jvd2luZyBUcmVlcyIsImRlc2NyaXB0aW9uIjoiPHA+RWdvbiB0YWtlcyBjYXJlIG9mIGEgZ2FyZGVuIHdpdGggTiBhcHBsZSB0cmVlcy4gSGlzIHJlc3BvbnNpYmlsaXRpZXMgaW5jbHVkZSB0d28gdHlwZXMgb2YgdGFza3M6IGZlcnRpbGl6aW5nIHRoZSB0cmVlcyBhbmQgY29tcHV0aW5nIHNvbWUgc3RhdGlzdGljcyBhYm91dCB0aGVtLjxcL3A+XHJcblxyXG48cD5Gb3IgZmVydGlsaXppbmcgdGhlIHRyZWVzIGhlIGhhcyBzZXZlcmFsIGJvdHRsZXMgb2YgTWVnYUJvb3N0RmVydGlsaXplciwgd2hpY2gsIHdoZW4gdHJlYXRlZCBvbiB0cmVlcywgY2F1c2VzIHRoZW0gdG8gZ3JvdyBvbmUgY2VudGltZXRlciB1cCBpbnN0YW50bHkuIEV2ZXJ5IGJvdHRsZSBoYXMgYSBsaW1pdGVkIGNhcGFjaXR5IGM8c3ViPmk8XC9zdWI+ICwgd2hpY2ggZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIHRyZWVzIGl0IGNhbiBiZSBhcHBsaWVkIHRvLiBNb3Jlb3ZlciwgZm9yIGVhY2ggYm90dGxlIHRoZXJlIGlzIGEgbWluaW1hbCBoZWlnaHQgaDxzdWI+aTxcL3N1Yj4gb2YgdHJlZXMsIHdoaWNoIGNhbiBiZSB0cmVhdGVkIHdpdGggaXQuIFNpbmNlIEVnb24gd2FudHMgdG8gaGF2ZSBhbGwgaGlzIHRyZWVzIGFzIGJpZyBhcyBwb3NzaWJsZSwgaGUgYWx3YXlzIGFwcGxpZXMgdGhlIGZlcnRpbGl6ZXIgdG8gdGhlIGM8c3ViPmk8XC9zdWI+IHNtYWxsZXN0IHRyZWVzIGNob3NlbiBmcm9tIHRoZSB0cmVlcyB0aGF0IGFyZSBhdCBsZWFzdCBoPHN1Yj5pPFwvc3ViPiBjZW50aW1ldGVycyBoaWdoLjxcL3A+XHJcblxyXG48cD5XaGVuIEVnb24gY29tcHV0ZXMgc3RhdGlzdGljcyBhYm91dCB0cmVlcyBoZSBoYXMgdG8gZGV0ZXJtaW5lIHRoZSBudW1iZXIgb2YgdHJlZXMgd2hvc2UgaGVpZ2h0IGlzIGluIHNvbWUgZ2l2ZW4gaW50ZXJ2YWwuIEVnb24gaXMgcXVpdGUgYnVzeSB3b3JraW5nIGluIHRoZSBnYXJkZW4sIHNvIGhlIGFza2VkIHlvdSB0byB3cml0ZSBhIHByb2dyYW0sIHRoYXQgZ2l2ZW4gdGhlIGxpc3Qgb2YgaGlzIHRhc2tzLCBjb21wdXRlcyB0aGUgc3RhdGlzdGljcyBmb3IgaGltLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHRyZWVzIGluIEVnb24mcnNxdW87cyBnYXJkZW4gYW5kIHRoZSBudW1iZXIgb2YgaGlzIHRhc2tzLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBOIGludGVnZXJzIGZyb20gdGhlIHJhbmdlIFsxLCBOXSBkZXNjcmliaW5nIHRoZSBpbml0aWFsIGhlaWdodHMgb2YgdGhlIHRyZWVzIGluIGNlbnRpbWV0ZXJzLiBUaGUgZm9sbG93aW5nIE0gbGluZXMgZGVzY3JpYmUgdGhlIHRhc2tzIGluIGNocm9ub2xvZ2ljYWwgb3JkZXIuIEVhY2ggb2YgdGhvc2UgbGluZXMgYmVnaW5zIHdpdGggYSBjaGFyYWN0ZXIgdDxzdWI+aTxcL3N1Yj4gKHQ8c3ViPmk8XC9zdWI+ID0gRiBvciB0PHN1Yj5pPFwvc3ViPiA9IEMpLCB3aGljaCBkZXNjcmliZXMgdGhlIHR5cGUgb2YgdGhlIHRhc2suPFwvcD5cclxuXHJcbjxwPklmIHQ8c3ViPmk8XC9zdWI+ID0gRiB0aGVuIHR3byBpbnRlZ2VycyBjPHN1Yj5pPFwvc3ViPiBhbmQgaDxzdWI+aTxcL3N1Yj4gZm9sbG93LiBTdWNoIGEgbGluZSBtZWFucyB0aGF0IEVnb24gYXBwbGllcyBhIGJvdHRsZSBvZiBNZWdhQm9vc3RGZXJ0aWxpemVyIHRvIHRoZSBjPHN1Yj5pPFwvc3ViPiBzbWFsbGVzdCB0cmVlcyBhbW9uZyB0aG9zZSB0cmVlcyB0aGF0IGFyZSBhdCBsZWFzdCBoPHN1Yj5pPFwvc3ViPiBjZW50aW1ldGVycyBoaWdoLiBXaGVuIHRoZXJlIGFyZSBsZXNzIHRoYW4gYzxzdWI+aTxcL3N1Yj4gdHJlZXMgb2Ygc3VmXHVmYjAxY2llbnQgaGVpZ2h0LCBoZSBhcHBsaWVzIHRoZSBmZXJ0aWxpemVyIHRvIGFsbCBzdWNoIHRyZWVzIGFuZCBkaXNjYXJkcyB0aGUgYm90dGxlIHdpdGggc29tZSBmZXJ0aWxpemVyIHJlbWFpbmluZy48XC9wPlxyXG5cclxuPHA+SWYgdDxzdWI+aTxcL3N1Yj4gPSBDIHRoZW4gdHdvIGludGVnZXJzIG1pbjxzdWI+aTxcL3N1Yj4gYW5kIG1heDxzdWI+aTxcL3N1Yj4gZm9sbG93LiBUaGV5IGRlbm90ZSB0aGF0IEVnb24gaGFzIHRvIGNvbXB1dGUgdGhlIG51bWJlciBvZiB0cmVlcyB3aG9zZSBoZWlnaHQgSCBpcyBiZXR3ZWVuIG1pbjxzdWI+aTxcL3N1Yj4gYW5kIG1heDxzdWI+aTxcL3N1Yj4gY2VudGltZXRlcnMgKG1pbjxzdWI+aTxcL3N1Yj4gJmxlOyBIICZsZTsgbWF4PHN1Yj5pPFwvc3ViPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGV2ZXJ5IHRhc2sgb2YgdHlwZSBDLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIGFwcGxlIHRyZWVzIHRoYXQgaGF2ZSB0aGUgcmVxdWlyZWQgaGVpZ2h0LiBUaGUgb3JkZXIgb2YgdGhlIHJlc3VsdHMgc2hvdWxkIGNvbmZvcm0gdG8gdGhlIG9yZGVyIG9mIHR5cGUgQyB0YXNrcyBpbiB0aGUgaW5wdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiwgTSAmbGU7IDEwMCAwMDA7PFwvbGk+XHJcblx0PGxpPjEgJmxlOyBjPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIDAgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDA7PFwvbGk+XHJcblx0PGxpPjEgJmxlOyBtaW48c3ViPmk8XC9zdWI+ICZsZTsgbWF4PHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDAuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 1번