题目描述

小明有 $N$ 张双面卡片，第 $i$ 张卡片的正面印有一个整数 $A_i$，反面印有一个整数 $B_i$。

初始时，所有卡片均为正面朝上。

现在你可以选择若干张卡片将其翻面（即将正面变为反面）。 翻动一张卡片的代价为 $1$。

设所有卡片当前正面朝上的数字之和为

对于每一个整数 $x$，满足

请你计算：

使得所有卡片正面朝上的数字之和 恰好等于 $x$ 时，最少需要翻动多少张卡片。

若无法达到该和，则输出 $-1$。

输入格式

第一行包含两个整数 $N, K$。

接下来 $N$ 行，每行包含两个整数 $A_i, B_i$。

输出格式

输出一行 $K+1$ 个整数。

第 $x$ 个整数（从 $0$ 开始编号）表示： 使总和恰好等于 $x$ 的最少翻转次数。

若无法达到该和，输出 $-1$。

数据范围

• $1 \le N \le 200$
• $0 \le A_i, B_i \le 1000$
• $0 \le K \le 10^5$

样例

输入

3 7
4 1
3 5
2 6

输出

-1 -1 -1 -1 -1 -1 1 -1

样例解释

初始总和为

翻转第 $1$ 张卡片后总和为

因此当 $x = 6$ 时答案为 $1$。 ...

其余无法达到的值输出 $-1$。