Конфетки

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

요약
각 손님은 b_i개 이상 담긴 상자마다 사탕을 하나씩 꺼내 먹을 때, 손님별로 먹은 사탕 수를 순서대로 구한다.
난이도

보통10점 중 6점

유형
정렬, 이분 탐색, 누적 합, 구현
정답자
아직 제출이 없습니다

문제

У Кролика день рождения! Он пригласил в гости nn гостей. Чтобы гостям не было грустно и скучно, Кролик купил nn коробок конфет. Кролик любит разнообразие, поэтому конфеты были разные. В ii-й коробке лежало a_ia\_i конфет.

В назначенный день с самого утра к Кролику начали приходить гости. Каждый гость характеризуется своей наглостью b_ib\_i. Это означает, что, зайдя домой к Кролику и увидев коробки конфет, он брал из каждой коробки, в которой не меньше, чем b_ib\_i, конфет, по одной и съедал её. Например, у Винни-Пуха вполне могла была быть наглость один. Это значит, что он бы съел по конфете из каждой коробки.

Вечером, когда гости разошлись, Кролику стало интересно, кто съел сколько конфет. Помогите ему определить это.

입력

В первой строке задано целое число nn (1≤n≤100,0001 \leq n \leq 100{\\,}000) --- количество коробок конфет. В следующей строке задано nn натуральных чисел a_ia\_i (1≤a_i≤1091\leq a\_i \leq 10^9) --- сколько конфет в каждой коробке.

Далее, в следующей строке задано число число mm (1≤m≤100,0001\leq m \leq 100{\\,}000) --- количество гостей. В четвёртой и последней строке задано mm чисел b_ib\_i (1≤b_i≤1091 \leq b\_i \leq 10^9) --- наглости гостей.

출력

В выходной файл выведите nn строк, ii-ая из которых должна содержать количество конфет съеденных ii-ым гостем.

예제1

  1. 예제 1

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