Welcome to Sevenkplus' perfect math class! In this class, you will learn about representation theory. And this class is in a different format than before: Learning by doing! You need to solve a problem, which can be solved elegantly using (really elementary) representation theory. (Of course you can solve this problem without representation theory. But learning more is helpful!)

Sevenkplus had an $n\times n$ complex matrix ${M}$. He calculated $Tr(M^0),...,Tr(M^{m-1})$ and found that $M^{m}=I$. (For a square matrix ${A}$, $Tr(A)$ is the trace of ${A}$. ${I}$ is the $n\times n$ identity matrix.)
However, the dark side of the world destroyed $\mbox{M}$, and only $n,m,Tr(M^0),...,Tr(M^{m-1})$ remained.

Sevenkplus wants to recover his beloved ${M}$. However, this is impossible. 

Nevertheless, doing something weaker is possible: Only recover the eigenvalues of ${M}$. Here the eigenvalues are defined to be the entries on the diagonal of the Jordan normal form of ${M}$. For a fixed ${M}$, they are unique up to permutation.

Input Format

The first line contains two space separated integers, $n$ and $m$. 

Followed by $m$ lines where for each value of $k\in[0,m)$ line contains two real numbers $a_{k},b_{k}$, which means that $Tr(M^k)=a_k+i\cdot b_k$, where $\boldsymbol{i}$ is the imaginary unit.  

Constraints 

$1\leqslant n\leqslant10000$ 

$1\leq m\leqslant2000$ 

$|a_k|,|b_k|\leqslant10000$ 

It is guaranteed that there is an ${M}$ that satisfies the relations.  

Output Format

Print $n$ lines where for each value of $k\in[0,m)$ line contains two real numbers $c_k,d_k$. 

The multi-set of $c_{k}+i\cdot d_{k}$ should be the multi-set of eigenvalues of ${M}$.  

You can output the eigenvalues in any order. 

In case of multiple answers output any of them, your answer is considered correct if your answer satisfies the input, within absolute error ${10^{-6}}$.  

Sample Input
2 4
2 0
0 0
2 0
0 0

Sample Output
1 0
-1 0

Explanation

Two possible ${M}$'s are $\left[\begin{matrix}1&0\\ 0&-1\end{matrix}\right]$ and $\left[\begin{array}{cc}-1&0\\ 0&1\end{array}\right]$. Note that there may be other $\mbox{M}$'s that satisfies the relations.

Difficulty: HARD
Tags: Combinatorics

Starter code:

Solutions:
from math import pi, e
r = lambda type: map(type, input().split())
read_complex = lambda : complex(*r(float))
(n, m) = r(int)
c = [read_complex() for _ in range(m)]
omega = e ** (-2j * pi / m)
omega_pow = [1]
for _ in range(1, m):
	omega_pow.append(omega_pow[-1] * omega)
d = [sum((omega_pow[i * j % m] * c[j] for j in range(m))) / m for i in range(m)]
cnt = [round(x.real) for x in d]
for (i, rep) in enumerate(cnt):
	val = omega_pow[-i % m]
	outp = '{} {}'.format(val.real, val.imag)
	for j in range(cnt[i]):
		print(outp)


import fileinput
import math
inpt = fileinput.input()
line = inpt.readline().split(' ')
n = int(line[0])
m = int(line[1])
s = []
for k in range(m):
	line = inpt.readline().split(' ')
	s.append(complex(float(line[0]), float(line[1])))
for k in range(m):
	phi = 2 * math.pi * k / m
	z = math.cos(phi) + 1j * math.sin(phi)
	cnt = 0
	for i in range(m):
		cnt += z ** i * (s[i].conjugate() / m)
	cnt = int(round(abs(cnt)))
	for i in range(cnt):
		print('%.9f %.9f' % (z.real, z.imag))


import fileinput
import math
inpt = fileinput.input()
line = inpt.readline().strip().split(' ')
n = int(line[0])
m = int(line[1])
s = []
for k in range(m):
	line = inpt.readline().strip().split(' ')
	s.append(complex(float(line[0]), float(line[1])))
if True:
	for k in range(m):
		phi = 2 * math.pi * k / m
		z = math.cos(phi) + 1j * math.sin(phi)
		cnt = 0
		for i in range(m):
			cnt += z ** i * (s[i].conjugate() / m)
		cnt = int(round(abs(cnt)))
		for i in range(cnt):
			print('%.7f %.7f' % (z.real, z.imag))


import math

def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def cosine(theta):
	theta = ref(theta)
	return 1 - pow(theta, 2) / 2 + pow(theta, 4) / 24 - pow(theta, 6) / 720 + pow(theta, 8) / 40320

def sine(theta):
	theta = ref(theta)
	return theta - pow(theta, 3) / 6 + pow(theta, 5) / 120 - pow(theta, 7) / 5040 + pow(theta, 9) / 362880

