시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 311 239 211 77.574%

문제

현수는 학생들에게 노래를 가르치고 있다. 총 N개의 악보가 있고 i번째 악보는 Bi초로 이루어져 있다. 학생들은 0초부터 1번 악보를 따라 노래하기 시작했다. 즉 B1-1초에 1번 악보를 끝마치게 되고 B1초부터 B1+B2-1초까지 2번 악보를 따라 부르게 된다.

악보 1 1 2 3 3 3
시간 0 1 2 3 4 5

문제는 T1부터 TQ까지 Q개의 시간에 대해 대답을 하는 것인데, Ti초 때 노래하는 악보를 i번째에 출력하는 것이다.

입력

첫 줄에는 악보 수 N(1 ≤ N ≤ 100)과 질문의 개수 Q(1 ≤ Q ≤ 1,000)가 주어진다. 다음 N개의 줄에는 1번 악보부터 N번 악보까지 각 악보가 차지하는 시간(초)이 한 줄에 하나씩 주어진다. 각 악보가 차지하는 시간은 100 이하의 정수이다. 다음 Q개의 줄에는 알고자 하는 Q개의 시간(초)이 한 줄에 하나씩 주어진다. 묻는 시간 역시 정수만 주어진다.

출력

Q개에 줄에 1번 질문부터 Q번 질문까지 해당 시간(초)에 부르는 악보의 번호를 출력한다.

예제 입력 1

3 5
2
1
3
2
3
4
0
1

예제 출력 1

2
3
3
1
1

힌트

