今天你需要解决一个不同寻常的背包问题。给定 $n$ 个物品，第 $i$ 个物品的重量为 $w_i$，价值为 $c_i$。此外，给定一个质数 $p$。对于每个模 $p$ 的余数 $r$，你需要找到一个物品集合，使得该集合中物品的总重量模 $p$ 的余数为 $r$，且总价值最大。除了样例之外，每个测试点中的所有重量和价值都是在范围 $[0, 10^9]$ 内随机且独立地选择的。$n$ 和 $p$ 是手动选定的。

输入格式

第一行包含两个整数 $n, p$ ($1 \le n \le 10^6, 2 \le p \le 3000$)，分别表示物品的数量和质数模数。 第二行包含 $n$ 个整数 $w_i$ ($0 \le w_i \le 10^9$)，表示物品的重量。 第三行包含 $n$ 个整数 $c_i$ ($0 \le c_i \le 10^9$)，表示物品的价值。

输出格式

输出一行，包含 $p$ 个整数。其中第 $i$ 个数（从 $0$ 开始索引）应等于总重量模 $p$ 的余数为 $i$ 的物品集合的最大总价值，如果不存在这样的集合，则输出 $-1$。

样例

样例输入 1

2 2
1 2
1 1

样例输出 1

1 2

样例输入 2

2 2
2 2
1 1

样例输出 2

2 -1