F. Футболки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Перед началом весны в магазин поступила большая партия новых футболок. Всего в продажу поступили n типов футболок. Футболка i-го типа характеризуется двумя целочисленными параметрами — ci и qi, где ci — цена футболки i-го типа, а qi — качество футболки i-го типа. В данной задаче следует полагать, что в магазин поступило бесконечное количество футболок каждого типа, а качество, в общем случае, никак не связано с ценой.

По прогнозам отдела продаж в ближайший месяц в магазин придут k покупателей, причем j-й покупатель будет готов потратить на покупку футболок сумму равную bj.

Все покупатели при покупке футболок придерживаются одинаковой стратегии. В первую очередь покупатель хочет купить максимально возможное количество самых качественных футболок, затем купить максимально возможное количество самых качественных футболок из оставшихся и так далее. При этом из нескольких футболок одинакового качества он в первую очередь купит ту, которая дешевле. Покупатели не любят одинаковые футболки, поэтому ни один покупатель не будет покупать более одной футболки каждого типа.

Перед вами стоит задача определить, сколько футболок купит каждый из покупателей, если они будут действовать по описанному алгоритму. Все покупатели действуют независимо друг от друга, и покупки одного никак не влияют на покупки другого.

Входные данные

В первой строке следует целое положительное число n (1 ≤ n ≤ 2·105) — количество типов футболок.

В каждой из следующих n строк следуют по два целых числа ci и qi (1 ≤ ci, qi ≤ 109) — стоимость и качество футболки i-го типа.

В следующей строке следует целое положительное число k (1 ≤ k ≤ 2·105) — количество покупателей.

В следующей строке следуют k целых положительных чисел b1, b2, ..., bk (1 ≤ bj ≤ 109), где j-е число равно сумме, которую готов потратить j-й покупатель на покупку футболок.

Выходные данные

В первой строке выходных данных должна содержаться последовательность из k целых чисел, где i-е число должно быть равно количеству футболок, которые будут куплены i-м покупателем.

Примеры
Входные данные
3
7 5
3 5
4 3
2
13 14
Выходные данные
2 3
Входные данные
2
100 500
50 499
4
50 200 150 100
Выходные данные
1 2 2 1
Примечание

В первом тестовом примере первый покупатель купит сначала футболку второго типа, а затем купит футболку первого типа. На это он потратит 10 и не сможет купить футболку третьего типа, так как она стоит 4, а у покупателя останется лишь 3. Второй же покупатель купит все три футболки (сначала футболку второго типа, потом футболку первого типа и, затем, футболку третьего типа). На это он потратит все свои деньги.