시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 1024 MB20427919.149%

문제

Whiteking은 지역 꾸미기 게임을 하려고 한다. 그가 꾸미려는 지역은 단위 격자가 1 × 1 정사각형 타일로 표현되는 N × N 격자판 형태이며, 가장 왼쪽 위 타일의 좌표가 (1, 1)이고, 가장 오른쪽 아래 타일의 좌표는 (N, N)이다. 이 때 타일의 좌표란 타일의 오른쪽 아래 꼭짓점의 좌표를 말한다. 이로부터 (xy)에 위치한 타일은 [x-1x]×[y-1y]에 해당하는 정사각형 영역을 차지함을 알 수 있다. 각 타일은 고유한 아름다움 값을 가지는데, 초기에 모든 타일의 아름다움 값은 0이다.

지역 꾸미기 게임은 다음 세 가지 행동을 통해 점수를 얻는 게임이다.

  1. 가로 또는 세로로 직선을 그어 격자판을 서로 다른 구역으로 분할한다. 처음에는 N × N 크기의 구역 한 개만 존재하며, 만약 가로와 세로로 직선을 한 번씩 긋는다면 구역은 네 개로 나뉘어질 것이다.
  2. 타일을 하나 선택해 해당 타일이 속한 구역을 꾸민다. 이 결과 꾸며진 구역에 속한 모든 타일의 아름다움은 X만큼 증가한다.
  3. 격자판에 포함되는 직사각형을 하나 선택해 그 안에 속한 타일 중 가장 아름다운 타일의 아름다움만큼 점수를 획득한다.

Whiteking은 자신이 3번 행동을 할 때마다 얻게 될 점수를 미리 알고 싶다. 따라서 그는 자신이 할 행동을 다음과 같은 쿼리로 표현해 여러분에게 알려줄 것이다.

  • 1 a b : a가 0이면 x=b, a가 1이면 y=b로 표현되는 직선을 긋는다.
  • 2 a b X : (a, b)에 위치한 타일을 선택해 2번 행동을 한다.
  • 3 a b c d : 가장 왼쪽 위 타일의 좌표가 (a, b)이고 가장 오른쪽 아래 타일의 좌표가 (c, d)인 직사각형을 선택하여 3번 행동을 한다.

Whiteking을 위해 3번 쿼리가 주어질 때마다 얻을 수 있는 점수를 구해보자!

입력

첫째 줄에는 두 양의 정수 N, Q가 주어진다.

둘째 줄부터 Q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 

출력

3번 쿼리가 들어올 때마다 그 시점에서 Whiteking이 얻을 수 있는 최대 점수를 출력해라. 

제한

  • 1 ≤ ≤ 100,000
  • 1 ≤ Q ≤ 300,000
  • 모든 1번 쿼리에 대하여 0 ≤ a ≤ 1, 1 ≤ b ≤ N-1
  • 모든 2번 쿼리에 대하여 1 ≤ a, bN, -109X ≤ 109
  • 모든 3번 쿼리에 대하여 1 ≤ acN, 1 ≤ bdN
  • 2번 쿼리는 최대 25,000번만 주어진다.
  • 3번 쿼리는 하나 이상 주어진다.

예제 입력 1

3 7
3 1 1 3 3
2 1 3 -3
3 1 1 3 3
1 0 1
2 1 1 4
3 2 2 3 3
3 1 1 3 3

예제 출력 1

