fredbr

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
const int maxq = 100010;

struct Query
{
	int l, r, id;

fredbr

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
// double tambem funciona na maioria dos casos

typedef long long ll;

struct line

fredbr

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

const int maxn = 510000;
const int maxlog = 22;

fredbr

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

// modular multiplication to numbers up to 10^18 in O(1)
// __int128 is a well accepted gcc extension also compatible with clang
inline ll mul(ll a, ll b, ll c)
{

fredbr

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int maxn = 100100;

// prime bigger than any value of the original string
const ull p = 113;

fredbr

// codigo de gabriel pastori

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main() {

fredbr

// codigo de lucio cardoso

#include <bits/stdc++.h>

using namespace std;

int n;

bool check(int a, int b, int c)
{

fredbr

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

// o resultado pode ultrapassar o inteiro normal
typedef long long ll;
typedef pair<ll, ll> ii;

fredbr

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n;
	cin >> n;

	string s;

fredbr

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
const int inf = 0x3f3f3f3f;

int v[maxn];

int main()