There are 
~N~ chairs in a circle. Exactly 
~K~ of these chairs are empty and there are 
~K+1~ students numbered from 
~1~ to ~K+1~ standing at some of these chairs. Every second, each student moves forward by one chair. In particular, if they are currently standing by chair ~N~, then they will move to chair ~1~ after. If a student reaches an empty chair, including at the very beginning, they will sit down for the remaining time. Who will be the last standing student?
It is guaranteed that every student begins at a different chair.
Edit: The test data has been fixed.
Constraints
For all subtasks:
All the indices in the input will be between ~1~ and ~N~ inclusive.
Subtask 1 [30%]
~1 \le K < N \le 5\,000~
Subtask 2 [50%]
~1 \le K < N \le 200\,000~
Subtask 3 [20%]
~1 \le K < N \le 1\,000\,000~
Input Specification
The first line will have two space-separated integers, ~N~ and ~K~.
The next line will have ~K~ space-separated integers representing the indices of the empty chairs.
The third line will have ~K+1~ space-separated integers. The 
~i^\text{th}~ integer is the chair at which student 
~i~ begins at.
Output Specification
Output a single integer, the index of the last standing student.
Sample Input
7 2
2 1
6 5 4
Sample Output
3
Comments
Okay. Thanks wleung_bvg very much!
Will that happen?
What should I output if more than one students remain standing in the end and sit down at the same time? Will that happen?
Since there is exactly 1 less chair than students, if the last 2 students were to sit down at the same time, then they must be sitting down at the same chair. Since each student only move forward exactly one spot each second, then for this to happen, they would have had to start at the same place. Since the problem guarantees that each student starts at a different location, we know that this situation is impossible.
What if the input is:
4 2
2 4
1 2 3?
2nd student will immediately sit down. After one round, 1 sit on 2 and 3 sit on 4.
For clarification, if a student sit on a chair, will that chair count as non-empty?
Student 1 cannot sit on chair 2 since student 2 is already sitting there.