시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 128 10 7 14.286%

문제

택희는 자료구조 수업시간에 다음과 같은 자료구조를 만들었다. 이 자료구조는 택희가 좋아하는 숫자 N개로 이루어진 수열에 아래와 같은 연산을 수행하는 것이다.

연산 형식 설명 예제
1 A B X A번째부터 B번째까지 수를 X로 바꾼다. (9,8,7,6,5,4,3,2,1)
-> 1 3 5 0 ->
(9,8,0,0,0,4,3,2,1)
2 A B X A번째 수에는 X를, A+1번째 수에는 2*X를, ..., B번째 수에는 (B-A+1)*X를 더한다. (9,8,7,6,5,4,3,2,1)
-> 2 3 5 2 ->
(9,8,9,10,11,4,3,2,1)
3 C X C번째 숫자 바로 앞에 X를 삽입한다. (9,8,7,6,5,4,3,2,1)
-> 3 4 100 ->
(9,8,7,100,6,5,4,3,2,1)
4 A B A번째 수부터 B번째 수를 더해서 출력한다. (2,18,7,6,1,4,7,7,2)
-> 4 6 7 ->
결과: 11

택희가 좋아하는 숫자 N개로 이루어진 수열과 택희가 수행한 연산 목록이 주어졌을 때, 4번이 나올때 마다 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 Q가 주어진다. (1<=N,Q<=100,000) N은 처음 수열의 크기이고, Q는 택희가 수행한 연산의 개수이다.

둘째 줄에는 처음 수열이 주어진다. 수열의 수는 100,000을 넘지않는 음이 아닌 정수이며, 공백으로 구분되어져 있다.

셋째 줄부터 Q개의 줄에는 택희가 수행한 연산이 차례대로 주어진다. 1<=X<=100, 1<=A<=B<=현재 수열의 크기, 1<=C<=현재 수열의 크기+1

출력

4번 연산이 나올때 마다 합을 출력한다. 합이 32비트 정수를 넘어갈 수 있다.

예제 입력 1

5 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5

예제 출력 1

