We all know how to calculate $a^{b}$ using $\boldsymbol{b}$ operations by multiplying $1$ by $\boldsymbol{a}$ a total of $\boldsymbol{b}$ times. The drawback to this method is that $\boldsymbol{b}$ can be large, which makes exponentiation very slow.

There is a well known method called Russian Peasant Multiplication that you can read about here. Now let's use this to raise some complex numbers to powers!

You're given $\textit{q}$ queries where each query consists of four integers: $\boldsymbol{a}$, $\boldsymbol{b}$, $\boldsymbol{\mbox{k}}$, and $m$. For each query, calculate $(a+b\cdot i)^k=c+d\cdot i$ (where $\boldsymbol{i}$ is an imaginary unit) and then print the respective values of $c\ \textbf{mod}\ m$ and $d\:\textbf{mod}\:m$ as two space-separated integers on a new line.

Input Format

The first line contains a single integer, $\textit{q}$, denoting the number of queries.

Each of the $\textit{q}$ subsequent lines describes a query in the form of four space-separated integers: $\boldsymbol{a}$, $\boldsymbol{b}$, $\boldsymbol{\mbox{k}}$, and $m$ (respectively).

Constraints

$1\leq q\leq10^5$
$0\leq k\leq10^{18}$
$2\leq m\leq10^9$
$0\leq a,b\leq m$

Output Format

For each query, print the two space-separated integers denoting the respective values of $c\ \textbf{mod}\ m$ and $d\:\textbf{mod}\:m$ on a new line.

Sample Input
3
2 0 9 1000
0 1 5 10
8 2 10 1000000000

Sample Output
512 0
0 1
880332800 927506432

Explanation

In the first query, we have $\boldsymbol{a}=2$, $\boldsymbol{b=0}$, $k=9$, $m=1000$. We calculate the following:

$2^9=512$
$i^5=i$

见题面

见题面