#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using ll = long long;
const int Q = 1e5;
const int N = 20;
const int V = N*Q;
const ll LINF = 1e18;
struct MinMaxValue {
ll min_value;
ll max_value;
MinMaxValue operator * (const MinMaxValue& x) const {
if (x.max_value < 0 || max_value < 0) {
return MinMaxValue { 0, -1 };
}
return MinMaxValue {
.min_value = x.min_value + min_value,
.max_value = x.max_value + max_value
};
}
MinMaxValue operator + (const MinMaxValue& x) const {
if (x.max_value == -1) return *this;
if (max_value == -1) return x;
return MinMaxValue {
.min_value = min(x.min_value, min_value),
.max_value = max(x.max_value, max_value)
};
}
MinMaxValue& operator += (const MinMaxValue& x) {
return *this = *this + x;
}
void Reset() {
min_value = 0;
max_value = -1;
}
};
struct {
MinMaxValue dig, ver, hor;
int cnt;
int go[4];
} nd[V];
int vc = 0;
MinMaxValue dig[N+1], ver[N+1], hor[N+1];
std::set<ll> words;
int NewVertex(int h) {
int* go = nd[vc].go;
go[0] = go[1] = go[2] = go[3] = -1;
nd[vc].dig = dig[h];
nd[vc].hor = hor[h];
nd[vc].ver = ver[h];
nd[vc].cnt = 0;
return vc++;
}
tuple<const MinMaxValue&, const MinMaxValue&, const MinMaxValue&, int> GetState(int v, int h) {
return v == -1 ? make_tuple(cref(dig[h]), cref(ver[h]), cref(hor[h]), 0)
: make_tuple(cref(nd[v].dig), cref(nd[v].ver), cref(nd[v].hor), nd[v].cnt);
}
void Calculate(int v, int h, int corner) {
auto [dig0, ver0, hor0, cnt0] = GetState(nd[v].go[corner^0], h-1);
auto [dig1, ver1, hor1, cnt1] = GetState(nd[v].go[corner^1], h-1);
auto [dig2, ver2, hor2, cnt2] = GetState(nd[v].go[corner^2], h-1);
auto [dig3, ver3, hor3, cnt3] = GetState(nd[v].go[corner^3], h-1);
nd[v].cnt = cnt0 + cnt1 + cnt2 + cnt3;
nd[v].dig.Reset();
if (cnt0 == 0) nd[v].dig += hor2 * dig3 * ver1;
if (cnt3 == 0) nd[v].dig += ver2 * dig0 * hor1;
nd[v].hor = ver0 * dig2 * dig3 * ver1;
if (cnt2 + cnt3 == 0) nd[v].hor += hor0 * hor1;
nd[v].ver = hor0 * dig1 * dig3 * hor2;
if (cnt1 + cnt3 == 0) nd[v].ver += ver0 * ver2;
}
void UpdateCount(int v, int h, int corner, ll msk, ll msk_save) {
if (h == 0) {
if (nd[v].cnt == 0) {
words.insert(msk_save);
} else {
words.erase(msk_save);
}
nd[v].cnt ^= 1;
} else {
UpdateCount(nd[v].go[msk & 3], h-1, msk & 3, msk >> 2, msk_save);
Calculate(v, h, corner);
}
}
bool near_symbols[256][256];
MinMaxValue GetAnswer(int h) {
int v = 0;
if (nd[v].cnt == 0) {
return MinMaxValue { .min_value = 2, .max_value = 4 * dig[h-1].max_value };
}
MinMaxValue res; res.Reset();
bool cycle_len2 = false;
if (nd[v].cnt <= 1) cycle_len2 = true;
if (nd[v].cnt == 2) {
string s, t;
for (ll msk = *words.begin(); s.size() < h; msk >>= 2) s.push_back("abdc"[msk & 3]);
for (ll msk = *next(words.begin()); t.size() < h; msk >>= 2) t.push_back("abdc"[msk & 3]);
auto flag = near_symbols[s.back()][t.back()];
if (s.substr(0, h-1) == t.substr(0, h-1) && flag) {
cycle_len2 = true;
}
int s_suf = 0, t_suf = 0;
while (s_suf < h && s[h - s_suf - 1] == s.back()) ++s_suf;
while (t_suf < h && t[h - t_suf - 1] == t.back()) ++t_suf;
if (s_suf == t_suf && s_suf < h && flag && s.substr(0, h-s_suf-1) == t.substr(0, h-t_suf-1)
&& s.back() == t[h - s_suf - 1]
&& t.back() == s[h - t_suf - 1]) cycle_len2 = true;
}
if (cycle_len2) {
res.min_value = 2;
res.max_value = 2;
}
while (h != 0) {
const int v0 = nd[v].go[0], v1 = nd[v].go[1], v2 = nd[v].go[2], v3 = nd[v].go[3];
const auto& dig0 = get<0>(GetState(v0, h-1));
const auto& dig1 = get<0>(GetState(v1, h-1));
const auto& dig2 = get<0>(GetState(v2, h-1));
const auto& dig3 = get<0>(GetState(v3, h-1));
if(dig0.max_value > 0 && dig1.max_value > 0 && dig2.max_value > 0 && dig3.max_value > 0) {
res += dig0 * dig1 * dig2 * dig3;
}
--h;
if (v0 != -1 && nd[v0].cnt == nd[v].cnt) { v = v0; continue; }
if (v1 != -1 && nd[v1].cnt == nd[v].cnt) { v = v1; continue; }
if (v2 != -1 && nd[v2].cnt == nd[v].cnt) { v = v2; continue; }
if (v3 != -1 && nd[v3].cnt == nd[v].cnt) { v = v3; continue; }
break;
}
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
vector<ll> v(q);
for (int i = 0; i < 4; ++i) {
int j = (i + 1) % 4;
near_symbols['a' + i]['a' + j] = true;
near_symbols['a' + j]['a' + i] = true;
}
dig[0] = ver[0] = hor[0] = { 1, 1 };
for (int i = 1; i <= n; ++i) {
dig[i] = hor[i-1] * dig[i-1] * ver[i-1];
hor[i] = ver[i] = hor[i-1] * hor[i-1] + ver[i-1] * ver[i-1] * dig[i-1] * dig[i-1];
}
int m_root = NewVertex(n); // make_root
assert(m_root == 0);
for (int i = 0; i < q; ++i) {
string s; cin >> s;
for (int j = 0; j < n; ++j) {
v[i] += (s[j] == 'b' || s[j] == 'c' ? 1ll : 0) << (2*j);
v[i] += (s[j] == 'c' || s[j] == 'd' ? 2ll : 0) << (2*j);
}
int w = 0;
for (int j = 0; j < n; ++j) {
int& next = nd[w].go[(v[i] >> (2*j)) & 3];
if (next == -1) next = NewVertex(n-j-1);
w = next;
}
}
for (ll msk : v) {
UpdateCount(0, n, 0, msk, msk);
auto [a, b] = GetAnswer(n);
if (a > b) {
cout << -1 << '\n';
} else {
cout << a << " " << b << '\n';
}
}
}