akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vec> mat;
void add(int &a,int b) {a+=b; if(a>=MOD) a-=MOD;}
int n;
ll k;
mat mul(mat A,mat B)
{
    mat C(A.size(),vec(B[0].size()));
    for(int i=0;i<(int)A.size();i++)
        for(int k=0;k<(int)B.size();k++)
            for(int j=0;j<(int)B[0].size();j++)
                C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
    return C;
}
mat _pow(mat A,ll n)
{
    mat B(A.size(),vec(A.size()));
    for(int i=0;i<(int)A.size();i++)
        B[i][i]=1;
    while(n>0)
    {
        if(n&1) B=mul(B,A);
        A=mul(A,A);
        n>>=1;
    }
    return B;
}
int main()
{
    scanf("%d%lld",&n,&k);
    mat A(n,vec(n));
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&A[i][j]);
    A=_pow(A,k);
    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            add(ans,A[i][j]);
    printf("%d\n",ans);
    return 0;
}



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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)
template<class T, class U> void umin(T& x, const U& y){ x = min(x, (T)y);}
template<class T, class U> void umax(T& x, const U& y){ x = max(x, (T)y);}
template<class T, class U> void init(vector<T> &v, U x, size_t n) { v=vector<T>(n, x); }
template<class T, class U> void init(vector<T> &v, U x, size_t n, size_t m...) { v=vector<T>(n); for(auto& a : v) init(a, x, m);}

int m;
struct ttt{
    int l, r, i;
    bool operator < (const ttt& o){
        if (l / m != o.l / m) return l / m < o.l / m;
        return r > o.r;
    }
};

//#define TEST 1
int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);

    int n, q;
    cin >> n >> q;

    vector<int> c(n);
#if TEST
    FOR(i, n) c[i] = rand() % 100;
#else
    FOR(i, n) cin >> c[i];
#endif

    vector<ttt> v;
    FOR(i, q){
        int l, r;
#if TEST
        l = 1 + rand() % n;
        r = l + rand() % n;
        if (r < l) swap(l, r);
#else
        cin >> l >> r;
#endif
        l--; r--;
        v.push_back({l, r, i});
    }
    m = sqrt(n);
    sort(v.begin(), v.end());

    int cnt = 0;
    vector<int> H(n+1);
    for(int i = v[0].l; i <= v[0].r; i++) {
        H[c[i]]++;
        cnt += H[c[i]] == 1;
    }

    vector<int> sol(q);
    sol[v[0].i] = cnt;
    int l = v[0].l, r = v[0].r;
    FOR1(i, q-1){
        while(r > v[i].r){
            H[c[r]]--; if (H[c[r]] == 0) cnt--;
            r--;
        }
        while(r < v[i].r){
            r++;
            H[c[r]]++; if (H[c[r]] == 1) cnt++;
        }
        while(l < v[i].l){
            H[c[l]]--; if (H[c[l]] == 0) cnt--;
            l++;
        }
        while(l > v[i].l){
            l--;
            H[c[l]]++; if (H[c[l]] == 1) cnt++;
        }
        sol[v[i].i] = cnt;
    }
    FOR(i, q)
        cout << sol[i] << '\n';
    cout << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

Measured memory_bytes: 15452
from collections import defaultdict
nametag = defaultdict(lambda: 0)
N = int(input())
for _ in range(N):
    s = input()
    if s[0] == 'M':
        nametag['M'] += 1
    if s[0] == 'A':
        nametag['A'] += 1
    if s[0] == 'R':
        nametag['R'] += 1
    if s[0] == 'C':
        nametag['C'] += 1
    if s[0] == 'H':
        nametag['H'] += 1
ans = 0
march = list(nametag.keys())
for i in march:
    for j in march:
        for k in march:
            if i == k or j == k or i == j:
                continue
            ans += nametag[i]*nametag[j]*nametag[k]
