Lord of the Characteristic Polynomials (2)

For an $n \times n$ matrix $A$, the determinant is defined as follows, where $a_{ij}$ is the entry in row $i$ and column $j$. $S_n$ is the set of permutations of $\{1, \cdots, n\}$, so $\{1, \cdots, n\} = \{\sigma(1), \cdots, \sigma(n)\}$ holds for every $\sigma \in S_n$.

$\det A = \sum_{\sigma \in S_{n}} \mathrm{sgn}(\sigma) \cdot \left(\prod_{i = 1}^{n} a_{i \sigma(i)}\right)$

The characteristic polynomial $\phi_{A}(x)$ of $A$ is a polynomial of degree $n$ in $x$, defined as $\phi_{A}(x) = \det(xI - A) = c_{n}x^{n} + c_{n-1}x^{n-1} + \cdots + c_{0}$.

In this problem the entries are special. You are given an integer $D \neq 1$ that is not divisible by any perfect square greater than 1. Every entry of $A$ has the form $a + b\sqrt{D}$ with integers $a$ and $b$, so each entry is an element of the set

$\mathbb{Z}[\sqrt{D}] = \{a + b\sqrt{D} \mid a, b \in \mathbb{Z} \}$

The coefficients $c_{0}, \cdots, c_{n}$ of $\phi_{A}(x)$ are also elements of $\mathbb{Z}[\sqrt{D}]$, and this can be proven. Each $c_{i} = p_{i} + q_{i}\sqrt{D}$ has unique integers $p_{i}$ and $q_{i}$. Given an integer $M$, write a program that outputs the remainder of each $p_{i}$ and $q_{i}$ divided by $M$.

The first line contains the size $n$ of the matrix, the integer $M$ used for division, and the integer $D$.

Each of the next $n$ lines contains $2n$ integers. If the $2j-1$-th number on line $i$ is $x$ and the $2j$-th number is $y$, then $a_{ij} = x + y\sqrt{D}$.

Print $n+1$ lines. On line $i$, print the remainders of $p_{i}$ and $q_{i}$ divided by $M$, separated by a space.

The remainder of an integer $a$ divided by $M$ is the smallest non-negative integer $b$ such that $a - b$ is a multiple of $M$.

• $1 \le n \le 100$
• $1 \le M \le 10^{9}$
• $-10^{9} \le D \le 10^{9}$
• $D \neq 1$, and $D$ is not divisible by any perfect square greater than 1.
• For all $1 \le i, j \le n$, if $a_{ij} = x + y\sqrt{D}$, then $0 \le x, y < M$.

• For each $x \in \mathbb{Z}[\sqrt{D}]$, there are unique integers $a, b$ such that $x = a + b\sqrt{D}$.
• $(a + b\sqrt{D}) + (c + d\sqrt{D}) = (a + c) + (b + d)\sqrt{D}$
• $(a + b\sqrt{D})(c + d\sqrt{D}) = (ac + bdD) + (ad + bc)\sqrt{D}$