Circular Exit (APCS 2020-07 Advanced)

1.0s 256M

There are \(n\) rooms arranged in a ring, numbered \(0\) to \(n-1\). The paths between rooms are one-way: from room \(i\) you can only walk to room \((i+1) \bmod n\).

Each time you enter room \(i\) you gain \(p_i\) points (the room you start in also gives its points).

There are \(m\) tasks to be done in order; the \(i\)-th task requires collecting \(q_i\) points. For each task, if you start in room \(s\) and the required points are collected upon reaching room \(t\), then after finishing the task you stop in room \((t+1) \bmod n\).

You start in room \(0\). After finishing all \(m\) tasks in order, which room do you stop in?

Input

The first line contains two positive integers \(n\) and \(m\) (\(1 \le n \le 200000\), \(1 \le m \le 20000\)).

The second line contains \(n\) positive integers \(p_0, p_1, p_2, \ldots, p_{n-1}\); the sum of all \(p\) does not exceed \(10^9\).

The third line contains \(m\) positive integers \(q_0, q_1, q_2, \ldots, q_{m-1}\); no \(q_i\) exceeds the sum of all \(p\).

Output

Output one non-negative integer: the number of the room you finally stop in.

Scoring

  • 20 points: \(1 \le n, m \le 100\)
  • 80 points: the original limits

Sample Input 1

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

Sample Output 1

4

Sample Input 2

4 3
1 3 5 7
4 2 2

Sample Output 2

0

Source

APCS July 2020, programming problem 3 "Circular Exit"; also available as ZeroJudge f581.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.