#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
void read_array(int t, const vector<int> & v){
int n = v.size();
stack<int> s;
string b;
int a[n];
s.push(n);
int m = log2(n);
for(int i = n - 1; i >= 0; i--){
while(!s.empty() && s.top() != n && v[s.top()] < v[i])
s.pop();
a[i] = s.top();
s.push(i);
}
for(int i = 0; i < n; i++){
for(int j = m; j >= 0; j--){
if(((a[i] >> j) & 1))
b.append('1');
else b.append('0');
}
}
reverse(all(b));
save_to_floppy(b);
}
vector<int> solve_queries(int t, int n, const string & b, const vector<int> & l, const vector<int> & r){
int o;
string s = b;
int m = log2(n);
vector<int> ans;
int x[n + 1][m + 1];
for(int i = 0; i < n; i++)
x[i][0] = 0;
for(int i = 0; i < n; i++){
for(int j = m; j >= 0; j--){
if(s.back() == '1')
x[i][0] += (1 << j);
s.pop_back();
}
}
x[n][0] = n;
for(int i = 0; i <= n; i++)
for(int j = 1; j <= m; j++)
x[i][j] = n;
for(int j = 0; j < m; j++)
for(int i = 1; i < n; i++)
x[i][j + 1] = x[x[i][j]][j];
for(int i = 0; i < l.size(); i++){
o = l[i];
while(x[o][0] <= r[i])
o = x[o][0];
ans.append(o);
}
return ans;
}
