> For the complete documentation index, see [llms.txt](https://eaglepb2.gitbook.io/cpw/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://eaglepb2.gitbook.io/cpw/meta-coding-competitions/2011/round-1c/polynomial-factoring.md).

# Polynomial Factoring

## Question

A polynomial in x of degree D can be written as:

$$
a\_Dx^D + a\_{D-1}x^{D-1} + ... + a\_1x^1 + a\_0
$$

In some cases, a polynomial of degree D can also be written as the product of two polynomials of degrees $$D\_1$$ and $$D\_2$$, where $$D = D\_1 + D\_2$$. For instance,

$$
4 x^2 + 11x ^1 + 6 = (4x^1 + 3) \* (1 x^1 + 2)
$$

In this problem, you will be given two polynomials, denoted F and G. Your task is to find a polynomial H such that G \* H = F, and each $$a\_i$$ is an integer.

### Input Format

You should first read an integer N, the number of test cases. Each test case will start by describing F and then describe G. Each polynomial will start with its degree D, which will be followed by D+1 integers, denoting $$a\_0, a\_1, ... , a\_D$$. Each polynomial will have a non-zero coefficient for its highest order term.

### Constraints

$$
N \le 60
$$

$$
0 ≤ D ≤ 20
$$

$$
-10000 ≤ a\_i ≤ 10000
$$

### Output Format

For each test case, output a single line describing H. If H has degree $$D\_H$$, you should output a line containing $$D\_H+1$$ integers, starting with $$a\_0$$ for H. If no H exists such that G\*H=F, you should output "no solution".

### Sample Inputs:

{% tabs %}
{% tab title="Input 0" %}

#### Input

```
5
2 6 11 4
1 3 4
2 1 2 1
1 1 1
2 1 0 -1
1 1 1
1 1 1
2 1 2 1
5 1 1 1 1 1 1
3 1 1 1 1
```

#### Output

```
2 1
1 1
1 -1
no solution
no solution
```

{% endtab %}
{% endtabs %}

***

<details>

<summary>Solution</summary>

</details>