Problema

La strada JOI si estende in linea retta da est a ovest, e lungo la strada JOI ci sono $n$ stazioni di posta. Le stazioni di posta sono numerate $1, 2, \dots, n$ in ordine da ovest a est. La stazione di posta $1$ è la più occidentale e la stazione di posta $n$ è la più orientale.

Il signor JOI parte dalla stazione di posta $1$ per un viaggio di $m$ giorni. Decide il suo itinerario di viaggio secondo una sequenza $a_1, a_2, \dots, a_m$. Qui, $a_i$ è un intero diverso da zero che rappresenta il metodo di spostamento nel giorno $i$. Nello specifico, se nel giorno $i$ il signor JOI parte dalla stazione di posta $k$, entro il giorno $i$ si sposta direttamente dalla stazione di posta $k$ alla stazione di posta $k + a_i$.

Dati il numero di stazioni di posta $n$, il numero di giorni di viaggio $m$, le informazioni sulle distanze tra stazioni di posta adiacenti e la sequenza $a_1, a_2, \dots, a_m$ che rappresenta i metodi di spostamento, scrivi un programma per trovare il resto della divisione della distanza totale percorsa dal signor JOI nel viaggio di $m$ giorni per $100000 = 10^5$.

Input

Leggi l'input dal file input.txt.

Sulla riga $1$ dell'input sono scritti due interi $n, m$ ($2 \le n \le 100000 = 10^5$, $1 \le m \le 100000 = 10^5$) separati da uno spazio, che rappresentano il numero di stazioni di posta $n$ e il numero di giorni di viaggio $m$.

Sulle successive $n - 1$ righe sono scritte le distanze tra le stazioni di posta adiacenti. Sulla riga $i + 1$ ($1 \le i \le n - 1$) è scritto un intero positivo $s_i$ ($1 \le s_i \le 100$) che rappresenta la distanza tra la stazione di posta $i$ e la stazione di posta $i + 1$.

Sulle successive $m$ righe sono scritte le informazioni sui metodi di spostamento. Sulla riga $i + n$ ($1 \le i \le m$) è scritto un intero diverso da zero $a_i$ che rappresenta il metodo di spostamento nel giorno $i$. Non esiste mai uno spostamento che vada a ovest della stazione di posta $1$ o a est della stazione di posta $n$.

Nel $50\%$ dei dati di valutazione valgono $n \le 100$ e $m \le 100$.

Output

Scrivi l'output nel file output.txt.

L'output è costituito da $1$ riga contenente il resto della divisione della distanza totale percorsa dal signor JOI nel viaggio di $m$ giorni per $100000 = 10^5$.

Esempio 1

Input

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

Output

18

Spiegazione

Nel giorno $1$, si sposta dalla stazione di posta $1$ alla stazione di posta $3$. Nel giorno $2$, si sposta dalla stazione di posta $3$ alla stazione di posta $2$. Nel giorno $3$, si sposta dalla stazione di posta $2$ alla stazione di posta $5$. Nel giorno $4$, si sposta dalla stazione di posta $5$ alla stazione di posta $7$. Nel giorno $5$, si sposta dalla stazione di posta $7$ alla stazione di posta $4$. La distanza totale percorsa nel viaggio di $5$ giorni è $18$.