001 - 旅人

時間制限 8 秒 / メモリ制限 64 MB / 得点 100 / x 3 /


TLE
8sec
MLE
64MB
得点
100

問題

 あなたは JOI 街道を旅する旅人である. JOI 街道は東西にまっすぐに延びた道路で, JOI 街道上には n 個の宿場町がある.宿場町には西から東の順に 1 から n までの番号が付けられている. JOI 街道上の最も西の宿場町が宿場町 1 であり, 最も東の宿場町が宿場町 n である.
 あなたは, 宿場町 1 から出発して m 日間の旅に出ることになった. あなたの旅程は数列 a1, a2, ..., am に 従い,次のように決められている. aii 日目の移動方法を表す 0 ではない整数である. i 日目にあなたが出発する宿場町を宿場町 k とおくと, i 日目にあなたは宿場町 k から宿場町 k + ai までまっすぐに移動することを意味する.
 宿場町の個数 n, 旅の日数 m, 宿場町間の距離の情報と, 移動方法を表す数列 a1, a2, ..., am が与えられたとき, m 日間の旅におけるあなたの移動距離の合計を 100000 = 105 で割った余りを求めるプログラムを作成せよ.

入出力の例に対応する図

入力

 1 行目には整数 n, m が空白区切りで書かれている. n (2 ≤ n ≤ 100000 = 105) は JOI 街道上の宿場町の個数を, m (1 ≤ m ≤ 100000 = 105) は旅の日数を表す.
 続く n - 1 行は JOI 街道上の宿場町間の距離を表す. i + 1 行目(1 ≤ in - 1) には宿場町 i と宿場町 i + 1 の距離を表す正整数 si (1 ≤ si ≤ 100) が書かれている.
 続く m 行には m 日間の移動方法を表す数列が書かれている. i + n 行目(1 ≤ im) には i 日目のあなたの移動方法を表す 0 ではない整数 ai が書かれている.
 採点用データにおいて, 宿場町 1 より西に移動することや, 宿場町 n より東に移動することはない.
 採点用データのうち, 配点の 50% 分については, n ≤ 100 かつ m ≤ 100 を満たす.

出力

 m 日間の旅におけるあなたの移動距離の合計を 100000 = 105 で割った余りを含む 1 行からなる.

入出力例

入力例 1

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

出力例 1

18

 1 日目に, あなたは宿場町 1 から宿場町 3 まで移動する. 2 日目に, あなたは宿場町 3 から宿場町 2 まで移動する. そして, 3 日目に宿場町 2 から宿場町 5 まで移動し, 4 日目に宿場町 5 から宿場町 7 まで移動し, 5 日目に宿場町 7 から宿場町 4 まで移動する. 5 日間の旅におけるあなたの移動距離の合計は 18 である.