akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long hxtype;
typedef pair<int,int> pii;
#define rep(i,l,r) for(i=(l);i<=(r);++i)
#define per(i,l,r) for(i=(l);i>=(r);--i)
#define REP(i,l,r) for(i=(l);i< (r);++i)
#define PER(i,l,r) for(i=(l);i> (r);--i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
const ll p=998244353ll,pp=p*p;
inline void app(ll &a){if(a> pp)a-=pp;}
inline void spp(ll &a){if(a<0ll)a+=pp;}
const int m=1000000;
ll x[m+5];
inline ll expo(ll a){
	int b=998244351;
	ll c=1ll;
	while(b){
		if(b&1)c=c*a%p;
		b>>=1; a=a*a%p;
	}
	return c;
}
int main(){
	int n,i,a;ll sum=0ll,tmp=0ll;
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%d",&a);
		sum+=a;
		x[a]+=a;
	}
	rep(i,1,m){
		tmp=x[i];
		for(a=i<<1;a<=m;a+=i)tmp+=x[a];
		tmp%=p;
		x[i]=tmp*tmp;
	}
	per(i,m,1){
		tmp=x[i];
		for(a=i<<1;a<=m;a+=i)spp(tmp-=x[a]);
		x[i]=tmp%p;
	}
	tmp=0ll;
	rep(i,1,m)app(tmp+=x[i]*expo(i));
	printf("%lld",((tmp-sum+pp)%p)*499122177ll%p);
	return 0;
}

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

int main()
{
    long long int k,n,a[200005],i,j,mx=0,add=0;
    cin>>k>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(i=2;i<=n;i++)
    {
        add=add+a[i]-a[i-1];
        mx=max(mx,a[i]-a[i-1]);
    }

    add=add+k-a[n]+a[1];
    mx=max(mx,k-a[n]+a[1]);

    cout<<add-mx<<endl;

}


Measured memory_bytes: 1920
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>
 
int main(void){
    int n;
    scanf("%d",&n);
    if (n<1200){
        printf("ABC\n");
    } else if (n<2800){
        printf("ARC\n");
    } else {
        printf("AGC\n");
    }
	return 0 ;
}

Measured memory_bytes: 128
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [a[0]]
cnt = 1
for i in range(1, n):
	if a[i] == b[-1]:
		b.append(a[i])
		cnt = cnt + 1
	else:
		if (cnt & 1):
			b.pop()
		b.append(a[i])
		cnt = 1
if (cnt & 1):
	b.pop()
if len(b) < 4:
	print(0)
else:
	print(b[-1] * b[-3])
		


Measured memory_bytes: 14224
function main()
  
  N = parse(Int,readline())
  
  dict = Dict()
  
  for i in 1:N
    A = chomp(readline())
    dict[A] = get(dict,A,0) + 1
  end
  
  ans = 0
  
  for i in keys(dict)
    if dict[i] % 2 == 1
      ans += 1
    end
  end
  
  println(ans)
  
end

main()

Measured memory_bytes: 141276
n, k, c = map(int, input().split())
S = list(input())


def f(S):
    L = []
    on = True
    cnt = 0
    for i in range(n):
        if not on:
            if cnt == c:
                on = True
            cnt += 1
        if on and S[i] == 'o':
            on = False
            cnt = 0
            L.append(i)
            if len(L) == k:
                break
    return L


L = f(S)
R = [n-1-i for i in f(S[::-1])][::-1]
for i in range(k):
    if L[i] == R[i]:
        print(L[i]+1)


Measured memory_bytes: 69832
while True:
    H,W = map(int, input().split())
    if H==0 & W==0 : break 

    for i in range(H):
      for j in range(W):
        if i == 0 or i == H-1 or j == 0 or j == W-1:
          print("#", end="")
        else:
            print(".", end="")
      print()
    print()


Measured memory_bytes: 7004
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

enum Type{
	Call,
	Called_or_Lonely,
};

int N,memo[5001][2];

vector<int> V[5001];

int recursive(int node_id,Type type){

	if(memo[node_id][type] != -1)return memo[node_id][type];

	int ret = 0,tmp,sum;

	switch(type){
	case Call:
		sum = 0;
		for(int i = 0; i < V[node_id].size(); i++){
			sum += max(recursive(V[node_id][i],Call),recursive(V[node_id][i],Called_or_Lonely));
		}
		for(int i = 0; i < V[node_id].size(); i++){
			ret = max(ret,sum-max(memo[V[node_id][i]][Call],memo[V[node_id][i]][Called_or_Lonely])+recursive(V[node_id][i],Called_or_Lonely)+1);
		}
		break;
	case Called_or_Lonely:
		for(int i = 0; i < V[node_id].size(); i++){
			ret += max(recursive(V[node_id][i],Call),recursive(V[node_id][i],Called_or_Lonely));
		}
		break;
	}

	return memo[node_id][type] = ret;
}

int func(){

	return max(recursive(0,Call),recursive(0,Called_or_Lonely));
}