0
-3
-3
1
W3sicHJvYmxlbV9pZCI6IjE4OTQzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjOWMwXHVjNWVkIFx1YWZiOFx1YmJmOFx1YWUzMCBcdWFjOGNcdWM3ODQiLCJkZXNjcmlwdGlvbiI6IjxwPldoaXRla2luZ1x1Yzc0MCBcdWM5YzBcdWM1ZWQgXHVhZmI4XHViYmY4XHVhZTMwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWFjMDAgXHVhZmI4XHViYmY4XHViODI0XHViMjk0IFx1YzljMFx1YzVlZFx1Yzc0MCBcdWIyZThcdWM3MDQgXHVhY2E5XHVjNzkwXHVhYzAwJm5ic3A7MSAmdGltZXM7IDEgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBjMFx1Yzc3Y1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWIyOTQgPGVtPk48XC9lbT4gJnRpbWVzOyA8ZW0+TjxcL2VtPiBcdWFjYTlcdWM3OTBcdWQzMTAgXHVkNjE1XHVkMGRjXHVjNzc0XHViYTcwLCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWQwYzBcdWM3N2NcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwICgxLCAxKVx1Yzc3NFx1YWNlMCwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVkMGMwXHVjNzdjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAoPGVtPk48XC9lbT4sIDxlbT5OPFwvZW0+KVx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YjU0YyBcdWQwYzBcdWM3N2NcdWM3NTggXHVjODhjXHVkNDVjXHViNzgwIFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LiZuYnNwO1x1Yzc3NFx1Yjg1Y1x1YmQ4MFx1ZDEzMCAoPGVtPng8XC9lbT4sJm5ic3A7PGVtPnk8XC9lbT4pXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWQwYzBcdWM3N2NcdWM3NDAgWzxlbT54LTE8XC9lbT4sJm5ic3A7PGVtPng8XC9lbT5dJnRpbWVzO1s8ZW0+eS0xPFwvZW0+LCZuYnNwOzxlbT55PFwvZW0+XVx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YzYwMVx1YzVlZFx1Yzc0NCBcdWNjMjhcdWM5YzBcdWQ1NjhcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSZuYnNwO1x1ZDBjMFx1Yzc3Y1x1Yzc0MCBcdWFjZTBcdWM3MjBcdWQ1NWMgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmMwIFx1YWMxMlx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTRcdWIzNzAsJm5ic3A7XHVjZDA4XHVhZTMwXHVjNWQwJm5ic3A7XHViYWE4XHViNGUwIFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YzAgXHVhYzEyXHVjNzQwIDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzVlZCBcdWFmYjhcdWJiZjhcdWFlMzAgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjJlNFx1Yzc0YyBcdWMxMzggXHVhYzAwXHVjOWMwIFx1ZDU4OVx1YjNkOVx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVhYzAwXHViODVjIFx1YjYxMFx1YjI5NCBcdWMxMzhcdWI4NWNcdWI4NWMgXHVjOWMxXHVjMTIwXHVjNzQ0IFx1YWRmOFx1YzViNCBcdWFjYTlcdWM3OTBcdWQzMTBcdWM3NDQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFkNmNcdWM1ZWRcdWM3M2NcdWI4NWMgXHViZDg0XHVkNTYwXHVkNTVjXHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDBcdWIyOTQgPGVtPk48XC9lbT4gJnRpbWVzOyZuYnNwOzxlbT5OPFwvZW0+IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFkNmNcdWM1ZWQgXHVkNTVjIFx1YWMxY1x1YjljYyBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzAsIFx1YjljY1x1YzU3ZCBcdWFjMDBcdWI4NWNcdWM2NDAgXHVjMTM4XHViODVjXHViODVjIFx1YzljMVx1YzEyMFx1Yzc0NCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YWUwYlx1YjI5NFx1YjJlNFx1YmE3NCBcdWFkNmNcdWM1ZWRcdWM3NDAgXHViMTI0IFx1YWMxY1x1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjRcdWM5YzggXHVhYzgzXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQwYzBcdWM3N2NcdWM3NDQgXHVkNTU4XHViMDk4IFx1YzEyMFx1ZDBkZFx1ZDU3NCBcdWQ1NzRcdWIyZjkgXHVkMGMwXHVjNzdjXHVjNzc0IFx1YzE4ZFx1ZDU1YyBcdWFkNmNcdWM1ZWRcdWM3NDQgXHVhZmI4XHViYmZjXHViMmU0LiBcdWM3NzQgXHVhY2IwXHVhY2ZjIFx1YWZiOFx1YmE3MFx1YzljNCBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHVjMThkXHVkNTVjIFx1YmFhOFx1YjRlMCBcdWQwYzBcdWM3N2NcdWM3NTggXHVjNTQ0XHViOTg0XHViMmU0XHVjNmMwXHVjNzQwIDxlbT5YPFwvZW0+XHViOWNjXHVkMDdjIFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhY2E5XHVjNzkwXHVkMzEwXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkNTU4XHViMDk4IFx1YzEyMFx1ZDBkZFx1ZDU3NCBcdWFkZjggXHVjNTQ4XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWQwYzBcdWM3N2MgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVkMGMwXHVjNzdjXHVjNzU4IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZjMFx1YjljY1x1ZDA3YyBcdWM4MTBcdWMyMThcdWI5N2MgXHVkNjhkXHViNGRkXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPldoaXRla2luZ1x1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NzQgM1x1YmM4OCBcdWQ1ODlcdWIzZDlcdWM3NDQgXHVkNTYwIFx1YjU0Y1x1YjljOFx1YjJlNCBcdWM1YmJcdWFjOGMgXHViNDIwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWJiZjhcdWI5YWMgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YWRmOFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVkNTYwIFx1ZDU4OVx1YjNkOVx1Yzc0NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Y2ZmY1x1YjlhY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NzQgXHVjNWVjXHViN2VjXHViZDg0XHVjNWQwXHVhYzhjIFx1YzU0Y1x1YjgyNFx1YzkwNCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGNvZGU+MSBhJm5ic3A7YjxcL2NvZGU+Jm5ic3A7OiA8ZW0+YTxcL2VtPlx1YWMwMCAwXHVjNzc0XHViYTc0IDxlbT54PWI8XC9lbT4sIDxlbT5hPFwvZW0+XHVhYzAwIDFcdWM3NzRcdWJhNzQgPGVtPnk9YjxcL2VtPlx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWIyOTQmbmJzcDtcdWM5YzFcdWMxMjBcdWM3NDQgXHVhZTBiXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT48Y29kZT4yIGEgYiZuYnNwO1g8XC9jb2RlPiZuYnNwOzogKDxlbT5hPFwvZW0+LCA8ZW0+YjxcL2VtPilcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTVjIFx1ZDBjMFx1Yzc3Y1x1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NzQgMlx1YmM4OCBcdWQ1ODlcdWIzZDlcdWM3NDQgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT48Y29kZT4zIGEgYiBjIGQ8XC9jb2RlPiZuYnNwOzogXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVkMGMwXHVjNzdjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCAoPGVtPmE8XC9lbT4sIDxlbT5iPFwvZW0+KVx1Yzc3NFx1YWNlMCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWQwYzBcdWM3N2NcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwICg8ZW0+YzxcL2VtPiwgPGVtPmQ8XC9lbT4pXHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWM1ZWMgM1x1YmM4OCBcdWQ1ODlcdWIzZDlcdWM3NDQgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPldoaXRla2luZ1x1Yzc0NCBcdWM3MDRcdWQ1NzQgM1x1YmM4OCBcdWNmZmNcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0Y1x1YjljOFx1YjJlNCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCZuYnNwO1x1YjQ1MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IDxlbT5OPFwvZW0+LCA8ZW0+UTxcL2VtPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgPGVtPlE8XC9lbT5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+M1x1YmM4OCBcdWNmZmNcdWI5YWNcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjJjIFx1YjU0Y1x1YjljOFx1YjJlNCBcdWFkZjggXHVjMmRjXHVjODEwXHVjNWQwXHVjMTFjIFdoaXRla2luZ1x1Yzc3NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1Yjc3Yy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IDxlbT5OJm5ic3A7PFwvZW0+JmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyA8ZW0+UTxcL2VtPiAmbGU7IDMwMCwwMDA8XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIDFcdWJjODggXHVjZmZjXHViOWFjXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyZuYnNwOzAgJmxlOyA8ZW0+YTxcL2VtPiAmbGU7IDEsIDEmbmJzcDsmbGU7IDxlbT5iPFwvZW0+ICZsZTsgTi0xPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCAyXHViYzg4IFx1Y2ZmY1x1YjlhY1x1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMmbmJzcDsxICZsZTsgPGVtPmE8XC9lbT4sIDxlbT5iPFwvZW0+ICZsZTsgPGVtPk48XC9lbT4sIC0xMDxzdXA+OTxcL3N1cD4gJmxlOyA8ZW0+WDxcL2VtPiAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgM1x1YmM4OCBcdWNmZmNcdWI5YWNcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjJm5ic3A7MSAmbGU7IDxlbT5hPFwvZW0+ICZsZTsgPGVtPmM8XC9lbT4gJmxlOyA8ZW0+TjxcL2VtPiwgMSAmbGU7IDxlbT5iPFwvZW0+ICZsZTsgPGVtPmQ8XC9lbT4gJmxlOyA8ZW0+TjxcL2VtPjxcL2xpPlxyXG5cdDxsaT4yXHViYzg4IFx1Y2ZmY1x1YjlhY1x1YjI5NCBcdWNkNWNcdWIzMDAgMjUsMDAwXHViYzg4XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+M1x1YmM4OCBcdWNmZmNcdWI5YWNcdWIyOTQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxODk0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhcmRlbmluZyBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5XaGl0ZWtpbmcgaXMgZ29pbmcgdG8gcGxheSBhIGxvY2FsIGRlY29yYXRpbmcgZ2FtZS4gVGhlIGFyZWEgaGUgd2FudHMgdG8gZGVjb3JhdGUgaXMgaW4gdGhlIGZvcm0gb2YgYW4gJE4gXFx0aW1lcyBOJCBncmlkIGluIHdoaWNoIHRoZSB1bml0IGdyaWQgaXMgcmVwcmVzZW50ZWQgYnkgJDEgXFx0aW1lcyAxJCBzcXVhcmUgdGlsZXMsIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgdG9wIGxlZnQgdGlsZSBhcmUgJCgxLCAxKSQsIGFuZCB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIGJvdHRvbSByaWdodCB0aWxlIGFyZSAkKE4sIE4pJC4gVGh1cyB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHRpbGUgcmVmZXIgdG8gdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBsb3dlciByaWdodCBjb3JuZXIgb2YgdGhlIHRpbGUuIEZyb20gdGhpcywgaXQgY2FuIGJlIHNlZW4gdGhhdCB0aGUgdGlsZSBsb2NhdGVkIGF0ICQoeCwgeSkkIG9jY3VwaWVzIGEgc3F1YXJlIGFyZWEgY29ycmVzcG9uZGluZyB0byAkW3gtMSwgeF0gXFx0aW1lcyBbeS0xLCB5XSQuIEVhY2ggdGlsZSBoYXMgaXRzIG93biBiZWF1dHkgdmFsdWUsIGluaXRpYWxseSBhbGwgdGlsZXMgaGF2ZSBhIGJlYXV0eSB2YWx1ZSBvZiAkMCQuPFwvcD5cclxuXHJcbjxwPlRoZSBsb2NhbCBkZWNvcmF0aW5nIGdhbWUgaXMgYSBnYW1lIHdoZXJlIHRoZSBwbGF5ZXIgZWFybnMgcG9pbnRzIHVzaW5nIHRoZSBmb2xsb3dpbmcgdGhyZWUgYWN0aW9ucy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5EaXZpZGUgdGhlIGdyaWQgaW50byBkaWZmZXJlbnQgem9uZXMgYnkgZHJhd2luZyBhIHN0cmFpZ2h0IGxpbmUgaG9yaXpvbnRhbGx5IG9yIHZlcnRpY2FsbHkuIEluaXRpYWxseSwgdGhlcmUgaXMgb25seSBvbmUgYXJlYSBvZiBzaXplICROIFxcdGltZXMgTiQuIFRoZSBsaW5lcyBhcmUgaW5maW5pdGUgaW4gYm90aCBkaXJlY3Rpb25zOiBmb3IgZXhhbXBsZSwgaWYgeW91IGRyYXcgYSBzdHJhaWdodCBsaW5lIGhvcml6b250YWxseSBhbmQgYW5vdGhlciBvbmUgdmVydGljYWxseSwgdGhlIGluaXRpYWwgYXJlYSB3aWxsIGJlIGRpdmlkZWQgaW50byBhIHRvdGFsIG9mIGZvdXIgYXJlYXMuPFwvbGk+XHJcblx0PGxpPlNlbGVjdCBhIHRpbGUgYW5kIGRlY29yYXRlIHRoZSBhcmVhIGl0IGJlbG9uZ3MgdG8uIEFzIGEgcmVzdWx0LCB0aGUgYmVhdXR5IG9mIGFsbCB0aWxlcyBpbiB0aGUgZGVjb3JhdGVkIGFyZWEgaXMgaW5jcmVhc2VkIGJ5IGEgZ2l2ZW4gdmFsdWUuPFwvbGk+XHJcblx0PGxpPlNlbGVjdCBhIHJlY3RhbmdsZSBvbiB0aGUgZ3JpZCBhbmQgZWFybiBwb2ludHMgZXF1YWwgdG8gdGhlIGJlYXV0eSBvZiB0aGUgbW9zdCBiZWF1dGlmdWwgdGlsZSBpbiBpdC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5XaGl0ZWtpbmcgd2FudHMgdG8ga25vdyBpbiBhZHZhbmNlIGhvdyBtYW55IHBvaW50cyBoZSB3aWxsIGVhcm4gZm9yIGV2ZXJ5IGFjdGlvbiBvZiB0aGUgdGhpcmQgdHlwZS4gU28gaGUgd2lsbCBzaG93IHlvdSBhbiBvcmRlcmVkIGxpc3Qgb2YgYWN0aW9ucyBoZSBpcyBnb2luZyB0byBwZXJmb3JtLiBUaGUgYWN0aW9ucyB3aWxsIGJlIGdpdmVuIGluIHRoZSBmb2xsb3dpbmcgZm9ybWF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiZxdW90Ozxjb2RlPjE8XC9jb2RlPiAkYSQgJGIkJnF1b3Q7OiBJZiAkYSQgaXMgJDAkLCBkcmF3IHRoZSBzdHJhaWdodCBsaW5lICR4ID0gYiQsIGFuZCBpZiAkYSQgaXMgJDEkLCBkcmF3ICR5ID0gYiQuPFwvbGk+XHJcblx0PGxpPiZxdW90Ozxjb2RlPjI8XC9jb2RlPiAkYSQgJGIkICRYJCZxdW90OzogU2VsZWN0IHRoZSB0aWxlIGxvY2F0ZWQgYXQgJChhLCBiKSQgZGVjb3JhdGUgdGhlIGFyZWEgaXQgYmVsb25ncyB0bywgaW5jcmVhc2luZyB0aGUgYmVhdXR5IG9mIGFsbCB0aWxlcyBpbiBpdCBieSAkWCQuPFwvbGk+XHJcblx0PGxpPiZxdW90Ozxjb2RlPjM8XC9jb2RlPiAkYSQgJGIkICRjJCAkZCQmcXVvdDs6IFNlbGVjdCBhIHJlY3RhbmdsZSB3aXRoICQoYSwgYikkIGFzIHRoZSB0b3AgbGVmdCB0aWxlIGFuZCAkKGMsIGQpJCBhcyB0aGUgYm90dG9tIHJpZ2h0IHRpbGUsIGFuZCBlYXJuIHBvaW50cyBlcXVhbCB0byB0aGUgYmVhdXR5IG9mIHRoZSBtb3N0IGJlYXV0aWZ1bCB0aWxlIGluIGl0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkhlbHAgV2hpdGVraW5nIGZpbmQgd2hhdCB3aWxsIGJlIHRoZSBzY29yZSBmb3IgZXZlcnkgYWN0aW9uIG9mIHRoZSB0aGlyZCB0eXBlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJFEkICgkMSBcXGxlIE4gXFxsZSAxMF41JCwgJDEgXFxsZSBRIFxcbGUgMyBcXGNkb3QgMTBeNSQpLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0ICRRJCBsaW5lcyBkZXNjcmliZXMgYW4gYWN0aW9uIGluIHRoZSBmb3JtYXQgc2hvd24gaW4gdGhlIHByb2JsZW0gc3RhdGVtZW50LjxcL3A+XHJcblxyXG48cD5Gb3IgYW4gYWN0aW9uIG9mIHR5cGUgPGNvZGU+MTxcL2NvZGU+LCAkMCBcXGxlIGEgXFxsZSAxJCBhbmQgJDEgXFxsZSBiIFxcbGUgTiAtIDEkLjxcL3A+XHJcblxyXG48cD5Gb3IgYW4gYWN0aW9uIG9mIHR5cGUgPGNvZGU+MjxcL2NvZGU+LCAkMSBcXGxlIGEsIGIgXFxsZSBOJCBhbmQgJC0xMF45IFxcbGUgWCBcXGxlIDEwXjkkLjxcL3A+XHJcblxyXG48cD5Gb3IgYW4gYWN0aW9uIG9mIHR5cGUgPGNvZGU+MzxcL2NvZGU+LCAkMSBcXGxlIGEgXFxsZSBjIFxcbGUgTiQgYW5kICQxIFxcbGUgYiBcXGxlIGQgXFxsZSBOJC48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIGF0IG1vc3QgJDI1XFwsMDAwJCBhY3Rpb25zIG9mIHR5cGUgJDIkLCBhbmQgYXQgbGVhc3QgJDEkIGFjdGlvbiBvZiB0eXBlICQzJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgYWN0aW9uIG9mIHRoZSB0aGlyZCB0eXBlLCBwcmludCB0aGUgc2NvcmUgdGhhdCBXaGl0ZWtpbmcgd2lsbCBnZXQgZm9yIHRoYXQgYWN0aW9uLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup G번

Camp > Petrozavodsk Programming Camp > Summer 2020 > Day 6: Korean Contest C번