Перед началом весны в магазин поступила большая партия новых футболок. Всего в продажу поступили n типов футболок. Футболка i-го типа характеризуется двумя целочисленными параметрами — ci и qi, где ci — цена футболки i-го типа, а qi — качество футболки i-го типа. В данной задаче следует полагать, что в магазин поступило бесконечное количество футболок каждого типа, а качество, в общем случае, никак не связано с ценой.
По прогнозам отдела продаж в ближайший месяц в магазин придут k покупателей, причем j-й покупатель будет готов потратить на покупку футболок сумму равную bj.
Все покупатели при покупке футболок придерживаются одинаковой стратегии. В первую очередь покупатель хочет купить максимально возможное количество самых качественных футболок, затем купить максимально возможное количество самых качественных футболок из оставшихся и так далее. При этом из нескольких футболок одинакового качества он в первую очередь купит ту, которая дешевле. Покупатели не любят одинаковые футболки, поэтому ни один покупатель не будет покупать более одной футболки каждого типа.
Перед вами стоит задача определить, сколько футболок купит каждый из покупателей, если они будут действовать по описанному алгоритму. Все покупатели действуют независимо друг от друга, и покупки одного никак не влияют на покупки другого.
Выходные данные
В первой строке выходных данных должна содержаться последовательность из k целых чисел, где i-е число должно быть равно количеству футболок, которые будут куплены i-м покупателем.
Примечание
В первом тестовом примере первый покупатель купит сначала футболку второго типа, а затем купит футболку первого типа. На это он потратит 10 и не сможет купить футболку третьего типа, так как она стоит 4, а у покупателя останется лишь 3. Второй же покупатель купит все три футболки (сначала футболку второго типа, потом футболку первого типа и, затем, футболку третьего типа). На это он потратит все свои деньги.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7 5
3 5
4 3
2
13 14
|
2 3
|
|
2
|
2
100 500
50 499
4
50 200 150 100
|
1 2 2 1
|