시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 256 MB6021659227.964%

문제

아날로그 다이얼이란 0부터 9까지 각 숫자 중 하나를 항상 표시하고 있는 작은 기계이다. 다이얼에는 화면에 보이는 숫자를 1 증가시킬 수 있는 버튼도 있다. (9를 1 증가시키면 0이 된다)

상근이는 이러한 아날로그 다이얼을 N개 가지고 있고, 모두 책상에 일렬로 올려 놓았다. 왼쪽 기계부터 1번기계이며, 가장 오른쪽 기계는 N번 기계이다. 또, 기계의 앞에 무엇인가를 작성할 수 있도록 종이 두 장을 놓았다.

가장 처음에 상근이는 다이얼에 보이는 숫자를 첫 번째 종이에 적는다. 그 다음 다음과 같은 행동을 M번 반복한다.

1. 두 정수 A와 B를 고른 다음, 첫 번째 종이에 작성한다. (1 ≤ A ≤ B ≤ N)

2. A번째 다이얼부터 B번째 다이얼에 적혀있는 숫자의 합을 구한 다음에 두 번째 종이에 작성한다.

3. A번째부터 B번째 다이얼의 버튼을 한 번씩 누른다.

상근이는 위와 같은 게임(?)을 모두 완료했다. 하지만, 갑자기 벽에서 정인이가 튀어나왔고, 두 번째 종이와 다이얼 N개를 모두 들고 군대로 도망가버렸다.

상근이는 첫 번째 종이만 가지고 있다. 두 번째 종이에 쓰여 있는 수를 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ M ≤ 100,000)

둘째 줄에는 가장 처음에 다이얼에 표시된 숫자가 주어진다. 이 숫자는 공백없이 주어진다.

다음 M개 줄에는 상근이가 고른 숫자인 A와 B가 주어진다. (1 ≤ A ≤ B ≤ N)

출력

출력은 총 M개 줄이다. 상근이가 구한 다이얼의 합을 순서대로 출력한다.

예제 입력 1

4 3
1234
1 4
1 4
1 4

예제 출력 1

10
14
18

예제 입력 2

4 4
1234
1 1
1 2
1 3
1 4

예제 출력 2

1
4
9
16

예제 입력 3

7 5
9081337
1 3
3 7
1 3
3 7
1 3

예제 출력 3