print(ans//6)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout <<(#x)<<" is "<<(x)<<endl
#define debug cout <<"hi"<<endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int MOD=1e9+7;
const int INF32=1<<30;
const ll INF64=1LL<<60;

int main(){
  int n; cin >>n;
  ll sum=0,sq=0;
  for(int i=0; i<n; i++){
    ll x; cin >>x;
    sum=(sum+x)%MOD;
    sq=(sq+(x*x)%MOD)%MOD;
  }
  ll ans=(sum*sum-sq)%MOD;
  if(ans%2) ans+=MOD;
  cout <<ans/2; 
return 0;}

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

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

	int grid[10][10] = { 0 };
	for (int i = 1; i <= N; i++) {
		string s = to_string(i);
		int a = s[0] - '0';
		int b = s[s.size() - 1] - '0';
		grid[a][b]++;
	}

	int ans = 0;
	for (int i = 1; i < 10; i++) {
		for (int j = 1; j < 10; j++) {
			ans += grid[i][j] * grid[j][i];
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
int ta[30][30],tta[30][30];;
#define P pair<int,int>
int w,h,sx,sy,gx,gy;

struct jou{
	int y;
	int x;
	int now;
	vector<P>del;
	};
	
	int fx[]={1,0,-1,0},fy[]={0,1,0,-1};
int main(){
	
while(cin>>w>>h,h||w){
	for(int i=0;i<h;i++)for(int j=0;j<w;j++){
	cin>>ta[i][j];
	if(ta[i][j]==2)sx=j,sy=i;
	if(ta[i][j]==3)gx=j,gy=i;
	}
	bool f=0;
	queue<jou>bfs;
	jou tmp;
	vector<P>aa(0);
	tmp.del=aa;
	tmp.y=sy,tmp.x=sx,tmp.now=0;
	bfs.push(tmp);
	
	
	while(!bfs.empty()){
		jou next=bfs.front();
		bfs.pop();
		int ny=next.y,nx=next.x;
		int nny=ny,nnx=nx;
		vector<P>de=next.del;
		if(next.now>=10)break;
		
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)tta[i][j]=ta[i][j];
		
		for(int i=0;i<(int)de.size();i++){
			int dey=de[i].first,dex=de[i].second;
			if(ta[dey][dex]==1)tta[dey][dex]=0;
		}
		//cout<<nx<<" "<<ny<<endl;
		//cout<<next.now<<endl;
		//cout<<de.size()<<" ";for(int i=0;i<h;i++)for(int j=0;j<w;j++)cout<<tta[i][j]<<" ";cout<<endl;
		for(int i=0;i<4;i++){
			ny=nny,nx=nnx;
			//if(nx+fx[i]<0||nx+fx[i]>=w||ny+fy[i]<0||ny+fy[i]>=h)continue;
			while(true){
				nx+=fx[i],ny+=fy[i];
				if(nx<0||nx>=w||ny<0||ny>=h || (nx==nnx+fx[i]&&ny==nny+fy[i])&&(tta[ny][nx]==1))break;
				
				if(tta[ny][nx]==1){
					jou nnext;
					nnext.x=nx-fx[i],nnext.y=ny-fy[i];
					nnext.now=next.now+1;
					vector<P>temp(0);
					for(int k=0;k<(int)de.size();k++)temp.push_back(de[k]);
					temp.push_back(make_pair(ny,nx));
					nnext.del=temp;
					bfs.push(nnext);
					break;
				}
				if(ny==gy&&nx==gx){
					cout<<next.now+1<<endl;
					f=1;
					goto end;
				}

			}
		
		}
	}
	end:;
	if(f==0)cout<<"-1"<<endl;
}
	return 0;
}






/*#include<iostream>
using namespace std;
int main(){
	int n,r=0,l=0,a,b;
	char c;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a>>c>>b;
		if(c==')')r+=b;
		else l+=b;
		if(l==r)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}

	return 0;
}*/

Measured memory_bytes: 11384
s=input()*2;n=len(s)/2
def f(i,t,k):
 if k>n-i:return 0
 a=max(t,int(s[i]));i+=1;
 if t:return f(i,9,k)+a*f(i,9,k-1)if k else 1
 else:return(f(i,9,k)+(a-1)*f(i,9,k-1)+f(i,0,k-1)if k else 1)if a else f(i,0,k)
print(f(0,0,int(input())))

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
#define string(n) to_string(n)
#define int(w) stoi(w)
#define len(l) l.size()
#define append(l,i) l.push_back(i)
int main() {
    int n,k,n1;
    map<int,int> d;
    cin>>n>>k;
    vector<int> l;
    rep(i,n){
        cin>>n1;
        if (d.count(n1)){
            d[n1]+=1;
        }
        else{
            d[n1]=1;
        }
    }
    vector<int> ll;
    for (pair<int,int> p:d){
        append(ll,p.second);

    }
    sort(all(ll));
    int ans=0;
    rep(i,len(ll)-k){
        ans+=ll.at(i);

    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 10748
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,K = map(int,input().split())

S = np.array(list(input()), dtype='U1')

x = np.count_nonzero(S[1:] == S[:-1])

x += 2*K
x = min(x, N-1)
print(x)


Measured memory_bytes: 13780
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N, K;
    cin >> N >> K;
    vector<double> p(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];
        p[i] = (1+p[i])/2;
    }
    double ans = 0;
    for (int i = 0; i < K; i++) {
        ans += p[i];
    }
    double r = ans;
    for (int i = K; i < N; i++) {
        r += p[i];
        r -= p[i-K];
        ans = max(ans, r);
    }
    printf("%.10lf\n", ans);
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

#define EPS 1e-9

using namespace std;

int n;
double W;

bool pred(pair<int,int> a, pair<int,int> b){
    return a.first * b.second > a.second * b.first;
}

int main(){
    cin >> n >> W;
    vector<pair<int,int> > vp;
    double ret=0;
    double w,v;
    for(int i=0;i<n;i++){
        cin >> w >> v;
        if(w <= 0 && v >= 0){
            W -= w;
            ret += v;
        }else if(w >=0 && v <= 0){
            //do nothing
        }else if(v < 0 && w < 0){
            W -= w;
            ret += v;
            vp.push_back(make_pair(-v,-w));
        }else{
            vp.push_back(make_pair(v,w));
        }
    }
    sort(vp.begin(), vp.end(), pred);
    for(int i=0;i<vp.size();i++){
        double tmp = min(1.0, W/vp[i].second);
        ret += vp[i].first * tmp;
        W -= tmp * vp[i].second;
        if(W < EPS) break;
    }
    printf("%.9f\n", ret);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(),(a).end()

using namespace std;

int main(int argc, char const *argv[]) {
    string S;
    int num=2;
    std::cin >> S;
    while (true) {
        if(S.substr(0,(S.size()-num)/2)==S.substr((S.size()-num)/2,(S.size()-num)/2)){
            std::cout << S.size()-num << '\n';
            return 0;
        }
        num+=2;
    }
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	ll n,a,b,ans;
	cin >> n >> a >> b;
	ans = (n/(a+b))*a+min(n%(a+b),a);
	cout << ans << endl;
	return 0;
}


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


int main(){
  int n, m;
  cin >> n >> m;
  ll a[n], b[n], c[m], d[m];
  rep(i, n) {
    cin >> a[i] >> b[i];
   }
  rep(i, m){
    cin >> c[i] >> d[i];
  }
  ll ans[n];

  rep(i, n){
    ll kyori = 4 * pow(10, 8) + 1;
    int num = 0;
    rep(j, m){
      ll man = abs(a[i]-c[j]) + abs(b[i]-d[j]);
      if (man < kyori){
        kyori = man;
        num = j+1;
      }
    }
    ans[i] = num;
  } 
  rep(i, n) cout << ans[i] << endl;
}

Measured memory_bytes: 3684
h, w = map(int, input().split())
s = []
for i in range(h):
    s += input().split()

idx = s.index("snuke")
if w != 1:
    col = (idx+1)%w
    alpha = chr(col+64)
else:
    alpha = "A"

row = idx//w+1
ans = alpha + str(row)
print(ans)



Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int test=in.nextInt();
        ArrayList<Integer> ar=new ArrayList<>();
        for (int i = 0; i < test; i++) {
            int a,b = 0;
            a=in.nextInt();
            if(a!=2){
              b=in.nextInt();  
            }
            if(a==0){
                ar.add(b);
            }
            else if(a==2){
                ar.remove((ar.size()-1));
            }
            else{
                System.out.println(ar.get(b));
            }
        }
    }
}


Measured memory_bytes: 141288
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#define SE -1e10
#define EE 2e10
using namespace std;
int main()
{
  ios::sync_with_stdio(false);
  int a,b,q;
  cin>>a>>b>>q;
  vector<long>s(a+2),t(b+2);
  for(int i=0;i<a;i++)
  {
    cin>>s[i+1];
  }
  for(int i=0;i<b;i++)
  {
    cin>>t[i+1];
  }
  s[0]=SE;t[0]=SE;
  s[a+1]=EE;
  t[b+1]=EE;
  long x;
  long res;
  for(int i=0;i<q;i++)
  {
    cin>>x;
    auto si=lower_bound(s.begin(), s.end(), x);
    auto ti=lower_bound(t.begin(), t.end(), x);
    res=0;
    res=min(x-min(*(si-1),*(ti-1)),max(*si,*ti)-x);
    res=min(res,*ti-*(si-1)+min(*ti-x,x-*(si-1)));
    res=min(res,*si-*(ti-1)+min(*si-x,x-*(ti-1)));

    cout<<res<<"\n";




  }

  return 0;

}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
vector<pair<int,int>> E[101010];

int pat[1<<15];
vector<int> V[16];
int dp[1<<16];


int dfs(int cur,int pre) {
	int x=0;
	
	FORR(e,E[cur]) if(e.first!=pre) {
		int y=dfs(e.first,cur);
		e.second^=y;
		FORR(e2,E[e.first]) if(e2.first==cur) e2.second=e.second;
		x^=y^e.second;
	}
	return x;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>j;
		E[x].push_back({y,j});
		E[y].push_back({x,j});
	}
	dfs(0,-1);
	
	
	FOR(i,1<<16) dp[i]=1010;
	int mask=0;
	for(mask=0;mask<1<<15;mask++) {
		dp[mask]=__builtin_popcount(mask);
		FOR(y,15) if(mask&(1<<y)) {
			dp[mask]=min(dp[mask],dp[mask^(1<<y)]+1);
			FOR(x,y) if(mask&(1<<x)) {
				j=(x+1)^(y+1);
				if(mask&(1<<(j-1))) {
					dp[mask]=min(dp[mask],dp[mask^(1<<y)^(1<<x)^(1<<(j-1))]+2);
				}
				else {
					dp[mask]=min(dp[mask],dp[mask^(1<<y)^(1<<x)^(1<<(j-1))]+1);
				}
			}
		}
	}
	
	int cnt[16]={};
	FOR(i,N) FORR(e,E[i]) if(e.first<i) cnt[e.second]++;
	int tot=0;
	mask=0;
	for(i=1;i<=15;i++) {
		tot+=cnt[i]/2;
		if(cnt[i]%2) mask |= 1<<(i-1);
	}
	cout<<tot+dp[mask]<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 10496
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;

template<class T> inline bool chmin(T& a,T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if (a < b) {a = b; return true;} return false;}

const ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

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

ll lcm(ll x, ll y){
  return (x * y) / gcd(x, y);
}

int main(){
  int N, X; cin >> N >> X;
  vector<ll> x(N); rep(i, N) cin >> x[i];

  vector<ll> que(N);
  rep(i, N) que[i] = abs(X - x[i]);
  int ans = que[0];
  for (int i = 1; i < N; ++i){
    ans = gcd(ans, que[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<string.h>

char c[6600];


int main(){
  int i,j,k,hoge,head,tail,size,v,keta,ci,isEOF,isL;
  char code[15],form[6],b;
  size=head=tail=ci=0;
  keta=1;
  c[23]=' ';
  c[364]='\'';
  c[688]=',';;
  c[5495]='-';
  c[610]='.';
  c[607]='?';
  c[635]='A';
  c[4118]='B';
  c[70]='C';
  c[67]='D';
  c[17]='E';
  c[205]='F';
  c[6305]='G';
  c[367]='H';
  c[79]='I';
  c[3389]='J';
  c[52]='K';
  c[130]='L';
  c[5576]='M';
  c[4361]='N';
  c[211]='O';
  c[26]='P';
  c[6548]='Q';
  c[41]='R';
  c[157]='S';
  c[238]='T';
  c[3632]='U';
  c[5819]='V';
  c[445]='W';
  c[4037]='X';
  c[6224]='Y';
  c[3308]='Z';
  isEOF=0;
  isL=0;
  do{
    for(i=size;i<8;i+=5){
      if((b=getchar())!=EOF){
	if(isalpha(b)){
	  for(j=0,hoge=1,v=0;j<5;j++,hoge*=10)
	    v+=((((int)b-(int)'A')>>j)&1)*hoge;
	  sprintf(form,"%05d",v);
	}else if(b==' '){
	  strcpy(form,"11010");
	}else if(b=='.'){
	  strcpy(form,"11011");
	}else if(b==','){
	  strcpy(form,"11100");
	}else if(b=='-'){
	  strcpy(form,"11101");
	}else if(b=='\''){
	  strcpy(form,"11110");
	}else if(b=='?'){
	  strcpy(form,"11111");
	}else if(b=='\n'){
	  isL=1;
	  break;;
	}
	for(j=tail,k=0;form[k];k++,j=(j+1)%15){
	  code[j]=form[k];
	}
	size+=5;
	tail=(tail+5)%15;
      }else{
	isEOF=1;
	break;
      }
    }/*
    printf("head=%d tail=%d\n",head,tail);
    for(i=head;i!=tail;i=(i+1)%15)
      printf("%c",code[i]);
    printf("\n");
     */
    for(i=head;i!=tail;i=(i+1)%15){
      ci+=((int)code[i]-(int)'0'+1)*keta;
      keta*=3;
      if(c[ci]){
	printf("%c",c[ci]);
	keta=1;
	ci=0;
	head=(i+1)%15;
	size=head<=tail?tail-head:15-head+tail;
      }
    }
    ci=0;
    keta=1;
    if(isL){
      printf("\n");
      isL=0;
      size=head=tail=ci=0;
    }
    if(isEOF) break;
  }while(1);
  return 0;
}

Measured memory_bytes: 0
using System;
using System.Linq;
using System.Collections.Generic;

// https://atcoder.jp/contests/abc079/tasks/abc079_a
namespace AtCoder
{
    public class GoodInteger
    {
        static void Main(string[] args)
        {
            var output = Console.ReadLine();
            var isGoodNumber = false;
            var prev = -1;
            var matchCount = 0;
            var value = 0;
            var log = "";

            for (var i = 0; i < output.Length; ++i, prev = value)
            {
                value = int.Parse(output[i].ToString());
                if (matchCount == 0)
                {
                    matchCount += 1;
                    log += $"[{i}] match count:{matchCount}\n";
                    continue;
                }

                log += $"[{i}] value:{value} prevValue:{prev} isMatch:{(value == prev)} NextValue:{(value == prev ? matchCount + 1 : 1)}\n";
                matchCount = value == prev ? matchCount + 1 : 1;
                if (matchCount >= 3)
                {
                    isGoodNumber = true;
                }
            }
            Console.WriteLine(isGoodNumber ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <numeric>
#include <iomanip>
#include <climits>
#include <cstring>
#include <cmath>

using namespace std;

#define int long long
#define rep(i, n) for (int i=0;i<(int)(n);++i)
#define rep1(i, n) for (int i=1;i<=(int)(n);++i)
#define rrep(i, n) for (int i=(int)(n)-1;i>=0;--i)
#define rrep1(i, n) for (int i=(int)(n);i>=1;--i)
#define range(i, l, r) for (int i=l;i<(int)(r);++i)
#define rrange(i, l, r) for (int i=(int)(r)-1;i>=l;--i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;
using vpii=vector<pii>;
using ll=long long;

constexpr int TEN(int n){return n==0?1:10*TEN(n-1);}
bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
int read(){int a;scanf("%lld",&a);return a;}

const double PI = acos(-1);

int A,B,H,M;

signed main()
{
	cin>>A>>B>>H>>M;

	double hrad = 2.0*PI/12 * H + 2.0*PI/12/60*M, mrad = 2.0*PI/60*M;

	double hx = sin(hrad)*A, hy = cos(hrad)*A;
	double mx = sin(mrad)*B, my = cos(mrad)*B;

	printf("%.10f\n", sqrt((hx - mx)*(hx - mx)+(hy - my)*(hy - my)));
}




Measured memory_bytes: 4064
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool eq(const string &s){
  int n = s.length();
  if(n%2) return false;
  for(int i=0;i<n/2;++i){
    if(s[i]!=s[i+n/2]) return false;
  }
  return true;
}

int main(){
  string str;
  cin >> str;
  
  int num = 0;
  while(num==0||!eq(str)){
    str.pop_back();
    num++;
  }
  cout << str.length() << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 100010;

int main(){
        int r0, w0, c, r;
        while(scanf("%d%d%d%d", &r0, &w0, &c, &r) && r0){
                if(c*w0<=r0) printf("%d\n", 0);
                else printf("%d\n", (c*w0-r0-1)/r+1);
        }
}


Measured memory_bytes: 3236
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 5010, mod = 1e9+7;
int n,cnt,cir,a[N],f[N][N];

int fa[N],siz[N],flag[N];
inline int Find(int x){
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}

inline int power(int a,int b){
	int ret=1;
	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) ret=1ll*ret*a%mod;
	return ret;
}

int main(){
	n=read();
	For(i,1,n) fa[i]=i;
	For(i,1,n){
		a[i]=read(),cnt+=(a[i]==-1);
		if (a[i]==-1) continue;
		int x=Find(i),y=Find(a[i]);
		if (x==y) ++cir,flag[x]=1;
			else fa[x]=y,flag[y]|=flag[x];
	}
	For(i,1,n) siz[Find(i)]++;
	vector<int>v;
	For(i,1,n) if (Find(i)==i&&!flag[i]) v.pb(siz[i]);
	f[0][0]=1;
	For(i,1,siz(v)){
		f[i][0]=1ll*f[i-1][0]*(n-1)%mod;
		For(j,1,i) f[i][j]=(1ll*f[i-1][j]*(n-1)+1ll*f[i-1][j-1]*(j==1?1:j-1)%mod*v[i-1])%mod; 
	}
	int ans=1ll*n*power(n-1,cnt)%mod;
	For(i,2,siz(v)) ans=(ans+mod-f[siz(v)][i])%mod;
	for (auto i:v) ans=(ans+mod-1ll*(i-1)*power(n-1,siz(v)-1)%mod)%mod;
	ans=(ans+mod-1ll*cir*power(n-1,cnt)%mod)%mod;
	printf("%d\n",ans);
}


Measured memory_bytes: 70592
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define lli long long int

using namespace std;

lli n, w[110], v[110], memo[110][100010];

lli dp(lli id, lli cap) {
	lli ret;
	if (id == n)
		return 0;
	if (memo[id][cap] != -1)
		return memo[id][cap];
	ret = dp(id + 1, cap);
	if (w[id] <= cap)
		ret = max(ret, dp(id + 1, cap - w[id]) + v[id]);
	memo[id][cap] = ret;
	return ret;
}

int main() {
	lli c, ans;
	scanf("%lld %lld", &n, &c);
	for (int i = 0; i < n; i++)
		scanf("%lld %lld", &w[i], &v[i]);
	memset(memo, -1, sizeof memo);
	ans = dp(0, c);
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 86144
fun main(args:Array<String>) {

    val (n,a,b) = readLine()!!.split(" ").map { it.toLong() }
    val pointList = readLine()!!.split(" ").map { it.toLong() }
    val ans = (1..pointList.lastIndex).map { Math.min(b, (pointList[it]-pointList[it-1])*a) }.sum()
    println(ans)
}



Measured memory_bytes: 58120
//#pragma region ALL(include define etc)
#include <iostream>   // swap(a, b)
#include <string>
#include <cmath>      // abs(絶対値) sin cos tan(角度 / 180.0 * 3.141592)
#include <vector>     // vec.push_back(a) vec.pop_back()
#include <algorithm>  // max(a, b) min(a, b) reverse() sort()
#include <functional> // sort(a, a + N, greater<型>());
#include <limits>
#include <math.h>
#include <iomanip>
#define int long long
//#define int double
//#define int unsigned long long
#define ll long long
#define double long double
using namespace std;
//#pragma endregion

signed main()
{
	// 10^18 = 1000000000000000000

	//int h1, h2, m1, m2, k;
	//int box, box1,box2;

	//int N;
	int n;
	//char n;
	//int a, b, c;
	//int m;
	//int h, w, x;
	int k;
	//int d,t,s;
	//int t;
	//string s;
	//string t;
	//int m1, m2;
	//int a, b, c, k;
	int x, y;
	int a, b, c, d;

	string s;
	string t;
	//string s[100000];
	//string c[7];
	//int a[100000];
	//int b[200000];
	//int a[2000000] = { 0 };
	//int b[2000000] = { 0 };
	//int a[20000] = { 0 };
	//int b[20000] = { 0 };
	//vector<int>a(2000000);
	//vector<int>b(2000000);

	//int aaa = 0;
	//int bbb = 0;

	int box[20000] = { 0 };
	//char box[20000];
	//int a[2000000] = { 0 };
	//int box = 0;
	//int box[7][7] = { 0 };
	//int box2;
	//int p[1111];
	//int x[2000], y[2000];
	//int l[100];


	//long double aaa;

	int count = 0;
	int count1 = 0;
	int count2 = 0;
	int count3 = 0;
	int count4 = 0;
	//int k, d;
	//int a = 0;
	int all = 0;
	//double all;
	//double a, b;
	//double h, m;
	//int a[30000] = { 0 };
	//double c, d, e;

	//double mbox, hbox;
	//double box, box2;

	bool flag = true;
	//bool flag = false;

	//string str;

	//cin >> h1 >> m1 >> h2 >> m2 >> k;
	//cin >> n;
	cin >> a >> b >> c >> d;
	//cin >> s;
	//cin >> t;
	//cin >> d >> t >> s;
	//cin >> n >> x >> t;

	/*for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}*/
	
	count1 = a * c;
	count2 = a * d;
	count3 = b * c;
	count4 = b * d;

	count = max(count1, count2);
	count = max(count, count3);
	count = max(count, count4);

	all = count;
	/*count = d / s;

	if (count <= t)
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}*/

	/*do {
		for (int i = 0; i < n; i++) {
			if (i % n == 0)
				cout << "\n";
			cout << a[i] << " ";
		}
	} while (next_permutation(a, a + n));*/

	//getline(cin, s);

	/*for (int i = 0; i < count; i++)
	{
		all += s[i] - '0';
	}*/

	//n = s.length();

	//sort(box, box + count);
	//sort(p, p + n);
	//n = n - 'Z';

	//box = n % 26;

	//for (int i = 0; i < k; i++)
	//{
	//	all += p[i];
	//}

	//all = n + (n * n) + (n * n * n);

	/*if (n > 0)
	{
		cout << "a\n";
	}
	else
	{
		cout << "A\n";
	}*/
	//n = t.length();

	/*cout << "AC x " << ac << "\n";
	cout << "WA x " << wa << "\n";
	cout << "TLE x " << tle << "\n";
	cout << "RE x " << re << "\n";*/

	//cout << x << "\n";
	cout << all << "\n";
	//cout << box << "\n";
	//cout << a << b << c << "\n";

	/*if (flag == true)
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}*/

	//cout << fixed << setprecision(111) << all;
	//return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

const pid_t pid = getpid();
// Problem Specific Parameter:

const int limit = 100000;
const ll inf = 1LL << 40;
ll dp[110][limit + 10];

int main(void){
	int n, wlimit;
	cin >> n >> wlimit;

	rep(i,n+1)rep(j,limit+1) dp[i][j] = inf;
	dp[0][0] = 0LL;

	rep(i,n){
		ll w,v;
		cin >> w >> v;
		
		rep(j,limit+1){
			if(dp[i][j] == inf) continue;
			chmin(dp[i+1][j], dp[i][j]);
			chmin(dp[i+1][j + v], dp[i][j] + w);
		}
	}

	ll ans = 0LL;
	rep(j,limit+1) if(dp[n][j] <= wlimit) ans = j;
	cout << ans << endl;
	
	return 0;
}

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

#define REP(i, n) for(decltype(n) i = 0; i < n; i++)

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

const int MOD  = (int)1e9 + 7;
const int INF  = (int)1e9 + 1;
const ll  LINF = (ll)1e18 + 1;

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

    int H, W, K;
    std::cin >> H >> W >> K;

    vector<vector<ll>> dp(H + 1, vector<ll>(W, 0));

    dp[0][0] = 1;
    for(int hi = 1; hi < H + 1; hi++) {
        REP(wi, W) {
            // bit全探索
            for(int i = 0; i < (1 << (W - 1)); i++) {
                [&]() {
                    for(int j = 0; j < W - 2; j++) {
                        if(i & (1 << j) && i & (1 << (j + 1))) {
                            return;
                        }
                    }
                    bool l = i & (1 << (wi - 1));
                    bool r = i & (1 << wi);
                    if(l) {
                        dp[hi][wi] += dp[hi - 1][wi - 1];
                    }
                    else if(r) {
                        dp[hi][wi] += dp[hi - 1][wi + 1];
                    }
                    else {
                        dp[hi][wi] += dp[hi - 1][wi];
                    }
                    dp[hi][wi] %= MOD;
                }();
            }
        }
    }

    std::cout << dp[H][K - 1] << std::endl;

    return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var k, a, b int
	fmt.Scan(&k)
	fmt.Scan(&a)
	fmt.Scan(&b)

	ok := false
	for i := a; i <= b; i++ {
		if i%k == 0 {
			fmt.Println("OK")
			ok = true
			break
		}
	}
	if !ok {
		fmt.Println("NG")
	}
}


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int W,N;
int dp [1001] [1001];

int main()
{
	int testCase = 1;
	while(scanf("%d",&W),W){
		scanf("%d",&N);
		vector<int> x(N),y(N);
		FOR(i,0,N){
			scanf("%d,%d",&x [i],&y [i]);
		}
		memset(dp,0,sizeof(dp));
		FOR(i,0,N) FOR(j,0,W + 1){
			chmax(dp [i + 1] [j],dp [i] [j]);
			if(j + y [i] <= W) chmax(dp [i + 1] [j + y [i]],dp [i] [j] + x [i]);
		}
		pair<int,int> ans(-1,-1);
		FOR(j,0,W + 1){
			if(dp [N] [j] > ans.first){
				ans.first = dp [N] [j];
				ans.second = j;
			}
		}
		printf("Case %d:\n",testCase);
		printf("%d\n",ans.first);
		printf("%d\n",ans.second);
		testCase++;
	}

	return 0;
}

Measured memory_bytes: 7060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;

  if (a + b <= 2 * c) {
    cout << a * x + b * y << endl;
  }
  else {
    int ans = 0;
    if (x < y) {
      swap(a, b);
      swap(x, y);
    }
    ans += c * 2 * y;
    x -= y;
    if (a <= 2 * c) {
      ans += a * x;
    }
    else {
      ans += c * 2 * x;
    }
    cout << ans << endl;
  }

  
  return 0;
}

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

int main(void)
{
	int N,n;
	int a_max = -1, a_min = -1;
	scanf("%d\n",&N);
	for (n=0;n<N;n++){
		int a;
		scanf("%d ",&a);
		if (a_max<0 || a>a_max)a_max=a;
		if (a_min<0 || a<a_min)a_min=a;
	}
	printf("%d\n",a_max-a_min);
	return 0;
}


Measured memory_bytes: 128
use proconio::marker::*;
use proconio::*;

fn main() {
    input! {
        n: usize,
        s: Chars,
    };

    let x = s
        .iter()
        .map(|v| v.to_digit(2).unwrap() as i64)
        .collect::<Vec<_>>();
    let pc: i64 = x.iter().sum();
    let mut ans = vec![0; n];

    for b in 0..=1 {
        let mut pc = pc;
        if b == 0 {
            pc += 1;
        } else {
            if pc <= 1 {
                continue;
            }
            pc -= 1;
        }

        let mut r0 = 0;
        for &v in &x {
            r0 = ((r0 << 1) + v).rem_euclid(pc);
        }

        let mut k = 1;
        for i in (0..x.len()).rev() {
            if x[i] == b {
                if b == 0 {
                    ans[i] = f((r0 + k).rem_euclid(pc)) + 1;
                } else {
                    ans[i] = f((r0 - k).rem_euclid(pc)) + 1;
                }
            }
            k = (k << 1).rem_euclid(pc);
        }
    }

    for v in &ans {
        println!("{}", v);
    }
}

fn f(n: i64) -> i64 {
    if n == 0 {
        return 0;
    }

    1 + f(n.rem_euclid(n.count_ones() as i64))
}


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

struct Edge{
	int s,g,d;
	Edge(int a, int b, int c) : s(a), g(b), d(c) {}
	
	bool operator<(const Edge &b){
		if(d!=b.d) return d<b.d;
		if(s!=b.s) return s<b.s;
		return g < b.g;
	}
};

struct Unionfind {
	vector< int > par;
	Unionfind(int N) : par(N,-1){
	}
	bool unite(int x, int y) {
		x = root(x), y = root(y);
		if(x == y) return 0;
		if(par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return 1;
	}
	int root(int k) {
		if(par[k] < 0) return (k);
		return (par[k] = root(par[k]));
	}
	bool same(int x, int y){
		x = root(x);
		y = root(y);
		return x==y;
	}
	int size(int k) {
		return (-par[root(k)]);
	}
};

int main() {
	
	int n,e;
	cin >> n >> e;
	vector<Edge> g;
	for(int i=0; i<e; i++){
		int s, t, w;
		cin >> s >> t >> w;
		g.push_back({s,t,w});
	}
	sort(g.begin(),g.end());
	int ans{};
	Unionfind uf(n);
	for(auto i:g){
		if(!uf.same(i.s,i.g)){
			uf.unite(i.s,i.g);
			ans += i.d;
		}
	}
	cout << ans << endl;
	
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

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

	ll n;cin >> n;
	vector<P> v(n);
	REP(i, n){
		cin >> v[i].FI;
		v[i].SE = i + 1;
	}

	sort(ALL(v));
	REP(i, n){
		cout << v[i].SE << " ";
	}
	cout << endl;

	return 0;
}


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

int main(){
    char c;

    cin >> c;

    if(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o')
        cout << "vowel" << endl;
    else
        cout << "consonant" << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        for (;;) {
			s = s.substring(0, s.length() - 2);
			if (s.substring(0, s.length() / 2).equals(s.substring(s.length() / 2))) {
				System.out.println(s.length());
				break;
			}
		}
       
    }
}

Measured memory_bytes: 23124
<?php

$arg1 = fscanf(STDIN, "%d%d%d");
$flag5 = 0;
$flag7 = 0;
//echo "$arg1[0]:$arg1[1]:$arg1[2]\n";

for($i=0;$i<count($arg1);$i++){
	if($arg1[$i] == 5) $flag5++;
	else if($arg1[$i] == 7) $flag7++;
}


if($flag5 == 2 && $flag7 == 1) echo "YES\n";
else echo "NO\n";

?>

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;
ll MOD = 1e9 + 7;

int main(){
  int N;
  vector<string> S(2);
  cin >> N;
  REP(i,2) cin >> S[i];

  vector<int> typ;
  char prev = S[0][0];
  int cnt = 1;
  for(int i = 1; i <= N; ++i) {
    if((i == N) || S[0][i] != prev) {
      typ.push_back(cnt);
      cnt = 1;
    }else{
      ++cnt;
    }
    prev = S[0][i];
  }

  ll ret = 1;
  int p = 0;
  for(int e: typ) {
    if(p == 0) {
      if(e == 1) ret = 3;
      else if(e == 2) ret = 6;
    }else if(p == 1){
      ret = ret * 2 % MOD;
    }else if(p == 2) {
      if(e == 2) ret = ret * 3 % MOD;
    }
    p = e;
  }
  cout << ret << endl;
  return 0;
}
// RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
// 1 2 2111 2 21 2 2 2 2 2 21 211111 21111111 2 21 2 21


Measured memory_bytes: 256
#include<cstdio> 
#include<cstring>
#define ll long long
#define fo(i, x, y) for(int i = x ; i <= y; i ++)
using namespace std;

int n;
char s[200005];
ll ans;

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	int p = 0;
	fo(i, 1, n) {
		if(s[i] == 'B') {
			p ++;
		} else ans += p;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 384
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int N=300010;
int n,m,a[N],r[N],mx[N];

int main(){
    scanf("%d",&m); int n=1<<m;
    for (int i=0; i<n; i++) scanf("%d",&a[i]);
    for (int i=0; i<n; i++)
        for (int j=i; j<n; j=(j+1)|i)
            r[j]=max(r[j],a[i]+mx[j]),mx[j]=max(mx[j],a[i]);
    for (int i=1; i<n; i++) printf("%d\n",r[i]=max(r[i],r[i-1]));
    return 0;
}

Measured memory_bytes: 6016
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    vector<int>A(N);
  	int mod=1000000007;
  	long long sum=0;
  	long long answer=0;
  	for(int i=0;i<N;i++){
      cin>>A[i];
      sum+=A[i];
      sum%=mod;
    }
  	for(int j=0;j<N;j++){
      sum-=A[j];
      if(sum<0) sum+=mod;
      answer+=A[j]*sum;
      answer%=mod;
    }
  	cout<<answer<<endl;
}

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

#define MAX 2000005
#define VAL_MAX 10005

int main(int, char**)
{
    int n;
    cin >> n;

    int a[MAX];
    int b[MAX];
    int c[VAL_MAX] = {0};
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
        c[a[i]]++;

    for (int i = 1; i < VAL_MAX; i++)
        c[i] += c[i-1];

    for (int i = n-1; i >= 0; i--) {
        b[c[a[i]]] = a[i];
        c[a[i]]--;
    }

    for (int i = 1; i < n; i++)
        cout << b[i] << " ";
    cout << b[n] << endl;

    return 0;
}


Measured memory_bytes: 18692
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}


int main() {

    int N;
    cin >> N;

    vector<int> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];

    map<int, int> m_even, m_odd;
    for (int i = 0; i < N; i++)if (i % 2 == 0)m_even[v[i]]++;
    for (int i = 0; i < N; i++) if (i % 2) m_odd[v[i]]++;

    vector<pair<int, int>> p_even, p_odd;
    for (auto x: m_even) p_even.push_back(make_pair(N / 2 - x.second, x.first));
    for (auto x:m_odd) p_odd.push_back(make_pair(N / 2 - x.second, x.first));
    sort(p_even.begin(), p_even.end());
    sort(p_odd.begin(), p_odd.end());
    p_even.push_back(make_pair(N / 2, 3242422));
    p_odd.push_back(make_pair(N / 2, 44444242));

    int ans = 0;
    if (p_even[0].second != p_odd[0].second) {
        ans += p_even[0].first + p_odd[0].first;
    } else {
        int ans1 = p_even[0].first + p_odd[1].first;
        int ans2 = p_even[1].first + p_odd[0].first;
        ans = min(ans1, ans2);
    }

    cout << ans << endl;

    return 0;
}











































































Measured memory_bytes: 6520
fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s
}

fn read_ints() -> Vec<i32> {
    read_line()
        .split_whitespace()
        .map(|w| w.parse().unwrap())
        .collect()
}

fn main() {
    let N = read_ints()[0];
    let A = read_ints()[0];

    println!("{}", if N % 500 <= A { "Yes" } else { "No" });
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <math.h>
#include <map>
#include <set>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0, i##_len=(n); i<i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

int main(){
        int R;
        cin >> R;
        if(R<1200){
                cout << "ABC" << endl;
        }else if(1200<=R and R<2800){
                cout << "ARC" << endl;
        }else{
                cout << "AGC" << endl;
        }
        return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // uint64_t

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))

int get_int2(int *a1, int *a2) {
  scanf("%d %d", a1, a2);
  return 0;
}

// <arr[0]> <arr[1]> .. <arr[size-1]>
int fget_array(int *arr, int size) {
    int i;
    for(i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }
    return 0;
}

#define NUM_MAX 100000
#define INF (1e+9)

int main(void) {
    int num, k;
    get_int2(&num, &k);
    int arr[NUM_MAX];
    fget_array(arr, num);
    int i;
    int ans = INF;
    for(i = k-1; i < num; i++) {
        int start = arr[i-(k-1)];
        int end = arr[i];
        int diff = min(abs(start), abs(end));
        ans = min(ans, diff + end-start);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 512
#include <cstddef>
#include <complex>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <limits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <memory>
#include <random>
#include <fstream>
#include <locale>
#include <bitset>

using ll = long long;
using ull = unsigned long long;

//vector
template <class T>
using vec = std::vector<T>;

template <class T>
using vvec = vec<vec<T>>;

constexpr std::size_t operator""_sz(ull n) { return std::size_t(n); }

using bit = std::bitset<50>;

int main()
{
    using namespace std;

    int n;
    cin >> n;
    string s;
    cin >> s;

    auto r = count(s.cbegin(), s.cend(), 'R');

    if (r > n - r)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

    return 0;
}

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

int main() {
    string a, b;
    cin >> a >> b;
    if (a.size() > b.size()) {
        cout << "GREATER" << endl;
    } else if (a.size() < b.size()) {
        cout << "LESS" << endl;
    } else {
        for (int i = 0; i < a.size(); i++) {
            if (a[i] > b[i]) {
                cout << "GREATER" << endl;
                return 0;
            } else if (a[i] < b[i]) {
                cout << "LESS" << endl;
                return 0;
            }
        }
        cout << "EQUAL" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int h,w,d;
  cin>>h>>w>>d;
  vector<string> ans(h,string(w,'#'));
  auto draw=[&](Int u,Int v,char c){
    if((u+v+10000)&1) return;
    //cout<<u<<" "<<v<<":"<<c<<endl;
    Int x=(u+v)/2,y=(u-v)/2;
    if(0<=x&&x<w&&0<=y&&y<h) ans[y][x]=c;
  };
  string B="RYGB";
  Int x=0;
   for(Int i=0;i<=h+w;i+=d){
     Int p=x<<1;
     x=!x;
     for(Int j=-h;j<=w;j+=d){
       for(Int a=0;a<d;a++)
	 for(Int b=0;b<d;b++)
	   draw(i+a,j+b,B[p%4]);
       p++;
     }
  }
  
  for(Int i=0;i<h;i++) cout<<ans[i]<<endl;
  return 0;
}


Measured memory_bytes: 768
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;
 
int main(void){
  int A,B,C,ans=0;
  cin >> A >> B >> C;
  int M=max3(A,B,C);
  int dis=M*3-A-B-C;
  if(dis%2==0) cout << dis/2 << endl;
  else cout << 1+(dis+1)/2 << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int prime(int n){
  int i;
  for(i = 2;i*i <= n;i++){
    if(n % i == 0){
      return 0;
    }
  }
  return 1;
}
int main(){
  int n, i;
  scanf("%d", &n);
  while(n != 0){
    for(i = n;i > 0;i--){
      if(prime(i)){
        if(prime(i-2)){
          printf("%d %d\n", i-2, i);
          break;
        }
      }
    }
    scanf("%d", &n);
  }
  return 0;
}

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

long long dp[100010][13];
string s;

int main() {
    cin >> s;
    int n = 0;
    n = s.size();
    
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        int check = 0;
        if (s[i] == '?') check = -1;
        else check = s[i] - '0';

        for (int j = 0; j < 10; j++) {
            if (check != -1 && check != j) continue;
            for (int k = 0; k < 13; k++) {
                dp[i + 1][(10 * k + j) % 13] += dp[i][k];
            }
        }
        for (int j = 0; j < 13; j++) dp[i + 1][j] %= 1000000007;
    }
    cout << dp[n][5] << endl;

    return 0;
}


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

using namespace std;
typedef long long ll;

int main() {
    int n, m; cin >> n >> m;
    vector<int> pcnt(n);
    vector<int> ac(n);
    int ans_c = 0;
    int ans_p = 0;
    for (int i = 0; i < m; i++) {
        int p; cin >> p;
        string s; cin >> s;
        if (s == "WA") pcnt[p-1]++;
        else if (s == "AC") {
            if (ac[p-1] == 1) continue;
            ac[p-1] = 1;
            ans_c++;
            ans_p += pcnt[p-1];
        }
    }

    cout << ans_c << " " << ans_p << endl;
}



Measured memory_bytes: 1024