AlgoLiga 2018

Twoim zadaniem jest podzielić wielomian przez inny wielomian :) Żeby nie było zbyt łatwo należy tego dokonać w pierścieniu Z_n, gdzie n jest liczbą pierwszą. Pierścień Z_n oznacza, że dzielenie można przeprowadzić tylko wśród licz całkowitych z przedziału [0;n-1]. Jeszcze prościej mówiąc należy wykonać dzielenie wielomianów modulo n.

Wejście

W pierwszym wierszu jedna liczba t ∈ [1;10⁴] reprezentująca liczbę testów.

Każdy test składa się z trzech wierszy. W pierwszym podana jest liczba n ∈ [5;10⁴]. W drugim liczba k₁ ∈ [1;100], po czym ciąg k₁ liczb całkowitych należących do przedziału [0;n-1] reprezentujących współczynniki wielomianu będącego dzielną. W ostatnim wierszu liczba k₂ ∈ [1;k₁], po czym ciąg k₂ liczb całkowitych należących do przedziału [0;n-1] reprezentujących współczynniki wielomianu będącego dzielnikiem.

Przykładowo test:

5
7 1 2 3 0 0 4 4
3 3 2 1

Reprezentuje dzielenie:

(x⁶+2x⁵+3x⁴+4x+4) / (3x²+2x+1)

w pierscieniu Z₅.

Wyjście

Odpowiedź dla każdego testu powinna zostać wypisana w 2 liniach. W pierwszej lini współczyniki wielomianu części całkowitej. W drugiej lini współczyniki wielomianu reszty z dzielenia.

Przykład

Wejście:

2
11
5 2 8 1 6 2
3 5 0 2
11
4 1 3 7 6
3 1 7 2

Wyjście:

7 6 4
5 5
1 7
3