def ref(theta):
	pi = 3.141592653589793
	if 0 <= theta <= pi / 2:
		return theta
	elif pi / 2 < theta <= pi:
		return pi - theta
	elif pi < theta <= 3 * pi / 2:
		return theta - pi
	elif 3 * pi / 2 < theta <= 2 * pi:
		return 2 * pi - theta
	else:
		return theta

def c_mult(a, b, c, d):
	return (a * c - b * d, a * d + b * c)

def complex_binary_pow(a, b, p):
	p_bits = bitize(p)
	current_a = a
	current_b = b
	current_real = 1
	current_im = 0
	for i in range(0, len(p_bits)):
		if p_bits[i]:
			(current_real, current_im) = c_mult(current_a, current_b, current_real, current_im)
		prev_a = current_a
		current_a = current_a * current_a - current_b * current_b
		current_b *= 2 * prev_a
	return (current_real, current_im)

def compute_eigenvalues(n, m, trace_powers):
	zeta_m = []
	current_r = 1
	current_im = 0
	eigenvalues = []
	pi = 3.141592653589793
	zeta_a = math.cos(2 * pi / m)
	zeta_b = -1 * math.sin(2 * pi / m)
	for K in range(0, m):
		zeta_m.append([round(current_r, 10), round(current_im, 10)])
		(current_r, current_im) = c_mult(current_r, current_im, zeta_a, zeta_b)
	current_zeta = [[1, 0] for _ in zeta_m]
	for p in range(0, m):
		total_re = 0
		total_im = 0
		for k in range(0, m):
			(c_re, c_im) = c_mult(trace_powers[k][0], trace_powers[k][1], current_zeta[k][0], current_zeta[k][1])
			(current_zeta[k][0], current_zeta[k][1]) = c_mult(current_zeta[k][0], current_zeta[k][1], zeta_m[k][0], zeta_m[k][1])
			total_re += c_re
			total_im += c_im
		t = int(round(total_re, 0))
		t //= m
		for e in range(0, t):
			eigenvalues.append([zeta_m[p][0], -1 * zeta_m[p][1]])
	return eigenvalues
(n, m) = [int(a) for a in input().split()]
trace_powers = []
for _ in range(0, m):
	(a, b) = [float(x) for x in input().split()]
	trace_powers.append([a, b])
eigenvalues = compute_eigenvalues(n, m, trace_powers)
for e in eigenvalues:
	print(e[0], e[1])


import os
import sys
import math

def cmul(x, y):
	a = x[0]
	b = x[1]
	c = y[0]
	d = y[1]
	return [a * c - b * d, a * d + b * c]

def scalarProduct(j, chi, m):
	root = [math.cos(2 * j * math.pi / m), math.sin(2 * j * math.pi / m)]
	sum = [0, 0]
	power = [1, 0]
	for x in range(0, len(chi)):
		u = [chi[x][0], -chi[x][1]]
		buffer = cmul(power, u)
		sum = [sum[0] + buffer[0], sum[1] + buffer[1]]
		power = cmul(power, root)
	return [sum[0] / m, sum[1] / m]
first = input().split()
n = int(first[0])
m = int(first[1])
chi = []
for x in range(m):
	line = input().split()
	chi.append([float(line[0]), float(line[1])])
for j in range(m):
	sp = scalarProduct(j, chi, m)[0]
	mult = round(sp)
	for x in range(mult):
		root = [math.cos(2 * j * math.pi / m), math.sin(2 * j * math.pi / m)]
		print(root[0], ' ', root[1], file=sys.stdout)


import os, sys, math
from math import pi
from cmath import rect

def solve(n, m, s):
	s = [complex(*a) for a in s]
	basis = [0] * m
	pi2m = 2 * pi / m
	for i in range(m):
		basis[i] = rect(1, -i * pi2m)
	counts = [0] * m
	for k in range(m):
		yr = math.fsum([(basis[k * i % m] * s[i]).real for i in range(m)])
		counts[k] = round(yr / m)
	for k in range(m):
		c = counts[k]
		if c == 0:
			continue
		z = 1 / basis[k]
		for _ in range(c):
			print('{:.10f} {:.10f}'.format(z.real, z.imag))

def main():
	(n, m) = list(map(int, sys.stdin.readline().split()))
	s = []
	for _ in range(m):
		s.append(list(map(float, sys.stdin.readline().split())))
	solve(n, m, s)
main()


import os
import sys
from math import pi, cos, sin

def lire():
	a = []
	b = []
	(n, m) = list(map(int, input().split()))
	for k in range(m):
		(ak, bk) = list(map(float, input().split()))
		a.append(ak)
		b.append(bk)
	return (a, b, n, m)

