#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <ctime>
#include <iomanip>
#include <cassert>
#include <random>
#include <chrono>
#include <map>
#include <unordered_map>
#include <complex>
#define ll long long
#define ld long double
#define pii pair <int, int>
#define x first
#define y second
#pragma GCC optimize("Ofast")
#pragma warning(disable : 4996)
using namespace std;
mt19937_64 gen(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());
uniform_int_distribution <int> rng;
const int MOD = (int)1e9 + 7;
namespace recurrences {
// binary exponentiation
template <int MOD>
int lgput(int n, int p) {
int ans = 1, x = n;
while (p) {
if (p & 1)
ans = 1LL * ans * x % MOD;
x = 1LL * x * x % MOD;
p >>= 1;
}
return ans;
}
// modular integer class
template <int MOD>
struct Int {
int x;
Int() {
x = 0;
}
Int(int _x) {
if (_x < 0)
_x += MOD;
if (_x >= MOD)
_x -= MOD;
x = _x;
}
friend ostream& operator << (ostream& os, const Int& X) {
os << (false ? X.x - MOD : X.x);
return os;
}
friend istream& operator >> (istream& is, Int& X) {
is >> X.x;
return is;
}
Int operator + (const Int& other) const {
int val = x + other.x;
return (val >= MOD ? val - MOD : val);
}
Int operator += (const Int& other) {
return *this = *this + other;
}
Int operator - (const Int& other) const {
int val = x - other.x;
return (val < 0 ? val + MOD : val);
}
Int operator -= (const Int& other) {
return *this = *this - other;
}
Int operator * (const Int& other) const {
return 1LL * x * other.x % MOD;
}
Int operator *= (const Int& other) {
return *this = *this * other;
}
Int operator / (const Int& other) const {
return 1LL * x * other.inv() % MOD;
}
bool operator == (const Int& other) const {
return x == other.x;
}
bool operator != (const Int& other) const {
return x != other.x;
}
int pow(int p) const {
return lgput<MOD>(x, p);
}
int inv() const {
return lgput<MOD>(x, MOD - 2);
}
};
const bool slow_mult = false;
int get_primitive_root(int p) {
vector<int> fact;
int phi = p - 1, n = phi;
for (int i = 2; i * i <= n; ++i)
if (n % i == 0) {
fact.push_back(i);
while (n % i == 0)
n /= i;
}
if (n > 1)
fact.push_back(n);
for (int res = 2; res <= p; ++res) {
bool ok = true;
for (size_t i = 0; i < fact.size() && ok; ++i)
ok &= lgput<MOD>(res, phi / fact[i]) != 1;
if (ok) {
return res;
}
}
return -1;
}
int primitive_root = get_primitive_root(MOD);
int get_smallest_power(int n) {
int p = 1;
while (p < n)
p <<= 1;
return p;
}
bool calcW = true;
Int<MOD> valw[30], invvalw[30];
// modular
template <typename T>
struct Poly {
vector <T> p;
Poly() {
p.clear();
}
Poly(vector <T> values) {
p = values;
}
Poly(int val) {
p = { val };
}
T& operator [] (int index) {
assert(index < (int)p.size());
return p[index];
}
void setDegree(int deg) {
p.resize(deg + 1);
}
int deg() const {
return p.size() - 1;
}
friend ostream& operator << (ostream& os, const Poly& P) {
for (auto& i : P.p)
os << i << " ";
return os;
}
bool operator == (const Poly& other) const {
if (deg() != other.deg())
return 0;
for (int i = 0; i <= deg(); i++) {
if (p[i] != other.p[i])
return 0;
}
return 1;
}
Poly operator + (const Poly& other) const {
Poly sum(p);
sum.setDegree(max(deg(), other.deg()));
for (int i = 0; i <= other.deg(); i++)
sum[i] += other.p[i];
return sum;
}
// add
Poly operator += (const Poly& other) {
return *this = *this + other;
}
Poly operator - (const Poly& other) const {
Poly dif(p);
dif.setDegree(max(deg(), other.deg()));
for (int i = 0; i <= other.deg(); i++)
dif[i] -= other.p[i];
return dif;
}
// substract
Poly operator -= (const Poly& other) {
return *this = *this - other;
}
// scalar multiplication
Poly operator * (const T& other) const {
Poly mult(*this);
for (auto& i : mult.p)
i *= other;
return mult;
}
// scalar multiplication
Poly operator *= (const T& other) {
return *this = *this * other;
}
// scalar division
Poly operator / (const T& other) const {
Poly mult(*this);
Int<MOD> val = other.inv();
for (auto& i : mult.p)
i *= val;
return mult;
}
// scalar division
Poly operator /= (const T& other) {
return *this = *this / other;
}
Poly fft(bool invert) {
Poly Ans(p);
Int<MOD> root(primitive_root);
if (calcW) {
calcW = false;
for (int i = 0; i < 30; i++) {
valw[i] = root.pow((MOD - 1) >> (i + 1));
invvalw[i] = valw[i].inv();
}
}
int ind = 0, n = deg();
for (int i = 1; i < n; i++) {
int b;
for (b = n / 2; ind & b; b >>= 1)
ind ^= b;
ind ^= b;
if (i < ind)
swap(Ans[i], Ans[ind]);
}
for (int l = 2, p = 0; l <= n; l <<= 1, p++) {
Int<MOD> bw(!invert ? valw[p] : invvalw[p]);
for (int i = 0; i < n; i += l) {
Int<MOD> w(1);
for (int j = 0; j < l / 2; j++) {
int i1 = i + j, i2 = i + j + l / 2;
Int<MOD> val1(Ans[i1]), val2(Ans[i2] * w);
Ans[i1] = val1 + val2;
Ans[i2] = val1 - val2;
w *= bw;
}
}
}
if (invert) {
Int<MOD> inv = Int<MOD>(n).inv();
for (int i = 0; i < n; i++)
Ans[i] *= inv;
}
return Ans;
}
// multiplies 2 polynomials
Poly operator * (const Poly& other) const {
if (!primitive_root) { // for small sizes, use naive multiplication
Poly mult;
mult.setDegree(deg() + other.deg());
for (int i = 0; i <= deg(); i++) {
for (int j = 0; j <= other.deg(); j++)
mult[i + j] += p[i] * other.p[j];
}
return mult;
}
Poly A(p), B(other.p);
int sz = max(get_smallest_power(A.deg() + 1), get_smallest_power(B.deg() + 1)) * 2;
A.setDegree(sz), B.setDegree(sz);
A = A.fft(0);
B = B.fft(0);
for (int i = 0; i < sz; i++)
A[i] *= B[i];
A = A.fft(1);
A.setDegree(deg() + other.deg());
return A;
}
// p mod q
Poly operator % (const Poly& other) const {
int d = deg() - other.deg();
if (d < 0)
return *this;
if (false) {
Poly R2(p);
for (int i = deg(); i >= other.deg(); i--) {
R2 -= (other * R2[i] / other.p[other.deg()]).shift(i - other.deg());
}
R2.setDegree(other.deg() - 1);
//return R;
}
Poly A, B = other;
for (int i = 0; i <= d; i++) {
A.p.push_back(p[deg() - i]);
}
for (int i = 0; i <= B.deg() / 2; i++)
swap(B[i], B[B.deg() - i]);
Poly C = A * B.inverse(d);
C.setDegree(d);
for (int i = 0; i <= d / 2; i++)
swap(C[i], C[d - i]);
Poly R = *this - other * C;
R.setDegree(other.deg() - 1);
return R;
}
// *x^n
Poly shift(int index) {
Poly q = p;
q.setDegree(deg() + index);
for (int i = deg(); i >= 0; i--)
q[i + index] = q[i];
for (int i = index - 1; i >= 0; i--)
q[i] = T(0);
return q;
}
// derivate of P
Poly derivative() {
Poly D;
D.setDegree(deg() - 1);
for (int i = 1; i <= deg(); i++)
D[i - 1] = T(i) * p[i];
return D;
}
// integral of P
Poly integral() {
Poly I;
I.setDegree(deg() + 1);
for (int i = 0; i <= deg(); i++)
I[i + 1] = p[i] / T(i + 1);
return I;
}
// P^-1 mod x^n
Poly inverse(int n) {
Poly Inv(p[0].inv()), two(2);
int power = 1;
while ((power / 2) <= n) {
Poly A;
for (int i = 0; i <= power; i++)
A.p.push_back((i <= deg() ? p[i] : 0));
Inv = Inv * (two - A * Inv);
Inv.setDegree(power);
power <<= 1;
}
Inv.setDegree(n);
return Inv;
}
// log(P) mod x^n
Poly log(int n) {
Poly Log(derivative());
Log = Log * this->inverse(n);
return Log.integral();
}
// e^P mod x^n
Poly exp(int n) {
Poly Exp(1);
int power = 1;
while ((power / 2) <= n) {
Poly A(p);
A.setDegree(power);
Exp += Exp * A - Exp * Exp.log(power);
Exp.setDegree(power);
power <<= 1;
}
Exp.setDegree(n);
return Exp;
}
// p^power mod mod, where mod is a polynomial
Poly pow(uint64_t power, Poly mod) {
Poly Pow(1), X(p);
while (power) {
if (power & 1)
Pow = Pow * X % mod;
X = X * X % mod;
power >>= 1;
}
return Pow;
}
};
// berlekamp-massey algorithm
template <int MOD>
Poly<Int<MOD>> berlekamp_massey(vector <Int<MOD>> values) {
Poly<Int<MOD>> P(values), B, C, Pol(-1);
int n = values.size(), lst = -1;
Int<MOD> lstError;
for (int i = 0; i < n; i++) {
Int<MOD> error = P[i];
for (int j = 1; j <= C.deg() + 1; j++)
error -= C[j - 1] * P[i - j];
if (error == Int<MOD>(0))
continue;
if (lst == -1) {
C = C.shift(i + 1);
lst = i;
lstError = P[i];
continue;
}
Poly<Int<MOD>> D = (Pol * error / lstError);
Poly<Int<MOD>> t = C;
// instead of shifting D with i - lst - 1 positions
// do the substraction on the last D.deg() coeficients
if (i - lst - 1 + D.deg() > C.deg())
C.setDegree(i - lst - 1 + D.deg());
for (int j = 0; j <= D.deg(); j++)
C[j + i - lst - 1] -= D[j];
if (i - t.deg() > lst - B.deg()) {
B = t;
Pol = B;
Pol = Pol.shift(1);
Pol[0] = Int<MOD>(-1);
lst = i;
lstError = error;
}
//C -= D;
}
return C;
}
// find kth term based on terms of recurrence
// assuming first term has index 1
template <int MOD>
Int<MOD> kth_term(vector <Int<MOD>> v, uint64_t k) {
vector <Int<MOD>> x = { Int<MOD>(0), Int<MOD>(1) };
Poly<Int<MOD>> CP = berlekamp_massey<MOD>(v);
Poly<Int<MOD>> X(x);
// characteristic polynomial is of form
// x^n - sigma(i = 1..n, c[i] * x^(n-i))
// that's why we need to reverse the recurrence
// from berlekamp-massey
CP *= Int<MOD>(-1);
CP = CP.shift(1);
for (int i = 0; i <= CP.deg() / 2; i++)
swap(CP[i], CP[CP.deg() - i]);
CP[CP.deg()] = 1;
X = X.pow(k - 1, CP);
Int<MOD> term(0);
for (int i = 0; i <= X.deg(); i++)
term += X[i] * v[i];
return term;
}
template <int MOD>
void berlekamp_massey_test() {
int n;
vector<Int<MOD>> v;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
v.push_back(x);
}
Poly<Int<MOD>> rec = berlekamp_massey<MOD>(v);
// sanity check
for (int k = rec.deg() + 2; k <= 30; k++) {
Int<MOD> val(0);
for (int i = k - rec.deg() - 1; i < k; i++)
val += v[i - 1] * rec[k - 1 - i];
assert(val == kth_term(v, k));
if (k > n)
v.push_back(val);
}
uint64_t k;
cin >> k;
cout << kth_term<MOD>(v, k) << "\n";
}
template <int MOD>
void berlekamp_massey_speed_test() {
int n;
vector<Int<MOD>> v;
n = 1000;
for (int i = 0; i < n; i++) {
int x;
//cin >> x;
x = rng(gen);
v.push_back(x);
}
ld t1 = clock();
for (int k = 1; k <= 200; k++)
kth_term<MOD>(v, k);
ld t2 = clock();
cout << (t2 - t1) / CLOCKS_PER_SEC << "s\n";
}
template <int MOD>
void inverse_test() {
int n;
cin >> n;
vector <Int<MOD>> v;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
v.push_back(Int<MOD>(x));
}
Poly<Int<MOD>> P(v), Inv, Exp, Log;
int deg = 10;
Inv = P.inverse(deg);
cout << "Inverse: " << Inv << "\n";
Exp = P.exp(deg);
cout << "Exponential: " << Exp << "\n";
Log = P.log(deg);
cout << "Logarithm: " << Log << '\n';
}
};
using namespace recurrences;
struct FFT {
double PI = acos(-1);
void fft(vector <complex <double>>& v, bool inv) {
int n = v.size();
if (n == 1)
return;
vector <complex <double>> va(n / 2), vb(n / 2);
for (int i = 0; i < n / 2; i++) {
va[i] = v[2 * i];
vb[i] = v[2 * i + 1];
}
fft(va, inv);
fft(vb, inv);
double alpha = 2 * PI / n * (inv ? -1 : 1);
complex <double> w(1), z(cos(alpha), sin(alpha));
for (int i = 0; i < n / 2; i++) {
v[i] = va[i] + w * vb[i];
v[i + n / 2] = va[i] - w * vb[i];
if (inv)
v[i] /= 2, v[i + n / 2] /= 2;
w *= z;
}
}
template <typename T>
vector <T> mult_normal(vector <T> a, vector <T> b) {
int n = 1;
while (n < a.size() + b.size())
n *= 2;
vector <complex <double>> va, vb;
for (auto& i : a)
va.push_back(i);
for (auto& i : b)
vb.push_back(i);
va.resize(n);
vb.resize(n);
fft(va, 0);
fft(vb, 0);
for (int i = 0; i < n; i++)
va[i] *= vb[i];
fft(va, 1);
vector <T> ans;
for (auto& i : va)
ans.push_back(round(i.real()));
return ans;
}
template <typename T, int MOD>
vector <T> mult_mod(vector <T> a, vector <T> b) {
int val = sqrt(MOD);
vector <T> a1(a.size()), a2(a.size()), b1(b.size()), b2(b.size());
for (int i = 0; i < a.size(); i++)
a1[i] = a[i] / val, a2[i] = a[i] % val;
for (int i = 0; i < b.size(); i++)
b1[i] = b[i] / val, b2[i] = b[i] % val;
vector <T> x1 = mult_normal<T>(a1, b1), x2 = mult_normal<T>(a1, b2), x3 = mult_normal<T>(a2, b1), x4 = mult_normal<T>(a2, b2);
vector <T> ans(x1.size());
for(int i = 0; i < x1.size(); i++)
ans[i] = (1LL * x1[i] % MOD * val % MOD * val % MOD + 1LL * (x2[i] % MOD + x3[i] % MOD) * val % MOD + x4[i] % MOD) % MOD;
return ans;
}
} fft;
struct Gauss {
int n, m, sgn;
vector <vector <ld>> v;
vector <int> ind;
void init(int _n, int _m, vector <vector <ld>> w) {
v = w, n = _n, m = _m;
ind.resize(n + 5);
sgn = 1;
}
void solve() {
for (int j = 1; j <= m; j++) {
int line = 0;
ld mx = -1e18;
for (int i = j; i <= n; i++) {
if (abs(v[i][j]) < 1e-9) continue;
if (abs(v[i][j]) > mx) {
mx = abs(v[i][j]);
line = i;
}
}
if (!line) continue;
swap(v[line], v[j]);
if (line != j) sgn *= -1;
for (int k = m + 1; k >= j; k--)
v[j][k] /= v[j][j];
for (int i = 1; i <= n; i++) {
if (abs(v[i][j]) < 1e-9 || i == j) continue;
for (int k = m + 1; k >= j; k--) v[i][k] -= v[i][j] * v[j][k];
}
}
}
vector <ld> get_solutions() {
// assuming "solve" was called before
vector <ld> x(m + 1);
for (int j = 1; j <= m; j++) {
x[j] = (j <= n ? v[j][m + 1] : 0);
if (j <= n && abs(v[j][j]) < 1e-9 && abs(x[j]) >= 1e-9) {
x.clear();
return x;
}
}
for (int j = m + 1; j <= n; j++) {
if (abs(v[j][m + 1]) >= 1e-9) {
x.clear();
return x;
}
}
return x;
}
} gs;
void solve() {
int n, m;
vector <vector <ld>> v;
cin >> n >> m;
v.resize(n + 1);
for (int i = 1; i <= n; i++) {
v[i].resize(m + 2);
for (int j = 1; j <= m + 1; j++)
cin >> v[i][j];
}
gs.init(n, m, v);
gs.solve();
vector <ld> x = gs.get_solutions();
if (x.empty()) {
cout << "Imposibil\n";
return;
}
for (int j = 1; j <= m; j++)
cout << fixed << setprecision(10) << x[j] << " ";
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
freopen("gauss.in", "r", stdin);
freopen("gauss.out", "w", stdout);
#endif
int T = 1;
for (; T; T--) {
solve();
}
return 0;
}