문제

JOI 가도는 동서로 곧게 뻗은 도로이며, JOI 가도를 따라 $n$개의 역참 마을이 있다. 역참 마을에는 서쪽에서 동쪽 순서대로 $1, 2, \dots, n$의 번호가 붙어 있다. 역참 마을 $1$은 가장 서쪽에 있는 역참 마을이고, 역참 마을 $n$은 가장 동쪽에 있는 역참 마을이다.

JOI 씨는 역참 마을 $1$을 출발하여 $m$일 동안의 여행을 한다. JOI 씨는 수열 $a_1, a_2, \dots, a_m$에 따라 여행 일정을 정한다. 여기서 $a_i$는 영이 아닌 정수이며, $i$일째의 이동 방법을 나타낸다. 구체적으로, $i$일째에 역참 마을 $k$에서 출발했다고 하면, JOI 씨는 $i$일째 동안에 역참 마을 $k$에서 역참 마을 $k + a_i$까지 곧장 이동한다.

역참 마을의 개수 $n$, 여행 일수 $m$, 이웃한 역참 마을 사이의 거리 정보, 이동 방법을 나타내는 수열 $a_1, a_2, \dots, a_m$이 주어졌을 때, $m$일 동안의 여행에서 JOI 씨의 총 이동 거리를 $100000 = 10^5$으로 나눈 나머지를 구하는 프로그램을 작성하라.

입력

입력은 파일 input.txt에서 읽어들인다.

입력의 $1$번째 줄에는 공백으로 구분된 두 정수 $n, m$ ($2 \le n \le 100000 = 10^5$, $1 \le m \le 100000 = 10^5$)이 적혀 있으며, 역참 마을의 개수 $n$과 여행 일수 $m$을 나타낸다.

이어지는 $n - 1$개의 줄에는 이웃한 역참 마을 사이의 거리가 적혀 있다. $i + 1$번째 줄 ($1 \le i \le n - 1$)에는 역참 마을 $i$와 역참 마을 $i + 1$ 사이의 거리를 나타내는 양의 정수 $s_i$ ($1 \le s_i \le 100$)가 적혀 있다.

이어지는 $m$개의 줄에는 이동 방법의 정보가 적혀 있다. $i + n$번째 줄 ($1 \le i \le m$)에는 $i$일째의 이동 방법을 나타내는 영이 아닌 정수 $a_i$가 적혀 있다. 역참 마을 $1$보다 서쪽으로 가는 이동이나 역참 마을 $n$보다 동쪽으로 가는 이동은 존재하지 않는다.

채점용 데이터 중 배점의 $50\%$에 대해서는 $n \le 100$ 및 $m \le 100$을 만족한다.

출력

출력은 파일 output.txt에 한다.

출력은 $m$일 동안의 여행에서 JOI 씨의 총 이동 거리를 $100000 = 10^5$으로 나눈 나머지를 포함하는 $1$줄로 이루어진다.

입출력 예 1

입력

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

출력

18

설명

$1$일째에는 역참 마을 $1$에서 역참 마을 $3$으로 이동한다. $2$일째에는 역참 마을 $3$에서 역참 마을 $2$로 이동한다. $3$일째에는 역참 마을 $2$에서 역참 마을 $5$로 이동한다. $4$일째에는 역참 마을 $5$에서 역참 마을 $7$로 이동한다. $5$일째에는 역참 마을 $7$에서 역참 마을 $4$로 이동한다. $5$일 동안의 여행에서 총 이동 거리는 $18$이다.