Kingdom Division

문제

In a far away kingdom, there are $NN$ cities numbered between $00$ and $N-1N\; -\; 1$. The cities are connected by $N-1N\; -\; 1$ two-way roads. Each road connects exactly two cities, such that there is a unique path between any pair of cities. Each city $ii$ has some value $C[i]C[i]$ (possibly negative).

Unfortunately, the old king of the kingdom died, without appointing a successor. Thus a civil war broke out in the kingdom, between the $PP$ lords (also numbered between $00$ and $P-1P\; -\; 1$) who wish to gain control of the kongdom.

After a long and terrible war, the lords realized none of them could beat all the other lords in the war. They agreed to a truce, and decided to divide the kingdom into $PP$ parts, one part per lord. The parts must be so that if two cities $aa$ and $bb$ lie in the same part, all cities in the unique path between them must also lie in that part. Since no lord wants to be left out, each one must be given at least one city.

Since no lord wants to get less than another, the value of each part must be the same. The value of a part is the sum of the values of all cities in that part.

입력

The sample judge reads input in the following format:

• line $11$: N P
• line $22$: C[0] C[1] .. C[N - 1]
• line $33$: F[0] F[1] .. F[N - 2]
• line $44$: T[0] T[1] .. T[N - 2]

출력

The sample judge will first write a single line with the return value of division(N, P, C, F, T). The next line will contain $NN$ integers containing the input to the parts(R) call.