This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#include "test/template.hpp"
using u64 = uint64_t;
#include "src/data-structure/FastSet.hpp"
int main() {
cin.tie(0)->sync_with_stdio(0);
ll N, Q;
cin >> N >> Q;
string S;
cin >> S;
FastSet s(N);
rep(i, 0, N) if(S[i] == '1') s.set(i);
while(Q--) {
ll c, k;
cin >> c >> k;
if(c == 0) s.set(k);
if(c == 1) s.reset(k);
if(c == 2) cout << (s.a[0][k / B] >> (k % B) & 1) << '\n';
if(c == 3) {
ll ans = s.next(k - 1);
cout << (ans == N ? -1 : ans) << '\n';
}
if(c == 4) cout << s.prev(k + 1) << '\n';
}
}
#line 1 "test/data-structure/FastSet.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 3 "test/data-structure/FastSet.test.cpp"
using u64 = uint64_t;
#line 1 "src/data-structure/FastSet.hpp"
// using u64 = uint64_t;
const u64 B = 64;
struct FastSet {
u64 n;
vector<vector<u64>> a;
FastSet(u64 n_) : n(n_) {
do a.emplace_back(n_ = (n_ + B - 1) / B);
while(n_ > 1);
}
// bool operator[](ll i) const { return a[0][i / B] >> (i % B) & 1; }
void set(ll i) {
for(auto& v : a) {
v[i / B] |= 1ULL << (i % B);
i /= B;
}
}
void reset(ll i) {
for(auto& v : a) {
v[i / B] &= ~(1ULL << (i % B));
if(v[i / B]) break;
i /= B;
}
}
ll next(ll i) { // i を超える最⼩の要素
rep(h, 0, sz(a)) {
i++;
if(i / B >= sz(a[h])) break;
u64 d = a[h][i / B] >> (i % B);
if(d) {
i += countr_zero(d);
while(h--) i = i * B + countr_zero(a[h][i]);
return i;
}
i /= B;
}
return n;
}
ll prev(ll i) { // i より小さい最⼤の要素
rep(h, 0, sz(a)) {
i--;
if(i < 0) break;
u64 d = a[h][i / B] << (~i % B);
if(d) {
i -= countl_zero(d);
while(h--) i = i * B + __lg(a[h][i]);
return i;
}
i /= B;
}
return -1;
}
};
#line 5 "test/data-structure/FastSet.test.cpp"
int main() {
cin.tie(0)->sync_with_stdio(0);
ll N, Q;
cin >> N >> Q;
string S;
cin >> S;
FastSet s(N);
rep(i, 0, N) if(S[i] == '1') s.set(i);
while(Q--) {
ll c, k;
cin >> c >> k;
if(c == 0) s.set(k);
if(c == 1) s.reset(k);
if(c == 2) cout << (s.a[0][k / B] >> (k % B) & 1) << '\n';
if(c == 3) {
ll ans = s.next(k - 1);
cout << (ans == N ? -1 : ans) << '\n';
}
if(c == 4) cout << s.prev(k + 1) << '\n';
}
}