You are part of a university admissions office and need to keep track of the ~k~-th highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.

Input Specification

On the first line, an integers ~K~ and ~N~ will be printed: the ~k~-th highest score to track and the number of new applicants.

On the second line, ~K~ space-separated integers, ~a_i~, representing the initial applicant scores.

On the third line, ~N~ space-separated integers, ~b_i~ representing new applicant scores.

Output Specification

On one line, print ~N+1~ space-separated integers, representing the ~k~-th highest score before the new applicants, then after each new addition.

Constraints

~1 \le K \le 10^6~

~1 \le N \le 10^6~

~1 \le a_i, b_i, \le 10^6~

Sample Input 1

3 5
4 5 8
3 6 2 9 4

Sample Output 1

4 4 5 5 6 6