#include "floppy.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
void read_array(int subtask_id, const vector<int>& _v){
string s = "";
vector<int>a = _v;
if(subtask_id == 1){
for(int i = 0; i < a.size(); i++){
for(int bit = 0, x = a[i] + 1e9; bit < 31; bit++){
s += char((x >> bit & 1) + 48);
}
}
save_to_floppy(s);
return;
}
if(subtask_id == 2){
vector<int>c = a;
sort(c.begin(), c.end());
int lgn = 0, n = a.size();
while((1 << lgn) < n){
lgn++;
}
for(int i = 0; i < n; i++){
for(int bit = 0, x = lower_bound(c.begin(), c.end(), a[i]) - c.begin(); bit < lgn; bit++){
s += char((x >> bit & 1) + 48);
}
}
save_to_floppy(s);
return;
}
stack<int>st;
for(int i = 0; i < a.size(); st.push(i++), s += '1'){
while(!st.empty() && a[st.top()] < a[i]){
st.pop();
s += '0';
}
}
save_to_floppy(s);
}
vector<int>solve_queries(int subtask_id, int n, const string& _bits, const vector<int>& _a, const vector<int>& _b){
vector<int>ql = _a, qr = _b;
string info = _bits;
if(subtask_id == 1){
vector<int>v(n, 0), ans(ql.size());
for(int i = 0; i < n; i++){
for(int bit = 0; bit < 31; bit++){
if(info[i * 31 + bit] == '1'){
v[i] |= 1 << bit;
}
}
}
for(int i = 0; i < ql.size(); i++){
for(int j = ql[i], x = -1; j <= qr[i]; j++){
if(maximize(x, v[j])){
ans[i] = j;
}
}
}
return ans;
}
if(subtask_id == 2){
vector<int>v(n, 0), ans(ql.size());
int lgn = 0;
while((1 << lgn) < n){
lgn++;
}
for(int i = 0; i < n; i++){
for(int bit = 0; bit < lgn; bit++){
if(info[i * lgn + bit] == '1'){
v[i] |= 1 << bit;
}
}
}
for(int i = 0; i < ql.size(); i++){
for(int j = ql[i], x = -1; j <= qr[i]; j++){
if(maximize(x, v[j])){
ans[i] = j;
}
}
}
return ans;
}
vector<vector<int>>up(16, vector<int>(n + 1));
for(int i = 0; i < 16; i++){
up[i][0] = 0;
}
stack<int>st;
for(int i = 0, j = 0; i < n; st.push(i++), j++){
while(j < info.size() && info[j] == '0'){
st.pop();
j++;
}
up[0][i + 1] = (st.empty() ? 0 : st.top() + 1);
}
for(int i = 1; i < 16; i++){
for(int j = 1; j <= n; j++){
up[i][j] = up[i - 1][up[i - 1][j]];
}
}
vector<int>ans(ql.size());
for(int i = 0; i < ql.size(); ans[i++]--){
ans[i] = qr[i] + 1;
for(int bit = 15; bit > -1; bit--){
if(up[bit][ans[i]] > ql[i]){
ans[i] = up[bit][ans[i]];
}
}
}
return ans;
}
