# Polynomial GCD

Given two polynomials f(x) and g(x) in Zn, you have to find their GCD polynomial, ie, a polynomial r(x) (also in Zn) which has the greatest degree of all the polynomials in Zn that divide both f(x) and g(x). There can be more than one such polynomial, of which you are to find the one with a leading coefficient of 1 (1 is the unity in Zn. Such polynomial is also called a monic polynomial). Note: A function f(x) is in Zn means all the coefficients in f(x) is modulo n. Input There will be no more than 101 test cases. Each test case consists of three lines: the first line has n, which will be a prime number not more than 1500. The second and third lines give the two polynomials f(x) and g(x). The polynomials are represented by first an integer D which represents the degree of the polynomial, followed by (D + 1) positive integers representing the coefficients of the polynomial. the coefficients are in decreasing order of Exponent. Input ends with n = 0. The value of D wonâ€™t be more than 100. Output For each test case, print the test case number and r(x), in the same format as the input Note: The first sample input has 2x3 +2x2 +x+1 and x4 +2x2 +2x+2 as the functions. Sample Input 3 32211 410222 0 Sample Output Case 1: 2 1 2 1