시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB52724215847.447%

문제

지안지아는 똑같은 크기의 벽돌을 쌓아서 벽을 만들고 있다. 이 벽은 n열의 벽돌로 되어 있는데, 각 열은 왼쪽부터 오른쪽으로 차례대로 0부터 n-1까지 번호가 매겨져 있다. 각 열의 높이는 서로 다를 수 있다. 열의 높이는 이 열에 쌓인 벽돌의 수이다.

지안지아는 다음과 같이 벽을 만든다. 처음에는 어느 열에도 벽돌이 없다. 다음, 지안지아는 k 단계에 걸쳐 벽돌을 더하거나 또는 빼거나 한다. k 단계가 다 끝나면 벽을 다 쌓은 것이다. 매 단계마다 지안지아는 연속된 벽돌 열의 범위와 높이 h를 받고, 다음과 같은 절차에 따라 정해진 일을 한다.

  • 벽돌을 더하는 단계에서는, 지안지아는 주어진 범위에 해당하는 열들 중 h장 미만의 벽돌이 쌓인 열들에 벽돌을 더해서 정확히 벽돌 h장이 쌓이게 한다. h장 이상 벽돌이 있는 열에는 아무 일도 하지 않는다.
  • 벽돌을 빼는 단계에는, 지안지아는 주어진 범위에 해당하는 열들 중 h장 초과의 벽돌이 쌓인 열들에서 벽돌을 빼서 정확히 벽돌 h장이 쌓이게 한다. h장 이하 벽돌이 있는 열에는 아무 일도 하지 않는다.

당신이 할 일은 벽의 최종 모양을 결정하는 것이다.

10열의 벽돌이 있고 6단계를 거쳐 벽을 만든다고 가정하자. 아래 표의 모든 범위는 양 끝을 포함한다. 각 단계가 끝났을 때 벽의 모양은 아래 그림과 같다.

단계 하는 일 범위 높이
0 더하기 1열부터 8열까지 4
1 빼기 4열부터 9열까지 1
2 빼기 3열부터 6열까지 5
3 더하기 0열부터 5열까지 3
4 더하기 2열 5
5 빼기 6열부터 7열까지 0

처음에 모든 열에는 벽돌이 없기 때문에, 단계 0이 끝나면 1열부터 8열까지는 모두 4장의 벽돌이 있다. 0열과 9열은 비어 있다. 단계 1에서는, 4열부터 8열까지는 벽돌이 빠져서 모든 열에 각각 벽돌이 1장이 있고, 9열은 계속 비어 있다. 주어진 범위 밖인 0열부터 3열은 아무 변화가 없다. 단계 2는 아무 변화가 없는데, 3열부터 6열까지 5장을 초과하여 벽돌이 있는 열이 없기 때문이다. 단계 3이 끝나면 0, 4, 5열의 벽돌은 3장으로 늘어난다. 단계 4가 끝나면 2열에는 벽돌이 5장 있다. 단계 5는 6열과 7열의 모든 벽돌을 없앤다.

각 단계에서 하는 일이 주어졌을 때, 모든 단계가 끝난 다음 각 열에 남아 있는 벽돌의 수를 계산하시오.

입력

첫째 줄에 벽에 있는 열의 수 n과 단계의 수 k가 주어진다.

둘째 줄부터 총 k개의 줄에 걸쳐서 단계 i에서 하는 일이 주어진다. op, left, right, height로 이루어져 있으며, 아래와 같은 의미를 갖는다.

  • op: 1이면 더하는 단계, 2이면 빼는 단계이다.
  • left와 right: 각 단계에 해당하는 열의 범위이다. left 열에서 시작하고, right 열에서 끝난다. (양 끝점 left와 right도 포함된다) 항상 left ≤ right이다.
  • height: 각 단계에서 주어지는 높이이다.

출력

모든 단계가 끝난 다음 각 열에 남아 있는 벽돌의 수를 한 줄에 하나씩 순서대로 출력한다.

서브태스크

모든 부분문제에서 모든 단계의 높이 파라미터는 100,000 이하인 음이 아닌 정수이다.

번호 배점 제한
1 8

1 ≤ n ≤ 10,000, 1 ≤ k ≤ 5,000

2 24

1 ≤ n ≤ 100,000, 1 ≤ k ≤ 500,000, 모든 더하기 단계는 모든 빼기 단계보다 앞에 옴

