시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 356 91 44 27.160%

문제

아날로그 다이얼이란 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
W3sicHJvYmxlbV9pZCI6IjMwMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWIwYTBcdWI4NWNcdWFkZjggXHViMmU0XHVjNzc0XHVjNWJjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1NDRcdWIwYTBcdWI4NWNcdWFkZjggXHViMmU0XHVjNzc0XHVjNWJjXHVjNzc0XHViNzgwIDBcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWFjMDEgXHVjMjJiXHVjNzkwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVkNTZkXHVjMGMxIFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNzkxXHVjNzQwIFx1YWUzMFx1YWNjNFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzc0XHVjNWJjXHVjNWQwXHViMjk0IFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjMjJiXHVjNzkwXHViOTdjIDEgXHVjOTlkXHVhYzAwXHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzg0XHVkMmJjXHViM2M0IFx1Yzc4OFx1YjJlNC4gKDlcdWI5N2MgMSBcdWM5OWRcdWFjMDBcdWMyZGNcdWQwYTRcdWJhNzQgMFx1Yzc3NCBcdWI0MWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjNTQ0XHViMGEwXHViODVjXHVhZGY4IFx1YjJlNFx1Yzc3NFx1YzViY1x1Yzc0NCBOXHVhYzFjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YmFhOFx1YjQ1MCBcdWNjNDVcdWMwYzFcdWM1ZDAgXHVjNzdjXHViODJjXHViODVjIFx1YzYyY1x1YjgyNCBcdWIxOTNcdWM1NThcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWFlMzBcdWFjYzRcdWJkODBcdWQxMzAgMVx1YmM4OFx1YWUzMFx1YWNjNFx1Yzc3NFx1YmE3MCwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFlMzBcdWFjYzRcdWIyOTQgTlx1YmM4OCBcdWFlMzBcdWFjYzRcdWM3NzRcdWIyZTQuIFx1YjYxMCwgXHVhZTMwXHVhY2M0XHVjNzU4IFx1YzU1ZVx1YzVkMCBcdWJiMzRcdWM1YzdcdWM3NzhcdWFjMDBcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVjODg1XHVjNzc0IFx1YjQ1MCBcdWM3YTVcdWM3NDQgXHViMTkzXHVjNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NzRcdWM1YmNcdWM1ZDAgXHViY2Y0XHVjNzc0XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM4MDFcdWIyOTRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ1ODlcdWIzZDlcdWM3NDQgTVx1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDEuIFx1YjQ1MCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHViOTdjIFx1YWNlMFx1Yjk3OCBcdWIyZTRcdWM3NGMsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzc0XHVjNWQwIFx1Yzc5MVx1YzEzMVx1ZDU1Y1x1YjJlNC4gKDEgJmxlOyBBICZsZTsgQiAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlxyXG5cdDIuIEFcdWJjODhcdWM5ZjggXHViMmU0XHVjNzc0XHVjNWJjXHViZDgwXHVkMTMwIEJcdWJjODhcdWM5ZjggXHViMmU0XHVjNzc0XHVjNWJjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1YyBcdWIyZTRcdWM3NGNcdWM1ZDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjNzkxXHVjMTMxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQzLiBBXHViYzg4XHVjOWY4XHViZDgwXHVkMTMwIEJcdWJjODhcdWM5ZjggXHViMmU0XHVjNzc0XHVjNWJjXHVjNzU4IFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjIwNFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhYzhjXHVjNzg0KD8pXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM2NDRcdWI4Y2NcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzExXHVjNzkwXHVhZTMwIFx1YmNiZFx1YzVkMFx1YzExYyBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVkMjgwXHVjNWI0XHViMDk4XHVjNjU0XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NFx1YzY0MCBcdWIyZTRcdWM3NzRcdWM1YmMgTlx1YWMxY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHViNGU0XHVhY2UwIFx1YWQ3MFx1YjMwMFx1Yjg1YyBcdWIzYzRcdWI5ZGRcdWFjMDBcdWJjODRcdWI4MzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NFx1YjljYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyNTAsMDAwLCAxICZsZTsgTSAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWIyZTRcdWM3NzRcdWM1YmNcdWM1ZDAgXHVkNDVjXHVjMmRjXHViNDFjIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFjZTBcdWI5NzggXHVjMjJiXHVjNzkwXHVjNzc4IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSAmbGU7IEIgJmxlOyBOKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWNkMWQgTVx1YWMxYyBcdWM5MDRcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFkNmNcdWQ1NWMgXHViMmU0XHVjNzc0XHVjNWJjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSRURPS1MiLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgaXMgbm90IHBheWluZyBhdHRlbnRpb24gaW4gY2xhc3MgYWdhaW4sIHdoaWxlIHRoZSB0ZWFjaGVyIGlzIGV4cGxhaW5pbmcgcmVkb3ggcmVhY3Rpb25zLiBJbnN0ZWFkIG9mIHBheWluZyBhdHRlbnRpb24sIGhlIGlzIHBsYXlpbmcgd2l0aCBhbmFsb2cgZGlhbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFuIGFuYWxvZyBkaWFsIGlzIGEgc21hbGwgZGV2aWNlIHdoaWNoIGFsd2F5cyBzaG93cyBvbmUgZGlnaXQgYmV0d2VlbiAwIGFuZCA5LiBJdCBhbHNvIGNvbnRhaW5zIGEgc21hbGwgYnV0dG9uIHdoaWNoIGluY3JlYXNlcyB0aGUgbnVtYmVyIGJ5IDEgKHVubGVzcyBpdCBpcyA5LCBpbiB3aGljaCBjYXNlIGl0IGlzIGNoYW5nZWQgdG8gMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkx1a2EgaGFzIE4gc3VjaCBkaWFscyBvbiBoaXMgZGVzaywgbnVtYmVyZWQgMSB0byBOIGxlZnQgdG8gcmlnaHQsIGFuZCB0d28gc2hlZXRzIG9mIHBhcGVyIGZvciBoaW0gdG8gd3JpdGUgb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkx1a2EmIzM5O3MgZ2FtZSBzdGFydHMgd2l0aCBoaW0gc2V0dGluZyB0aGUgZGlhbHMgaW4gc29tZSBzdGFydGluZyBjb25maWd1cmF0aW9uLCB3aGljaCBoZSB0aGVuIHdyaXRlcyBvbnRvIHRoZSBmaXJzdCBzaGVldC4gTHVrYSB0aGVuIGRvZXMgdGhlIGZvbGxvd2luZyBNIHRpbWVzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkNob29zZSB0d28gaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEgJmxlOyBCICZsZTsgTikgYW5kIHdyaXRlIHRoZW0gZG93biBvbiB0aGUgZmlyc3Qgc2hlZXQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkNhbGN1bGF0ZSB0aGUgc3VtIG9mIG51bWJlcnMgb24gZGlhbHMgbnVtYmVyZWQgYmV0d2VlbiBBIGFuZCBCIChpbmNsdXNpdmUpLCBhbmQgd3JpdGUgdGhlIHN1bSBkb3duIG9uIHRoZSBzZWNvbmQgc2hlZXQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlByZXNzIHRoZSBidXR0b24gb25jZSBvbiBhbGwgZGlhbHMgbnVtYmVyZWQgYmV0d2VlbiBBIGFuZCBCLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkp1c3QgYXMgaGUgaGFkIGZpbmlzaGVkIGhpcyBnYW1lLCB0aGUgdGVhY2hlciBub3RpY2VkIGhpbSwgYW5kIHRvb2sgYXdheSBhbGwgaGlzIGRpYWxzIGFuZCB0aGUgc2Vjb25kIHNoZWV0IG9mIHBhcGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgY29udGVudHMgb2YgdGhlIGZpcnN0IHNoZWV0LCBoZWxwIGhpbSBjYWxjdWxhdGUgdGhlIG51bWJlcnMgb24gdGhlIHNlY29uZCBzaGVldC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNICgxICZsZTsgTiAmbGU7IDI1MDAwMCwgMSAmbGU7IE0gJmxlOyAxMDAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGluaXRpYWwgY29uZmlndXJhdGlvbiBvZiB0aGUgZGlhbHMsIE4gZGVjaW1hbCBkaWdpdHMgd2l0aCBubyBzcGFjZXMuIFRoZSBmaXJzdCBkaWdpdCBpcyB0aGUgbnVtYmVyIGluaXRpYWxseSBvbiBkaWFsIDEsIHRoZSBzZWNvbmQgZGlnaXQgdGhlIG51bWJlciBvbiBkaWFsIDIgYW5kIHNvIG9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEgJmxlOyBCICZsZTsgTikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE0gbGluZXMsIHRoZSBzdW1zIGNhbGN1bGF0ZWQgYnkgTHVrYSwgaW4gb3JkZXIgaW4gd2hpY2ggaGUgY2FsY3VsYXRlZCB0aGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=