akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vll>;
using vb = vector<bool>;
 
const int INF = 2e9+5;
const ll LLINF = (1ULL<<63) - 1;
 
/*
  filippos
  Contest : AtCoder DP contest
  Task : Z - Frog 3
*/

struct line {
  ll best_x;
  int m;
  ll q;
};

// smallest int such that f(m, q) <= f(a)
ll compute_best_x(line &a, int m, ll q){
  return (q - a.q + a.m - m - 1) / (a.m - m);
}

// formula dp:

int main(){
  cin.tie(0), cin.sync_with_stdio(0), cout.tie(0), cout.sync_with_stdio(0);

  int n; ll c; cin >> n >> c;

  vi v(n);
  for(int &i : v)
    cin >> i;

  vll dp(n);
  int j = 0;
  vector<line> cht;

  dp[0] = 0;
  cht.push_back({-LLINF, -2 * v[0], v[0] * (ll)v[0]});

  for(int i = 1; i < n; i++){
    // se possiamo migliorare la soluzione con la j
    while(j + 1 < cht.size() && cht[j+1].best_x <= v[i]) j++;

    dp[i] = v[i] * (ll)v[i] + c + cht[j].q + cht[j].m * (ll)v[i];

    // formula di dp ma stiamo offrendo una funzione, quindi siamo "j"
    int m = -2 * v[i];
    ll q = v[i]*(ll)v[i] + dp[i];
    while(!cht.empty() && compute_best_x(cht.back(), m, q) <= cht.back().best_x) cht.pop_back(); 

    cht.push_back({compute_best_x(cht.back(), m, q), m, q});
    j = min(j, (int)cht.size() - 1);
  }

  cout << dp[n - 1];

  return cout << endl, 0;
}

Measured memory_bytes: 10864
#include <bits/stdc++.h>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000

typedef long long ll;
typedef pair<ll,ll> P;

int main()
{
	int n,a;cin >> n >> a;
	if(n % 500 <= a)cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }
    
    int root(int x) { // データxが属する木の根を再帰で得る：find(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    
    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根をrxをyの根ryにつける
    }
    
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> P(N);
    for(int i = 0; i < N; i++){
        cin >> P[i];
    }
    
    UnionFind tree(N);
    
    for(int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        tree.unite(x-1, y-1); // x-1の木とy-1の木を併合する
    }
    
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        if (tree.same(i, P[i]-1)) { //iとP[i]-1が同じ木に属するなら，カウンタに1追加
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <cstdio>
 
using namespace std;
using ll = long long;
 
#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define RS resize
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);
#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);
 
#define MOD 1000000007
void init();
void solve();

signed main()
{
    init();
    solve();
}

struct LAN {
	vector<int> p;
};

struct PERSON {
	vector<int> l;
};

vector<LAN> L;
vector<PERSON> P;
int N, M;

void init()
{
	cin >> N >> M;
	P.RS(N);
	L.RS(M);
	rep(i, N) {
		int k;
		cin >> k;
		rep(j, k) {
			int t;
			cin >> t;
			t--;
			P[i].l.PB(t);
			L[t].p.PB(i);
		}
	}
}

bool memop[100100];
bool memol[100100];

void dfsl(int pos);

void dfsp(int pos = 0) {
	if (memop[pos]) return;
	memop[pos] = true;
	for (auto x : P[pos].l) {
		dfsl(x);
	}
}

void dfsl(int pos) {
	if (memol[pos]) return;
	memol[pos] = true;
	for (auto x : L[pos].p) {
		dfsp(x);
	}
}

void solve()
{
	dfsp();
	rep(i, N) {
		if (!memop[i]) {
			cout << "NO" << endl;
			return;
		}
	}
	cout << "YES" << endl;
}



Measured memory_bytes: 8568
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <set>

#define REP(i,x,y) for(int i=(x);i<(y);i++)
#define RREP(i,x,y) for(int i=(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
// #define int long long

using namespace std;

// conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define eprintf(...) 42
#define dump(x) 42
#define debug(x) 42
#endif

typedef long long ll;

const int MAX_N = 100000;
ll N, X;
ll x[MAX_N];

ll gcd(ll a, ll b) {
    return b != 0 ? gcd(b, a % b) : a;
}

ll solve() {
    ll answer = abs(X - x[0]);
    REP(i,0,N) {
        answer = gcd(answer, abs(X - x[i]));
    }
    return answer;
}

