32644번 - 랜덤 넘버 추측하기 스페셜 저지

문제

영과일에서 한 학기동안 문제를 열심히 푼 회원들을 추첨하여 상품을 지급하려고 한다.

각 회원들에겐 문제를 푼 개수만큼 추첨 확률을 높일 수 있는 가중치가 부여된다. 문제를 $p$개 풀었다면 그 회원의 가중치는 $p$이다.

한 학기 동안 문제를 푼 적이 있는 회원은 총 $N$명이고, 그러한 회원들에게 1ドル$번부터 $N$번까지의 고유 번호를 부여한다.

회원 $N$명중에서 $M(1 \leq M \leq N)$명을 뽑으려고 할 때, $i=1$부터 시작하여 다음과 같은 방식으로 추첨을 진행하려고 한다.

1. 1ドル$번 회원부터 $N$번 회원까지 번호 순서대로, 각 회원의 가중치만큼 응모권을 리스트 $W$에 반복해서 넣는다. 예를 들어, 회원이 총 3ドル$명이고 각각의 가중치가 2,ドル\ 1,\ 3$ 이라면 $W = [T_1,\ T_1,\ T_2,\ T_3,\ T_3,\ T_3]$이다. ($T_k$는 $k$번 회원의 응모권)
2. 1ドル$부터 $|W|$까지의 정수 중 하나를 랜덤하게 선택하고, 이 수를 $X_i$라 하자.
3. 리스트 $W$의 앞에서부터 $X_i$번째에 해당하는 응모권을 선택해 당첨자 한 명을 뽑는다.
4. 리스트 $W$에서 방금 당첨된 회원의 응모권을 모두 제거한다.
5. $i \neq M$이면 $i$를 1ドル$만큼 증가시킨 후 2번 과정으로 돌아가고, 그렇지 않다면 추첨을 종료한다.

위 방식을 통해 뽑힌 당첨자의 고유 번호가 순서대로 주어졌을 때, 랜덤하게 나온 수가 차례대로 무엇일지 추측하려고 한다.

입력

첫 번째 줄에 문제를 푼 회원수 $N$과 당첨인원수 $M$이 공백을 사이에 두고 주어진다. $(1 \leq N \leq 500,000円; 1 \leq M \leq N)$

두 번째 줄에 각 회원의 가중치 $p$가 공백을 사이에 두고 $N$개 주어진다. $(1 \leq p \leq 1,000円)$

세 번째 줄에 뽑힌 순서대로 회원의 번호 $k$가 공백을 사이에 두고 $M$개 주어진다. $(1 \leq k \leq N)$

입력에서 주어지는 수는 모두 정수이다.

출력

추첨 과정을 통해 랜덤하게 나온 수열 $X$를 공백을 사이에 두고 출력한다.

만약 가능한 수열이 여러 개라면 아무 수열이나 하나 출력한다.

제한

힌트