圓環出口 (APCS 2020-07 中高級)

有 \(n\) 個房間排成一個環，編號分別是 \(0\) 到 \(n-1\)。房間之間有單向的路徑，編號 \(i\) 的房間可以走到編號 \((i+1) \bmod n\) 的房間。

每次進入編號 \(i\) 的房間可以獲得 \(p_i\) 個點數（最一開始待的房間也可以獲得點數）。

現在依序有 \(m\) 個任務，第 \(i\) 個任務需要蒐集到 \(q_i\) 個點數。對於每次的任務，若一開始在編號 \(s\) 的房間，且走到編號 \(t\) 的房間時候可以蒐集到需要的點數，則完成這次任務後會停在編號 \((t+1) \bmod n\) 的房間。

一開始在編號 \(0\) 的房間，依據接收到 \(m\) 個任務，請求出完成第 \(m\) 個任務後會停在哪個編號的房間？

輸入格式

第一行包含兩個正整數 \(n\)、\(m\)（\(1 \le n \le 200000\)，\(1 \le m \le 20000\)）。

第二行包含 \(n\) 個正整數 \(p_0, p_1, p_2, \ldots, p_{n-1}\)，\(p\) 的總和不超過 \(10^9\)。

第三行包含 \(m\) 個正整數 \(q_0, q_1, q_2, \ldots, q_{m-1}\)，\(q_i\) 不會超過 \(p\) 的總和。

輸出格式

輸出一個非負整數表示最後停在哪個編號的房間。

評分說明

• 20 分：\(1 \le n, m \le 100\)
• 80 分：同原題目限制

範例輸入 1

7 3
2 1 5 4 3 5 3
8 9 12

範例輸出 1

4

範例輸入 2

4 3
1 3 5 7
4 2 2

範例輸出 2

0

題目來源

APCS 2020 年 7 月實作題第 3 題。

題敘參考 ZeroJudge f581「圓環出口」 整理，細節可能與正式試題有出入。