시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 82 24 18 27.692%

문제

세계적인 석유 재벌 "규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 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+ICZsdDs9IEggJmx0Oz0gbWF4PHN1Yj5pPFwvc3ViPikgKDEmbHQ7PU4sTSZsdDs9MTAwLDAwMCwgMSZsdDs9QzxzdWI+aTxcL3N1Yj4mbHQ7PU4sIDAmbHQ7PUg8c3ViPmk8XC9zdWI+Jmx0Oz0xLDAwMCwwMDAsMDAwLCAxJmx0Oz1taW48c3ViPmk8XC9zdWI+Jmx0Oz1tYXg8c3ViPmk8XC9zdWI+Jmx0Oz0xLDAwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDY0ZFx1ZDBkY1x1YzExZFx1Yzc3NCBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc1OCBcdWQwYzBcdWM3ODVcdWM3NzQgQ1x1Yzc3Y1x1YjU0YyBcdWI5YzhcdWIyZTQsIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikdyb3dpbmcgVHJlZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkVnb24gdGFrZXMgY2FyZSBvZiBhIGdhcmRlbiB3aXRoIE4gYXBwbGUgdHJlZXMuIEhpcyByZXNwb25zaWJpbGl0aWVzIGluY2x1ZGUgdHdvIHR5cGVzIG9mIHRhc2tzOiBmZXJ0aWxpemluZyB0aGUgdHJlZXMgYW5kIGNvbXB1dGluZyBzb21lIHN0YXRpc3RpY3MgYWJvdXQgdGhlbS48XC9wPlxyXG5cclxuPHA+Rm9yIGZlcnRpbGl6aW5nIHRoZSB0cmVlcyBoZSBoYXMgc2V2ZXJhbCBib3R0bGVzIG9mIE1lZ2FCb29zdEZlcnRpbGl6ZXIsIHdoaWNoLCB3aGVuIHRyZWF0ZWQgb24gdHJlZXMsIGNhdXNlcyB0aGVtIHRvIGdyb3cgb25lIGNlbnRpbWV0ZXIgdXAgaW5zdGFudGx5LiBFdmVyeSBib3R0bGUgaGFzIGEgbGltaXRlZCBjYXBhY2l0eSBjPHN1Yj5pPFwvc3ViPiAsIHdoaWNoIGRldGVybWluZXMgdGhlIG51bWJlciBvZiB0cmVlcyBpdCBjYW4gYmUgYXBwbGllZCB0by4gTW9yZW92ZXIsIGZvciBlYWNoIGJvdHRsZSB0aGVyZSBpcyBhIG1pbmltYWwgaGVpZ2h0IGg8c3ViPmk8XC9zdWI+IG9mIHRyZWVzLCB3aGljaCBjYW4gYmUgdHJlYXRlZCB3aXRoIGl0LiBTaW5jZSBFZ29uIHdhbnRzIHRvIGhhdmUgYWxsIGhpcyB0cmVlcyBhcyBiaWcgYXMgcG9zc2libGUsIGhlIGFsd2F5cyBhcHBsaWVzIHRoZSBmZXJ0aWxpemVyIHRvIHRoZSBjPHN1Yj5pPFwvc3ViPiBzbWFsbGVzdCB0cmVlcyBjaG9zZW4gZnJvbSB0aGUgdHJlZXMgdGhhdCBhcmUgYXQgbGVhc3QgaDxzdWI+aTxcL3N1Yj4gY2VudGltZXRlcnMgaGlnaC48XC9wPlxyXG5cclxuPHA+V2hlbiBFZ29uIGNvbXB1dGVzIHN0YXRpc3RpY3MgYWJvdXQgdHJlZXMgaGUgaGFzIHRvIGRldGVybWluZSB0aGUgbnVtYmVyIG9mIHRyZWVzIHdob3NlIGhlaWdodCBpcyBpbiBzb21lIGdpdmVuIGludGVydmFsLiBFZ29uIGlzIHF1aXRlIGJ1c3kgd29ya2luZyBpbiB0aGUgZ2FyZGVuLCBzbyBoZSBhc2tlZCB5b3UgdG8gd3JpdGUgYSBwcm9ncmFtLCB0aGF0IGdpdmVuIHRoZSBsaXN0IG9mIGhpcyB0YXNrcywgY29tcHV0ZXMgdGhlIHN0YXRpc3RpY3MgZm9yIGhpbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0gZGVub3RpbmcgdGhlIG51bWJlciBvZiB0cmVlcyBpbiBFZ29uJnJzcXVvO3MgZ2FyZGVuIGFuZCB0aGUgbnVtYmVyIG9mIGhpcyB0YXNrcy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgTiBpbnRlZ2VycyBmcm9tIHRoZSByYW5nZSBbMSwgTl0gZGVzY3JpYmluZyB0aGUgaW5pdGlhbCBoZWlnaHRzIG9mIHRoZSB0cmVlcyBpbiBjZW50aW1ldGVycy4gVGhlIGZvbGxvd2luZyBNIGxpbmVzIGRlc2NyaWJlIHRoZSB0YXNrcyBpbiBjaHJvbm9sb2dpY2FsIG9yZGVyLiBFYWNoIG9mIHRob3NlIGxpbmVzIGJlZ2lucyB3aXRoIGEgY2hhcmFjdGVyIHQ8c3ViPmk8XC9zdWI+ICh0PHN1Yj5pPFwvc3ViPiA9IEYgb3IgdDxzdWI+aTxcL3N1Yj4gPSBDKSwgd2hpY2ggZGVzY3JpYmVzIHRoZSB0eXBlIG9mIHRoZSB0YXNrLjxcL3A+XHJcblxyXG48cD5JZiB0PHN1Yj5pPFwvc3ViPiA9IEYgdGhlbiB0d28gaW50ZWdlcnMgYzxzdWI+aTxcL3N1Yj4gYW5kIGg8c3ViPmk8XC9zdWI+IGZvbGxvdy4gU3VjaCBhIGxpbmUgbWVhbnMgdGhhdCBFZ29uIGFwcGxpZXMgYSBib3R0bGUgb2YgTWVnYUJvb3N0RmVydGlsaXplciB0byB0aGUgYzxzdWI+aTxcL3N1Yj4gc21hbGxlc3QgdHJlZXMgYW1vbmcgdGhvc2UgdHJlZXMgdGhhdCBhcmUgYXQgbGVhc3QgaDxzdWI+aTxcL3N1Yj4gY2VudGltZXRlcnMgaGlnaC4gV2hlbiB0aGVyZSBhcmUgbGVzcyB0aGFuIGM8c3ViPmk8XC9zdWI+IHRyZWVzIG9mIHN1Zlx1ZmIwMWNpZW50IGhlaWdodCwgaGUgYXBwbGllcyB0aGUgZmVydGlsaXplciB0byBhbGwgc3VjaCB0cmVlcyBhbmQgZGlzY2FyZHMgdGhlIGJvdHRsZSB3aXRoIHNvbWUgZmVydGlsaXplciByZW1haW5pbmcuPFwvcD5cclxuXHJcbjxwPklmIHQ8c3ViPmk8XC9zdWI+ID0gQyB0aGVuIHR3byBpbnRlZ2VycyBtaW48c3ViPmk8XC9zdWI+IGFuZCBtYXg8c3ViPmk8XC9zdWI+IGZvbGxvdy4gVGhleSBkZW5vdGUgdGhhdCBFZ29uIGhhcyB0byBjb21wdXRlIHRoZSBudW1iZXIgb2YgdHJlZXMgd2hvc2UgaGVpZ2h0IEggaXMgYmV0d2VlbiBtaW5pIGFuZCBtYXhpIGNlbnRpbWV0ZXJzIChtaW48c3ViPmk8XC9zdWI+ICZsZTsgSCAmbGU7IG1heDxzdWI+aTxcL3N1Yj4pLjxcL3A+XHJcblxyXG48cD4xICZsZTsgTiwgTSAmbGU7IDEwMCAwMDA7PGJyIFwvPlxyXG4xICZsZTsgYzxzdWI+aTxcL3N1Yj4gJmxlOyBOLCAwICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwOzxiciBcLz5cclxuMSAmbGU7IG1pbjxzdWI+aTxcL3N1Yj4gJmxlOyBtYXg8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwIDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGFzayBvZiB0eXBlIEMsIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgYXBwbGUgdHJlZXMgdGhhdCBoYXZlIHRoZSByZXF1aXJlZCBoZWlnaHQuIFRoZSBvcmRlciBvZiB0aGUgcmVzdWx0cyBzaG91bGQgY29uZm9ybSB0byB0aGUgb3JkZXIgb2YgdHlwZSBDIHRhc2tzIGluIHRoZSBpbnB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 1번