akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//-------------------------------------------------------
struct Fact{
	vector<long> f;
	vector<long> rf;
	long pow(long N,long K){
		if(K == 0){
			return 1;
		}
		else if(K % 2 == 0){
			long t = pow(N,K/2);
			return t*t%mod;
		}
		else{
			return N*pow(N,K-1)%mod;
		}
	}
	Fact(int N):f(N+1),rf(N+1){
		for(int i=0;i<N+1;i++){
			if(i == 0){
				f[i] = 1;
			}
			else{
				f[i] = (f[i-1]*i)%mod;
			}
		}
		for(int i=N;i>=0;i--){
			if(i == N){
				rf[i] = pow(f[N],mod-2);
			}
			else{
				rf[i] = rf[i+1]*(i+1)%mod;
			}
		}
	}
	long GetFact(int N){
		return f[N];
	}
	long GetPerm(int N,int R){
		return f[N] * rf[N-R] % mod;
	}
	long GetConv(int N,int R){
		return ((f[N]*rf[R])%mod*rf[N-R])%mod;
	}
	long GetRev(int N){
		if(N == 0){
			return 1;
		}
		else{
			return rf[N] * f[N-1] % mod;
		}
	}
};

void Calc(){
	int B = rei();
	int W = rei();
	Fact F(B+W);
	long HALF = mod/2+1;
	long Nob = 0;
	long Now = 0;
	long HALFP = 1;
	for(int i=1;i<=B+W;i++){
		long P = (Now + mod + HALF - (Nob+Now)*HALF%mod) % mod;
		HALFP *= HALF;
		HALFP %= mod;
		if(B <= i){
			Nob += HALFP * F.GetConv(i-1,B-1);
			Nob %= mod;
		}
		if(W <= i){
			Now += HALFP * F.GetConv(i-1,W-1);
			Now %= mod;
		}
		cout << P << endl;
	}	
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 5376
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
typedef unsigned long long ull;
#define rep(i,a) for(int i=0;i<a;i++)
#define loop(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const double eps = 1e-10;
const double pi = acos(-1);
const double inf = (int)1e8;

int j,y;
void dfs(int a,int b,string game){
  if(a == j && b == y){
    cout<<game<<endl;				
    return ;
  }else if(a>j||b>y)return;
  else if((a<=3 && b==5) || 
	  (a==5 && b<=3) ||
	  (a==6 && b==6)) return;
  else{
    dfs(a+1,b,game+'A');
    dfs(a,b+1,game+'B');
  }
}


int main(void){
  cin>>j>>y;
  dfs(0,0,"");
}

Measured memory_bytes: 1200
#include<stdio.h>

void koubaisu(int array[],int ans[],int i){
  int r,tmp;
  int a=ans[i];
  int b=array[i+2];
  if(a<b){
    tmp=a;
    a=b;
    b=tmp;
  }
  r=a%b;
  while(r!=0){
    a=b;
    b=r;
    r=a%b;
  }
  ans[i+1]=b;
}

int main(void){
  int n,i,r,a,b,tmp,count;
  while(scanf("%d",&n)!=1);
  int array[n];
  int ans[n];
  for(i=0;i<n;i++){
    while(scanf("%d",&array[i])!=1);
  }
  for(i=0;i<n;i++){
    if(array[i]==array[i+1])count++;
  }
  if(count==n-1){
    printf("%d\n",array[0]);
  }else{
    a=array[1];
    b=array[0];
    if(a<b){
      tmp=a;
      a=b;
      b=tmp;
    }
    r=a%b;
    while(r!=0){
      a=b;
      b=r;
      r=a%b;
    }
    ans[0]=b;
    for(i=0;i<n-2;i++){
      koubaisu(array,ans,i);
    }
    printf("%d\n",ans[n-2]);
  }
  return 0;
}



Measured memory_bytes: 896
//Reference https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
 use std::cmp::min;
  use std::cmp::max;
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
fn main(){
    input!{
        N: usize,
        W: [i32; N],
    }
    let mut Max = 0;
    let mut Min = 1_000_000;
    for i in 0..N{
        Max = max(W[i], Max);
        Min = min(W[i], Min);   
    }
    let mut ans = 1_000_000;
    for T in Min..(Max + 1){
        let  (mut S_1, mut S_2) = (0, 0);
        for i in 0..N{
            if i < T as usize{
                S_1 += W[i];
            }else{
                S_2 += W[i];
            }
        }
        ans = min(ans, (S_1 - S_2).abs());
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
struct node { int v; node *nxt; } edge[maxn*2],*head[maxn],*ncnt;
int n,m,dist[maxn],cirlen,spx,spy,sum[maxn],xs[maxn],st[maxn],t;
bool vis[maxn];
void addedge(int u,int v)
{
	ncnt++;
	ncnt->v=v,ncnt->nxt=head[u];
	head[u]=ncnt;
}
void dfs(int u,int fa)
{
	vis[u]=true;
	for(node *p=head[u];p;p=p->nxt)
	{
		int v=p->v;
		if(v==fa) continue;
		if(vis[v]) spx=u,spy=v,cirlen=dist[u]-dist[v]+1;
		else { dist[v]=dist[u]+1; dfs(v,u); }
	}
}
void getxs(int u,int fa)
{
	vis[u]=true;
	for(node *p=head[u];p;p=p->nxt)
	{
		int v=p->v;
		if(vis[v]) continue;
		getxs(v,u);
		xs[u]+=xs[v],sum[u]+=sum[v];
	}
}
int main()
{
	ncnt=&edge[0];
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v); addedge(v,u);
	}
	dfs(1,0);
	int ans=0,tot=0;
	for(int i=1;i<=n;i++)
	{
		if(dist[i]&1) sum[i]=-1;
		else sum[i]=1;
		tot+=sum[i];
	}
	if(m==n-1&&tot) { printf("-1\n"); return 0; }
	else if(m==n)
	{
		if(cirlen%2)
		{
			if(tot%2) { printf("-1\n"); return 0; }
			sum[spx]-=tot/2,sum[spy]-=tot/2;
			ans+=abs(tot)/2;
		}
		else
		{
			if(tot) { printf("-1\n"); return 0; }
			xs[spx]=1,xs[spy]=-1;
		}
	}
	memset(vis,0,sizeof(vis));
	getxs(1,0);
	for(int i=1;i<=n;i++)
	{
		if(!xs[i]) ans+=abs(sum[i]);
		else
		{
			if(xs[i]==1) sum[i]=-sum[i];
			st[++t]=sum[i];
		}
	}
	st[++t]=0;
	sort(st+1,st+t+1);
	int k=st[(t+1)/2];
	for(int i=1;i<=t;i++) ans+=abs(st[i]-k);
	printf("%d\n",ans);
}

Measured memory_bytes: 10368
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
#define N 100007
#define pb push_back;
vector<ll> v[N];
vector<bool> vs(N);
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);

