#include <bits/stdc++.h>
#ifndef LOCAL
#include "Anna.h"
#endif
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
namespace {
int variable_example = 0;
}
#ifdef LOCAL
vector<int> sent;
void Send(int a) {
assert(a == 0 or a == 1);
sent.push_back(a);
}
#endif
const int S = 63;
long long f[70][2];
void builddp() {
f[0][0] = 1;
FOR(i, 1, S) {
f[i][0] = f[i - 1][0] + f[i - 1][1];
f[i][1] = f[i - 1][0];
}
}
const int G = 42;
void Anna(int n, vector<char> s) {
builddp();
vector<int> res;
int pos = -1;
for(int i = 0; i < n; ++i) {
if (s[i] != 'X') {
res.push_back(0);
} else {
res.push_back(1);
res.push_back(0);
pos = i;
break ;
}
}
if (pos != -1) {
for(int i = pos + 1; i < n; ++i) {
int j = i;
while (j + 1 < n and s[j + 1] == s[j]) {
++j;
}
FOR(k, 1, j - i) res.push_back(0);
res.push_back( s[j] == 'Z' );
i = j;
}
}
// for(int x : res) cout << x << ' '; cout << nl;
for(int i = 0; i < sz(res); i += S) {
int r = min(sz(res) - 1, i + S - 1);
int len = r - i + 1;
long long val = 0;
FOR(j, i, r) {
if (res[j] == 1) {
val += f[len][0];
}
--len;
}
val += 1;
FOD(i, G, 0) {
Send(1LL & val >> i);
}
}
}
#ifdef LOCAL
int main() {
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
int n;
cin >> n;
vector<char> s(n);
for(int i = 0; i < n; ++i) {
cin >> s[i];
}
Anna(n, s);
cout << n << ' ' << sz(sent) << nl;
for(int x : sent) cout << x << ' ';
return 0;
}
#endif
#include <bits/stdc++.h>
#ifndef LOCAL
#include "Bruno.h"
#endif
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b or a==-1) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
namespace {
int variable_example = 0;
int FunctionExample(int P) { return 1 - P; }
} // namespace
#ifdef LOCAL
void Remove(int d) {
cout << d << nl;
}
#endif
#define MASK(i) (1 << (i))
const int S = 63;
long long f[70][2];
void builddp() {
f[0][0] = 1;
FOR(i, 1, S) {
f[i][0] = f[i - 1][0] + f[i - 1][1];
f[i][1] = f[i - 1][0];
}
}
const int G = 42;
void Bruno(int n, int l, vector<int> a) {
builddp();
vector<int> v;
int pt = 0;
bool ex = n%S != l%S;
if (!ex){
FOR(i, 0, n - 1) Remove(i);
return ;
}
// FOR(mask, 0, (1 << 5) - 1) {
// FOR(i, 0, 4) cout << (1 & mask >> i);
// cout << nl;
// }
// FOR(i, 0, 6) cout << f[i][0] << ' '; cout << nl;
// FOR(i, 0, 6) cout << f[i][1] << ' '; cout << nl;
for(int i = 0; i < n + 1; i += S) {
int r = min(i + S - 1, n);
int len = r - i + 1;
// cerr << i << ' ' << len << nl;
long long val = 0;
FOR(j, 0, G) val = val * 2LL + a[pt++];
// cout << val << nl;
FOD(i, len, 1) {
v.push_back(val > f[i][0]);
if (f[i][0] < val) {
val -= f[i][0];
}
}
}
int pos = 0;
FOR(i, 0, sz(v) - 1) {
if (v[i] == 1) {
pos = i;
v.erase(v.begin() + i + 1);
break ;
} else
Remove(i);
}
// for(int x : v) cout << x << ' '; cout << nl;
for(int i = pos + 1, lst = pos; i < n; ++i) {
if (v[i] == 1) {
FOD(j, i-1, lst+1) {
Remove(j);
}
Remove(i);
lst = i;
}
}
FOD(i, n - 1, 0) {
if (v[i] == 0) {
Remove(i);
} else
break ;
}
Remove(pos);
}
#ifdef LOCAL
int main() {
freopen(task".out", "r", stdin);
// freopen(task".out", "w", stdout);
int n, l;
cin >> n >> l;
vector<int> a(l);
for(int i = 0; i < l; ++i) cin >> a[i];
Bruno(n, l, a);
}
#endif
/* Let the river flows naturally */
