시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 (추가 시간 없음) 256 MB85562.500%

문제

Today you should solve unusual knapsack problem. You are given $n$ items, $i$-th of them has weight $w_i$ and cost $c_i$. Also a prime $p$ is given. For every remainder $r$ modulo $p$ you should find the maximum total cost of a set of items with total weight having remainder $r$ modulo $p$. All weights and costs in each test except samples are chosen randomly and independently from range $[0 \dots 10^9]$. $n$ and $p$ are chosen manually.

입력

The first line contains two integers $n$, $p$ ($1\leq n\leq 10^6, 2\leq p\leq 3000$) -- the number of items and the prime modulo.

The next line contains $n$ integers $w_i$ ($0\leq w_i\leq 10^9$) --- the weights of items.

The next line contains $n$ integers $c_i$ ($0\leq c_i\leq 10^9$) --- the costs of items.

출력

Output one line with $p$ integers. $i$-th of them ($0$-indexed) should be equal to the maximum total cost of a set of items with total weight having remainder $i$ modulo $p$, or $-1$ if such set doesn't exist.

예제 입력 1

2 2
1 2
1 1

예제 출력 1

1 2

예제 입력 2

2 2
2 2
1 1

예제 출력 2

2 -1