int main()
{
    ll x,n,i;
    cin>>x>>n;
    vector<ll> v;
    map<ll,ll> mp;
    for(i=0;i<n;i++)
    {
        ll y;
        cin>>y;
        mp[y]++;
    }
    for(i=0;i<=107;i++)
    {
        if(mp[i]==0)
        {
            v.push_back(i);
        }
    }
    ll ind=lower_bound(v.begin(),v.end(),x)-v.begin();
    if(ind==0)
    {
        cout<<v[ind];
    }
    else
    {
        if(abs(x-v[ind])>=abs(x-v[ind-1]))
        {
            cout<<v[ind-1];
        }
        else
        {
            cout<<v[ind];
        }
    }
}

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

typedef long long ll;
typedef unsigned long long ull;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SZ(x) (int)(x).size()
#define mset(a,x) memset(a,x,sizeof(a))
#define dbg(x) cout<<#x<<": "<<(x)<<"\n"
#define pb push_back
#define mp make_pair

int h,w;
int px=0, py=0;
int dx[]={1,0}, dy[]={0,1};
vector<string> v;

bool check() {
    rep(y,h) {
        rep(x,w){
            if(v[y][x]=='#') {
                if(x==0 or y==h-1) continue;
                if(v[y+1][x-1] == '#') return false;
            }
        }
    }
    return true;
}

int main() {
    while(cin>>h>>w) {
        v.resize(h);
        rep(i,h) cin>>v[i];

        if(check()) {
            puts("Possible");
        } else {
            puts("Impossible");
        }
    }
    return 0;
}


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

using namespace std;

typedef long long ll;
const int N = (int) 2e5 + 7;
const int K = 18;
int n;
int dif;
int q;
int a[N];
int u[K][N];
ll f[K][N];
int u2[K][N];
ll f2[K][N];

ll compute1(int x, int lim)
{
    ll sol = x - 1;
    for (int k = K - 1; k >= 0; k--)
    {
        if (u[k][x] <= lim)
        {
            sol += f[k][x] - (1 << k);
            x = u[k][x];
        }
    }
    return sol;
}

ll compute2(int x, int lim)
{
    ll sol = x;
    for (int k = K - 1; k >= 0; k--)
    {
        if (lim <= u2[k][x])
        {
            sol += f2[k][x];
            x = u2[k][x];
        }
    }
    return sol;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);


    cin >> n >> dif;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    a[n + 1] = a[n] + dif;
    int j = 1;
    for (int i = 1; i <= n; i++)
    {
        while (a[j] - a[i] < dif)
        {
            j++;
        }
        u[0][i] = j;
        f[0][i] = j;
    }
    a[0] = a[1] - dif;
    j = n;
    for (int i = n; i >= 1; i--)
    {
        while (a[i] - a[j] < dif)
        {
            j--;
        }
        u2[0][i] = j;
        f2[0][i] = j;
    }
    for (int k = 1; k < K; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (u[k - 1][i] == n + 1)
            {
                u[k][i] = n + 1;
            }
            else
            {
                f[k][i] = f[k - 1][i] + f[k - 1][u[k - 1][i]];
                u[k][i] = u[k - 1][u[k - 1][i]];
            }
            /// boooo
            if (u2[k - 1][i] == 0)
            {
                u2[k][i] = 0;
            }
            else
            {
                f2[k][i] = f2[k - 1][i] + f2[k - 1][u2[k - 1][i]];
                u2[k][i] = u2[k - 1][u2[k - 1][i]];
            }
        }
    }
    cin >> q;
    while (q--)
    {
        int l, r, best = 0, sol = 0;
        cin >> l >> r;
        cout << compute2(r, l) - compute1(l, r) << "\n";
    }
    return 0;

}


Measured memory_bytes: 86732
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
P = LIST()
Q = LIST()

a = [i + 1 for i in range(N)]

per = permutations(a)

index = 1
for i in per:
	if list(i) == P:
		a = index
	if list(i) == Q:
		b = index
	index += 1

print(abs(a-b))

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define DEBUG_ARR(v,n) cout<<#v<<":";REP(i,n)cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

bool isPrime(ll n){
    if(n==2) return true;
    if(n==1 || (n&1)==0) return false;

    ll d = (n-1)>>1;
    while((d&1)==0) d=d>>1;
    for(int k=0;k<100;k++){
        //ll a = (ll)abs(rand()) << (sizeof(int)*8);
        ll a = (ll)abs(rand()) << (sizeof(int)*7);
        a = 1 + (abs(a|(ll)rand()) % (n-1));
        ll t = d;
        //ll y = modpow(a,t,n);
        ll y = 1;
        //modpow
        while (t > 0) {
            if (t & 1) y = y * a % n;
            a = a * a % n;
            t >>= 1;
        }
        t = d;

        while(t != n - 1 && y != 1 && y != n - 1){
            y = (y * y) % n;
            t <<= 1;
        }

        if(y != n - 1 && (t & 1) == 0)
            return false;
    }
    return true;
}