int main(void){

	scanf("%d",&N);
	int tmp;

    for(int day = 1;day <= N; day++){

        scanf("%d",&tmp);
        V[tmp].push_back(day);
        for(int i = 0; i <= day; i++){
        	for(int k = 0; k < 3; k++)memo[i][k] = -1;
        }

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

Measured memory_bytes: 3488
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    long long n;
    cin >> n;
    long long ans = n-1LL;
    for(long long i = 1LL; i <= (long long)sqrt(n)+1LL; i++){
        if(n % i == 0){
            ans = min(ans, (i-1LL)+(n/i-1LL));
        }
    }

    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 256
using System;
class Program
{
    static void Main(string[] args)
    {
        string S = Console.ReadLine();

        int c = 0;
        int c1 = 0;
        for (int i = 0; i < S.Length; i++)
        {
            if (S[i] == ((i % 2 == 0) ? '0' : '1'))
                c++;
            else
                c1++;
        }
        Console.WriteLine(c < c1 ? c : c1);
    }
}


Measured memory_bytes: 13116
#include <bits/stdc++.h>
using namespace std;
 
#define clr(i, j)     memset(i, j, sizeof(i))
#define pb            push_back
 #define PI acos(-1)
 #define MOD ((int)1e9+7)
typedef long long ll;
const int mx=1e9+5;
ll dp[107][100009];
//dp[i][w] aktr value ttgab b awl i elements w el weight bt3ha w
int main(){
    ll n,w;cin>>n>>w;
   ll ww[n+7];
ll v[n+7];
     for(ll i=1;i<=n;i++){
        cin>>ww[i]>>v[i]; 
        dp[i][ww[i]]=v[i];
    }
    /*
    3 8
3 30
4 50
5 60*/

    for(int i=1;i<=n;i++){
        
        for(ll j=0;j<=w;j++){
            if(j!=0){dp[0][j]=-1000000;}
            dp[i][j]=-1000000;  
             if(j-ww[i]>=0){
                 dp[i][j]=max(dp[i-1][j-ww[i]]+v[i],dp[i-1][j]);
             }
             dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
    }
        ll ans=0;
        for(ll j=0;j<=w;j++){
           ans=max(ans,dp[n][j]);
        
    }
    cout<<ans;
}

Measured memory_bytes: 82440
#include <iostream>
using namespace std;
int main(){
    string S;
    cin >> S;
    int N = S.size(), MOD = 1000000007;
     
    long long dp[100010][4] = {};
    for(int i = N; i >= 0; --i){
        for(int j = 3; j >= 0; --j){
            if(i == N){
                dp[i][j] = (j == 3 ? 1 : 0);
            }else{
                dp[i][j] = dp[i+1][j] * (S[i] == '?' ? 3LL : 1LL);
                if(j < 3 && (S[i] == '?' || S[i] == "ABC"[j])){
                    dp[i][j] += dp[i+1][j+1];
                }
                dp[i][j] %= MOD;
            }
        }
    }
cout << dp[0][0] << endl;
}

Measured memory_bytes: 6860
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
typedef long long ll;
int main() {
  int n,k;
  cin >> n >> k;
  vector<ll> a(n);
  ll sum=0;
  rep(i,n){
    cin >> a.at(i);
    sum+=a.at(i);
  }
  sort(ALL(a));
  ll minus=0;
  rep(i,min(n,k)){
    minus+=a.at(n-i-1);
  }
  cout << sum-minus << endl;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <deque>
#include <unordered_map>
#include <map>
#include <bitset>
#include <string>
#include <cstring>
#include <cassert>

#define pb push_back
#define mp make_pair
#define l(x) x << 1
#define r(x) x << 1 | 1
#define scan(x) do {while((x=getchar())<'0') ; for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0') ; } while(0)
char _;
#define x first
#define y second

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<float, float> pff;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

// int N, A[100005], dp[1005][1005];
// int x = 1;

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    printf("%d\n", (N - 1) * (M - 1));

    // scanf("%d", &N);
    // for (int i = 1; i <= N; i++) {
    //     scanf("%d", &A[i]);
    // }
    // do {
    //     for (int i = N; i >= 1; i--) {
    //         for (int j = i; j <= N; j++) {
    //             if (i == j) {
    //                 dp[i][j] = A[i];
    //             } else if (j - i == 1) {
    //                 dp[i][j] = max(A[i], A[j]);
    //             } else {
    //                 int lp = min(dp[i + 2][j], dp[i + 1][j - 1]) + A[i];
    //                 int rp = min(dp[i + 1][j - 1], dp[i][j - 2]) + A[j];
    //                 dp[i][j] = max(lp, rp);
    //             }
    //         }
    //     }
    //     // printf("%d\n", dp[1][N]);
    //     for (int i = 1; i <= N; i++) {
    //         for (int j = 1; j <= N; j++) {
    //             printf("%d ", dp[i][j]);
    //         }
    //         printf("\n");
    //     }
    //     printf("===\n");
    // } while (next_permutation(A + 1, A + 1 + N));
}

Measured memory_bytes: 256
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD (1000000007)
#define MOD2 (998244353)
#define MOD3 (1000000009)
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
ifstream cinn("input.txt");ofstream coutt("output.txt");
int poww(int a,int b,int m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;}

pii f(pii p){
    int a=p.first;
    int b=p.second;
    
    if(a==0)return {0,1};
    if(b==0)return {1,0};
    
    if(b<0){
        a=-a;
        b=-b;
    }
    return {a,b};
}

pii fi(pii p){
    int a=p.first;
    int b=p.second;
    
    return f({-b,a});
}

signed main(){
    FASTER;
    int n;cin>>n;
    vii v(n);cin>>v;
    
    int cnt=0;
    map<pii,int> mp;
    for(pii &p:v){
        if(p.first==0 && p.second==0){
            cnt++;
            continue;
        }
        int g=__gcd(abs(p.first),abs(p.second));
        p.first/=g;
        p.second/=g;
        mp[f(p)]++;
    }
    
    map<pii,bool> vis;
    int ans=1;
    for(pii p:v){
        pii x=f(p);
        pii y=fi(x);
        if(vis[x]||vis[y])continue;
        
        int le=(poww(2,mp[x])+poww(2,mp[y])-1+MOD)%MOD;
        (ans*=le)%=MOD;
        
        vis[x]=vis[y]=1;
    }
    (ans+=cnt-1+MOD)%=MOD;
    cout<<ans;
}

Measured memory_bytes: 56196
N, X = map(int, input().split())
x = list(map(int, input().split()))
d = []
min=abs(x[0]-X)
for i in range(N):
    d.append(abs(x[i] - X))

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

if len(d) == 1:
    print(d[0])
else:    
    g = gcd(d[0], d[1])
    for i in range(2,N):
        g=gcd(g,d[i])
    print(g)

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

int main() {
  int N;//データ
  int A,B;//上限:A,下限:B
  int ans = 0; //答え
  
  //入力部
  cin >>N>>A>>B;
  
  //計算部:0～9999までの足し算
  for (int i=0;N >= 1000*i && i<10;i++){
    for (int j=0;N >= 1000*i+100*j && j<10;j++){
      for (int k=0;N >= 1000*i+100*j+10*k && k<10;k++){
        for (int l=0;N >= 1000*i+100*j+10*k+l && l<10;l++){
          if((i+j+k+l)<=B && (i+j+k+l)>=A)
            ans += 1000*i + 100*j +10*k +l;
        }
      }
    }
  }
  
  //計算部:10000のときのみ使用
  if (N == 10000&&A <=1 && B >= 1)
    
    ans+= 10000;
  
  //出力部
  cout << ans<< endl;
}

    
  
  
  
    
  
  


Measured memory_bytes: 3628
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#define pb push_back
using namespace std;
typedef long long int lli;
typedef pair<int,long long int> pii;
vector<vector<pii> > g;
lli resv[111111];
bool vis[111111];

void dfs(int x,lli t){
  resv[x]=t;
  vis[x]=true;
  for(int i=0;i<g[x].size();i++){
    if(!vis[g[x][i].first]) dfs(g[x][i].first,t+g[x][i].second);
  }
}

int main(void){
  int n,q,k;
  lli a,b,c,x,y;
  cin>>n;
  for(int i=0;i<=n;i++){
    vector<pii> p;
    g.pb(p);
  }
  for(int i=0;i<n-1;i++){
    cin>>a>>b>>c;
    g[a].pb(pii(b,c));
    g[b].pb(pii(a,c));
  }
  cin>>q>>k;
  dfs(k,0);
  for(int i=0;i<q;i++){
    cin>>x>>y;
    cout<<resv[x]+resv[y]<<endl;
  }
  return 0;
}

Measured memory_bytes: 13040
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <string>
#include <sstream>
#define ll long long
#define F first
#define S second
#define pb push_back
#define ld long double
#define pll pair<long long,long long>
#define pld pair<long double,long double>
#define ios     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll mod=998244353;
ll INF=1e18;
ll gcd (ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll fastexp(ll x ,ll n)
{
    ll result =1;
    while(n>0)
    {
        if(n%2==1)
            result*=x;
        x*=x;
        n=n/2;
    }
    return result;
}

ll modularExp(ll x,ll n,ll mod)
{
    ll result=1;
    while(n>0)
    {
        if(n%2==1)
            result=(result*x)%mod;
        x=((x%mod)*(x%mod))%mod;
        n=n/2;
    }
    return (result)%mod;
}
bool isPrime(ll n)
{
    for(ll i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}
bool mycomp(pll &a,pll &b)
{
    if(a.F!=b.F)
        return a.F < b.F;
    else
        return a.S < b.S;
}
vector<ll> par(2005),sz(2005,1);

ll froot(ll x)
{
     if(x==par[x])
          return x;
     return par[x]=froot(par[x]);
}
void solve()
{
     ll n,k;
     cin>>n>>k;
     vector<pll> v(k);
     vector<ll> dp(n+1),pre(n+1);
     ll i,j;
     for(i=0;i<k;i++)
          cin>>v[i].F>>v[i].S;
     dp[1]=1;
     pre[1]=1;
     for(i=2;i<=n;i++)
     {
          for(j=0;j<k;j++)
          {
               ll l = max(0LL,i-v[j].F);
               ll r = max(0LL,i-v[j].S-1);
               // cout<<l<<" "<<r<<"!\n";
               dp[i]=(dp[i]+pre[l]%mod-pre[r]%mod+mod)%mod;
          }
          pre[i]=(pre[i-1]+dp[i])%mod;
     }
     cout<<dp[n];
     
     
}

int main()
{
    ios;
    ll t;
     // cin>>t;
     t=1;
     while(t--)
     {
          solve();
     }
}


Measured memory_bytes: 6348
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
  int n;
  cin >> n;
  int ans = 0;
  int sum = 0;
  rep(i, n){
    int d1, d2;
    cin >> d1 >> d2;
    if(d1 == d2) sum++;
    else sum = 0;
    ans = max(ans, sum);
  }
  if(ans >= 3) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
#define ld long double 
#define ll long long 
using namespace std;

int main()
{
	std::ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	ll a[n];
	ll i=0;
	ll p=1;
	ld m=1;
	for(i=0;i<n;i++)
	{
		
		cin>>a[i];	
	
	}
	
	for(i=0;i<n;i++)
	{
		
	    p=p*a[i];
	    m=m*a[i];
			
    
	}
	 
	ll k= pow(10,18);
	if(m>k) 
	{
		
		cout<<"-1"<<endl;
		
	}
	
	
	else 
	{
		
		cout<<p<<endl;
		
	}
	

	

	return 0;
	
}

Measured memory_bytes: 4416
#include <iostream>
#include <vector>

using namespace std;

struct edge{
	int to, cap, rev;
};

int N;
int S, T;
int a[105], b[105], c[105], d[105];
vector<edge> G[5005];
bool used[5005];

int dfs(int s, int t, int c)
{
	if(s == t) return c;
	used[s] = true;
	
	int ret;
	for(int i = 0; i < (int)G[s].size(); i++){
		if(used[G[s][i].to] || G[s][i].cap == 0) continue;
		ret = dfs(G[s][i].to, t, min(c, G[s][i].cap));
		if(ret > 0){
			G[s][i].cap -= ret;
			G[ G[s][i].to ][ G[s][i].rev ].cap += ret;
			return ret;
		}
	}
	return 0;
}

void add_edge(int a, int b, int c)
{
	G[a].push_back((edge){b, c, G[b].size()});
	G[b].push_back((edge){a, 0, G[a].size()-1});
}

int main(void)
{
	cin >> N;
	for(int i = 1; i <= N; i++) cin >> a[i] >> b[i];
	for(int i = 1; i <= N; i++) cin >> c[i] >> d[i];
	
	S = 2*N+1, T = 2*N+2;
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			if(a[i] < c[j] && b[i] < d[j]){
				add_edge(i, N+j, 1);
			}
		}
	}
	for(int i = 1; i <= N; i++) add_edge(S, i, 1);
	for(int i = 1; i <= N; i++) add_edge(i+N, T, 1);
	
	int ans = 0, ret;
	while(1){
		for(int i = 0; i <= T; i++) used[i] = false;
		ret = dfs(S, T, 10000000);
		if(ret == 0) break;
		ans += ret;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
def insertion_sort(A):
    for i in range(1,len(A)):
        print(*A)
        key = A[i]
        #/* insert A[i] into the sorted sequence A[0,...,j-1] */
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j-=1
        A[j+1] = key
 
if __name__=='__main__':
   n=int(input()) 
   A=list(map(int,input().split()))
   insertion_sort(A)
   print(*A)


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

#define ll long long
#define db double
#define f first
#define s second
const int mod=1e9+7;
int a[399];
priority_queue<int>q;
int main()
{
    int n,x,sum1=0,sum2=0;
    cin>>n;
    for(int i=0;i<n;i++){cin>>x;q.push(x);}
    while(q.size())
    {
        sum1+=q.top();
        q.pop();
        if(q.empty())break;
        sum2+=q.top();
        q.pop();
    }
    cout<<sum1-sum2;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
    int a, b;
    
    cin >> a >> b;
    cout << "a ";
    if (a > b) {
        cout << "> ";
    } else if(a < b) {
        cout << "< ";
    } else if(a == b) {
        cout << "== ";
    }
    cout << "b" << endl;
    
    return 0;
}


Measured memory_bytes: 3088
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int N,Q;
const int W=700;
int c[5<<17];
int ans[5<<17];
int cnt[5<<17];
main()
{
	scanf("%d%d",&N,&Q);
	for(int i=0;i<N;i++)scanf("%d",&c[i]);
	vector<vector<pair<int,pair<int,int> > > >qs((N+W-1)/W);
	for(int i=0;i<Q;i++)
	{
		int l,r;scanf("%d%d",&l,&r);
		l--;
		qs[l/W].push_back(make_pair(r,make_pair(l,i)));
	}
	int L=0,R=0;
	int all=0;
	for(int i=0;i<qs.size();i++)
	{
		while(L<i*W&&L<N)
		{
			if(!--cnt[c[L++]])all--;
		}
		while(i*W<R)
		{
			if(!--cnt[c[--R]])all--;
		}
		sort(qs[i].begin(),qs[i].end());
		for(int j=0;j<qs[i].size();j++)
		{
			int r=qs[i][j].first;
			while(R<r)
			{
				if(!cnt[c[R++]]++)all++;
			}
			int l=qs[i][j].second.first;
			while(L<l)
			{
				if(!--cnt[c[L++]])all--;
			}
			while(L>l)
			{
				if(!cnt[c[--L]]++)all++;
			}
			ans[qs[i][j].second.second]=all;
		}
	}
	for(int i=0;i<Q;i++)printf("%d\n",ans[i]);
}


Measured memory_bytes: 18668
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body
(defun main ()
  (let* ((m (read))
         (k (read))
         (len (expt 2 (+ m 1)))
         (res (make-array len :element-type 'uint32)))
    (declare (uint32 k)
             ((integer 0 17) m))
    (cond ((zerop k)
           (dotimes (i len (terpri))
             (unless (zerop i) (write-char #\ ))
             (write (floor i 2))))
          ((= k (loop with res of-type uint32 = 0
                      for i from 0 below (expt 2 m)
                      unless (= i k)
                      do (setf res (logxor res i))
                      finally (return res)))
           (let ((index 0))
             (dotimes (num (expt 2 m))
               (if (= num k)
                   (progn (setf (aref res (- (expt 2 m) 1)) num)
                          (setf (aref res (- len 1)) num))
                   (progn
                     (setf (aref res index) num)
                     (setf (aref res (- len 2 index)) num)
                     (incf index)))))
           (loop with init = t
                 for c across res
                 do (if init
                        (setq init nil)
                        (write-char #\ ))
                    (princ c))
           (terpri))
          (t (println -1)))))

#-swank(main)


Measured memory_bytes: 20584
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define all(a) (a).begin(), (a).end()


int main() {
    int AB, BC, CA;
    cin >> AB >> BC >> CA;
    cout << AB * BC / 2 << endl;
}


Measured memory_bytes: 3644
main = do
  [n, k] <- map read . words <$> getLine :: IO [Int]
  a <- map read . words <$> getLine :: IO [Int]
  let d = foldl gcd 0 a
  putStrLn $ if any (\x -> x >= k && (x - k) `mod` d == 0) a then "POSSIBLE" else "IMPOSSIBLE"

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

typedef unsigned long long ll; 

ll gcd(ll a, ll b)
{
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}

int main() {
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
    a--;
	ll nc = (b/c) - (a/c);
	ll nd = (b/d) - (a/d);
	ll lcd = lcm(c,d);
	ll ncd = (b/lcd) - (a/lcd);
	cout << (b-a) - nc - nd + ncd << endl; 

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    int r;
    
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }

    return a;
}        
int main(){
    long long  n, x,  i, ans, dif[100090];
    vector <long long> a; 
    cin >> n >> x;
    a.push_back(x);
    for(i=0;i<n;i++){
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    for(i=0;i<n;i++){
        dif[i]=a[i+1]-a[i];
    }
    ans=gcd(dif[0], dif[1]);
    for(i=2;i<n;i++){
        ans=gcd(ans, dif[i]);
    }
    cout << ans <<endl;

return 0;
}

Measured memory_bytes: 1908
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007LL;
const int INF = LLONG_MAX;

void dfs(int cur, vector<int> &result, vector<vector<int> > &g, int cost){
    result[cur] = cost;
    for(auto nxt : g[cur]){
        if(result[nxt] == -1){
            dfs(nxt, result, g, cost + 1);
        }
    }
}

signed main(){
    
    int n; cin >> n;
    vector<vector<int> > g(n);
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> result_f(n, -1);
    vector<int> result_s(n, -1);
    dfs(0, result_f, g, 0);
    dfs(n - 1, result_s, g, 0);
    int cnt_f = 0;
    int cnt_s = 0;
    for(int i = 0; i < n; i++){
        if(result_f[i] <= result_s[i]) cnt_f++;
        else cnt_s++;
    }

    //cout << cnt_f << " " << cnt_s << endl;

    if(cnt_f > cnt_s) cout << "Fennec" << endl;
    else cout << "Snuke" << endl;
    return 0;
}

Measured memory_bytes: 12032
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)

ll N, M, Q;
vector<ll> a, b, c, d;


ll score(const vector<ll> &A){
  ll res = 0;
  rep1(i,Q){
    if (A[b[i]]-A[a[i]] == c[i]) res += d[i];
  }
  return res;
}

ll dfs(vector<ll> &A) {
  if (A.size() == N){
    return score(A);
  }
  ll res = 0;
  ll prev_last = (A.empty() ? 0 : A.back());
  for (ll v = prev_last; v < M; v++){
    A.push_back(v);
    res = max(res, dfs(A));
    A.pop_back();
  }
  return res;
}


int main() {
  cin >> N >> M >> Q;
  a.resize(Q); b.resize(Q); c.resize(Q); d.resize(Q);
  rep1(i,Q){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--, b[i]--;
  }
  vector<ll> A;
  cout << dfs(A) << endl;
}

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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    vector<int> vec1;
    vector<int> vec2;
    for (int i = 0; i < n; i ++) {
        int t;
        cin >> t;
        vec1.push_back(t);
    }
    for (int i = 0; i < n; i ++) {
        int t;
        cin >> t;
        vec2.push_back(t);
    }

    sort(vec1.begin(), vec1.end());
    reverse(vec1.begin(), vec1.end());
    sort(vec2.begin(), vec2.end());


    bool war = true;
    for (int i = vec1[0] + 1; i <= vec2[0]; i ++) {
        if (i > x && i <= y){
            war = false;
            break;
        }
    }

    if (war)
        cout << "War";
    else
        cout << "No War";

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	
	static int step(int n) {
		if(n==1) return 1;
		if(n==2) return 2;
		if(n==3) return 4;
		else return step(n-1)+step(n-2)+step(n-3);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if(n==0) break;
			int ans = step(n);
			System.out.println((ans%3650==0) ? ans/3650:ans/3650+1);
		}
	}	
}





Measured memory_bytes: 26232
n = int(input())

odd = [2*i + 1 for i in range(n) if (2*i +1) <= n]
ans = 0
for i in odd:
    cnt =0 
    for j in range(1,i+1):
        if (i % j) == 0:
            cnt+=1
    if(cnt==8):
        ans += 1
print(ans)


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main () {
    int N, X, T;
    cin >> N >> X >> T;
    cout << (N / X + bool(N % X)) * T << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
template <long long mod>
class Combination
{
    std::vector<long long> fact, finv, inv;
public:
    Combination(int sz)
    {
        fact.resize(sz);
        finv.resize(sz);
        inv.resize(sz);
        fact[0] = 1;
        for (int i = 1; i < sz; ++i)
        {
            fact[i] = fact[i - 1] * i % mod;
        }
        inv[0] = 0;
        inv[1] = 1;
        for (int i = 2; i < sz; ++i)
        {
            inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        }
        finv[0] = 1;
        for (int i = 1; i < sz; ++i)
        {
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    long long C(long long n, long long k)
    {
        if (n < k)
            return 0;
        if (n < 0 || k < 0)
            return 0;
        return (fact[n] * finv[k] % mod) * finv[n - k] % mod;
    }
    long long P(long long n, long long k)
    {
        if (n < k)
            return 0;
        if (n < 0 || k < 0)
            return 0;
        return fact[n] * finv[n - k] % mod;
    }
    long long H(long long n, long long k)
    {
        return this->C(n + k - 1, k);
    }
    long long getfact(int i)
    {
        return fact[i];
    }
    long long getinv(int i)
    {
        return inv[i];
    }
    long long getfinv(int i)
    {
        return finv[i];
    }
};
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template< typename T >
T mod_pow(T x, T n, const T &p) {
  T ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  ll n, a, b; cin >> n >> a >> b;
  Combination<MOD> comb(200010);
  ll ans = mod_pow<ll>(2, n, MOD);
  ans--;
  ll tmpa = 1;
  for(int i=0;i<a;++i) {
    tmpa *= n-i;
    tmpa %= MOD;
  }
  tmpa *= comb.getfinv(a);
  tmpa %= MOD;
  ll tmpb = 1;
  for(int i=0;i<b;++i) {
    tmpb *= n-i;
    tmpb %= MOD;
  }
  tmpb *= comb.getfinv(b);
  tmpb %= MOD;
  ans += MOD - tmpa;
  ans %= MOD;
  ans += MOD - tmpb;
  ans %= MOD;
  cout << ans << endl;
}


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

template <typename T> class SegmentTree{
	public :
		int n;
		SegmentTree(int size,T o): out_of_range(o){
			for(n=1;n<size;n<<=1);
			data=vector<T>(2*n,out_of_range);
			lazy=vector<bool>(2*n,false);
		}

		void update(int a,int b,T x,int k,int l,int r){
			if(r<=a || b<=l) return;
			if(a<=l&&r<=b){data[k]=x,lazy[k]=true;return;}
			if(lazy[k]) lazy_evaluate(k);
			update(a,b,x,k*2+1,l,(l+r)/2);
			update(a,b,x,k*2+2,(l+r)/2,r);
			data[k]=min(data[k*2+1],data[k*2+2]);
		}

		T query(int a,int b,int k,int l,int r){
			if(r<=a||b<=l) return out_of_range;
			if(lazy[k]) return data[k];
			if(a<=l&&r<=b) return data[k];
			T vl = query(a,b,k*2+1,l,(l+r)/2);
			T vr = query(a,b,k*2+2,(l+r)/2,r);
			return min(vl,vr);
		}

	private:
		vector<T> data;
		vector<bool> lazy;
		const T out_of_range;

		inline void lazy_evaluate(int k){
			data[k*2+1]=data[k];lazy[k*2+1]=true;
			data[k*2+2]=data[k];lazy[k*2+2]=true;
			lazy[k]=false;
		}
};

int main(void){
	int N,Q;
	cin >>  N >> Q;
	SegmentTree<int> rmq(N,INT_MAX);

	for(int i=0;i<Q;i++){
		int type;
		cin >> type;
		if(type){
			int s,t;
			cin >> s >> t;
			cout << rmq.query(s,t+1,0,0,rmq.n) << endl;
		}else{
			int a,x;
			cin >> a >> x;
			rmq.update(a,a+1,x,0,0,rmq.n);
		}
	}
	return 0;
}

Measured memory_bytes: 2252
def is_good_grid():
    for r in range(n):
        for c in range(r):
            if t[r][c] != t[c][r]:
                return False
    return True


n = int(input())
s = tuple(input() for _ in range(n))

# (0,0)==(1,1)==...==(n-1,n-1)
# colのオフセットだけ変化させる
# それぞれのループで、n個の状態(0,k)==(1,k+1)==...を扱う

ans = 0
for k in range(n):
    t = [[''] * n for _ in range(n)]
    for r in range(n):
        for c in range(n):
            t[r][c] = s[r][(c + k) % n]
    if is_good_grid():
        ans += n
print(ans)


Measured memory_bytes: 138152
#include <iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;


int main() {
	int N,L,sum=0,max=0;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> L;
		sum += L;
		if (max < L)max = L;
	}
	if (sum > 2 * max)cout << "Yes" << endl;
	else cout << "No" << endl; 
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>

using namespace std;

int n;

bool pa(bool a[]){
	int b = 0;
	for(int i = 1; i <= 2*n; i++){
		b += a[i];
	}
	return b>0?false:true;
}

int main(void){
	
	while(scanf("%d", &n) && n != 0) {
		bool flg[256];
		bool taro[256];
		bool hana[256];
		int x;
		int field=-1;
		
		fill(flg,flg+256,false);
		fill(taro,taro+256,false);
		fill(hana,hana+256,false);
		
		
		
		for(int i = 0; i < n; i++){
			scanf("%d", &x);
			taro[x] = true;
			flg[x] = true;
		}
		for(int i = 1; i <= 2*n; i++){
			if(!flg[i])hana[i] = true;
		}
		
		int turn = -1;
		while(1){
			
			if(field == -1){
				if(turn == -1){
					for(int i = 1; i <= 2*n; i++){
						if(taro[i]){
							field = i;
							taro[i] = false;
							break;
						}
					}
				}else{
					for(int i = 1; i <= 2*n; i++){
						if(hana[i]){
							field = i;
							hana[i] = false;
							break;
						}
					}
				}
			}else{
				if(turn == -1){
					for(int i = 1; i <= 2*n; i++){
						if(taro[i] && i > field){
							field = i;
							taro[i] = false;
							break;
						}
						if(i == 2*n)field = -1;
					}
				}else {
					for(int i = 1; i <= 2*n; i++){
						if(hana[i] && i > field){
							field = i;
							hana[i] = false;
							break;
						}
						if(i == 2*n)field = -1;
					}
				}
			}
			if(pa(taro))break;
			if(pa(hana))break;
			turn *=-1;
		}
		
		int ts = 0;
		int hs = 0;
		
		for(int i = 1; i <= 2*n; i++)hs+=taro[i];
		for(int i = 1; i <= 2*n; i++)ts+=hana[i];
		
		printf("%d\n%d\n",ts,hs);
		}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()


//library mod int
template <int mod>
struct modint{
    ll x;

    //constructor
    modint(ll x=0): x((x%mod+mod)%mod){}

    //unary operator
    modint operator-() const { return modint(mod-x);}
    modint inv() const { return this->pow(mod-2);}
    
    //compound assignment
    modint& operator+=(const modint& a){
        if((x+=a.x)>=mod) x-=mod;
        return *this;
    }
    modint& operator-=(const modint& a){
        if((x-=a.x)<0) x+=mod;
        return *this;
    }
    modint& operator*=(const modint& a){
        (x*=a.x)%=mod;
        return *this;
    }
    modint& operator/=(const modint& a){
        return *this *= a.inv();
    }

    //arithmetic
    // なぜmodintの後ろに＆を書いたり書かなかったりしてるかの理解ができていない
    //おそらく＆をつけるとポインタで参照しているのでもとの値を書き換えることができる
    //＆をつけないとコピーを作ってからそれに対して計算するので、もとの値は変更されない
    modint operator-(const modint& a) const {return modint (*this) -= a ; }
    modint operator+(const modint& a) const {return modint (*this) += a ; }
    modint operator*(const modint& a) const {return modint (*this) *= a ; }
    modint operator/(const modint& a) const {return modint (*this) /= a ; }
    //n should not be smaller than 0.
    modint pow(ll n) const{
        auto x=modint(1);
        auto m=*this;
        while(n>0){
            if(n&1) x*=m;
            n>>=1;
            m*=m;
        }
        return x;
    }

    //compare
    bool operator==(const modint& a) const {return x==a.x ; }
    bool operator!=(const modint& a) const {return x!=a.x ; }

    //I/O
    friend istream& operator>>(istream& is, modint& a ) noexcept {return is >> a.x ; }
    friend ostream& operator<<(ostream& os, const modint& a ) noexcept {return os << a.x ; }
};

//modの調整
constexpr int mod = 1e9 + 7;
using mint = modint<mod>;

//////////////////////////////////////////////////////////////////////
//combination
vector<mint> mintcombvector(3e6);
int startmintcomb(){
    mintcombvector[0]=0;
    mintcombvector[1]=1;
    rep(i,3e6-5){
        mintcombvector[i+2]=mintcombvector[i+1]*(i+2);
    }
    return 0;
}
mint comb(mint a, mint b){
    if(a.x<b.x || a.x<=0 || b.x<0) return mint(0);
    if(b.x==0) return mint(1);
    if(a==b) return mint(1);
    return mintcombvector[a.x]*(mintcombvector[b.x].inv())*(mintcombvector[a.x-b.x].inv());
}
//combinationを使いたいときは　startmintcomb(); を始めに打つこと

int main(){
    startmintcomb();
    int x,y;
    cin>>x>>y;
    if((x+y)%3!=0){
        cout<<0<<endl;
        return 0;
    }
    int z=(x+y)/3;
    mint a=x-z, b=y-z;
    cout<<comb((a+b),b)<<endl;
    return 0;
}

Measured memory_bytes: 23680
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll ceil1(ll n,ll m){
    if(n%m==0){return n/m;}
    return n/m +1;}


void solve()
{
	ll a,b,c;
	cin>>a>>b>>c;
	if(a==b && a!=c)
		cout<<"Yes";
	else if(b==c && c!=a)
		cout<<"Yes";
	else if(a==c && b!=c)
		cout<<"Yes";
	else
		cout<<"No";
	
}

int main()
{
	fast;
	ll q=1;
	// cin>>q;
	while(q--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace AtCoder {
    class Program {
        static void Main() {
            int[] args = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] a = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            Console.WriteLine(Math.Max(args[0] - a.Sum(), -1));
        }
    }
}

Measured memory_bytes: 29376
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//INSERT ABOVE HERE
signed main(){
  string s;
  cin>>s;
  string t(s);
  t.erase(unique(t.begin(),t.end()),t.end());
  if(t.size()==1u){
    cout<<1<<endl;
    return 0;
  }

  Int n=s.size(),m=0;
  for(Int i=0;i<n;i++) m+=s[i]-'a';
  m%=3;
  if(n<=3){
    set<string> ans({s});
    queue<string> q({s});
    while(!q.empty()){
      s=q.front();q.pop();
      for(Int i=1;i<n;i++){
	if(s[i-1]==s[i]) continue;
	char c='a'+(s[i-1]-'a'+s[i]-'a')*2%3;
	string t(s);
	t[i-1]=t[i]=c;
	if(!ans.count(t)){
	  ans.emplace(t);
	  q.emplace(t);
	}
      }
    }
    cout<<ans.size()<<endl;
    return 0;
  }
  
  const Int MOD = 998244353;
  auto add=[&](Int &a,Int b){a+=b;if(a>=MOD)a-=MOD;};
  
  auto dp=make_v<Int>(2,3,4,n+1);
  fill_v(dp,0);
  dp[0][0][3][0]=1;
  for(Int i=0;i<n;i++)
    for(Int f=0;f<2;f++)
      for(Int j=0;j<3;j++)
	for(Int k=0;k<4;k++)
	  for(Int l=0;l<3;l++)
	    add(dp[f|(k==l)][(j+l)%3][l][i+1],dp[f][j][k][i]);

  Int ans=0;
  for(Int j=0;j<3;j++) add(ans,dp[1][m][j][n]);
  if(s.size()==t.size()) add(ans,1);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 56952
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<iomanip>

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

#define debug(x) cout<<(#x)<<"="<<(x)<<", ";
#define debug1(x) debug(x) cout<<'\n';
#define debug2(x1, x2) debug(x1) debug(x2) cout<<'\n';
#define debug3(x1, x2, x3) debug(x1) debug(x2) debug(x3) cout<<'\n';
#define debug4(x1, x2, x3, x4) debug(x1) debug(x2) debug(x3) debug(x4) cout<<'\n';
#define debug5(x1, x2, x3, x4, x5) debug(x1) debug(x2) debug(x3) debug(x4) debug(x5) cout<<'\n';

#define fcout cout<<fixed<<setprecision(15)
#define repp(i,j,k) for(int i=j; i<k; ++i)
#define rep(i,j) repp(i,0,j)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define all(x) (x).begin(), (x).end()
#define sort(x) sort(x.begin(), x.end())
#define lb(x,val) lower_bound(x.begin(), x.end(), val)
#define ub(x,val) upper_bound(x.begin(), x.end(), val)
#define pb(x) emplace_back(x);

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef tuple<int, int, lli> tiil;

//const lli M=998244353ll;
const lli M=1000000007ll;
const double D=1.0;

int main(){
	fast_io
	int a,b; cin>>a>>b;
	if(a<=8 and b<=8) cout<<"Yay!";
	else cout<<":(";
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b;cin>>a>>b;
  if(a<=b)cout<<a<<endl;
  else cout<<a-1<<endl;
}

Measured memory_bytes: 256
# https://beta.atcoder.jp/contests/abc109/tasks/abc109_b


def solve():
    n = int(input())

    words = []
    words.append(input())

    for _ in range(n-1):
        word = input()
        # duplicated
        if word in words:
            print('No')
            exit()
        else:
            prev = words[-1]
            # print('prev, word', prev, word)
            if prev[-1] == word[0]:
                words.append(word)
                pass
            else:
                # not matches
                print('No')
                exit()
    else:
        print('Yes')


if __name__ == '__main__':
    solve()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define mod 1000000007 //10^9+7
#define INF 1000000000000 //10^12
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
int n;
int d[400000];
int m;
int t[400000];
bool ans=true;
signed main(){
    cin>>n;
    rep(i,n)cin>>d[i];
    cin>>m;
    rep(i,m)cin>>t[i];
    sort(d,d+n);
    sort(t,t+m);
    int cnt=0;
    rep(i,n){
        if(cnt==m)break;
        if(d[i]==t[cnt])cnt++;
    }
    if(cnt<m)ans=false;
    if(ans)puts("YES");
    else puts("NO");
    return 0;
}


Measured memory_bytes: 5888
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_STR_MAX		100005									// 最大文字列長

// 内部変数
static FILE *szpFpI;											// 入力
static char sc1StrA[D_STR_MAX], sc1StrB[D_STR_MAX];				// 文字列
static int siALen, siBLen;										// 文字列長

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 最大公約数 - 取得
long long
fGetGcd(
	long long plVal1			// <I> 値１
	, long long plVal2			// <I> 値２
)
{
	long long llWork;

	// ユークリッドの互除法
	if (plVal1 < plVal2) {
		llWork = plVal1;
		plVal1 = plVal2;
		plVal2 = llWork;
	}
	while (plVal2 > 0) {
		llWork = plVal1 % plVal2;
		plVal1 = plVal2;
		plVal2 = llWork;
	}

	return plVal1;
}

// 最小公倍数 - 取得
long long
fGetLcm(
	long long plVal1			// <I> 値１
	, long long plVal2			// <I> 値２
)
{
	// 最大公約数 - 取得
	long long llGcd = fGetGcd(plVal1, plVal2);

	// 約数
	long long llVal1 = plVal1 / llGcd;
	long long llVal2 = plVal2 / llGcd;

	return llVal1 * llVal2 * llGcd;
}

// 実行メイン
long long
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 文字列長 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &siALen, &siBLen);

	// 文字列 - 取得
	fgets(sc1StrA, sizeof(sc1StrA), szpFpI);
	fgets(sc1StrB, sizeof(sc1StrB), szpFpI);

	// 最大公約数 - 取得
	int liGcd = (int)fGetGcd(siALen, siBLen);

	// 比較間隔
	int liSpA = siALen / liGcd;
	int liSpB = siBLen / liGcd;

	// 比較
	for (i = 0; i < liGcd; i++) {
		if (sc1StrA[liSpA * i] != sc1StrB[liSpB * i]) {
			return -1;
		}
	}

	// 最小公倍数 - 取得
	return fGetLcm(siALen, siBLen);
}

// １回実行
int
fOne(
)
{
	long long llRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	llRet = fMain();

	// １行出力
	sprintf(lc1Buf, "%lld\n", llRet);
	fOutLine(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using Int = long long;
using namespace std;
template<typename T>
vector<T> factorize(T n) {
    vector<T> v;
    T i = 2;
    while (i * i <= n) {
        if (n % i == 0) {
            v.push_back(i);
            n /= i;
        } else {
            i++;
        }
    }
    if(n != 1)v.push_back(n);
    return v;
};
template<typename T>
set<T> primeFactors( const vector<T>& vec){
    /* vecotor must be factolized*/
    set<T> res;
    for(auto e : vec){
        res.insert(e);
    }
    return res;
}
int main(){
    Int N ;cin >> N;
    auto pv = factorize(N);
    map<Int,int>mp;
    for(auto p : pv) mp[p]++;
    map<Int,int>cnt;
    int ans = 0;
    auto pset = primeFactors(pv);
    for(auto p : pset){
        while(mp[p] >= cnt[p] + 1){
            ans += 1;
            cnt[p] += 1; mp[p] -= cnt[p];
        }
    }
    cout << ans << endl;
}





Measured memory_bytes: 3628
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
using lint = long long;

int main() {

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

	int N, Q;
	cin >> N >> Q;

	string S;
	cin >> S;

	vector<pair<char, char>> spell(Q);
	for (int i = 0; i < Q; i++) cin >> spell[i].first >> spell[i].second;

	auto dead = [&] (int idx, int key) {

		bool res = false;
		for (int i = 0; i < Q; i++) {
			if (spell[i].first == S[idx]) idx += spell[i].second == 'L' ? -1 : 1;
			if (idx < 0 || idx >= S.size()) break;
		}

		return idx < key;
	};

	auto biSearch = [&](auto f, int key) {
		int left = -1;
		int right = (int)S.size();

		while (right - left > 1) {
			int mid = left + (right - left) / 2;

			if (!f(mid, key)) right = mid;
			else left = mid;
		}

		return right;
	};

	int L = biSearch(dead, 0);
	int R = biSearch(dead, S.size());
	if (L < R) cout << R - L << "\n";
	else cout << 0 << "\n";

	return 0;
}


Measured memory_bytes: 976