#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string analyse(int n, int t) {
string ans = "";
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo+hi+1)/2;
string s = "";
for (int i = 0; i < mid; i++) s += '0';
if (make_test(s)) lo = mid;
else hi = mid-1;
}
for (int i = 0; i < hi; i++) ans += '0';
int cnt = hi;
string s = ans;
for (int i = 0; i < n-hi; i++) {
s += '1';
if (make_test(s)) cnt = 0;
else {
s.back() = '0';
cnt++;
if (cnt > hi) break;
}
}
lo = 0, hi = cnt;
while (lo < hi) {
int mid = (lo+hi)/2;
string temp = "";
for (int i = s.length()-mid-1; i >= 0; i--) temp += s[i];
reverse(temp.begin(), temp.end());
if (make_test(temp)) hi = mid;
else lo = mid+1;
}
for (int i = 0; i < hi; i++) s.pop_back();
ans = s;
for (int i = 0; i < n-s.length(); i++) {
ans = '1'+ans;
if (!make_test(ans)) ans[0] = '0';
}
return ans;
}