int x;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>x;
    if(x==2){
        cout << "2" << endl;
        return 0;
    }
    if(x%2==0) x++;
    for(int i=x; x<INT_MAX; i+=2){
        if(isPrime(i)){
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}

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

int64_t gcd(int64_t a, int64_t b) {
  if (b < a) std::swap(a, b);
  if (a == 0) return b;
  return gcd(b%a, a);
}

const int MAX_N = 200005;
const int64_t MOD = 1000000007;
int64_t N;
int64_t as[MAX_N], bs[MAX_N];
std::map<std::pair<int64_t, int64_t>, int64_t> counts1, counts2;
std::set<std::pair<int64_t, int64_t>> seen;

int64_t modpow(int64_t v, int64_t e) {
  if (e == 0) return 1;
  if (e == 1) return v % MOD;
  int64_t mm = modpow(v, e/2) % MOD;
  int64_t mmm = (mm * mm) % MOD;
  if (e % 2) {
    return (mmm * v) % MOD;
  }
  return mmm;
}

int main() {
  scanf("%lld", &N);
  int had_zero = 0;
  for (int i = 0; i < N; ++i) {
    scanf("%lld %lld", as + i, bs + i);
    if (bs[i] < 0 || (bs[i] == 0 && as[i] < 0)) {
      as[i] *= -1;
      bs[i] *= -1;
    }
    int64_t g = gcd(std::abs(as[i]), std::abs(bs[i]));
    if (as[i] == 0 && bs[i] == 0) {
      had_zero++;
      i--;
      N--;
      continue;
    }
    // printf("%lld %lld: %lld\n", as[i], bs[i], g);
    counts1[std::make_pair(as[i]/g, bs[i]/g)]++;
    // counts2[std::make_pair(bs[i]/g, -as[i]/g)]++;
  }
  int64_t val = 1;
  for (auto kv : counts1) {
    auto rev = std::make_pair(-kv.first.second, kv.first.first);
    if (rev.second < 0 || (rev.second == 0 && rev.first < 0)) {
      rev.first *= -1;
      rev.second *= -1;
    }
    if (seen.count(kv.first) || seen.count(rev)) continue;
    seen.insert(kv.first);
    seen.insert(rev);
        // printf("equiv: %lld %lld: %lld\n", kv.first.first, kv.first.second, kv.second);
    // printf("rev: %lld %lld: %lld\n", rev.first, rev.second, counts1[rev]);
    val = (val * ((modpow(2, kv.second) + modpow(2, counts1[rev]) - 1 + MOD) % MOD)) % MOD;
  }
  val = (val - 1 + MOD + had_zero) % MOD;
  printf("%lld\n", val);
}


Measured memory_bytes: 56956
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){ 
    string s; cin >> s;
    int year = stoi(s.substr(0, 4));
    int month = stoi(s.substr(5, 2));
    if( year < 2019 || year == 2019 && month <= 4) cout << "Heisei" << ln;
    else cout << "TBD" << ln;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin)-1;i>=(end);i--)
#define IREP(i, n) IFOR(i,n,0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" << v[0]; FOR(i_debug, 1, v.size()){ cout << "," << v[i_debug]; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;


template<typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) { REP(i, a.size()) {cin >> a[i]; a[i]--;} }

ll mod = 1000000007;