4
0
25
W3sicHJvYmxlbV9pZCI6IjI4NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWI4Y2MgXHVhZDZjXHVjODcwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQwZGRcdWQ3NmNcdWIyOTQgXHVjNzkwXHViOGNjXHVhZDZjXHVjODcwIFx1YzIxOFx1YzVjNVx1YzJkY1x1YWMwNFx1YzVkMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YjhjY1x1YWQ2Y1x1Yzg3MFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWM3OTBcdWI4Y2NcdWFkNmNcdWM4NzBcdWIyOTQgXHVkMGRkXHVkNzZjXHVhYzAwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMmJcdWM3OTAgTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo2MCU7XCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDoxMCU7XCI+XHJcblx0XHRcdFx0XHVjNWYwXHVjMGIwIFx1ZDYxNVx1YzJkZDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDoyNSU7XCI+XHJcblx0XHRcdFx0XHVjMTI0XHViYTg1PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjI1JTtcIj5cclxuXHRcdFx0XHRcdWM2MDhcdWM4MWM8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDEgQSBCIFg8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdEFcdWJjODhcdWM5ZjhcdWJkODBcdWQxMzAgQlx1YmM4OFx1YzlmOFx1YWU0Y1x1YzljMCBcdWMyMThcdWI5N2MgWFx1Yjg1YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQoOSw4LDcsNiw1LDQsMywyLDEpPGJyIFwvPlxyXG5cdFx0XHRcdC0mZ3Q7IDEgMyA1IDAgLSZndDs8YnIgXC8+XHJcblx0XHRcdFx0KDksOCw8c3Ryb25nPjAsMCwwLDxcL3N0cm9uZz40LDMsMiwxKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQyIEEgQiBYPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHRBXHViYzg4XHVjOWY4IFx1YzIxOFx1YzVkMFx1YjI5NCBYXHViOTdjLCBBKzFcdWJjODhcdWM5ZjggXHVjMjE4XHVjNWQwXHViMjk0IDIqWFx1Yjk3YywgLi4uLCBCXHViYzg4XHVjOWY4IFx1YzIxOFx1YzVkMFx1YjI5NCAoQi1BKzEpKlhcdWI5N2MgXHViMzU0XHVkNTVjXHViMmU0LjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0KDksOCw3LDYsNSw0LDMsMiwxKTxiciBcLz5cclxuXHRcdFx0XHQtJmd0OyAyIDMgNSAyIC0mZ3Q7PGJyIFwvPlxyXG5cdFx0XHRcdCg5LDgsPHN0cm9uZz45LDEwLDExLDxcL3N0cm9uZz40LDMsMiwxKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQzIEMgWDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0Q1x1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTAgXHViYzE0XHViODVjIFx1YzU1ZVx1YzVkMCBYXHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU1Y1x1YjJlNC48XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdCg5LDgsNyw2LDUsNCwzLDIsMSk8YnIgXC8+XHJcblx0XHRcdFx0LSZndDsgMyA0IDEwMCAtJmd0OzxiciBcLz5cclxuXHRcdFx0XHQoOSw4LDcsPHN0cm9uZz4xMDAsPFwvc3Ryb25nPjYsNSw0LDMsMiwxKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ0IEEgQjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0QVx1YmM4OFx1YzlmOCBcdWMyMThcdWJkODBcdWQxMzAgQlx1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgXHViMzU0XHVkNTc0XHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdCgyLDE4LDcsNiwxLDQsNyw3LDIpPGJyIFwvPlxyXG5cdFx0XHRcdC0mZ3Q7IDQgNiA3IC0mZ3Q7PGJyIFwvPlxyXG5cdFx0XHRcdFx1YWNiMFx1YWNmYzogMTE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlxyXG5cdFx1ZDBkZFx1ZDc2Y1x1YWMwMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMjJiXHVjNzkwIE5cdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1YWNmYyBcdWQwZGRcdWQ3NmNcdWFjMDAgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YzVmMFx1YzBiMCBcdWJhYTlcdWI4NWRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgNFx1YmM4OFx1Yzc3NCBcdWIwOThcdWM2MmNcdWI1NGMgXHViOWM4XHViMmU0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBRXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbHQ7PU4sUSZsdDs9MTAwLDAwMCkgTlx1Yzc0MCBcdWNjOThcdWM3NGMgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YWNlMCwgUVx1YjI5NCBcdWQwZGRcdWQ3NmNcdWFjMDAgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjOThcdWM3NGMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzIxOFx1YjI5NCAxMDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMFx1YzU0YVx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmE3MCwgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHVjMTRiXHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBRXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwZGRcdWQ3NmNcdWFjMDAgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAxJmx0Oz1YJmx0Oz0xMDAsIDEmbHQ7PUEmbHQ7PUImbHQ7PVx1ZDYwNFx1YzdhYyBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwLCAxJmx0Oz1DJmx0Oz1cdWQ2MDRcdWM3YWMgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCsxPFwvcD5cclxuXHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdDRcdWJjODggXHVjNWYwXHVjMGIwXHVjNzc0IFx1YjA5OFx1YzYyY1x1YjU0YyBcdWI5YzhcdWIyZTQgXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTY5XHVjNzc0IDMyXHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVVBJVCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gZ290IHRpcmVkIG9mIGltcGxlbWVudGluZyBhbGwga2luZHMgb2YgZGF0YSBzdHJ1Y3R1cmVzIGZvciBkaWZmZXJlbnQgdGFza3MuIFNvLCBoZSBkZWNpZGVkIHRvIGNvbWUgdXAgd2l0aCB0aGUgdWx0aW1hdGUgc3RydWN0dXJlLCBvbmUgdGhhdCB3aWxsIGFsbG93IGhpbSB0byBtYW5pcHVsYXRlIHdpdGggaGlzIGZhdm9yaXRlIG51bWJlciBzZXF1ZW5jZS4gSGVscCBoaW0hPFwvcD5cclxuXHJcbjxwPk1pcmtvIHdpbGwgZ2l2ZSB5b3UgaGlzIG51bWJlciBzZXF1ZW5jZSwgYW5kIGEgc2VxdWVuY2Ugb2YgcXVlcmllcyB5b3UgbXVzdCBleGVjdXRlLiBFYWNoIHF1ZXJ5IGVpdGhlciBhc2tzIGZvciBpbmZvcm1hdGlvbiwgb3IgbW9kaWZpZXMgdGhlIGV4aXN0aW5nIHNlcXVlbmNlLiBQb3NzaWJsZSBxdWVyeSB0eXBlcyBhcmUgbGlzdGVkIGJlbG93LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NjAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDoxMCVcIj5RdWVyeSB0eXBlPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjI1JVwiPkRlc2NyaXB0aW9uPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjI1JVwiPkV4YW1wbGU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEgQSBCIFg8XC90ZD5cclxuXHRcdFx0PHRkPlNldCBhbGwgZWxlbWVudHMgZnJvbSBBdGggdG8gQnRoIChpbmNsdXNpdmUpIHRvIHZhbHVlIFg8XC90ZD5cclxuXHRcdFx0PHRkPig5LDgsNyw2LDUsNCwzLDIsMSk8YnIgXC8+XHJcblx0XHRcdC0mZ3Q7IDEgMyA1IDAgLSZndDs8YnIgXC8+XHJcblx0XHRcdCg5LDgsPHN0cm9uZz4wLDAsMCw8XC9zdHJvbmc+NCwzLDIsMSk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MiBBIEIgWDxcL3RkPlxyXG5cdFx0XHQ8dGQ+QWRkIFggdG8gQXRoIGVsZW1lbnQsIDIqWCB0byAoQSsxKXRoLCAmaGVsbGlwOywgYW5kIChCLUErMSkqWCB0byB0aGUgQnRoIGVsZW1lbnQ8XC90ZD5cclxuXHRcdFx0PHRkPig5LDgsNyw2LDUsNCwzLDIsMSk8YnIgXC8+XHJcblx0XHRcdC0mZ3Q7IDIgMyA1IDIgLSZndDs8YnIgXC8+XHJcblx0XHRcdCg5LDgsPHN0cm9uZz45LDEwLDExLDxcL3N0cm9uZz40LDMsMiwxKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zIEMgWDxcL3RkPlxyXG5cdFx0XHQ8dGQ+SW5zZXJ0IG5ldyBlbGVtZW50IHdpdGggdmFsdWUgWCBpbW1lZGlhdGVseSBiZWZvcmUgdGhlIEN0aCBlbGVtZW50PFwvdGQ+XHJcblx0XHRcdDx0ZD4oOSw4LDcsNiw1LDQsMywyLDEpPGJyIFwvPlxyXG5cdFx0XHQtJmd0OyAzIDQgMTAwIC0mZ3Q7PGJyIFwvPlxyXG5cdFx0XHQoOSw4LDcsPHN0cm9uZz4xMDAsPFwvc3Ryb25nPjYsNSw0LDMsMiwxKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD40IEEgQjxcL3RkPlxyXG5cdFx0XHQ8dGQ+RmluZCB0aGUgc3VtIG9mIGFsbCBlbGVtZW50cyBmcm9tIEF0aCB0byBCdGg8XC90ZD5cclxuXHRcdFx0PHRkPigyLDE4LDcsNiwxLDQsNyw3LDIpPGJyIFwvPlxyXG5cdFx0XHQtJmd0OyA0IDYgNyAtJmd0OzxiciBcLz5cclxuXHRcdFx0cmVzdWx0OiAxMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4gYW5kIFEgKDEgJmxlOyBOLCBRICZsZTsgMTAwIDAwMCksIHRoZSBzdGFydGluZyBzZXF1ZW5jZSBsZW5ndGggYW5kIHRoZSBudW1iZXIgb2YgcXVlcmllcy48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIHRoZSBzdGFydGluZyBzZXF1ZW5jZS4gU2VxdWVuY2UgY29uc2lzdHMgb2Ygbm9uLW5lZ2F0aXZlIGludGVnZXJzIG5vdCBncmVhdGVyIHRoYW4gMTAwMDAwIHRoYXQgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBRIGxpbmVzIGNvbnRhaW4gcXVlcmllcyBpbiB0aGUgZm9ybWF0IGRlc2NyaWJlZCBhYm92ZS4gSW4gYWxsIHF1ZXJpZXMsIDEgJmxlOyBYICZsZTsgMTAwLCAxICZsZTsgQSAmbGU7IEIgJmxlOyBjdXJyZW50U2VxdWVuY2VMZW5ndGgsIGFuZCAxICZsZTsgQyAmbGU7IGN1cnJlbnRTZXF1ZW5jZUxlbmd0aCsxLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHF1ZXJ5IG9mIHR5cGUgNCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgcmVxdWVzdGVkIHN1bS48XC9wPlxyXG5cclxuPHA+Tm90ZTogbm90aWNlIHRoYXQgc29tZSBzdW1zIHdvbiZyc3F1bzt0IGZpdCBpbnRvIDMyLWJpdCBpbnRlZ2VyIGRhdGEgdHlwZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=