def solve(a, b, n, m):
	for k in range(m):
		x = cos(2 * pi * k / m)
		y = sin(2 * pi * k / m)
		m_k = 0
		for j in range(m):
			reste = j * k % m
			m_k += a[j] * cos(2 * pi * reste / m) + b[j] * sin(2 * pi * reste / m)
		m_k /= m
		m_k = int(round(m_k, 0))
		for _ in range(m_k):
			print('{0:.7f} {1:.7f}'.format(x, y))
solve(*lire())


import math

def cmppow(x, n):
	curr = n
	toret = complex(1, 0)
	xpow = x
	while curr > 0:
		if curr % 2 == 1:
			toret = toret * xpow
		xpow = xpow * xpow
		curr //= 2
	return toret
[n, m] = list(map(int, input().split()))
traces = []
for _ in range(m):
	[a, b] = list(map(float, input().split()))
	traces.append(complex(a, b))
pluroot = complex(math.cos(2 * math.pi / m), math.sin(2 * math.pi / m))
minroot = complex(math.cos(2 * math.pi / m), -math.sin(2 * math.pi / m))
for i in range(m):
	root = cmppow(minroot, i)
	tot = complex(0, 0)
	currrootpow = complex(1, 0)
	for j in range(m):
		tot += currrootpow * traces[j]
		currrootpow *= root
	reps = int(0.5 + tot.real / m)
	actroot = cmppow(pluroot, i)
	for j in range(reps):
		print(actroot.real, actroot.imag)


from math import pi, e
r = lambda type: map(type, input().split())
read_complex = lambda : complex(*r(float))
(n, m) = r(int)
c = [read_complex() for _ in range(m)]
omega = e ** (-2j * pi / m)
omega_pow = [1]
for _ in range(1, m):
	omega_pow.append(omega_pow[-1] * omega)
d = [sum((omega_pow[i * j % m] * c[j] for j in range(m))) / m for i in range(m)]
cnt = [round(x.real) for x in d]
for (i, rep) in enumerate(cnt):
	val = omega_pow[-i % m]
	outp = '{} {}'.format(val.real, val.imag)
	for j in range(cnt[i]):
		print(outp)


import cmath

def coeff(a, eps):
	eps1 = eps.conjugate()
	c = sum((ai * eps1 ** i for (i, ai) in enumerate(a))) / len(a)
	assert abs(c.imag) < 1e-07
	assert abs(c.real - round(c.real)) < 1e-07
	m = round(c.real)
	return (eps, m)
(n, m) = map(int, input().split())
a = [complex(*map(float, input().split())) for _ in range(m)]
eps = cmath.exp(complex(0, cmath.pi * 2 / m))
for i in range(m):
	(lambda_, n_lambda) = coeff(a, eps ** i)
	if n_lambda > 0:
		for _ in range(n_lambda):
			print(f'{lambda_.real:.7g} {lambda_.imag:.7g}')


from math import pi, e
r = lambda type: map(type, input().split())
read_complex = lambda : complex(*r(float))
(n, m) = r(int)
c = [read_complex() for _ in range(m)]
omega = e ** (-2j * pi / m)
omega_pow = [1]
for _ in range(1, m):
	omega_pow.append(omega_pow[-1] * omega)
d = [sum((omega_pow[i * j % m] * c[j] for j in range(m))) / m for i in range(m)]
cnt = [round(x.real) for x in d]
for (i, rep) in enumerate(cnt):
	val = omega_pow[-i % m]
	outp = '{} {}'.format(val.real, val.imag)
	for j in range(cnt[i]):
		print(outp)


from math import pi, e
r = lambda type: map(type, input().split())
read_complex = lambda : complex(*r(float))
(n, m) = r(int)
c = [read_complex() for _ in range(m)]
omega = e ** (-2j * pi / m)
omega_pow = [1]
for _ in range(1, m):
	omega_pow.append(omega_pow[-1] * omega)
d = [sum((omega_pow[i * j % m] * c[j] for j in range(m))) / m for i in range(m)]
cnt = [round(x.real) for x in d]
for (i, rep) in enumerate(cnt):
	val = omega_pow[-i % m]
	outp = '{} {}'.format(val.real, val.imag)
	for j in range(cnt[i]):
		print(outp)


from math import pi, e
r = lambda type: map(type, input().split())
read_complex = lambda : complex(*r(float))
(n, m) = r(int)
c = [read_complex() for _ in range(m)]
omega = e ** (-2j * pi / m)
omega_pow = [1]
for _ in range(1, m):
	omega_pow.append(omega_pow[-1] * omega)
d = [sum((omega_pow[i * j % m] * c[j] for j in range(m))) / m for i in range(m)]
cnt = [round(x.real) for x in d]
for (i, rep) in enumerate(cnt):
	val = omega_pow[-i % m]
	outp = '{} {}'.format(val.real, val.imag)
	for j in range(cnt[i]):
		print(outp)