int main()
{
	ll H, W;
	cin >> H >> W;
	vector<string> S(H);
	REP(i, H) {
		cin >> S[i];
	}

	vec s(H * W);
	vector<vec> clist(H * W, vec(0));

	ll N = H * W;

	ll numb = 0, numw = 0;
	REP(i, H) {
		REP(j, W) {
			if (S[i][j] == '.') {
				s[i * W + j] = 1;
				numw++;
			}
			else {
				s[i * W + j] = 0;
				numb++;
			}
		}
	}

	REP(i, N) {
		if (i - W >= 0) {
			if (s[i] == 1 && s[i - W] == 1) {
				clist[i].emplace_back(i - W);
				clist[i - W].emplace_back(i);
			}
		}
		if (i % W > 0) {
			if (s[i] == 1 && s[i - 1] == 1) {
				clist[i].emplace_back(i - 1);
				clist[i - 1].emplace_back(i);
			}
		}
	}

	// mdebug(clist);


	// BFS のためのデータ構造
	vector<ll> dist(N, -1); // 全頂点を「未訪問」に初期化
	queue<ll> que;

	// 初期条件 (頂点 0 を初期ノードとする)
	dist[0] = 0;
	que.push(0); // 0 を橙色頂点にする

	// BFS 開始 (キューが空になるまで探索を行う)
	while (!que.empty()) {
		int v = que.front(); // キューから先頭頂点を取り出す
		que.pop();

		// v から辿れる頂点をすべて調べる
		for (int nv : clist[v]) {
			if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

			// 新たな白色頂点 nv について距離情報を更新してキューに追加する
			dist[nv] = dist[v] + 1;
			que.push(nv);
		}
	}
	if (dist[N - 1] == -1) cout << -1 << endl;
	else {
		ll ans = numw - dist[N - 1] - 1;
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;

int main(){
    string S;
    ll K;
    cin >> S >> K;

    int N = S.size();
    int i=0;
    ll cnt = 0;

    bool mono = true;
    for(int i=0;i<N-1;i++){
      if(S[i]!=S[i+1]) mono = false;
    }

    while(i<N){
      int conti = 1;
      while(i<N-1 && S[i]==S[i+1]){
        conti++;
        i++;
      }
      cnt += conti/2;
      i++;
    }
    //cout << cnt <<endl;

    ll cnt2 = 0;
    i = 0;
    while(i<2*N){
      int conti = 1;
      while(i<2*N-1 && S[i%N]==S[(i+1)%N]){
        conti++;
        i++;
      }
      cnt2 += conti/2;
      i++;
    }

    if(S[0]!=S[N-1]){
      cout << K*cnt <<endl;
    }else if(mono){
      cout << (K*N)/2 <<endl;
    }else{
      cout << cnt + (cnt2-cnt)*(K-1) <<endl;
    }

  	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  double a,b,c,d,e,f,x,y;

  while(EOF!=scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f) ){
    y = (c*d-a*f)/(b*d-a*e);
    x = (c - b*y)/a;

//四捨五入

    printf("%.3f %.3f\n", x, y);
  }

  return 0;
}

Measured memory_bytes: 648
def resolver(N, A, Q, BC):
    total = sum(A)
    counter = dict()
    ans = []
    for a in A:
        counter[a] = counter.get(a, 0) + 1
    
    for (b, c) in BC:
        c0 = counter.pop(b) if b in counter else 0
        counter[c] = counter.get(c, 0) + c0
        total -= c0 * b
        total += c0 * c
        ans.append(total)
    
    return ans

def test():
    pass

def main():

    #test()

    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = []
    for _ in range(Q):
        bc = list(map(int, input().split()))
        BC.append(bc)

    ans = resolver(N, A, Q, BC)

    for a in ans:
        print(a)



if __name__ == '__main__':
    main()

Measured memory_bytes: 43408
<?php
  
fscanf(STDIN, "%d", $a);

echo countOdd($a);

function countOdd($a) {
	$len = strlen($a);
	if ($len === 1) {
  		return $a;
	}

  	$odds = 0;
	$b = intval(str_repeat('9', $len - 1));
	$is_odd = $len % 2; 
	if ($is_odd) {
		$odds = $a - $b;
	}
	$odds += countOdd($b);

  	return $odds;
}

Measured memory_bytes: 3576
c11, c12, c13 = map(int,input().split())
c21, c22, c23 = map(int,input().split())
c31, c32, c33 = map(int,input().split())

f1 = abs(c11 - c21) == abs(c12 - c22) == abs(c13 - c23)
f2 = abs(c21 - c31) == abs(c22 - c32) == abs(c23 - c33)
f3 = abs(c11 - c12) == abs(c21 - c22) == abs(c31 - c32)
f4 = abs(c12 - c13) == abs(c22 - c23) == abs(c32 - c33)

if f1 and f2 and f3 and f4:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"

bool palindrome(int n,char* a)
{
	//cout<<n<<endl;
	for(int i=0;i<n/2;i++)
	{
		//cout<<*(a+i)<<endl;
		if(a[i]!=a[n-i-1])
			return 0;
	}
	return 1;
}
int main()
{
	IOS
	int n;
	vector <char> a;
	char c;
	a.push_back('1');
	c=getchar();
	while(c!='\n')
	{
		a.push_back(c);
		c=getchar();
	}
	n=a.size()-1;
	if(palindrome(n,&a[1])&&palindrome((n-1)/2,&a[1])&&palindrome((n-1)/2,&a[(n+3)/2]))
	{
		cout<<"Yes";
	}
	else cout<<"No";
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
ll n,m;
int main(){
    string s;
    cin>>s;
    reverse(s.begin(),s.end());
    string t = s;
    reverse(s.begin(),s.end());
    if(t==s){
        string u = s.substr(0,(s.size()-1)/2);
        string v = s.substr(    (s.size()+3)/2-1,   s.size()-(s.size()+3)/2+1);
        reverse(u.begin(),u.end());
        reverse(v.begin(),v.end());
        string u2=u;
        string v2=v;
        reverse(u.begin(),u.end());
        reverse(v.begin(),v.end());
        if(u2==u && v2 == v) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
for i in range(1, n + 1):
	if i % 3 == 0:
		print(' %d' % i, end="")
	else:
		j = i
		while j > 0:
			if j % 10 == 3:
				print(' %d' % i, end="")
				break
			j //= 10
print("")


Measured memory_bytes: 5868
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] header = br.readLine().split(" ");
    long ans = 0;
    int r = Integer.parseInt(header[0]);
    int c = Integer.parseInt(header[1]);
    int k = Integer.parseInt(header[2]);

    long[][] map = new long[r + 1][c + 1];

    for (int i = 0; i < k; i++) {
      String[] line = br.readLine().split(" ");
      int ri = Integer.parseInt(line[0]);
      int ci = Integer.parseInt(line[1]);
      long vi = Long.parseLong(line[2]);
      map[ri][ci] = vi;
    }
    br.close();

    long[][][] dp = new long[r + 1][c + 1][4];
    for (int i = 1; i <= r; i++) {
      for (int j = 1; j <= c; j++) {
        dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j][0]);
        dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j][1]);
        dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j][2]);
        dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j][3]);
        dp[i][j][0] = Math.max(dp[i][j][0], dp[i][j - 1][0]);

        dp[i][j][1] = Math.max(dp[i][j][1], dp[i][j][0] + map[i][j]);
        dp[i][j][1] = Math.max(dp[i][j][1], dp[i][j - 1][0] + map[i][j]);
        dp[i][j][1] = Math.max(dp[i][j][1], dp[i][j - 1][1]);


        dp[i][j][2] = Math.max(dp[i][j - 1][2], dp[i][j - 1][1] + map[i][j]);
        dp[i][j][3] = Math.max(dp[i][j - 1][3], dp[i][j - 1][2] + map[i][j]);
      }
    }
    for(int i = 0; i <= 3; i++){
      ans = Math.max(ans, dp[r][c][i]);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 737468
main = interact $ unlines . show' . solve . read' . lines
  where
    solve (matrix, vector) = map (sum . zipWith (*) vector) matrix
    show' = map show
    read' (nm:xs) = (map (map read .words) matrix, map read vector)
      where
        (matrix, vector) = splitAt n xs
        n = head . (map read) . words $ nm


Measured memory_bytes: 7440
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
#define per(i,s,n) for(int i=n-1;i>=s;i--)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void Ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ll INF=1001001001;
const ll mod=1000000007;

struct UnionFind{
  vector<int> par;
  
  UnionFind(int n) : par(n){
    rep(i,n){
      par[i] = i;
    }
  }
//木を深くならないように調節
  int root(int x){
    if(par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  
  void unite(int x, int y){
    if(root(x) == root(y)) return;
    par[root(x)] = root(y);
  }
  
  bool same(int x, int y){
    return root(x) == root(y);
  }
  
  void update_par(){
  for(int i=0;i<par.size();i++){
    root(i);
  }
  }
  
  int count(){
    set<int> s;
    int a=0;
    for(int i=0;i<par.size();i++){
      if(s.find(par[i])!=s.end()) continue;
      s.insert(par[i]);
      a++;
    }
    return a;
  }
      
  
  
};

int main(){
  int n,m;
  cin>>n>>m;
  int x,y,z;
  
  UnionFind u(n);
  rep(i,m){
    cin>>x>>y>>z;
    x--;
    y--;
    u.unite(x,y);
  }
  u.update_par();
  
 // cout<<1<<endl;
  
  int h=u.count();
  
  cout<<h<<endl;
}
  
  
  

Measured memory_bytes: 5376
N=int(input())
L=[1 for i in range(N+1)]
L[0]=-10**10

import bisect
for i in range(N):
    n=int(input())
    L[bisect.bisect_right(L,-n)]=-n
#print(L)
ans=0
for i in range(1,N+1):
    if L[i]==1:
        break
    ans+=1
print(ans)

Measured memory_bytes: 79676
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int(i) = 0; (i) < (int)(n); ++(i))
#define rep_3(i, initial, n) for (int(i) = (int)(initial); (i) < (int)(n); ++(i))
#define rep(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int(i) = (int)(n); (i) > 0; (i)--)
#define rep_r_3(i, initial, n) for (int(i) = (int)(initial); (i) > (int)(n); (i)--)
#define rep_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define type definition
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;

// define construct variable
const double EPS = numeric_limits<double>::epsilon();
// 10^9 + 7
const ll MOD = ll(1e9)+7;
const ll INF = ll(1e10);
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

// define methods
// 最大公約数
ll gcd(const ll a, const ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(const ll a, const ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }
// 素因数分解
vector< pair<ll, ll> > prime_factorize(ll n) {
  vector< pair<ll, ll> > p;
  for (ll i = 2; i * i <= n; i++) {
    if ((n % i) != 0) continue;
    p.push_back(make_pair(i, 0));
    while ((n % i) == 0) {
      n /= i;
      p[i].second += 1;
    }
    p.push_back(make_pair(n, 0));
  }

  if (n != 1) p.push_back(make_pair(n, 1));
  return p;
}
// 組み合わせの整合性を保つ（後ほど解析する）
ll modinv(ll a) {
	ll b = MOD, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b;
		swap(a, b);
		u -= t * v;
		swap(u, v);
	}
	u %= MOD;
	if (u < 0) { u += MOD; }
	return u;
}
// 順列
ll permutation(const ll n, const ll m) {
	ll result = 1;
	for (ll i = n; i > n - m; i--) { result = (result * i) % MOD; }
	return result;
}

// 繰り返し n 乗法
ll repeat_square(const ll n, const ll x) {
	if (x == 0) return 1;
	ll res = repeat_square(n, x/2);
	res = res * res % MOD;
	if ((x % 2) == 1) res = res * n % MOD;
  return res;
}
// 組み合わせ
ll combination(const ll n, const ll a) {
	ll x = 1, y = 1;
  for(ll i = 0; i < a; i++){
    x = x * (n-i) % MOD;
    y = y * (i+1) % MOD;
  }
  return x * repeat_square(y, MOD-2) % MOD;
}

int result = 0;

void dfs(int N, int M, int Q, vector<int> A, map<int, vector<int> > m){
	if (A.size() == N+1) { // 最初に入っている [1] は除いた数列で判定するため
		int temp = 0;
		rep(i, Q) {
			int a = m[i][0];
			int b = m[i][1];
			int c = m[i][2];
			int d = m[i][3];
			if ((A[b] - A[a]) == c) temp += d; // Aは 1番目から参照しているため、添字は -1 しなくて良い
		}

		if (temp > result) result = temp;
		return;
	}
	A.push_back(A.back()); // 直前の数を push（A1 <= A2 <= A3 ... An のため）
	while(A.back() <= M) {
		dfs(N, M, Q, A, m);
		A.back()++;
	}
}

int main() {
	int K;
	string S;
	cin >> K >> S;

	string result = S.substr(0, K);
	if (K < S.length()) result += "...";

	cout << result << endl;
  return 0;
}


Measured memory_bytes: 3636
from collections import deque

n = int(input())
d = {i: [] for i in range(1, n+1)}
for _ in range(n-1):
    a, b, c = map(int, input().split())
    d[a].append((b, c))
    d[b].append((a, c))
q, k = map(int, input().split())
D = [-1] * (n + 1)
D[k] = 0
que = deque([k])
while que:
    t = que.popleft()
    dist = D[t]
    for l, c in d[t]:
        if D[l] < 0:
            D[l] = dist + c
            que.append(l)
for _ in range(q):
    x, y = map(int, input().split())
    print(D[x] + D[y])


Measured memory_bytes: 53864
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1000005;

int a[maxn];
int cnt[maxn], mark[maxn];
vector<int> primes;
int sz;

void sieve(){
  mark[1] = 1;
  for(int i = 4; i < maxn; i += 2)mark[i] = 1;
  int root = sqrt(maxn);
  for(int i = 3; i <= root; i += 2){
    if(!mark[i]){ 
      for(int j = i + i; j < maxn; j += i){
        mark[j] = 1;
      }
    }
  }
  primes.push_back(2);
  for(int i = 3; i < maxn; i += 2){
    if(!mark[i]){
      primes.push_back(i);
    }
  }
  sz = primes.size();
}

void fact(int x){
  if(x % 2 == 0){
    cnt[2]++;
    while(x % 2 == 0){
      x /= 2;
    }
  }
  for(int i = 1; i < sz && primes[i] * primes[i] <= x; ++i){
    if(x % primes[i] == 0){
      cnt[primes[i]]++;
      while(x % primes[i] == 0){
        x /= primes[i];
      }
    }
  }
  if(x > 1){
    cnt[x]++;
  }
}

int main(int argc, char const *argv[])
{
  int n;
  scanf("%d", &n);
  int gcd = 0;
  for(int i = 1; i <= n; ++i){
    scanf("%d", &a[i]);
    gcd = __gcd(a[i], gcd);
  }
  if(gcd != 1){
    printf("not coprime\n");
    return 0;
  }
  sieve();
  for(int i = 1; i <= n; ++i){
    fact(a[i]);
  }
  bool bad = 0;
  for(int i = 2; i < maxn; ++i){
    if(cnt[i] > 1){
      bad = 1;
      break;
    }
  }
  if(!bad){
    printf("pairwise coprime\n");
  }else {
    printf("setwise coprime\n");
  }

  return 0;
}

Measured memory_bytes: 15472
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;

int main()
{
    int N, K,gcd=0,m=0;
    bool flag = false;

    cin >> N >> K;
    vint A(N);
    rep(i,N)
    {
        cin >> A[i];
        gcd = __gcd(gcd, A[i]);
        m = max(m, A[i]);
    }
    if(K>m)
        flag = false;
    else if(K%gcd == 0)
    {
        flag = true;
    }
    else
    {
        flag = false;
    }
    cout << (flag ? "POSSIBLE" : "IMPOSSIBLE");
    return 0;
}

Measured memory_bytes: 640
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	// ReadString returns a WORD string.
	ReadString func() string
)

func init() {
	ReadString = newReadString(os.Stdin, bufio.ScanWords)
}

func newReadString(ior io.Reader, sf bufio.SplitFunc) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+9)) // for Codeforces
	r.Split(sf)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	n, _ := strconv.Atoi(ReadString())
	return n
}

