급식실의 선택 반찬

문제

학교 급식실에서는 학생들이 선택 반찬 한 종류를 직접 고를 수 있다. 오늘 준비한 선택 반찬의 종류는 M개이며, 각 종류에는 1부터 M까지의 번호가 붙어 있다. 급식실은 배식을 시작하기 전에 종류별로 준비된 반찬의 양을 한 사람분 단위로 기록해 두었다. 준비된 양이 0인 종류도 있을 수 있다. 학생 N명이 한 줄로 서서 차례대로 배식대에 도착한다. 각 학생은 원하는 반찬 번호 하나를 말한다. 학생이 도착했을 때 해당 반찬이 한 사람분 이상 남아 있으면, 담당자는 그 반찬을 정확히 한 사람분 주고 남은 양을 1만큼 줄인다. 해당 반찬이 이미 모두 떨어졌다면 그 학생에게는 선택 반찬을 주지 않는다. 이 경우 어떤 반찬의 남은 양도 바뀌지 않는다. 학생은 원하는 반찬을 받지 못하더라도 다른 종류를 다시 요청하지 않는다. 앞선 학생의 요청을 취소하거나, 이미 받은 반찬을 돌려주는 일도 없다. 배식 도중에 반찬을 추가로 준비하지 않으므로 모든 종류의 남은 양은 처음 준비된 양에서 시작하여 줄어들기만 한다. 학생의 요청은 반드시 입력에 주어진 순서대로 처리한다. 같은 반찬을 원하는 학생이 여러 명이면 먼저 도착한 학생부터 받는다. 마지막 한 사람분을 받은 학생 다음에 같은 번호를 요청한 학생은 받지 못한다. 다른 종류의 반찬이 많이 남아 있더라도 요청한 종류가 떨어졌다면 그 요청은 실패한 것으로 센다. 급식실은 배식 결과를 확인하기 위해 선택 반찬을 받은 학생 수와 받지 못한 학생 수를 각각 집계하려고 한다. 또한 다음 식사 준비에 참고할 수 있도록 모든 요청을 처리한 뒤 종류별로 몇 사람분이 남았는지도 확인하려고 한다. 두 학생 수와 최종 남은 양을 구한다. 모든 학생이 반찬을 받거나, 아무도 반찬을 받지 못하는 경우도 같은 규칙으로 처리한다.

입력

첫째 줄에 반찬 종류 수 M과 학생 수 N이 정수로 주어진다. 1 ≤ M ≤ 10,000이고 1 ≤ N ≤ 50,000이다.
둘째 줄에 각 종류의 처음 준비된 양 A_1, A_2, …, A_M이 정수로 주어진다. 0 ≤ A_i ≤ 9이다.
셋째 줄에 학생들이 요청한 반찬 번호 B_1, B_2, …, B_N이 도착 순서대로 정수로 주어진다. 1 ≤ B_i ≤ M이다.

출력

첫째 줄에 반찬을 받은 학생 수와 받지 못한 학생 수를 공백으로 구분하여 출력한다. 둘째 줄에 모든 요청을 처리한 뒤 남은 양을 반찬 번호 1부터 M까지 순서대로 공백으로 구분하여 출력한다.

3 6
2 0 3
1 2 3 1 1 3

4 2
0 0 1

2 3
0 0
2 1 2

0 3
0 0

1 2
9
1 1

2 0
7

출처: Devin.KR 자체 제작