만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

사탕

면접 대비

시간 제한2초메모리 제한1024 MB

요약
각 손님은 자신의 대담함 이상의 사탕이 든 모든 상자에서 사탕을 하나씩 먹습니다. 손님마다 먹은 사탕의 개수를 구합니다.
난이도

보통10점 중 5점

유형
정렬, 투 포인터, 그리디
정답자
아직 제출이 없습니다

문제

토끼의 생일이다. 토끼는 손님 nn명을 초대했다. 손님들이 심심하지 않도록 토끼는 사탕 상자 nn개를 샀다. 토끼는 다양한 것을 좋아하므로 사탕은 모두 서로 다르다. ii번째 상자에는 aia_i개의 사탕이 들어 있다.

손님들은 아침 일찍부터 찾아온다. 각 손님에게는 뻔뻔함 bib_i가 있다. 손님은 토끼의 집에 들어가 상자들을 살펴보고, 사탕이 bib_i개 이상 들어 있는 상자마다 사탕을 하나씩 꺼내 먹는다. 예를 들어 곰돌이 푸의 뻔뻔함이 1일 수 있다. 이는 푸가 모든 상자에서 사탕을 하나씩 먹는다는 뜻이다.

저녁에 손님들이 돌아가자 토끼는 각 손님이 사탕을 몇 개씩 먹었는지 궁금해졌다. 이를 알아내는 것을 도와달라.

입력

첫 줄에 사탕 상자의 개수 nn (1≤n≤100 0001 \leq n \leq 100\,000)이 주어진다. 둘째 줄에는 각 상자에 든 사탕의 개수 aia_i (1≤ai≤1091 \leq a_i \leq 10^9) nn개가 주어진다.

셋째 줄에 손님의 수 mm (1≤m≤100 0001 \leq m \leq 100\,000)이 주어진다. 넷째 줄에는 손님들의 뻔뻔함 bib_i (1≤bi≤1091 \leq b_i \leq 10^9) mm개가 주어진다.

출력

nn개의 줄을 출력한다. ii번째 줄에는 ii번째 손님이 먹은 사탕의 개수를 출력한다.

예제1

  1. 예제 1

    입력
    3
    3 1 1
    2
    1 1
    
    예상 출력
    3
    1