// 10 11 12 => [10, 11, 12]
func readIntSlice(size int) []int {
	a := make([]int, size)
	for i := 0; i < size; i++ {
		a[i] = readInt()
	}
	return a
}

func get2byte(size int) [][]byte {
	a := make([][]byte, size)
	for i := 0; i < size; i++ {
		var low string
		fmt.Scan(&low)
		a[i] = []byte(low)
	}
	return a
}

func transpose(a [][]int) {
	n := len(a)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			a[i][j], a[j][i] = a[j][i], a[i][j]
		}
	}
}

func fact(n, m int) int {
	res := 1
	for i := m + 1; i <= n; i++ {
		res *= i
	}
	return res
}

func perm(n, r int) int {
	if r > n {
		return 0
	}
	return fact(n, n-r)
}

func comb(n, m int) int {
	if m > n {
		return 0
	}
	return fact(n, n-m) / fact(m, 0)
}

func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func min(integers ...int) int {
	m := integers[0]
	for i, integer := range integers {
		if i == 0 {
			continue
		}
		if m > integer {
			m = integer
		}
	}
	return m
}

func max(integers ...int) int {
	m := integers[0]
	for i, integer := range integers {
		if i == 0 {
			continue
		}
		if m < integer {
			m = integer
		}
	}
	return m
}

