Énoncé

La route JOI s'étend en ligne droite d'est en ouest, et il y a $n$ villes-relais le long de la route JOI. Les villes-relais sont numérotées $1, 2, \dots, n$ dans l'ordre d'ouest en est. La ville-relais $1$ est la plus à l'ouest, et la ville-relais $n$ est la plus à l'est.

M. JOI part de la ville-relais $1$ pour un voyage de $m$ jours. Il décide de son itinéraire selon une suite $a_1, a_2, \dots, a_m$. Ici, $a_i$ est un entier non nul représentant le déplacement du jour $i$. Plus précisément, si M. JOI part de la ville-relais $k$ le jour $i$, il se déplace directement de la ville-relais $k$ à la ville-relais $k + a_i$ au cours du jour $i$.

Étant donné le nombre de villes-relais $n$, le nombre de jours de voyage $m$, les informations sur les distances entre les villes-relais adjacentes et la suite $a_1, a_2, \dots, a_m$ représentant les déplacements, écrivez un programme pour trouver le reste de la division par $100000 = 10^5$ de la distance totale parcourue par M. JOI au cours de son voyage de $m$ jours.

Entrée

Lisez l'entrée depuis le fichier input.txt.

Sur la ligne $1$ de l'entrée, deux entiers $n, m$ ($2 \le n \le 100000 = 10^5$, $1 \le m \le 100000 = 10^5$) séparés par un espace sont écrits, représentant le nombre de villes-relais $n$ et le nombre de jours de voyage $m$.

Sur les $n - 1$ lignes suivantes sont écrites les distances entre les villes-relais adjacentes. Sur la ligne $i + 1$ ($1 \le i \le n - 1$) est écrit un entier positif $s_i$ ($1 \le s_i \le 100$) représentant la distance entre la ville-relais $i$ et la ville-relais $i + 1$.

Sur les $m$ lignes suivantes sont écrites les informations sur les déplacements. Sur la ligne $i + n$ ($1 \le i \le m$) est écrit un entier non nul $a_i$ représentant le déplacement du jour $i$. Il n'y a jamais de déplacement allant à l'ouest de la ville-relais $1$ ni à l'est de la ville-relais $n$.

Dans $50\%$ des données d'évaluation, on a $n \le 100$ et $m \le 100$.

Sortie

Écrivez la sortie dans le fichier output.txt.

La sortie consiste en $1$ ligne contenant le reste de la division par $100000 = 10^5$ de la distance totale parcourue par M. JOI au cours de son voyage de $m$ jours.

Exemple 1

Entrée

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

Sortie

18

Explication

Le jour $1$, il se déplace de la ville-relais $1$ à la ville-relais $3$. Le jour $2$, il se déplace de la ville-relais $3$ à la ville-relais $2$. Le jour $3$, il se déplace de la ville-relais $2$ à la ville-relais $5$. Le jour $4$, il se déplace de la ville-relais $5$ à la ville-relais $7$. Le jour $5$, il se déplace de la ville-relais $7$ à la ville-relais $4$. La distance totale parcourue au cours de ce voyage de $5$ jours est $18$.