#1514 여행자

18  10 s   128 MB  

Description

 당신은 정올 가도를 여행하는 여행자다. 정올 가도는 동서로 뻗은 직선도로로, 정올 도로 위에는 n개의 숙소가 있다.

숙소는 서에서 동으로 순서데로 1부터 n까지 숫자가 붙어있다. 정올 도로 위에 가장 서쪽에 있는 숙소가 [숙소1]이고, 가장 동쪽에 있는 숙소가 [숙소n]이다.

 당신은 [숙소1]에서 출발해서 m일동안 여행을 떠나기로 했다. 당신의 여정은 수열 a_1,a_2,....,a_m 을 따라 다음과 같이 결정되어있다. a_i 는 i일 째의 이동방법을 표현하는 0이 아닌 정수이다. i일 째 당신이 출발하는 숙소를 [숙소k]라고 놓으면, i일째에 당신은 [숙소k]부터 [숙소 k+a_i]까지 이동하는 것을 의미한다.

숙소의 개수를 n, 여행일수를 m, 숙소간의 거리 정보, 이동방법을 표현하는 수열 a_1,a_2,....,a_m가 주어졌을 때,m일간 여행한 이동거리의 합계를 100000 = 10^5로 나눈 나머지를 구하는 프로그램을 작성해라.

입출력의 예에 따른 그림

9_1.jpg

Input

1행은 정수 n, m을 공백으로 구분해서 쓴다.

n ( 2\leqq n \leqq 100000 = 10^5 )은 정올의 도로 위에 숙소의 개수이다. m ( 2\leqq n \leqq 100000 = 10^5 )은 여행일을 나타낸다.

이어지는 n-1 행은 정올가도위의 숙소간의 거리를 나타낸다. i + 1 행째는 (1\leqq i\leqq n-1 ) 에는 숙소 i와 i+1사이의 거리를 나타내는 양의 정수 s_i (1\leqq s_i\leqq 100)가 써있다.

이어지는 m행에는 m일째에 이동하는 방법이 나타나는 수열이 써있다. i+n행째 (1\leqq i\leqq m)에는 i일째에 당신이 이동하는 방법을 나타내는 0이아닌 정수 a_i가 써있다.

[숙소 1]보다 서쪽으로 이동하는 일이나, [숙소 n]보다 동쪽으로 이동하는 일은 일어나지 않는다.

Output

m일간 여행을 한동안 당신의 이동거리의 합계를 100000 = 10^5로 나눈 나머지를 출력하라.

Sample Input

Sample Output

7 5
2
1
1
3
2
1
2
-1
3
2
-3
18

HINT

 1일째에 당신이 [숙소1]에서 [숙소3]까지 이동한다. 2일째에 당신은 [숙소3]에서 [숙소2]까지 이동한다. 그리고 3일째에는 [숙소2]부터 [숙소5]까지 이동하고, 4일째에는 [숙소5]부터 [숙소7]까지 이동한다. 5일쨰에는 [숙소7]부터 [숙소4]까지 이동한다. 5일간 당신이 이동한 이동거리는 18이 된다.

9_1.jpg

Source

Japan Olympiad in Informatics 2009-2010