func main() {
	n := readInt()
	s := ReadString()
	left := 0
	right := n - 1
	var counter int
	for left < right {
		if s[left] == 'W' && s[right] == 'R' {
			counter++
			left++
			right--
		} else if s[left] == 'W' {
			right--
		} else if s[right] == 'R' {
			left++
		} else {
			left++
			right--
		}
	}
	fmt.Println(counter)
}


Measured memory_bytes: 2444
#include <iostream>
#include <algorithm>
#include<set>
using namespace std;
std::set<int> st;
int main(void){
    int N,ans=0;
    cin>>N;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        if(st.count(a)!=0)st.erase(a);
        else st.insert(a);
    }
    cout<<st.size()<<endl;
}



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

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

#define fr first
#define sc second

const ll INF=1000000009;

bool comp(P x,P y){
	return x.fr*(y.sc+1)<y.fr*(x.sc+1);
}

int main(){
	static ll n,t;
	static ll a[200010],b[200010];
	scanf("%lld%lld",&n,&t);
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&a[i],&b[i]);
	}
	
	vector<P> vec;
	for(int i=0;i<n;i++){
		vec.push_back(P(a[i],b[i]));
	}
	sort(vec.begin(),vec.end(),comp);
	reverse(vec.begin(),vec.end());
	
	static ll dp[33];
	for(int i=0;i<33;i++){
		dp[i]=INF;
	}
	dp[0]=1;
	for(P p: vec){
		if(p.fr==0)break;
		for(int i=32;i>=0;i--){
			if(dp[i]<INF)dp[i+1]=min(dp[i+1],dp[i]+p.fr*dp[i]+p.sc+1);
		}
		/*cout<<a[k]<<" "<<b[k]<<endl;
		for(int i=0;i<=n;i++){
			cout<<dp[i]<<" ";
		}
		cout<<endl;*/
	}
	
	multiset<ll> S;
	for(int i=0;i<n;i++){
		if(a[i]==0)S.insert(b[i]);
	}
	static int ret=0;
	for(int i=0;i<33;i++){
		if(dp[i]>t+1)continue;
		//cout<<i<<" "<<dp[i]<<endl;
		int cnt=i;
		for(ll x: S){
			if(dp[i]+x+1>t+1)break;
			dp[i]+=x+1;
			cnt++;
		}
		ret=max(ret,cnt);
	}
	cout<<ret<<endl;
}



