Bạn là một lữ khách đang đi trên con đường JOI. Con đường này chạy thẳng theo hướng đông–tây, với \(n\) thị trấn dừng chân được đánh số từ \(1\) đến \(n\) theo thứ tự từ tây sang đông. Thị trấn \(1\) nằm xa nhất về phía tây, còn thị trấn \(n\) nằm xa nhất về phía đông.

Bạn xuất phát từ thị trấn \(1\) và thực hiện chuyến đi kéo dài \(m\) ngày. Lịch trình được xác định bởi dãy \(a_1,a_2,\ldots,a_m\). Số nguyên khác \(0\) \(a_i\) mô tả cách di chuyển trong ngày thứ \(i\): nếu bắt đầu ngày đó ở thị trấn \(k\), bạn đi thẳng từ thị trấn \(k\) đến thị trấn \(k+a_i\).

Yêu cầu

Cho số thị trấn \(n\), số ngày đi \(m\), khoảng cách giữa các thị trấn và dãy \(a_1,a_2,\ldots,a_m\), hãy viết chương trình tính phần dư khi chia tổng quãng đường bạn đi trong \(m\) ngày cho \(100000=10^5\).

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên \(n,m\), cách nhau bởi dấu cách, lần lượt là số thị trấn trên đường JOI và số ngày của chuyến đi.
• \(n-1\) dòng tiếp theo mô tả khoảng cách giữa các thị trấn. Dòng thứ \(i+1\) (\(1\le i\le n-1\)) chứa số nguyên dương \(s_i\), là khoảng cách giữa thị trấn \(i\) và thị trấn \(i+1\).
• \(m\) dòng tiếp theo chứa lịch trình của \(m\) ngày. Dòng thứ \(i+n\) (\(1\le i\le m\)) chứa số nguyên khác \(0\) \(a_i\), mô tả cách di chuyển trong ngày thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa phần dư khi chia tổng quãng đường đi trong \(m\) ngày cho \(100000=10^5\).

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
• \(2\le n\le100000=10^5\).
• \(1\le m\le100000=10^5\).
• \(1\le s_i\le100\) (\(1\le i\le n-1\)).
• \(a_i\) là số nguyên khác \(0\) (\(1\le i\le m\)).
• Trong mọi dữ liệu chấm, bạn không bao giờ đi về phía tây vượt quá thị trấn \(1\) hoặc về phía đông vượt quá thị trấn \(n\).

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(n\le100\) và \(m\le100\).

Ví dụ

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

18