| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 9 | 2 | 2 | 40.000% |
On the left side of the board, there are $N$ polynomials, and on the right side, there are $M$ polynomials. Your task is to construct each of the $M$ polynomials from the right side of the board with the minimum number of actions.
To construct a polynomial from the right side, first choose any of the $N$ polynomials from the left side. The following transformations can be applied to the chosen polynomial:
Transformations can be applied in arbitrary order any number of times, however, one application counts as one action. You can use no transformations at all if a polynomial from the right side matches some polynomial from the left side.
The first line of the input file contains two integers: $N$ and $M$ (1ドル\leq N,M\leq 10^5$).
Each of the following $N+M$ lines describes the polynomials, one polynomial per line. The first $N$ polynomials are polynomials from the left side of the board, the rest are from the right side of the board.
The description of the polynomial $a_0 + a_1 x + \dots + a_K x^K$ begins with a nonnegative integer $K$ --- its degree. Next come integers $a_0, a_1, \dots, a_K,ドル which are the coefficients of the polynomial ($-10^9\leq a_i \leq 10^9$). Herewith, $a_K\neq 0$.
It is guaranteed that the sum of degrees of all polynomials on the left side of the board is not greater than 10ドル^5$. It is the same for the polynomials on the right side of the board.
For each polynomial from the right side, print the minimum number of actions necessary for its construction. Print your answers one per line in the same order as the order in which the polynomials are listed in the input file.
2 1 2 1 1 1 2 7 6 2 2 7 6 1
4
2 1 2 1 1 1 0 1 1 1 1
1
In the second example there are two polynomials on the left side of the board: $p_1(x)=1+x+x^2$ and $p_2(x)=7+6x+2x^2$. We need to obtain the polynomial $q(x)=7+6x+x^2$. In order to do that we apply differentiation to $p_1$ twice obtaining $p_1'(x)=1+2x$ first, and $p_1"(x)=2$ next. Now, let's integrate $p_1"(x)$ with 6ドル$ as the integration constant producing 6ドル+2x$. We integrate the result once again with 7ドル$ as the integration constant to get 7ドル+6x+x^2$. We used 4ドル$ actions in total.