Measured memory_bytes: 16748
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define llong long long
#define fr(i,l,r) for(i=(l);i<(r);i++)
#define min(p,q)((p)<(q)?(p):(q))




int main(void)
{
	//変数の宣言
	char s[100010];
	int go=0;
	int pa=0;
	
	//よく使う変数
	int i,j,k,l;
	int flag=0;
	llong int ans=0;
	int count=0;
	int sum=0;
	long int temp,temp1,temp2;
	int max,min;
	int len;
	//データの読み込み
	
	scanf("%s",&s);
	
	
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	
	len=strlen(s);
	
	for(i=0;i<len;i++){
		if(s[i]=='g'){
			go++;
		}else if(s[i]=='p'){
			pa++;
		}else{
			printf("error");
		}
	}
	
//	printf("計算部分終了\n");
	//出力
	
	printf("%d",(go-pa)/2);
	
//	printf("結果の出力終了\n");
	
	return 0;
	
}



Measured memory_bytes: 384
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] num = new int[100001];
        int ans = 0;
        
        for(int i = 0;i < n;i++){
            int a = sc.nextInt();
            if(a != 0)
                num[a-1]++;
            num[a]++;
            num[a+1]++;
        }
        
        for(int i:num)
            ans = Math.max(ans,i);

        System.out.println(ans);
    }
}

Measured memory_bytes: 50616
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const int MAXN=500007;

int n;
bool t[26][4*MAXN];

void build(int idx, int v, int tl, int tr) {
	if (tl == tr) {
		t[idx][v] = false;
	} else {
		int tm = (tl + tr) / 2;
		build(idx, v*2, tl, tm);
		build(idx, v*2+1, tm+1, tr);
		t[idx][v] = t[idx][v*2] + t[idx][v*2+1];
	}
}

bool sum(int idx, int v, int tl, int tr, int l, int r) {
	if (l > r) 
		return false;
	if (l == tl && r == tr) {
		return t[idx][v];
	}
	int tm = (tl + tr) / 2;
	return sum(idx, v*2, tl, tm, l, min(r, tm)) || sum(idx, v*2+1, tm+1, tr, max(l, tm+1), r);
}

void update(int idx, int v, int tl, int tr, int pos, int new_val) {
	if (tl == tr) {
		t[idx][v] = new_val;
	} else {
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			update(idx, v*2, tl, tm, pos, new_val);
		else
			update(idx, v*2+1, tm+1, tr, pos, new_val);
		t[idx][v] = t[idx][v*2] || t[idx][v*2+1];
	}
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int N;
	string S; cin>>N>>S;
	n=N;
	for (int i=0; i<26; i++)
		build(i,1,0,n-1);
	for (int i=0; i<N; i++)
		update(S[i]-'a',1,0,n-1,i,true);
	int Q; cin>>Q;
	while(Q--) {
		int type; cin>>type;
		if(type==1) {
			int i; char c; cin>>i>>c; i--;
			update(S[i]-'a',1,0,n-1,i,false);
			S[i]=c;
			update(S[i]-'a',1,0,n-1,i,true);
		} else {
			int l,r; cin>>l>>r; l--; r--;
			int ret=0;
			for (int i=0; i<26; i++)
				if(sum(i,1,0,n-1,l,r))
					ret++;
			cout<<ret<<"\n";
		}
	}
	return 0;
}

Measured memory_bytes: 49820
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
#include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb emplace_back
#define koto_memory(a) cout<<(sizeof(a)/1048576.0)<<" MB";
#define res(v) sort(all(v)),v.erase(unique(all(v)), v.end());
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec "<<endl;
#define deb(x) cout<<endl<<"["<<#x<<" = "<<x<<"]"<<endl;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=3e6+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
int n,k,a[N],ans=1,z=1;unordered_map<int,int>t;
//queries
int sum(int l, int r,int v=1, int tl=0, int tr=N ) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return max(sum( l, min(r, tm),v*2, tl, tm)
           , sum(max(l, tm+1), r,v*2+1, tm+1, tr ));
}
//
void update(int pos, int new_val,int v=1, int tl=0, int tr=N ) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(pos,new_val,v*2, tl, tm);
        else
            update(pos,new_val,v*2+1, tm+1, tr);
        t[v] = max(t[v*2] , t[v*2+1]);
    }
}
void solve(){
  cin>>n>>k;
  rep(i,1,n){
    cin>>a[i];
    z=sum(max(a[i]-k,0LL),min(a[i]+k,N))+1;
    update(a[i],max(z,1LL));
    ans=max(ans,z);
   }
  cout<<ans;
}
int32_t main()
{
  ibs;cti;
  solve();return 0;
  int xx=0;
  int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<": "*/;solve();cout<<endl;}
  return 0;
}

Measured memory_bytes: 38132
from fractions import gcd

A, B = [int(i) for i in input().split()]

m = gcd(A, B)
pf = []
for i in range(2, m+1):
    if i ** 2 > m:
        break
    if m % i == 0:
        pf.append(i)
    while m % i == 0:
        m //= i
if m != 1:
    pf.append(m)
    
print(len(pf) + 1)

Measured memory_bytes: 5304
#include<bits/stdc++.h>
using namespace std;
int n,k,ans=1;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		if(ans<k){
			ans+=ans;
		}else{
			ans+=k;
		}
	}
	cout<<ans<<endl;
	return 0;
}



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

int main() {
	int cntTable[256] = {0};
	char ch;
	while (cin >> ch) cntTable[ch]++;
    for (int i = 97; i <= 122; i++)
        cout << (char)i << " : " << cntTable[i] + cntTable[i - 32] << endl;
    return 0;
}


