Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3915
AEK-AFH

Time Limit: 15 Seconds      Memory Limit: 65536 KB

This was a simple problem.

You were supposed to calculate the following algebraic expression.

algebraic expression0


But Bobgy thinks this is too easy. He wants you to calculate an algebraic expression that is more complex. The algebraic expression is shown below.

algebraic expression


In this algebraic expression, ei ( 1 ≤ i ≤ m ) may be a complex number.

To make this problem easier, we assume that zi ( 1 ≤ i ≤ m ) in this problem can only be 1, 2, 3, 5, 6, 7, 10.

Input

There are multiple cases. The first line of each test case contains two integers n and m ( 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 5 ) . From the second line, each line contains three integers z, a, b ( 1 ≤ z ≤ 10 , z does not belong to the set {4, 8, 9} , 1 ≤ a, b ≤ 10 ) . The coefficient e of algebraic expression is a+b*i where i is the imaginary unit, a and b are integers.

Output

For each test case, output the real part and the imaginary part of the coefficient of algebraic expression respectively.

Note that you must simplify the expression following the common sense before you output the coefficients. If your final expression is sigma((a_j+b_j*i)*sqrt(z_j)), j=1, 2, ..., k. (i is the imaginary unit), then there must be no term with a z that still has a divisor which is a square number.

Sample Input

1 3
2 1 0
3 1 0
6 1 0
2 3
2 1 0
3 1 0
6 1 0
2 3
6 3 2
7 2 5
6 1 3

Sample Output

0 0
11 0
-201 380

Hint

The expression for the third sample is algebraic expression
Author: YANG, Yilin
Source: ZOJ Monthly, February 2016
Submit    Status