W3sicHJvYmxlbV9pZCI6IjEzOTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxNzhcdWI3OTggXHVjNTQ1XHViY2Y0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MDRcdWMyMThcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNWQwXHVhYzhjIFx1YjE3OFx1Yjc5OFx1Yjk3YyBcdWFjMDBcdWI5NzRcdWNlNThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWM1NDVcdWJjZjRcdWFjMDAgXHVjNzg4XHVhY2UwIGlcdWJjODhcdWM5ZjggXHVjNTQ1XHViY2Y0XHViMjk0IEJpXHVjZDA4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCAwXHVjZDA4XHViZDgwXHVkMTMwIDFcdWJjODggXHVjNTQ1XHViY2Y0XHViOTdjIFx1YjUzMFx1Yjc3YyBcdWIxNzhcdWI3OThcdWQ1NThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0LiBcdWM5ODkgQjEtMVx1Y2QwOFx1YzVkMCAxXHViYzg4IFx1YzU0NVx1YmNmNFx1Yjk3YyBcdWIwNWRcdWI5YzhcdWNlNThcdWFjOGMgXHViNDE4XHVhY2UwIEIxXHVjZDA4XHViZDgwXHVkMTMwIEIxK0IyLTFcdWNkMDhcdWFlNGNcdWM5YzAgMlx1YmM4OCBcdWM1NDVcdWJjZjRcdWI5N2MgXHViNTMwXHViNzdjIFx1YmQ4MFx1Yjk3NFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozNSVcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+XHVjNTQ1XHViY2Y0PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPjE8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4yPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+MzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPjM8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4zPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj5cdWMyZGNcdWFjMDQ8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4wPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPjI8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4zPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+NDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPjU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1YjI5NCBUMVx1YmQ4MFx1ZDEzMCBUUVx1YWU0Y1x1YzljMCBRXHVhYzFjXHVjNzU4IFx1YzJkY1x1YWMwNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViMzAwXHViMmY1XHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzhcdWIzNzAsIFRpXHVjZDA4IFx1YjU0YyBcdWIxNzhcdWI3OThcdWQ1NThcdWIyOTQgXHVjNTQ1XHViY2Y0XHViOTdjIGlcdWJjODhcdWM5ZjhcdWM1ZDAgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTQ1XHViY2Y0IFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAwKVx1YWNmYyBcdWM5YzhcdWJiMzhcdWM3NTggXHVhYzFjXHVjMjE4IFEoMSAmbGU7IFEgJmxlOyAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMVx1YmM4OCBcdWM1NDVcdWJjZjRcdWJkODBcdWQxMzAgTlx1YmM4OCBcdWM1NDVcdWJjZjRcdWFlNGNcdWM5YzAgXHVhYzAxIFx1YzU0NVx1YmNmNFx1YWMwMCBcdWNjMjhcdWM5YzBcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0KFx1Y2QwOClcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjNTQ1XHViY2Y0XHVhYzAwIFx1Y2MyOFx1YzljMFx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgMTAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBRXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1NGNcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFFcdWFjMWNcdWM3NTggXHVjMmRjXHVhYzA0KFx1Y2QwOClcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiM2JcdWIyOTQgXHVjMmRjXHVhYzA0IFx1YzVlZFx1YzJkYyBcdWM4MTVcdWMyMThcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlFcdWFjMWNcdWM1ZDAgXHVjOTA0XHVjNWQwIDFcdWJjODggXHVjOWM4XHViYjM4XHViZDgwXHVkMTMwIFFcdWJjODggXHVjOWM4XHViYjM4XHVhZTRjXHVjOWMwIFx1ZDU3NFx1YjJmOSBcdWMyZGNcdWFjMDQoXHVjZDA4KVx1YzVkMCBcdWJkODBcdWI5NzRcdWIyOTQgXHVjNTQ1XHViY2Y0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTM5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik11c2ljIE5vdGVzIiwiZGVzY3JpcHRpb24iOiI8cD5GSiBpcyBnb2luZyB0byB0ZWFjaCBoaXMgY293cyBob3cgdG8gcGxheSBhIHNvbmcuIFRoZSBzb25nIGNvbnNpc3RzIG9mIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMDApIG5vdGVzLCBhbmQgdGhlIGktdGggbm90ZSBsYXN0cyBmb3IgQl9pICgxICZsdDs9IEJfaSAmbHQ7PSAxMDApIGJlYXRzLiBUaGUgY293cyB3aWxsIGJlZ2luIHBsYXlpbmcgdGhlIHNvbmcgYXQgdGltZSAwOyB0aHVzLCB0aGV5IHdpbGwgcGxheSBub3RlIDEgZnJvbSB0aW1lIDAgdG8gdGltZSBCXzEgLSAxLCBub3RlIDIgZnJvbXRpbWUgQl8xIHRvIHRpbWUgQl8xICsgQl8yIC0gMSwgZXRjLjxcL3A+XHJcblxyXG48cD5UaGUgY293cyBoYXZlIGxvc3QgaW50ZXJlc3QgaW4gdGhlIHNvbmcsIGFzIHRoZXkgZmVlbCB0aGF0IGl0IGlzIGxvbmcgYW5kIGJvcmluZy4gVGh1cywgdG8gbWFrZSBzdXJlIGhpcyBjb3dzIGFyZSBwYXlpbmcgYXR0ZW50aW9uLCBGSiBhc2tzIHRoZW0gUSAoMSAmbHQ7PSBRICZsdDs9IDEsMDAwKSBxdWVzdGlvbnMgb2YgdGhlIGZvcm0sICZxdW90O0R1cmluZyB0aGUgYmVhdCBhdCB0aW1lIFRfaSAoMCAmbHQ7PSBUX2kgJmx0OyBsZW5ndGggb2Ygc29uZyksIHdoaWNoIG5vdGUgc2hvdWxkIHlvdSBiZSBwbGF5aW5nPyZxdW90OyBUaGUgY293cyBuZWVkIHlvdXIgaGVscCB0byBhbnN3ZXIgdGhlc2UgcXVlc3Rpb25zLjxcL3A+XHJcblxyXG48cD5CeSB3YXkgb2YgZXhhbXBsZSwgY29uc2lkZXIgYSBzb25nIHdpdGggdGhlc2Ugc3BlY2lmaWNhdGlvbnM6IG5vdGUgMSBmb3IgbGVuZ3RoIDIsIG5vdGUgMiBmb3IgbGVuZ3RoIDEsIGFuZCBub3RlIDMgZm9yIGxlbmd0aCAzOjxcL3A+XHJcblxyXG48cHJlPlxyXG5OT1RFUyAgICAxICAgMSAgIDIgICAzICAgMyAgIDNcclxuICAgICAgICstLS0rLS0tKy0tLSstLS0rLS0tKy0tLStcclxuVElNRSAgICAgMCAgIDEgICAyICAgMyAgIDQgICA1XHJcbjxcL3ByZT4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBRPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyOiBCX2k8XC9wPlxyXG5cclxuPHA+KiBMaW5lcyBOKzIuLk4rUSsxOiBMaW5lIE4raSsxIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXI6IFRfaTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZXMgMS4uUTogTGluZSBpIGNvbnRhaW5zIHRoZSBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG5vdGUgdGhlIGNvd3Mgc2hvdWxkIGJlIHBsYXlpbmcgYXQgdGltZSBUX2k8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO January 2009 Contest > Bronze 3번