3 29

1 ≤ n ≤ 100,000, 1 ≤ k ≤ 500,000

4 39

1 ≤ n ≤ 2,000,000, 1 ≤ k ≤ 500,000

예제 입력 1

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

예제 출력 1

3
4
5
4
3
3
0
0
1
0
W3sicHJvYmxlbV9pZCI6IjEwMDcwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViY2JkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWIyOTQgXHViNjExXHVhYzE5XHVjNzQwIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjYmRcdWIzY2NcdWM3NDQgXHVjMzEzXHVjNTQ0XHVjMTFjIFx1YmNiZFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViY2JkXHVjNzQwIG5cdWM1ZjRcdWM3NTggXHViY2JkXHViM2NjXHViODVjIFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWMwMSBcdWM1ZjRcdWM3NDAgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgMFx1YmQ4MFx1ZDEzMCBuLTFcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM1ZjRcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNWY0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWM3NzQgXHVjNWY0XHVjNWQwIFx1YzMxM1x1Yzc3OCBcdWJjYmRcdWIzY2NcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJjYmRcdWM3NDQgXHViOWNjXHViNGUwXHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDBcdWIyOTQgXHVjNWI0XHViMjkwIFx1YzVmNFx1YzVkMFx1YjNjNCBcdWJjYmRcdWIzY2NcdWM3NzQgXHVjNWM2XHViMmU0LiBcdWIyZTRcdWM3NGMsIFx1YzljMFx1YzU0OFx1YzljMFx1YzU0NFx1YjI5NCBrIFx1YjJlOFx1YWNjNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViY2JkXHViM2NjXHVjNzQ0IFx1YjM1NFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWI2MTBcdWIyOTQgXHViZTdjXHVhYzcwXHViMDk4IFx1ZDU1Y1x1YjJlNC4gayBcdWIyZThcdWFjYzRcdWFjMDAgXHViMmU0IFx1YjA1ZFx1YjA5OFx1YmE3NCBcdWJjYmRcdWM3NDQgXHViMmU0IFx1YzMxM1x1Yzc0MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjllNCBcdWIyZThcdWFjYzRcdWI5YzhcdWIyZTQgXHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0XHViMjk0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWJjYmRcdWIzY2MgXHVjNWY0XHVjNzU4IFx1YmM5NFx1YzcwNFx1YzY0MCBcdWIxOTJcdWM3NzQgaFx1Yjk3YyBcdWJjMWJcdWFjZTAsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjODA4XHVjYzI4XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWM4MTVcdWQ1NzRcdWM5YzQgXHVjNzdjXHVjNzQ0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJjYmRcdWIzY2NcdWM3NDQgXHViMzU0XHVkNTU4XHViMjk0IFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExY1x1YjI5NCwgXHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljNCBcdWJjOTRcdWM3MDRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzVmNFx1YjRlNCBcdWM5MTEgaFx1YzdhNSBcdWJiZjhcdWI5Y2NcdWM3NTggXHViY2JkXHViM2NjXHVjNzc0IFx1YzMxM1x1Yzc3OCBcdWM1ZjRcdWI0ZTRcdWM1ZDAgXHViY2JkXHViM2NjXHVjNzQ0IFx1YjM1NFx1ZDU3NFx1YzExYyBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViY2JkXHViM2NjIGhcdWM3YTVcdWM3NzQgXHVjMzEzXHVjNzc0XHVhYzhjIFx1ZDU1Y1x1YjJlNC4gaFx1YzdhNSBcdWM3NzRcdWMwYzEgXHViY2JkXHViM2NjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM1ZjRcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0IFx1Yzc3Y1x1YjNjNCBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJjYmRcdWIzY2NcdWM3NDQgXHViZTdjXHViMjk0IFx1YjJlOFx1YWNjNFx1YzVkMFx1YjI5NCwgXHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljNCBcdWJjOTRcdWM3MDRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzVmNFx1YjRlNCBcdWM5MTEgaFx1YzdhNSBcdWNkMDhcdWFjZmNcdWM3NTggXHViY2JkXHViM2NjXHVjNzc0IFx1YzMxM1x1Yzc3OCBcdWM1ZjRcdWI0ZTRcdWM1ZDBcdWMxMWMgXHViY2JkXHViM2NjXHVjNzQ0IFx1YmU3Y1x1YzExYyBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViY2JkXHViM2NjIGhcdWM3YTVcdWM3NzQgXHVjMzEzXHVjNzc0XHVhYzhjIFx1ZDU1Y1x1YjJlNC4gaFx1YzdhNSBcdWM3NzRcdWQ1NTggXHViY2JkXHViM2NjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM1ZjRcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0IFx1Yzc3Y1x1YjNjNCBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc3NCBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YmNiZFx1Yzc1OCBcdWNkNWNcdWM4ODUgXHViYWE4XHVjNTkxXHVjNzQ0IFx1YWNiMFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjEwXHVjNWY0XHVjNzU4IFx1YmNiZFx1YjNjY1x1Yzc3NCBcdWM3ODhcdWFjZTAgNlx1YjJlOFx1YWNjNFx1Yjk3YyBcdWFjNzBcdWNjZDAgXHViY2JkXHVjNzQ0IFx1YjljY1x1YjRlMFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1YzU0NFx1Yjc5OCBcdWQ0NWNcdWM3NTggXHViYWE4XHViNGUwIFx1YmM5NFx1YzcwNFx1YjI5NCBcdWM1OTEgXHViMDVkXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YjJlOFx1YWNjNFx1YWMwMCBcdWIwNWRcdWIwYWNcdWM3NDQgXHViNTRjIFx1YmNiZFx1Yzc1OCBcdWJhYThcdWM1OTFcdWM3NDAgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo1MCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdWIyZThcdWFjYzQ8XC90aD5cclxuXHRcdFx0PHRoPlx1ZDU1OFx1YjI5NCBcdWM3N2M8XC90aD5cclxuXHRcdFx0PHRoPlx1YmM5NFx1YzcwNDxcL3RoPlxyXG5cdFx0XHQ8dGg+XHViMTkyXHVjNzc0PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWIzNTRcdWQ1NThcdWFlMzA8XC90ZD5cclxuXHRcdFx0PHRkPjFcdWM1ZjRcdWJkODBcdWQxMzAgOFx1YzVmNFx1YWU0Y1x1YzljMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWJlN2NcdWFlMzA8XC90ZD5cclxuXHRcdFx0PHRkPjRcdWM1ZjRcdWJkODBcdWQxMzAgOVx1YzVmNFx1YWU0Y1x1YzljMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWJlN2NcdWFlMzA8XC90ZD5cclxuXHRcdFx0PHRkPjNcdWM1ZjRcdWJkODBcdWQxMzAgNlx1YzVmNFx1YWU0Y1x1YzljMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWIzNTRcdWQ1NThcdWFlMzA8XC90ZD5cclxuXHRcdFx0PHRkPjBcdWM1ZjRcdWJkODBcdWQxMzAgNVx1YzVmNFx1YWU0Y1x1YzljMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWIzNTRcdWQ1NThcdWFlMzA8XC90ZD5cclxuXHRcdFx0PHRkPjJcdWM1ZjQ8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHViZTdjXHVhZTMwPFwvdGQ+XHJcblx0XHRcdDx0ZD42XHVjNWY0XHViZDgwXHVkMTMwIDdcdWM1ZjRcdWFlNGNcdWM5YzA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWJhYThcdWI0ZTAgXHVjNWY0XHVjNWQwXHViMjk0IFx1YmNiZFx1YjNjY1x1Yzc3NCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWIyZThcdWFjYzQgMFx1Yzc3NCBcdWIwNWRcdWIwOThcdWJhNzQgMVx1YzVmNFx1YmQ4MFx1ZDEzMCA4XHVjNWY0XHVhZTRjXHVjOWMwXHViMjk0IFx1YmFhOFx1YjQ1MCA0XHVjN2E1XHVjNzU4IFx1YmNiZFx1YjNjY1x1Yzc3NCBcdWM3ODhcdWIyZTQuIDBcdWM1ZjRcdWFjZmMgOVx1YzVmNFx1Yzc0MCBcdWJlNDRcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWIyZThcdWFjYzQgMVx1YzVkMFx1YzExY1x1YjI5NCwgNFx1YzVmNFx1YmQ4MFx1ZDEzMCA4XHVjNWY0XHVhZTRjXHVjOWMwXHViMjk0IFx1YmNiZFx1YjNjY1x1Yzc3NCBcdWJlNjBcdWM4MzhcdWMxMWMgXHViYWE4XHViNGUwIFx1YzVmNFx1YzVkMCBcdWFjMDFcdWFjMDEgXHViY2JkXHViM2NjXHVjNzc0IDFcdWM3YTVcdWM3NzQgXHVjNzg4XHVhY2UwLCA5XHVjNWY0XHVjNzQwIFx1YWNjNFx1YzE4ZCBcdWJlNDRcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYzk0XHVjNzA0IFx1YmMxNlx1Yzc3OCAwXHVjNWY0XHViZDgwXHVkMTMwIDNcdWM1ZjRcdWM3NDAgXHVjNTQ0XHViYjM0IFx1YmNjMFx1ZDY1NFx1YWMwMCBcdWM1YzZcdWIyZTQuIFx1YjJlOFx1YWNjNCAyXHViMjk0IFx1YzU0NFx1YmIzNCBcdWJjYzBcdWQ2NTRcdWFjMDAgXHVjNWM2XHViMjk0XHViMzcwLCAzXHVjNWY0XHViZDgwXHVkMTMwIDZcdWM1ZjRcdWFlNGNcdWM5YzAgNVx1YzdhNVx1Yzc0NCBcdWNkMDhcdWFjZmNcdWQ1NThcdWM1ZWMgXHViY2JkXHViM2NjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM1ZjRcdWM3NzQgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHViMmU4XHVhY2M0IDNcdWM3NzQgXHViMDVkXHViMDk4XHViYTc0IDAsIDQsIDVcdWM1ZjRcdWM3NTggXHViY2JkXHViM2NjXHVjNzQwIDNcdWM3YTVcdWM3M2NcdWI4NWMgXHViMjk4XHVjNWI0XHViMDljXHViMmU0LiBcdWIyZThcdWFjYzQgNFx1YWMwMCBcdWIwNWRcdWIwOThcdWJhNzQgMlx1YzVmNFx1YzVkMFx1YjI5NCBcdWJjYmRcdWIzY2NcdWM3NzQgNVx1YzdhNSBcdWM3ODhcdWIyZTQuIFx1YjJlOFx1YWNjNCA1XHViMjk0IDZcdWM1ZjRcdWFjZmMgN1x1YzVmNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViY2JkXHViM2NjXHVjNzQ0IFx1YzVjNlx1YzU2NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9hMzlhNTRiZC0yNjkyLTRjNDAtOWU1Ny05OWJmYjNmZjk5OTJcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI3OXB4OyBoZWlnaHQ6IDUwOHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1YjJlOFx1YWNjNFx1YWMwMCBcdWIwNWRcdWIwOWMgXHViMmU0XHVjNzRjIFx1YWMwMSBcdWM1ZjRcdWM1ZDAgXHViMGE4XHVjNTQ0IFx1Yzc4OFx1YjI5NCBcdWJjYmRcdWIzY2NcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2JkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM1ZjRcdWM3NTggXHVjMjE4IG5cdWFjZmMgXHViMmU4XHVhY2M0XHVjNzU4IFx1YzIxOCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWNkMWQga1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YjJlOFx1YWNjNCBpXHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBvcCwgbGVmdCwgcmlnaHQsIGhlaWdodFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1Yzc1OFx1YmJmOFx1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b3A6IDFcdWM3NzRcdWJhNzQgXHViMzU0XHVkNTU4XHViMjk0IFx1YjJlOFx1YWNjNCwgMlx1Yzc3NFx1YmE3NCBcdWJlN2NcdWIyOTQgXHViMmU4XHVhY2M0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5sZWZ0XHVjNjQwIHJpZ2h0OiBcdWFjMDEgXHViMmU4XHVhY2M0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWM1ZjRcdWM3NTggXHViYzk0XHVjNzA0XHVjNzc0XHViMmU0LiBsZWZ0IFx1YzVmNFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjZTAsIHJpZ2h0IFx1YzVmNFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOWNcdWIyZTQuIChcdWM1OTEgXHViMDVkXHVjODEwIGxlZnRcdWM2NDAgcmlnaHRcdWIzYzQgXHVkM2VjXHVkNTY4XHViNDFjXHViMmU0KSBcdWQ1NmRcdWMwYzEgbGVmdCAmbGU7IHJpZ2h0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5oZWlnaHQ6IFx1YWMwMSBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmFhOFx1YjRlMCBcdWIyZThcdWFjYzRcdWFjMDAgXHViMDVkXHViMDljIFx1YjJlNFx1Yzc0YyBcdWFjMDEgXHVjNWY0XHVjNWQwIFx1YjBhOFx1YzU0NCBcdWM3ODhcdWIyOTQgXHViY2JkXHViM2NjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInN1YnRhc2sxIjoiPHA+MSAmbGU7IG4gJmxlOyAxMCwwMDAsIDEgJmxlOyBrICZsZTsgNSwwMDA8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPjEgJmxlOyBuICZsZTsgMTAwLDAwMCwgMSAmbGU7IGsgJmxlOyA1MDAsMDAwLCBcdWJhYThcdWI0ZTAgXHViMzU0XHVkNTU4XHVhZTMwIFx1YjJlOFx1YWNjNFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViZTdjXHVhZTMwIFx1YjJlOFx1YWNjNFx1YmNmNFx1YjJlNCBcdWM1NWVcdWM1ZDAgXHVjNjM0PFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4xICZsZTsgbiAmbGU7IDEwMCwwMDAsIDEgJmxlOyBrICZsZTsgNTAwLDAwMDxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+MSAmbGU7IG4gJmxlOyAyLDAwMCwwMDAsIDEgJmxlOyBrICZsZTsgNTAwLDAwMDxcL3A+XHJcbiIsImN1c3RvbV9zdWJ0YXNrX3Njb3JpbmdfYiI6IjxwPlx1YmFhOFx1YjRlMCBcdWJkODBcdWJkODRcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHViYWE4XHViNGUwIFx1YjJlOFx1YWNjNFx1Yzc1OCBcdWIxOTJcdWM3NzQgXHVkMzBjXHViNzdjXHViYmY4XHVkMTMwXHViMjk0IDEwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc4IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjEwMDcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2FsbCIsImRlc2NyaXB0aW9uIjoiPHA+Smlhbi1KaWEgaXMgYnVpbGRpbmcgYSB3YWxsIGJ5IHN0YWNraW5nIGJyaWNrcyBvZiB0aGUgc2FtZSBzaXplIHRvZ2V0aGVyLiBUaGlzIHdhbGwgY29uc2lzdHMgb2YgY29sdW1ucyBvZiBicmlja3MsIHdoaWNoIGFyZSBudW1iZXJlZCAwIHRvIG4tMSBmcm9tIGxlZnQgdG8gcmlnaHQuIFRoZSBjb2x1bW5zIG1heSBoYXZlIGRpZmZlcmVudCBoZWlnaHRzLiBUaGUgaGVpZ2h0IG9mIGEgY29sdW1uIGlzIHRoZSBudW1iZXIgb2YgYnJpY2tzIGluIGl0LjxcL3A+XHJcblxyXG48cD5KaWFuLUppYSBidWlsZHMgdGhlIHdhbGwgYXMgZm9sbG93cy4gSW5pdGlhbGx5IHRoZXJlIGFyZSBubyBicmlja3MgaW4gYW55IGNvbHVtbi4gVGhlbiwgSmlhbi1KaWEgZ29lcyB0aHJvdWdoIGsgcGhhc2VzIG9mIGFkZGluZyBvciByZW1vdmluZyBicmlja3MuIFRoZSBidWlsZGluZyBwcm9jZXNzIGNvbXBsZXRlcyB3aGVuIGFsbCBrIHBoYXNlcyBhcmUgZmluaXNoZWQuIEluIGVhY2ggcGhhc2UgSmlhbi1KaWEgaXMgZ2l2ZW4gYSByYW5nZSBvZiBjb25zZWN1dGl2ZSBicmljayBjb2x1bW5zIGFuZCBhIGhlaWdodCBoLCBhbmQgaGUgZG9lcyB0aGUgZm9sbG93aW5nIHByb2NlZHVyZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JbiBhbiBhZGRpbmcgcGhhc2UsIEppYW4tSmlhIGFkZHMgYnJpY2tzIHRvIHRob3NlIGNvbHVtbnMgaW4gdGhlIGdpdmVuIHJhbmdlIHRoYXQgaGF2ZSBsZXNzIHRoYW4gaCBicmlja3MsIHNvIHRoYXQgdGhleSBoYXZlIGV4YWN0bHkgaCBicmlja3MuIEhlIGRvZXMgbm90aGluZyBvbiB0aGUgY29sdW1ucyBoYXZpbmcgaCBvciBtb3JlIGJyaWNrcy48XC9saT5cclxuXHQ8bGk+SW4gYSByZW1vdmluZyBwaGFzZSwgSmlhbi1KaWEgcmVtb3ZlcyBicmlja3MgZnJvbSB0aG9zZSBjb2x1bW5zIGluIHRoZSBnaXZlbiByYW5nZSB0aGF0IGhhdmUgbW9yZSB0aGFuIGggYnJpY2tzLCBzbyB0aGF0IHRoZXkgaGF2ZSBleGFjdGx5IGggYnJpY2tzLiBIZSBkb2VzIG5vdGhpbmcgb24gdGhlIGNvbHVtbnMgaGF2aW5nIGggYnJpY2tzIG9yIGxlc3MuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGRldGVybWluZSB0aGUgZmluYWxzaGFwZSBvZiB0aGUgd2FsbC48XC9wPlxyXG5cclxuPHA+V2UgYXNzdW1lIHRoYXQgdGhlcmUgYXJlIDEwIGJyaWNrIGNvbHVtbnMgYW5kIDYgd2FsbCBidWlsZGluZyBwaGFzZXMuIEFsbCByYW5nZXMgaW4gdGhlIGZvbGxvd2luZyB0YWJsZSBhcmUgaW5jbHVzaXZlLiBEaWFncmFtcyBvZiB0aGUgd2FsbCBhZnRlciBlYWNoIHBoYXNlIGFyZSBzaG93biBiZWxvdy48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjUwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPnBoYXNlPFwvdGg+XHJcblx0XHRcdDx0aD50eXBlPFwvdGg+XHJcblx0XHRcdDx0aD5yYW5nZTxcL3RoPlxyXG5cdFx0XHQ8dGg+aGVpZ2h0PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD5hZGQ8XC90ZD5cclxuXHRcdFx0PHRkPmNvbHVtbnMgMSB0byA4PFwvdGQ+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPnJlbW92ZTxcL3RkPlxyXG5cdFx0XHQ8dGQ+Y29sdW1ucyA0IHRvIDk8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+cmVtb3ZlPFwvdGQ+XHJcblx0XHRcdDx0ZD5jb2x1bW5zIDMgdG8gNjxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD5hZGQ8XC90ZD5cclxuXHRcdFx0PHRkPmNvbHVtbnMgMCB0byA1PFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPmFkZDxcL3RkPlxyXG5cdFx0XHQ8dGQ+Y29sdW1uIDI8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+cmVtb3ZlPFwvdGQ+XHJcblx0XHRcdDx0ZD5jb2x1bW5zIDYgdG8gNzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+U2luY2UgYWxsIGNvbHVtbnMgYXJlIGluaXRpYWxseSBlbXB0eSwgYWZ0ZXIgcGhhc2UgMCBlYWNoIG9mIHRoZSBjb2x1bW5zIDEgdG8gOCB3aWxsIGhhdmUgNCBicmlja3MuIENvbHVtbnMgMCBhbmQgOSByZW1haW4gZW1wdHkuIEluIHBoYXNlIDEsIHRoZSBicmlja3MgYXJlIHJlbW92ZWQgZnJvbSBjb2x1bW5zIDQgdG8gOCB1bnRpbCBlYWNoIG9mIHRoZW0gaGFzIDEgYnJpY2ssIGFuZCBjb2x1bW4gOSByZW1haW5zIGVtcHR5LiBDb2x1bW5zIDAgdG8gMywgd2hpY2ggYXJlIG91dCBvZiB0aGUgZ2l2ZW4gcmFuZ2UsIHJlbWFpbiB1bmNoYW5nZWQuIFBoYXNlIDIgbWFrZXMgbm8gY2hhbmdlIHNpbmNlIGNvbHVtbnMgMyB0byA2IGRvIG5vdCBoYXZlIG1vcmUgdGhhbiA1IGJyaWNrcy4gQWZ0ZXIgcGhhc2UgMyB0aGUgbnVtYmVycyBvZiBicmlja3MgaW4gY29sdW1ucyAwLCA0LCBhbmQgNSBpbmNyZWFzZSB0byAzLiBUaGVyZSBhcmUgNSBicmlja3MgaW4gY29sdW1uIDIgYWZ0ZXIgcGhhc2UgNC4gUGhhc2UgNSByZW1vdmVzIGFsbCBicmlja3MgZnJvbSBjb2x1bW5zIDYgYW5kIDcuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYTM5YTU0YmQtMjY5Mi00YzQwLTllNTctOTliZmIzZmY5OTkyXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyNzlweDsgaGVpZ2h0OiA1MDhweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBwaGFzZXMsIHBsZWFzZSBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBicmlja3MgaW4gZWFjaCBjb2x1bW4gYWZ0ZXIgYWxsIHBoYXNlcyBhcmUgZmluaXNoZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPmxpbmUgMTogbiwgay48XC9saT5cclxuXHQ8bGk+bGluZSAyK2kgKDAgJmxlOyBpICZsZTsgay0xKTogb3BbaV0sIGxlZnRbaV0sIHJpZ2h0W2ldLCBoZWlnaHRbaV0uXHJcblx0PHVsPlxyXG5cdFx0PGxpPm46IHRoZSBudW1iZXIgb2YgY29sdW1ucyBvZiB0aGUgd2FsbC48XC9saT5cclxuXHRcdDxsaT5rOiB0aGUgbnVtYmVyIG9mIHBoYXNlcy48XC9saT5cclxuXHRcdDxsaT5vcDogdGhlIHR5cGUgb2YgcGhhc2UgaTogMSBmb3IgYW4gYWRkaW5nIHBoYXNlIGFuZCAyIGZvciBhIHJlbW92aW5nIHBoYXNlLCBmb3IgMCAmbGU7IGkgJmxlOyBrLTEuPFwvbGk+XHJcblx0XHQ8bGk+bGVmdFtpXSBhbmQgcmlnaHRbaV06IHRoZSByYW5nZSBvZiBjb2x1bW5zIGluIHBoYXNlIGkgc3RhcnRzIHdpdGggY29sdW1uIGxlZnRbaV0gYW5kIGVuZHMgd2l0aCBjb2x1bW4gcmlnaHRbaV0gKGluY2x1ZGluZyBib3RoIGVuZHBvaW50cyBsZWZ0W2ldIGFuZCByaWdodFtpXSksIGZvciAwICZsZTsgaSAmbGU7IGstMS4gWW91IHdpbGwgYWx3YXlzIGhhdmUgbGVmdFtpXSAmbGU7IHJpZ2h0W2ldLjxcL2xpPlxyXG5cdFx0PGxpPmhlaWdodFtpXTogdGhlIGhlaWdodCBwYXJhbWV0ZXIgb2YgcGhhc2UgaSwgZm9yIDAgJmxlOyBpICZsZTsgay0xLjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgeW91ciByZXN1bHRzIGJ5IHBsYWNpbmcgdGhlIGZpbmFsIG51bWJlciBvZiBicmlja3MgaW4gY29sdW1uIGksIGZvciAwICZsZTsgaSAmbGU7IG4tMS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic3VidGFzazEiOiI8cD4xICZsZTsgbiAmbGU7IDEwLDAwMCwgMSAmbGU7IGsgJmxlOyA1LDAwMDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+MSAmbGU7IG4gJmxlOyAxMDAsMDAwLCAxICZsZTsgayAmbGU7IDUwMCwwMDAsIGFsbCBhZGRpbmcgcGhhc2VzIGFyZSBiZWZvcmUgYWxsIHJlbW92aW5nIHBoYXNlczxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+MSAmbGU7IG4gJmxlOyAxMDAsMDAwLCAxICZsZTsgayAmbGU7IDUwMCwwMDA8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPjEgJmxlOyBuICZsZTsgMiwwMDAsMDAwLCAxICZsZTsgayAmbGU7IDUwMCwwMDA8XC9wPlxyXG4iLCJjdXN0b21fc3VidGFza19zY29yaW5nX2IiOiI8cD5Gb3IgYWxsc3VidGFza3MgdGhlIGhlaWdodCBwYXJhbWV0ZXJzIG9mIGFsbCBwaGFzZXMgYXJlIG5vbm5lZ2F0aXZlIGludGVnZXJzIGxlc3Mgb3IgZXF1YWwgdG8gMTAwLDAwMC48XC9wPlxyXG4ifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2014 > Day 1 2번

  • 문제를 만든 사람: Bartosz Tarnawski

채점 및 기타 정보

  • 예제는 채점하지 않는다.