signed main() {
    // to shorten execution time for iostream
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> X;
    REP(i,0,N) cin >> x[i];
    cout << solve() << "\n";
    return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <string>
using namespace std;

string check(int num);

int main(){
	string s;
	string p;
	string ans;
	cin >> s >> p;
	for(int i = 0;i < 100;i++){
		ans = "No";
		if(!s[i])break;
		
		if(s[i]==p[0]){
			for(int j = 0;j < 100;j++){
				if(!p[j]){
					break;
				}else if(s[i+j] == p[j] || s[i+j-s.size()] == p[j]){
					ans = "Yes";
				}
				else{
					ans = "No";
					break;
				}
			}
		}
		
		if(ans == "Yes")break;
	}
	cout << ans << "\n";
	
	return 0;
}

Measured memory_bytes: 3208
a,b = map(int, raw_input().split())
num1, num2, ans = [], [], 0

for i in xrange(a):
    num1.append(map(int,raw_input().split()))
for i in xrange(b):
    num2.append(input())
for i in xrange(a):
    for j in xrange(b):
        ans += num1[i][j]*num2[j]
    print ans
    ans = 0

Measured memory_bytes: 6544
#include<iostream>
#include<queue>
#include<utility>
using namespace std;

long int inf=100000*100000+100;
int main()
{
    int v,e,r;
    int s[500000];
    int t[500000];
    int d[500000];
    long int dis[100000];
    cin>>v>>e>>r;
    for(int i=0;i<e;i++)
    {
        cin>>s[i]>>t[i]>>d[i];
    }
    
    for(int i=0;i<v;i++)
    {
        dis[i]=inf;
    }
    dis[r]=0;
    
    for(int i=0;i<v-1;i++)
    {
        int end=1;
        for(int j=0;j<e;j++)
        {
            if(dis[t[j]]>dis[s[j]]+d[j])
            {
                dis[t[j]]=dis[s[j]]+d[j];
                end=0;
            }
        }
        
        if(end==1)
            break;
    }
    
    for(int i=0;i<v;i++)
    {
        if(dis[i]==inf)
            cout<<"INF"<<endl;
        else
            cout<<dis[i]<<endl;
    }
}

Measured memory_bytes: 9560
import sys


fin = sys.stdin.readline
N = int(fin())
S = fin().rstrip("\n")
num_wests_from_left = [0] * N
cur_num_wests = 0
for i, d in enumerate(S):
    cur_num_wests += 1 if d == 'W' else 0
    num_wests_from_left[i] = cur_num_wests

num_easts_from_right = [0] * N
cur_num_easts = 0
for i in reversed(range(N)):
    d = S[i]
    cur_num_easts += 1 if d == 'E' else 0
    num_easts_from_right[i] = cur_num_easts

min_num_changing = N - 1
for i in range(N):
    num_changing = (num_wests_from_left[i - 1] if i > 0 else 0) + (num_easts_from_right[i + 1] if i < N - 1 else 0)
    min_num_changing = min(min_num_changing, num_changing)
print(min_num_changing)


Measured memory_bytes: 47264
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
namespace AtCoder.ABC088
{
    class CardGameForTwo
    {
        public static void Main()
        {
            var n = int.Parse(ReadLine().Trim());
            var cards = ReadLine().Trim().Split(' ').Select(_ => int.Parse(_)).OrderByDescending(_ => _);
            int sign = 1;
            int sum = 0;
            foreach(var card in cards)
            {
                sum += card * sign;
                sign *= -1;
            }
            WriteLine(sum);
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int ac, wa, tle, re;
  ac = wa = tle = re = 0;
  int N;
  cin >> N;
  
  for(int i = 0; i < N; i++){
    string str;
    cin >> str;
    if(str == "AC"){
      ac++;
    }else if(str == "WA"){
      wa++;
    }else if(str == "TLE"){
      tle++;
    }else if(str == "RE"){
      re++;
    }
  }
  
  cout << "AC x " << ac << endl;
  cout << "WA x " << wa << endl;
  cout << "TLE x " << tle << endl;
  cout << "RE x " << re;
}

Measured memory_bytes: 3628
#include<stdio.h>
int main()
{
	long long int a, b, n;
	scanf("%lld %lld %lld", &a, &b, &n);
	long long int ans = a * n / b - n / b * a;
	n = n / b * b;
	n--;
	if (ans < a * n / b - n / b * a)
		ans = a * n / b - n / b * a;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define REP(i,n) for(int i = 0;i < (int)(n);i++)
#define RREP(i,n) for(int i = (int)n-1;i >= 0;i--)
#define FOR(i,s,n) for(int i = s;i < (int)n;i++)
#define RFOR(i,s,n) for(int i = (int)n-1;i >= s;i--)
#define ALL(a) a.begin(),a.end()
#define IN(a, x, b) (a<=x && x<b)
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a = b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a = b;return true;}return false;}
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void in(T&t){cin>>t;}
template<class T,class... Ts>inline void in(T&t,Ts&...ts){cin>>t;in(ts...);}
template<class T>inline void out(T t){cout<<t<<"\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout<<t<<" ";out(ts...);}
template<typename T=int>vector<T>mv(size_t a){return vector<T>(a);}
template<typename T=int,typename... Ts>auto mv(size_t a,Ts... ts){return vector<decltype(mv<T>(ts...))>(a,mv<T>(ts...));}
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type fill(T&t,const V&v){t=v;}
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type fill(T&t,const V&v){for(auto &e:t)fill(e,v);}
constexpr long long INF = 1e18;
 
signed main(){
	int N,A,B;
	in(N,A,B);
	A--;B--;
	while(1){
		if(IN(0,A+1,N)&&A+1!=B)A++;
		else if(IN(0,A-1,N))A--;
		else{
			out("Borys");
			return 0;
		}
		if(IN(0,B-1,N)&&B-1!=A)B--;
		else if(IN(0,B+1,N))B++;
		else{
			out("Alice");
			return 0;
		}
	}
}

Measured memory_bytes: 256
<?php
//error_reporting(0);
$S = trim(fgets(STDIN));
$T = trim(fgets(STDIN));
//list($n,$m,$d) = explode(" ",trim(fgets(STDIN)));
//$a = explode(" ",trim(fgets(STDIN)));

$ans = false;
for($i=0;$i<strlen($T);$i++) {
  if ($S == $T) {
    $ans=true;
    break;
  }
  $S = substr($S,-1) . substr($S,0,strlen($S)-1);
}
if ($ans) {
  printf("Yes\n");
}
else {
  printf("No\n");
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define INF 1e9L
#define EPS 1e-9
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define pb push_back
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;

///解説放送を見て

int main(void)
{
    int x,y,z;
    cin >> x >> y >> z;
    int K;
    cin >> K;
    vector<ll> a(x), b(y), c(z);

    REP(i, x) cin >> a[i];
    REP(i, y) cin >> b[i];
    REP(i, z) cin >> c[i];

    RSORT(a);
    RSORT(b);
    RSORT(c);

    vector<ll> abc;
    REP(i, x){
        REP(j, y){
            if((i+1)*(j+1) > K) break;
            REP(k, z){
                if((i+1)*(j+1)*(k+1) > K) break;
                abc.pb(a[i] + b[j] + c[k]);
            }
        }
    }

    RSORT(abc);
    REP(i, K){
        pr(abc[i]);
    }
}

Measured memory_bytes: 1404
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}

const int MOD = 1000000007;

int main() {
    string a,b,c; cin >> a >> b >> c;
    if(a[a.length()-1] == b[0] && b[b.length()-1] == c[0]){
        cout << "YES";
    }else{
        cout << "NO";
    }
}



Measured memory_bytes: 256
unittest
{
	assert( [ "2 5", "4 9", "2 4" ].parse.expand.solve == 12 );
	assert( [ "4 30", "6 18", "2 5", "3 10", "7 9" ].parse.expand.solve == 130 );
	assert( [ "1 100000", "1000000000 100000" ].parse.expand.solve == 100000000000000 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nm = input.front.split.to!( long[] );
	auto abs = new long[][]( nm[ 0 ], 2 );
	foreach( ref ab; abs )
	{
		input.popFront;
		ab = input.front.split.to!( long[] );
	}
	return tuple( nm[ 1 ], abs );
}

auto solve( long m, long[][] abs )
{
	abs.sort();
	
	auto ans = 0L;
	foreach( ab; abs )
	{
		ans += ab[ 0 ] * min( m, ab[ 1 ] );
		m -= ab[ 1 ];
		if( m <= 0 ) break;
	}
	
	return ans;
}


Measured memory_bytes: 22780
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main() {
    int n;cin>>n;
    int n1 = n/100;
    int n2 = n%100;
    
    int c1 = 0;
    int c2 = 0;

    if(n1>=1 && n1<=12)c1=1;
    if(n2>=1 && n2<=12)c2=1;
    
    if(c1+c2 == 2)cout<<"AMBIGUOUS"<<endl;
    else if(c1+c2 == 0)cout<<"NA"<<endl;
    else if(c1 == 1)cout<<"MMYY"<<endl;
    else cout<<"YYMM"<<endl;
    
	return 0;
}

Measured memory_bytes: 3636
ipn = int(input())

flagP = False
flagW = False
flagG = False
flagY = False

st = input().split()

for i in range(ipn):
	if st[i] == "P":
		flagP = True
	if st[i] == "W":
		flagW = True
	if st[i] == "G":
		flagG = True
	if st[i] == "Y":
		flagY = True

if flagP and flagW and flagG and flagY:
	print("Four")
else:
	print("Three")

Measured memory_bytes: 3064
use proconio::input;
use proconio::marker::Chars;
fn main() {
    input! {
        _: u32,
        a: u32,
        b: u32,
        s: Chars,
    }

    println!("{}", solve(a, b, s));
}

fn solve(a: u32, b: u32, s: Vec<char>) -> String{
    let mut result = String::with_capacity(400000);
    let mut a_counter = 0;
    let mut b_counter = 0;
    let yes = "Yes\n";
    let no = "No\n";
    for &char in s.iter(){
        match char{
            'a' => {
                if a_counter + b_counter < a + b {
                    result.push_str(yes);
                    a_counter += 1;
                } else {
                    result.push_str(no);
                }
            }
            'b' => {
                if a_counter + b_counter < a + b && b_counter < b {
                    result.push_str(yes);
                    b_counter += 1;
                } else {
                    result.push_str(no);
                }
            }
            _ => result.push_str(no)
        }
    }
    result
}

Measured memory_bytes: 3032
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int MAX = 1000005;

int main() {
    int n; cin >> n;
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }
    bool judge[MAX];
    rep(i, MAX){
        judge[i] = true;
    }
    sort(A.begin(), A.end());

    int ans = 0;
    if(A[0] == 1){
        if(A[1] == 1){
            cout << 0 << endl;
            return 0;
        } else {
            cout << 1 << endl;
            return 0;
        }
    }
    
    set<int> S;
    for (int i = 0; i < n; i++){
        int a = A[i];
        if(!judge[a]){
            continue;
        }
        if(i != 0){
            if(a == A[i-1]){
                S.insert(A[i]);
                continue;
            }
        }
        
        if(judge[a]){
            ans++;
            for (int j = a+a; j < MAX; j+=a){
                judge[j] = false;
            }
        }
    }

    int ss = S.size();
    cout << ans - ss << endl;

    return 0;
}

Measured memory_bytes: 5424
#ifndef INCLUDED_ROLLING_HASH_HPP
#define INCLUDED_ROLLING_HASH_HPP

#include <vector>
#include <string>

class rolling_hash {
public:
	using u64 = std::uint_fast64_t;
	using size_type = std::uint_fast32_t;
	using i128 = __int128_t;

	static constexpr u64 MOD = (1uL << 61) - 1;
	static constexpr u64 base = 20200213;

	std::string str;
	std::vector<u64> hash_, pow;

private:
	static constexpr u64 mask30 = (1ul << 30) - 1;
	static constexpr u64 mask31 = (1ul << 31) - 1;

	u64 mul(i128 a, i128 b) const {
		i128 t = a * b;
		t = (t >> 61) + (t & MOD);
		
		if(t >= MOD) return t - MOD;
		return t;
	}
	size_type xorshift(size_type x) const {
		x ^= x << 13;
		x ^= x >> 17;
		x ^= x << 5;
		return x;
	}

public:
	rolling_hash(const rolling_hash &) = default;
	rolling_hash(rolling_hash&&) = default;

	rolling_hash() : str() {};
	rolling_hash(const std::string & str) : str(str) {
		hash_.resize(str.size() + 1, 0);
		pow.resize(str.size() + 1, 1);
		for(size_type i = 0; i < str.size(); i++) {
			hash_[i + 1] = mul(hash_[i], base) + xorshift(str[i] + 1);
			pow[i + 1] = mul(pow[i], base);
			if(hash_[i + 1] >= MOD) hash_[i + 1] -= MOD;
		}
	}

	u64 hash() const { return hash_.back(); }
	u64 hash(size_type l, size_type r) const {
		u64 ret = MOD + hash_[r] - mul(hash_[l], pow[r - l]);
		return ret < MOD ? ret : ret - MOD;
	}
	
	size_type size() const { return str.size(); }
};

#endif

#include <iostream>

int main() {
	int n; scanf("%d", &n);
	std::string s; std::cin >> s;
	
	int ans = 0;
	rolling_hash hash(s);
	for(int i = 0; i < s.size(); i++) {
		for(int j = i; j < s.size(); j++) {
			while(i + ans < j and j + ans < n) {
				if(hash.hash(i, i + ans + 1) != hash.hash(j, j + ans + 1)) break;
				ans++;
			}
		}
	}

	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 3828
n,q=map(int,input().split())
p=[i for i in range(n)]

def root(x):
    path_to_root=[]
    while p[x]!=x:
        path_to_root.append(x)
        x=p[x]
    for node in path_to_root:
        p[node]=x
    return x

for _ in range(q):
    com,x,y=map(int,input().split())
    if com:
        print(int(root(x)==root(y)))
    else:
        p[root(x)]=root(y)


Measured memory_bytes: 5984
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    // Your code here!
    int n, q;
    string s;
    cin>>n>>q>>s;
    vector<int> count(n+1);
    count[0] = 0;
    for(int i = 1; i<n; ++i){
        int counter = count[i];
        if(s[i-1]=='A'&&s[i]=='C'){
            ++counter;
        }
        count[i+1] = counter;
    }
    for(int i = 0; i<q; ++i){
        int l, r, res;
        cin>>l>>r;
        res = count[r] - count[l];
        cout << res << endl;
    }
}


Measured memory_bytes: 1408
#include<iostream> 
#include<iomanip> 
#include<vector> 
#include<map> 
#include<set> 
#include<algorithm> 
#include<numeric> 
#include<limits> 
#include<bitset> 
#include<functional> 
#include<type_traits> 
#include<queue> 
#include<stack> 
#include<array> 
#include<random> 
#include<utility> 
#include<cstdlib> 
#include<ctime>
//#define _LIBCPP_DEBUG 0
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define all(a) (a).begin(),(a),end()
#define rep(i,n) for (int i = 0; i < (n); ++i)	
//setprecision(16)

void outi(int x) { cout << x << endl;}
void soutl(ll x) { cout << x << endl;}
void outs(string x) { cout << x << endl;}
ll max(ll a, ll b) {
	ll max;
	if (a > b) max = a;
	else max = b;
	return max;
}
ll min(ll a, ll b) {
	ll min;
	if (a < b) min = a;
	else min = b;
	return min;
}
//---------------------------------------------------------------

int main() {
	int n;
	int p[22];

	cin >> n;
	rep(i, n) cin >> p[i];

	int ans = 0;
	rep(i, n - 2) {
		if ((p[i] < p[i + 1] && p[i + 1] < p[i + 2]) || (p[i] > p[i + 1] && p[i + 1] > p[i + 2])) ans++;
	}
	outi(ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>

using namespace std;
using lli = long long int;
// #define DEBUG
#ifdef DEBUG
#define debug(var) cout << (#var) << ": " << (var) << endl;
template<class T> void dump_array_impl(const T& a) {
  bool first = true;
  for (auto&& x : a) {
    if (!first) { cout << ", "; first = false; }
    cout << x;
  }
}
#define debug_array(a) cout<<(#a)<<": ";dump_array_impl(a);cout<<endl
#else
#define debug(var) {}
#define debug_array(a) {}
#endif
template<class T> void read_n(vector<T>& v, size_t n) {
  v = vector<T>(n);
  for (lli i=0; i<n; ++i) cin >> v[i];
}

int main() {
  string s;
  cin >> s;
  for (auto c:s) cout << (c=='1'?'9':'1');
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#pragma GCC diagnostic warning "-Wconversion"

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(a) begin(a), end(a)
#define has(a, b) (a.find(b) != a.end())
#define fora(i, n) for(int i = 0; i < n; i++)
#define forb(i, n) for(int i = 1; i <= n; i++)
#define forc(a, b) for(const auto &a : b)
#define ford(i, n) for(int i = n; i >= 0; i--)
#define maxval(t) numeric_limits<t>::max()
#define minval(t) numeric_limits<t>::min()
#define imin(a, b) a = min(a, b)
#define imax(a, b) a = max(a, b)

#define dbgs(x) #x << " = " << x
#define dbgs2(x, y) dbgs(x) << ", " << dbgs(y)
#define dbgs3(x, y, z) dbgs2(x, y) << ", " << dbgs(z)
#define dbgs4(w, x, y, z) dbgs3(w, x, y) << ", " << dbgs(z)

using ll = long long;

bool skip[305];
queue<int> all[305];
int cnt[305];
int glmi;
int N, M;

void count()
{
        fora(i, M)
        {
                cnt[i] = 0;
        }

        fora(i, N)
        {
                cnt[all[i].front()]++;
        }

        int cma = 0;
        fora(i, M)
        {
                imax(cma, cnt[i]);
        }
        imin(glmi, cma);
}

int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        cin >> N >> M;
        glmi = 500;

        fora(i, N)
        {
                fora(j, M)
                {
                        int d;
                        cin >> d;
                        --d;
                        all[i].push(d);
                }
        }

        count();

        fora(i, M - 1)
        {
                int wo = -1;
                int woval = 0;
                fora(j, M)
                {
                        if (cnt[j] > woval)
                        {
                                wo = j;
                                woval = cnt[j];
                        }
                }

                skip[wo] = true;

                fora(i, N)
                {
                        //cout << dbgs(wo) << endl;
                        //cout << dbgs3(all[i].size(), all[i].front(), skip[all[i].front()]) << endl;
                        while (skip[all[i].front()])
                        {
                                all[i].pop();
                                //cout << dbgs3(all[i].size(), all[i].front(), skip[all[i].front()]) << endl;
                        }
                        //cout << "A" << endl;
                }
                count();
        }
        cout << glmi << endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
const ll mod = 1000000007;
const ll INF = 9223372036854775807;
#define Sort(a) sort(a.begin(), a.end())
#define Bsort(a) sort(a.begin(), a.end(), greater<ll>())
#define Pi acos(-1)

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << setprecision(15) << fixed;
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  vector<ll> b(n);
  rep(i,n) {
    cin >> a[i];
    if (i == 0) b[i]= a[i];
    else b[i] = b[i-1]+a[i];
  }
  ll ans = 0;
  rep(i,n-k+1) {
    ll tmp = 0;
    if (i == 0) {
      tmp = b[k-1];
    }
    else {
      tmp = b[k-1+i] - b[i-1];
    }
    ans = max(ans, tmp);
  }
  cout << (ans+k)/2.0 << '\n';
}

Measured memory_bytes: 3328
n,m = list(map(int,input().split(" ")))
lights = []
for i in range(m):
  lights.append(list(map(int,input().split(" ")))[1:])

conditions = list(map(int,input().split(" ")))

p_num = 2**n
count = 0
for i in range(p_num):
  on_switch = []
  flag = True
  for digit in range(n):
    if (i%2 == 0):
      on_switch.append(digit+1)
    i = i//2
  for j in range(m):
    buf = [x for x in on_switch if x in lights[j]]
    if len(buf) % 2 != conditions[j]:
      flag = False
  if flag:
    count += 1

print(count)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
typedef long long int ll;
//#define PI 3.14159265358979323846264338327950L
using namespace std;

void solve()
{
    string s;
    cin >> s;
    for(int i=0;i<3;++i)
    {
        cout << s[i];
    }
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    /*int t;
    cin >> t;
    while(t--)
    {
         solve();  
    }
   */ solve();
    return 0;
}



Measured memory_bytes: 3644
from collections import defaultdict
N = int(input())
mod = 10 ** 9 + 7

res = defaultdict(int)
for n in range(2, N + 1):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res[i] += cnt
    if n > 1:
        res[n] += 1

ans = 1
for x in res.values():
    ans *= (x + 1)
    ans %= mod

print(ans)

Measured memory_bytes: 3444
n=int(input())
s=sorted([int(input()) for i in range(n)])
if sum(s)%10!=0:
  ans=sum(s)
else:
  i=0
  while s[i]%10==0:
    i+=1
    if i==n:
      ans=0
      break
  else:
    ans=sum(s)-s[i]
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k; cin>>n>>k;
    vll v(n);
    rep(i,n) cin>>v[i];
    ll ans=0;

    FOR(i,1,min(k,n)){
        FOR(j,0,i){
            priority_queue<ll,vll,greater<ll> > que;
            rep(l,j) que.push(v[l]);
            rep(l,i-j) que.push(v[n-l-1]);
            rep(l,k-i){
                if (que.empty()) break;
                if (que.top()<0) que.pop();
            }
            ll sum=0;
            while(que.size()){
                sum+=que.top(); que.pop();
            }
            ans = max(ans, sum);
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
using ld = long double;  using vld = vector<ld>; 

int main(void) {
	string s;	cin >>s;
	int n=0;
	
	rep(i,s.length()){
		if(s[i]=='+')
			n++;
		else
			n--;
	}
	
	cout << n <<endl;

	
    return 0;
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=int(a); i<int(b); ++i)
#define FORD(i,a,b) for(int i=int(a); i<int(b); --i)
#define REP(i,N) for(int i=0; i<int(N); ++i)
#define REPD(i,N) for(int i=0; i<int(N); --i)
#define PB push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7
#define MAXR 100000 //配列の最大のrenge

int main() {
    int A,B,C; cin>>A>>B>>C;
    string ans = "NO";
    ll tmp = 0;
    FOR(i,1,B+1) {
        tmp = A*i % B; 
        if (tmp == C) {
            ans = "YES";
            break;
        }
    }
    cout << ans;
}

Measured memory_bytes: 3372
#include <bits/stdc++.h>

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define pb push_back
#define mp make_pair
#define INF 999999999
#define MOD 1000000007
#define sp ' '
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()

//typedef
typedef long long ll;
typedef pair<int, int> pint;
typedef pair<long, long> pll;
typedef map<int, int> mint;
typedef set<int> sint;
typedef vector<int> vint;
typedef vector<char> vchr;
typedef vector<long long> vll;
typedef vector<string> vstr;


ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll a, ll b, ll c){ll ans=1; rep(i, b){ans=ans*a%c;} return ans;}


template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T>
void dpp(T n){cerr << n << endl;}
template<typename T>
void vpp(T a){rep(i,a.size()){cout << a[i] << endl;}}
template<typename T>
void vdp(T a){rep(i,a.size()){cerr << a[i] << endl;}}

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int ddx[8] = {1,0,-1,0,1,-1,-1,1};
const int ddy[8] = {0,1,0,-1,1,1,-1,-1};




template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}


vector<string> split(const string &str, char sep)
{
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.pb(buffer);
    }
    return v;
}




int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, i;
    cin >> n >> i;

    ppp(n-i+1);



    return 0;
}


Measured memory_bytes: 896
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int count = 0;
		if(s.contains("R")){
			 if(s.charAt(0)==s.charAt(1)&&
						s.charAt(0)==s.charAt(2)){
					count = 3;
				}
			else if(s.charAt(0)=='R'&&s.charAt(1)=='R'
					|| s.charAt(1)=='R'&&s.charAt(2)=='R') {
				count = 2;
			}
			else {
				count = 1;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 35520
import bisect

n = int(input())

num = [3, 5, 7]
last_num = [3, 5, 7]
tfs = [3, 5, 7]

for i in range(8):
    new_num = []
    for a in last_num:
        for b in tfs:
            new_num.append(a*10 + b)
    num += new_num
    last_num = new_num

num753 = []

for a in num:
    if len(set(str(a))) == 3:
        num753.append(a)

print(bisect.bisect_right(num753, n))

Measured memory_bytes: 4724
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n,m;
  cin >> n >> m;
  vector<int> c(n+1);
  rep(i,m){
    int l,r;
    cin >> l >> r;
    c[l-1]++; c[r]--; 
  }
  int ans = 0, cnt = 0;
  rep(i,n){
    cnt += c[i];
    if(cnt==m) ++ans;
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;

int main() {
  string s,t;
  cin>>s>>t;

  sort(s.begin(), s.end());
  sort(t.begin(), t.end(), greater<char>());
  if (s < t) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
         Scanner sc = new Scanner (System.in);
         while (true){
         int h = sc.nextInt();
         int w = sc.nextInt();
         if(h==0 && w==0){
             break;
         }
         for(int i=0;i<h;i++){
             for(int j=0; j<w;j++){
                 System.out.print("#");
             }
             System.out.println("");
         }
         System.out.print("\n");
        }
        sc.close();
    }
}


Measured memory_bytes: 36732
//file_name:ABC103_B.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts()
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;

    // 整数スキャン（複数）
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&y);

    // n個の整数のスキャン
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // 文字列スキャン
    /*
    string s;
    cin >> s;
    */


int main() {
    int n;
    scanf("%d",&n);
    ll ans = 0;
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
        ans += a[i] -1;
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(){
    int i=0,n=0;
    char s[200001],t[200001];
    scanf("%s",s);
    scanf("%s",t);
    for(i;s[i]!='\0';i++){
    if(s[i]!=t[i]){
        n++;
    }}
    printf("%d",n);
    return 0;


}

Measured memory_bytes: 2096
//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

template<typename integer>
integer __lcm(integer a, integer b) {
    return (a * b) / __gcd(a, b);
}

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

    // 10/4 -> あまり2だがそれらは適当な2人に配れば良い
    cout << (n%k!=0) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int stack[20];
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
	if(!x){putchar('0');return;}
	int top=0;
	while(x)stack[++top]=x%10,x/=10;
	while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
inline long long solve(long long n)
{
	if(n==1)return 1;
	else return 2*solve(n/2)+1;
}
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	long long n;
	scanf("%lld",&n);
	printf("%lld\n",solve(n));
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;


int main(){
  int H,N;
  cin >> H >> N;
  vector<int> A(N);
  vector<int> B(N);

  int maxA = 0;
  for(int i = 0;i<N;i++){
    cin >> A.at(i) >> B.at(i);
    if(A.at(i) > maxA){
      maxA = A.at(i);
    }
  }

  cerr << "maxA " << maxA << endl;
  int l = H + maxA + 1; 
  int bigM = 1000000000;
  vector<int> dp(l, bigM);
  
  dp[0] = 0;
  // initialize
  for(int i = 0; i <= H;i++){
    if(dp[i] == bigM) continue;
    for(int j = 0; j < N;j++){
      int nd = i + A.at(j);
      int nb = dp[i] + B.at(j);
      if(nb < dp[nd]){
        dp[nd] = nb;
      }
    }
  }

  int ans = dp[H];
  for(int i = H; i < l; i++){
    // cerr << i << " " << dp[i] << endl;
    if(dp[i] < ans) ans = dp[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int q = in.nextInt();
		String s = in.next();
		StringBuilder sb1 = new StringBuilder();
		StringBuilder sb2 = new StringBuilder();
		for(int i=0;i<q;i++) {
			sb1.append(in.next());
			sb2.append(in.next());
		}
		String t = sb1.toString();
		String d = sb2.toString();
		int ans = 0;
		//to_left
		int idx_l = 0;
		int idx_r = n-1;
		if(move(s,t,d,0)<0  && move(s,t,d,n-1)>=0) {
			while(idx_r-idx_l>1) {
				int idx_mid = (idx_l+idx_r)/2;
				int toward = move(s,t,d,idx_mid);
				if(toward<0) idx_l = idx_mid;
				else idx_r = idx_mid;
			}
			ans += idx_l+1;
		}else if(move(s,t,d,n-1)<0) {
			ans += n;
		}
		//to_right
		idx_l = 0;
		idx_r = n-1;
		if(move(s,t,d,0)<=0 && move(s,t,d,n-1)>0) {
			while(idx_r-idx_l>1) {
				int idx_mid = (idx_l+idx_r)/2;
				int toward = move(s,t,d,idx_mid);
				if(toward>0) idx_r = idx_mid;
				else idx_l = idx_mid;
			}
			ans += n-idx_r;
		}else if(move(s,t,d,0)>0) {
			ans += n;
		}
		System.out.println(n-ans);
		in.close();
	}
	
	public static int move(String s,String t,String d,int idx) {
		int n = s.length();
		int q = t.length();
		int ret = 0;
		for(int i=0;i<q;i++) {
			if(s.charAt(idx)==t.charAt(i)) {
				if(d.charAt(i)=='L') idx--;
				else idx++;
			}
			if(idx<0) {
				ret = -1;
				break;
			}
			if(idx>=n) {
				ret = 1;
				break;
			}
		}
		return ret;
	}

}


Measured memory_bytes: 66192
#include <bits/stdc++.h>
using namespace std;
int main() {
    // 入力受け取り, 入次数も管理する
int n;
    cin >> n ;

int flag=0;
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
if(n==i*j)flag=1;
}
}
if(flag==1)
cout << "Yes";
else
cout << "No";




   
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#define PI 3.14159265359
int main()
{
	int a,b,c;
	double rad;
	scanf("%d%d%d",&a,&b,&c);
	rad=c*PI/180;
	printf("%lf\n",0.5*a*b*sin(rad));
	printf("%lf\n",a+b+sqrt(a*a+b*b-(2*a*b*cos(rad))));
	printf("%lf\n",b*sin(rad));
	return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define ppp pop_back
#define pii pair<int,int>
#define fi first
#define se second

const int N = 2e5 + 5;
const ll inf = 1e18;

vector<pii> open[N], close[N];
ll dp[N], a[N];
ll t[4*N], ch[4*N];
ll good_value = - inf;
int n;

ll merge(ll a, ll b) {
	return max(a, b);
}

void build() {
	for (int i=0; i<4*N; i++) t[i] = ch[i] = 0;
}

void push(int v, int l, int r) {
	if (!ch[v]) return;
	t[v] += ch[v];
	if (l < r) {
		ch[v+v] += ch[v];
		ch[v+v+1] += ch[v];
	}
	ch[v] = 0;
}

void upd(int v, int l, int r, int L, int R, ll x) {
	push(v, l, r);
	if (l > R || L > r) return;
	if (L <= l && r <= R) {
		ch[v] += x;
		push(v, l, r);
		return;
	}
	int mid = (l + r) / 2;
	upd(v+v, l, mid, L, R, x);
	upd(v+v+1, mid+1, r, L, R, x);
	t[v] = merge(t[v+v], t[v+v+1]);
}

void upd(int L, int R, ll x) {
	upd(1, 1, n, L, R, x);
}

ll get(int v, int l, int r, int L, int R) {
	push(v, l, r);
	if (l > R || L > r) return good_value;
	if (L <= l && r <= R) return t[v];
	int mid = (l + r) / 2;
	ll res = merge(get(v+v, l, mid, L, R), get(v+v+1, mid+1, r, L, R));
	t[v] = merge(t[v+v], t[v+v+1]);
	return res;
}

ll get(int L, int R) {
	return get(1, 1, n, L, R);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int m;
	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		int l, r, a;
		cin >> l >> r >> a;
		open[l].pb({r, a});
		close[r].pb({l, a});
	}
	a[0] = 0;
	for (int i=1; i<=n; i++) {
		a[i] = a[i-1];
		for (pii cur : open[i]) a[i] += cur.se;
		for (pii cur : close[i-1]) a[i] -= cur.se;
	}
	build();
	for (int i=1; i<=n; i++) {
		for (pii cur : open[i]) {
			upd(i, cur.fi, -cur.se);
		}
		dp[i] = max(a[i], a[i] + get(1, i-1));
		upd(i, i, dp[i]);
		for (pii cur : close[i]) {
			upd(cur.fi, i, cur.se);
		}
	}
	ll ans = 0;
	for (int i=1; i<=n; i++) ans = max(ans, dp[i]);
	cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 37760
#include<bits/stdc++.h>
using namespace std;

int main() {
	string s;
	cin >> s;
	int n{};
	for(int i=0; i<s.size(); i++){
		if(s.at(i)=='1') n++;
		else n--;
	}
	cout << s.size()-abs(n) << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;

main(){
    unsigned long N, Q;
    cin >> N >> Q;
    vector<unsigned long> A(N), S(N), X, a;
    for(auto& i : A)cin >> i;
    partial_sum(A.rbegin(), A.rend(), S.begin());
    for(unsigned long i{(N + 1) / 2}, AS{0}; i--; AS += A[N - i * 2 - 1])a.push_back(S[i] + AS);
    for(unsigned long i{(N + 1) / 2}; --i;)X.push_back(A[N - i - 1] + A[N - i * 2 - 1]);
    auto beg = begin(X), edn = end(X);
    for(unsigned long i{0}, x; i < Q; ++i){
        cin >> x;
        cout << a[lower_bound(beg, edn, x * 2) - beg] << endl;
    }
    return 0;
}

Measured memory_bytes: 4216
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <utility>
#include <cstdio>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)

template <class T>
bool contain(const std::string &s, const T &v)
{
    return s.find(v) != std::string::npos;
}

int n,k;

int main()
{
    cin>>n>>k;
    int a = (double)n/2+0.5;
    if(a>=k){
        cout << "YES" << endl;
    }else{
        cout<<"NO"<<endl;
    }
    
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'


int32_t main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr), cout.tie(nullptr);

    for (int i = 1; i <= 5; i++) {
      int x; cin >> x;
      if (x == 0) {
        return cout << i, 0;
      }
    }
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>> n;
    int cnt[4] = {0};
    string x;
    for(int i = 0; i < n; i++) {
		cin>> x;
		if(x == "AC") {
			cnt[0]++;
		} else if(x == "WA") {
			cnt[1]++;
		} else if(x == "TLE") {
			cnt[2]++;
		} else {
			cnt[3]++;
		}
	}
	printf("AC x %d\n", cnt[0]);
	printf("WA x %d\n", cnt[1]);
	printf("TLE x %d\n", cnt[2]);
	printf("RE x %d\n", cnt[3]);
}


Measured memory_bytes: 3748
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class data
{
public:
    int a, b;
    bool operator<(const data& d) const{
        return b < d.b;
    }
};

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            break;
        vector<data> d(n);
        for(int i=0; i<n; ++i)
            cin >> d[i].a >> d[i].b;
        sort(d.begin(), d.end());

        int total = 0;
        bool ok = true;
        for(int i=0; i<n; ++i){
            total += d[i].a;
            if(total > d[i].b){
                ok = false;
                break;
            }
        }
        if(ok)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B;
  cin >> A >> B;
  int ans = 0;
  for(int i = 0; i < B - A + 1; i++){
    int x = 0;
    bool t = true;
    int a = A + i;
    for(int n = 0;;n++){
    a = a / 10 ;
        if( a == 0){
          break;
        }
      x++;
    }
    vector<int>uuu(x + 1);
    int k; 
    k = A + i;
    for(int l = 0; l < x + 1; l++){
    uuu.at(l) = k -10*(k /10);
      k =k /10 ;
    }
    for(int u = 0; u < (uuu.size() + 1)/2; u++){
      if (uuu.at(u) != uuu.at(uuu.size() - u - 1 )){
        t = false;
      }
    }
      if(t){
        ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3592