17
23
1
19
5
W3sicHJvYmxlbV9pZCI6IjMwMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWIwYTBcdWI4NWNcdWFkZjggXHViMmU0XHVjNzc0XHVjNWJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NDRcdWIwYTBcdWI4NWNcdWFkZjggXHViMmU0XHVjNzc0XHVjNWJjXHVjNzc0XHViNzgwIDBcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWFjMDEgXHVjMjJiXHVjNzkwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVkNTZkXHVjMGMxIFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNzkxXHVjNzQwIFx1YWUzMFx1YWNjNFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzc0XHVjNWJjXHVjNWQwXHViMjk0IFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjMjJiXHVjNzkwXHViOTdjIDEgXHVjOTlkXHVhYzAwXHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzg0XHVkMmJjXHViM2M0IFx1Yzc4OFx1YjJlNC4gKDlcdWI5N2MgMSBcdWM5OWRcdWFjMDBcdWMyZGNcdWQwYTRcdWJhNzQgMFx1Yzc3NCBcdWI0MWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjNTQ0XHViMGEwXHViODVjXHVhZGY4IFx1YjJlNFx1Yzc3NFx1YzViY1x1Yzc0NCBOXHVhYzFjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YmFhOFx1YjQ1MCBcdWNjNDVcdWMwYzFcdWM1ZDAgXHVjNzdjXHViODJjXHViODVjIFx1YzYyY1x1YjgyNCBcdWIxOTNcdWM1NThcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWFlMzBcdWFjYzRcdWJkODBcdWQxMzAgMVx1YmM4OFx1YWUzMFx1YWNjNFx1Yzc3NFx1YmE3MCwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFlMzBcdWFjYzRcdWIyOTQgTlx1YmM4OCBcdWFlMzBcdWFjYzRcdWM3NzRcdWIyZTQuIFx1YjYxMCwgXHVhZTMwXHVhY2M0XHVjNzU4IFx1YzU1ZVx1YzVkMCBcdWJiMzRcdWM1YzdcdWM3NzhcdWFjMDBcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVjODg1XHVjNzc0IFx1YjQ1MCBcdWM3YTVcdWM3NDQgXHViMTkzXHVjNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NzRcdWM1YmNcdWM1ZDAgXHViY2Y0XHVjNzc0XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM4MDFcdWIyOTRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ1ODlcdWIzZDlcdWM3NDQgTVx1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjEuIFx1YjQ1MCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHViOTdjIFx1YWNlMFx1Yjk3OCBcdWIyZTRcdWM3NGMsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzc0XHVjNWQwIFx1Yzc5MVx1YzEzMVx1ZDU1Y1x1YjJlNC4gKDEgJmxlOyBBICZsZTsgQiAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPjIuIEFcdWJjODhcdWM5ZjggXHViMmU0XHVjNzc0XHVjNWJjXHViZDgwXHVkMTMwIEJcdWJjODhcdWM5ZjggXHViMmU0XHVjNzc0XHVjNWJjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1YyBcdWIyZTRcdWM3NGNcdWM1ZDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjNzkxXHVjMTMxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4zLiBBXHViYzg4XHVjOWY4XHViZDgwXHVkMTMwIEJcdWJjODhcdWM5ZjggXHViMmU0XHVjNzc0XHVjNWJjXHVjNzU4IFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjIwNFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhYzhjXHVjNzg0KD8pXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM2NDRcdWI4Y2NcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzExXHVjNzkwXHVhZTMwIFx1YmNiZFx1YzVkMFx1YzExYyBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVkMjgwXHVjNWI0XHViMDk4XHVjNjU0XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NFx1YzY0MCBcdWIyZTRcdWM3NzRcdWM1YmMgTlx1YWMxY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHViNGU0XHVhY2UwIFx1YWQ3MFx1YjMwMFx1Yjg1YyBcdWIzYzRcdWI5ZGRcdWFjMDBcdWJjODRcdWI4MzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NFx1YjljYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDI1MCwwMDAsIDEgJmxlOyBNICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YjJlNFx1Yzc3NFx1YzViY1x1YzVkMCBcdWQ0NWNcdWMyZGNcdWI0MWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM1YzZcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWNlMFx1Yjk3OCBcdWMyMmJcdWM3OTBcdWM3NzggQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBICZsZTsgQiAmbGU7IE4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1Y2QxZCBNXHVhYzFjIFx1YzkwNFx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWQ2Y1x1ZDU1YyBcdWIyZTRcdWM3NzRcdWM1YmNcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzAwMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJFRE9LUyIsImRlc2NyaXB0aW9uIjoiPHA+THVrYSBpcyBub3QgcGF5aW5nIGF0dGVudGlvbiBpbiBjbGFzcyBhZ2Fpbiwgd2hpbGUgdGhlIHRlYWNoZXIgaXMgZXhwbGFpbmluZyByZWRveCByZWFjdGlvbnMuIEluc3RlYWQgb2YgcGF5aW5nIGF0dGVudGlvbiwgaGUgaXMgcGxheWluZyB3aXRoIGFuYWxvZyBkaWFscy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW4gYW5hbG9nIGRpYWwgaXMgYSBzbWFsbCBkZXZpY2Ugd2hpY2ggYWx3YXlzIHNob3dzIG9uZSBkaWdpdCBiZXR3ZWVuIDAgYW5kIDkuIEl0IGFsc28gY29udGFpbnMgYSBzbWFsbCBidXR0b24gd2hpY2ggaW5jcmVhc2VzIHRoZSBudW1iZXIgYnkgMSAodW5sZXNzIGl0IGlzIDksIGluIHdoaWNoIGNhc2UgaXQgaXMgY2hhbmdlZCB0byAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+THVrYSBoYXMgTiBzdWNoIGRpYWxzIG9uIGhpcyBkZXNrLCBudW1iZXJlZCAxIHRvIE4gbGVmdCB0byByaWdodCwgYW5kIHR3byBzaGVldHMgb2YgcGFwZXIgZm9yIGhpbSB0byB3cml0ZSBvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+THVrYSYjMzk7cyBnYW1lIHN0YXJ0cyB3aXRoIGhpbSBzZXR0aW5nIHRoZSBkaWFscyBpbiBzb21lIHN0YXJ0aW5nIGNvbmZpZ3VyYXRpb24sIHdoaWNoIGhlIHRoZW4gd3JpdGVzIG9udG8gdGhlIGZpcnN0IHNoZWV0LiBMdWthIHRoZW4gZG9lcyB0aGUgZm9sbG93aW5nIE0gdGltZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Q2hvb3NlIHR3byBpbnRlZ2VycyBBIGFuZCBCICgxICZsZTsgQSAmbGU7IEIgJmxlOyBOKSBhbmQgd3JpdGUgdGhlbSBkb3duIG9uIHRoZSBmaXJzdCBzaGVldC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+Q2FsY3VsYXRlIHRoZSBzdW0gb2YgbnVtYmVycyBvbiBkaWFscyBudW1iZXJlZCBiZXR3ZWVuIEEgYW5kIEIgKGluY2x1c2l2ZSksIGFuZCB3cml0ZSB0aGUgc3VtIGRvd24gb24gdGhlIHNlY29uZCBzaGVldC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+UHJlc3MgdGhlIGJ1dHRvbiBvbmNlIG9uIGFsbCBkaWFscyBudW1iZXJlZCBiZXR3ZWVuIEEgYW5kIEIuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SnVzdCBhcyBoZSBoYWQgZmluaXNoZWQgaGlzIGdhbWUsIHRoZSB0ZWFjaGVyIG5vdGljZWQgaGltLCBhbmQgdG9vayBhd2F5IGFsbCBoaXMgZGlhbHMgYW5kIHRoZSBzZWNvbmQgc2hlZXQgb2YgcGFwZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBjb250ZW50cyBvZiB0aGUgZmlyc3Qgc2hlZXQsIGhlbHAgaGltIGNhbGN1bGF0ZSB0aGUgbnVtYmVycyBvbiB0aGUgc2Vjb25kIHNoZWV0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0gKDEgJmxlOyBOICZsZTsgMjUwMDAwLCAxICZsZTsgTSAmbGU7IDEwMDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0aGUgaW5pdGlhbCBjb25maWd1cmF0aW9uIG9mIHRoZSBkaWFscywgTiBkZWNpbWFsIGRpZ2l0cyB3aXRoIG5vIHNwYWNlcy4gVGhlIGZpcnN0IGRpZ2l0IGlzIHRoZSBudW1iZXIgaW5pdGlhbGx5IG9uIGRpYWwgMSwgdGhlIHNlY29uZCBkaWdpdCB0aGUgbnVtYmVyIG9uIGRpYWwgMiBhbmQgc28gb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBBIGFuZCBCICgxICZsZTsgQSAmbGU7IEIgJmxlOyBOKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgTSBsaW5lcywgdGhlIHN1bXMgY2FsY3VsYXRlZCBieSBMdWthLCBpbiBvcmRlciBpbiB3aGljaCBoZSBjYWxjdWxhdGVkIHRoZW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #3 6번