Measured memory_bytes: 3072
N,M=map(int,input().split())
S=sorted([list(map(int,input().split())) for _ in range(N)], key=lambda x: x[0])

ans=0
for a,b in S:
    if M<=0: break
    x=min(M,b)
    ans+=a*x
    M-=x
print(ans)

Measured memory_bytes: 29320
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>
#include <string.h>

using namespace std;
typedef long long ll;

int main()
{
  ll n, k;
  cin >> n >> k;
  
  vector<ll> vec(n);
  for (ll i = 0; i < n; i++) {
    cin >> vec[i];
  }
  
  ll len = 0;
  for (ll i = 1; i <= k; i*=2) {
    len++;
  }
  
  ll x = 0;
  for (ll i = len - 1; i >= 0; i--) {
    ll one = 0, zero = 0;
    for (ll j = 0; j < n; j++) {
      if (vec[j] & (1LL << i)) {
        one++;
      } else {
        zero++;
      }
    }
    if (zero > one && (x | (1LL << i)) <= k) {
      x |= (1LL << i);
    }
  }
  ll ans = 0;
  for (ll i = 0; i < n; i++) {
    ans += vec[i] ^ x;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
# Problem A - Maximize the Formula

# input
num_list = list(map(int,input().split()))

# initialization
num_list = sorted(num_list, reverse=True)
num_list = list(map(str, num_list))

# output
ans = eval(num_list[0] + num_list[1] + "+" + num_list[2])
print(ans)


Measured memory_bytes: 38256
#include<iostream>
using namespace std;
int main(){
    int n,a,b,c,d;
    cin>>n>>a>>b>>c>>d;
    if(n%a>0)a=n/a+1;
    else a=n/a;
    if(n%c>0)c=n/c+1;
    else c=n/c;
    cout<<min(a*b,c*d)<<endl;
}


Measured memory_bytes: 3124
/*
const {stdin} = require('process');
let input = "";
stdin.on('data', x => {input += x});
stdin.on('end', () => {
    let lines = input.split('\n');
    let [n, m] = lines[0].split(' ')
        .map(x=>parseInt(x.trim()));
    if (m === 0) {
        console.log(0);
        return;
    }
    let signs = [
        [ 1, 1, 1],
        [ 1, 1,-1],
        [ 1,-1, 1],
        [ 1,-1,-1],
        [-1, 1, 1],
        [-1, 1,-1],
        [-1,-1,-1],
    ]
    let points = [];
    for (let _ of signs) { points.push(new Array<number>()); }
    for (let i = 0; i < n; i++) {
        let [x, y, z] = lines[i+1].split(' ')
            .map(x=>parseInt(x.trim()));
        signs.forEach(([a,b,c], i) => {
            points[i].push(x*a + y*b + z*c);
        });
    }
    let pointMax = points.map(x => {
        x.sort((x, y) => y - x);
        return x.slice(0, m).reduce((x, y) => x + y);
    });
    pointMax.sort((x, y) => y - x);
    console.log(pointMax[0]);
});
*/

var stdin = require('process').stdin;
var input = "";
stdin.on('data', function (x) { input += x; });
stdin.on('end', function () {
    var lines = input.split('\n');
    var _a = lines[0].split(' ')
        .map(function (x) { return parseInt(x.trim()); }), n = _a[0], m = _a[1];
    if (m === 0) {
        console.log(0);
        return;
    }
    var signs = [
        [1, 1, 1],
        [1, 1, -1],
        [1, -1, 1],
        [1, -1, -1],
        [-1, 1, 1],
        [-1, 1, -1],
        [-1, -1, -1],
    ];
    var points = [];
    for (var _i = 0, signs_1 = signs; _i < signs_1.length; _i++) {
        var _ = signs_1[_i];
        points.push(new Array());
    }
    var _loop_1 = function (i) {
        var _a = lines[i + 1].split(' ')
            .map(function (x) { return parseInt(x.trim()); }), x = _a[0], y = _a[1], z = _a[2];
        signs.forEach(function (_a, i) {
            var a = _a[0], b = _a[1], c = _a[2];
            points[i].push(x * a + y * b + z * c);
        });
    };
    for (var i = 0; i < n; i++) {
        _loop_1(i);
    }
    var pointMax = points.map(function (x) {
        x.sort(function (x, y) { return y - x; });
        return x.slice(0, m).reduce(function (x, y) { return x + y; });
    });
    pointMax.sort(function (x, y) { return y - x; });
    console.log(pointMax[0]);
});


Measured memory_bytes: 11540
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
//#include"testlib.h"
#define endl "\n"
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define sz(s)    (int)(s.size())
#define PI acos(-1)
#define EPS 1e-8
#define watch(x) cout << (#x)<<" = "<<x<<endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("street.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}


int main() {
	file();
	fast();
	int n, m, k; cin >> n >> m >> k;
	vector<string> v1(n);
	for (auto& it : v1)
		cin >> it;
	int ans = 0;
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < (1 << m); j++) {
			int cnt = 0;
			for (int x = 0; x < n; x++) {
				for (int y = 0; y < m; y++) {
					if (i & (1 << x))
						continue;
					if (j & (1 << y)) continue;
					if (v1[x][y] == '#') cnt++;
				}
			}
			ans += (cnt == k);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3616
#include <stdio.h>
int main(void){
    int n;
    
    scanf("%d",&n);
    
    int p[10];
    int max=0;
    int sum=0;
    
    for(int i=0;i<n;i++){
        scanf("%d",&p[i]);
        sum+=p[i];
        if(p[i]>max)max=p[i];
        
    }
    
    if(sum-2*max>0)printf("Yes\n");
    else printf("No\n");
    
    return 0;
}


Measured memory_bytes: 128