akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>

using namespace std;

struct Node{
public:
 Node* parent;
 Node* left;
 Node* right;
 int value;

 Node(Node* p = 0, Node* l = 0, Node* r = 0, int v = 0) : parent(p), left(l), right(r), value(v){};
private:
protected:
};

class Tree{
private:
 Node* root;
 enum ORDER {PREORDER = 0, INORDER, POSTORDER};
public:
 Tree(){root = 0;};

 void insert(long longz){
  Node* z = new Node(0, 0, 0, longz);
  insert(z);
 };


 void insert(Node* z){
  Node* y = 0;
  Node* x = root;
  while(x != 0){
   y = x;
   if(z->value < x->value){
    x = x->left;
   }else{
    x = x->right;
   }
  }
  z->parent = y;
  if(y == 0){
   root = z;
  }else if(z->value < y->value){
   y->left = z;
  }else{
   y->right = z;
  }
  return ;
 };

 void deleteValue(long value){
  Node* z = find(value);
  deleteValue(z);
 };

 void deleteValue(Node* z){
  Node* y = 0;

  if(z->left == 0 || z->right == 0){
   y = z; 
  }else{
   if(z->right != 0){
    y = minimum(z->right);
   }else{
    Node* buf = z->parent;
    while(buf != 0 && z == buf->right){
     z = buf;
     buf = buf->parent;
    }
    y = buf;
   }
  }
 
  Node* x = 0;
  if(y->left != 0) x = y->left;
  else x = y->right;
 
  if(x != 0) x->parent = y->parent;
  if(y->parent == 0){
   root = x;
  }else if(y == (y->parent)->left){
   (y->parent)->left = x;
  }else{
   (y->parent)->right = x; 
  }
  
  if(y != z) z->value = y->value;
 
 };

 Node* minimum(long value){
  Node* z = new Node(0, 0, 0, value);
   return minimum(z);
 };

 Node* minimum(Node* z){
  while(z->left != 0){
    z = z->left;
  }
  return z;
 };

 Node* find(long value){
  Node* findNode = new Node(0, 0, 0, value);
  return find(findNode);
 };

 Node* find(Node* z){
  Node* x = root;
  
  while(x != 0){
   if(z->value < x->value){
    x = x->left;
   }else if(z->value > x->value){
    x = x->right;
   }else{
    return x;
   }
  }
  return 0;
 };

 void print(){
  print(INORDER);
  print(PREORDER);
 };
 void print(ORDER order){
  Node* cur = root;
  Node* pre = cur->parent;

  if(root == 0) return;

  while(cur){
   if(pre == cur->parent){
    if(order == PREORDER) cout << " " << cur->value;
    if(cur->left != 0){
     pre = cur;
     cur = cur->left;
     continue;
    }else{
     pre = cur->left;
    }
   }

   if(pre == cur->left){
    if(order == INORDER) cout << " " << cur->value;
    if(cur->right != 0){
     pre = cur;
     cur = cur->right;
     continue;
    }else{
     pre = cur->right;
    }
   }

   if(pre == cur->right){
    if(order == POSTORDER) cout<< " " << cur->value;
    pre = cur;
    cur = cur->parent;
   }
  }
  cout << endl;
  return ;
 };


protected:
};


int main(){
 Tree tree;
 int n = 0; cin >> n;
 for(int i = 0; i < n; i++){
  string str = ""; cin >> str;

  if(str == "insert"){
   long x = 0; cin >> x; 
   tree.insert(x);
  }else if(str == "find"){
   long value = 0; cin >> value;
   Node* f = tree.find(value);
   if(f != 0) cout << "yes" << endl;
   else cout << "no" << endl;
  }else if(str == "delete"){
   long value = 0; cin >> value;
   tree.deleteValue(value);
  }else if(str == "print"){
   tree.print();
  }
 }

 return 0;
}

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

#define ll long long int
#define hell 998244353
#define vi vector <ll>
#define pb push_back
#define pii pair<ll,ll>
#define vii vector <pii>
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define sep(i,a,b)  for(ll i=a-1;i>=b;i--)
#define inf (ll)(1e16)

using namespace std;

void solve(){
    ll n,W;
    cin>>n>>W;
    vi v(n),w(n);
    rep(i,0,n)
        cin>>w[i]>>v[i];
    ll dp[n+1][100005];
    ll ans=0;
    rep(i,0,n+1)
    {
        rep(j,0,100005)
        {
            if(i==0&&j==0)
                dp[i][j]=0;
            else if(i==0)
                dp[i][j]=inf;
            else if(j==0)
                dp[i][j]=0;
            else if(v[i-1]>j)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=min(dp[i-1][j],w[i-1]+dp[i-1][j-v[i-1]]);
            if(dp[i][j]<=W)
                ans=max(ans,j);
        }
    }
    cout<<ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}


Measured memory_bytes: 79232
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

bool board[305][305], used[305][305];
int h, w;
void dfs(int y, int x) {
  if(used[y][x]) {
    cout << "err" << endl;
  }
  used[y][x] = true;
  REP(k, 4) {
    int nx = x + dx[k], ny = y + dy[k];
    if(IN(0LL, w, nx) && IN(0LL, h, ny) && !used[ny][nx] && !board[ny][nx]) {
      dfs(ny, nx);
    }
  }
}

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

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    VI sx(n), sy(n), gx(n), gy(n);
    VI vx, vy;
    REP(i, n) {
      cin >> sx[i] >> sy[i] >> gx[i] >> gy[i];
      sx[i] *= 2, sy[i] *= 2, gx[i] *= 2, gy[i] *= 2;
      vx.PB(sx[i]); vx.PB(sx[i]-1); vx.PB(sx[i]+1);
      vy.PB(sy[i]); vy.PB(sy[i]-1); vy.PB(sy[i]+1);
      vx.PB(gx[i]); vx.PB(gx[i]-1); vx.PB(gx[i]+1);
      vy.PB(gy[i]); vy.PB(gy[i]-1); vy.PB(gy[i]+1);
    }
    vx.PB(-1); vy.PB(-1);
    sort(ALL(vx)); vx.erase(unique(ALL(vx)), vx.end());
    sort(ALL(vy)); vy.erase(unique(ALL(vy)), vy.end());
    // cout << vx << endl << vy << endl;
    memset(board, false, sizeof(board));
    REP(i, n) {
      sx[i] = lower_bound(ALL(vx), sx[i]) - vx.begin();
      sy[i] = lower_bound(ALL(vy), sy[i]) - vy.begin();
      gx[i] = lower_bound(ALL(vx), gx[i]) - vx.begin();
      gy[i] = lower_bound(ALL(vy), gy[i]) - vy.begin();
      FOR(j, sx[i], gx[i]+1) {
        board[sy[i]][j] = board[gy[i]][j] = true;
      }
      FOR(j, gy[i], sy[i]+1) {
        board[j][sx[i]] = board[j][gx[i]] = true;
      }
    }

    h = vy.size(), w = vx.size();
    // REP(i, h) {
    //   REP(j, w) {
    //     cout << board[i][j];
    //   }
    //   cout << endl;
    // }

    memset(used, false, sizeof(used));
    int cnt = 0;
    REP(i, h) REP(j, w) {
      if(used[i][j] || board[i][j]) continue;
      dfs(i, j);
      // cout << "end" << endl;
      // cout << i << " " << j << endl;
      cnt++;
    }

    cout << cnt << endl;
  }

  return 0;
}



Measured memory_bytes: 4440
#import numpy as np

#def area--------------------------#
#ryouno syokiti
class ryou:
	def flinit(self):
		room=list()
		for i in range(10):
			room+=[0]
		return room

#def kaijo([a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_10]):


#def kaijo(x):
#	y=[]
#	for i in x:
#		y=y+ " "+x[i]
#	return y		
def kaijo(x):
	print "",
	for i in range(len(x)-1):
		print str(x[i]),
	print str(x[len(x)-1])


#----------------------------------#

floor_11=ryou().flinit()
floor_12=ryou().flinit()
floor_13=ryou().flinit()
floor_21=ryou().flinit()
floor_22=ryou().flinit()
floor_23=ryou().flinit()
floor_31=ryou().flinit()
floor_32=ryou().flinit()
floor_33=ryou().flinit()
floor_41=ryou().flinit()
floor_42=ryou().flinit()
floor_43=ryou().flinit()


fldic={"11":floor_11,
       "12":floor_12,
       "13":floor_13,
       "21":floor_21,
       "22":floor_22,
       "23":floor_23,
       "31":floor_31,
       "32":floor_32,
       "33":floor_33,
       "41":floor_41,
       "42":floor_42,
       "43":floor_43
       }

#----------------------------------#


#1kaime yomikomi
n=int(raw_input())

#nkaime syusyori

for l in range(n):
	list_mojiretsu=raw_input().split(" ")
	henka=map(int,list_mojiretsu)
	fldic[str(henka[0])+str(henka[1])][henka[2]-1]+=henka[3]
	


kaijo(floor_11)
kaijo(floor_12)
kaijo(floor_13)
print "####################"
kaijo(floor_21)
kaijo(floor_22)
kaijo(floor_23)
print "####################"
kaijo(floor_31)
kaijo(floor_32)
kaijo(floor_33)
print "####################"
kaijo(floor_41)
kaijo(floor_42)
kaijo(floor_43)

Measured memory_bytes: 6416
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
vector<ll> node;
int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    ll lk;
    cin>>lk;
    node.push_back(lk);
  }
  sort(node.begin(),node.end());
  ll ans=0;
  for(int i=0;i<n-2;i++){
    for(int j=i+1;j<n-1;j++){
      int left=j;
      int right=lower_bound(node.begin(),node.end(),node[i]+node[j])-node.begin();
      ans+=max(right-left-1,0);
      //if(right>left) cout<<i<<" "<<j<<" "<<left<<" "<<right<<endl;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 10000000000;
ll ans[100001];
int main() {
    int k;
    cin >> k;
    queue<ll> que;
    for (int i = 1; i <= 9; i++) {
        que.push(i);
    }
    int count = 1;
    while (count <= k) {
        ll n = que.front();
        ans[count] = n;
        count++;
        if (n % 10 == 0) {
            que.push(n * 10);
            que.push(n * 10 + 1);
        }
        else if (n % 10 == 9) {
            que.push(n * 10 + 8);
            que.push(n * 10 + 9);
        }
        else {
            que.push(n * 10 + n % 10 - 1);
            que.push(n * 10 + n % 10);
            que.push(n * 10 + n % 10 + 1);
        }
        que.pop();
    }
    cout << ans[k];
    return 0;
}

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

int main()
{
    string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ", ch;
    int n, i, j, l;

    cin >> n >> ch;

    l = ch.size();

    for(i = 0; i < l; i++){
        for(j = 0; j < 26; j++){
            if(s[j] == ch[i]){
                ch[i] = s[(j + n) % 26];
                break;
            }
        }
    }

    cout << ch << endl;

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(X: int):
    gohyaku = X // 500
    nokori = X % 500
    go = nokori // 5
    print(1000*gohyaku + 5 * go)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define vint vector<int>
#define pri_que priority_queue
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    vint a(n+1); range(i,1,n+1)cin >> a[i];
    vint b;
    range(i,1,n+1) b.pb(a[i]-i);
    sort(all(b));
    int mid=b[b.size()/2];
    int res=0;
    range(i,1,n+1) res+=abs(a[i]-mid-i);
    cout<<res<<endl;

}

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

typedef long long ll;

using namespace std;

#define swap(a, b)    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while(0)
#define repd(i, a, b) for(typeof(b) i = a; i < (b); ++i)
#define rep(i, n)     repd(i, 0, n)
#define dump(x)       cerr << #x << " = " << (x) << endl
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define YesNo(x)      cout << ((x) ? "Yes" : "No") << endl
#define YESNO(x)      cout << ((x) ? "YES" : "NO") << endl
#define absi(x)       ( ((x) >= 0) ? (x) : (-(x)) )

int main(int argc, const char* argv[]) {
	ll n;
	cin >> n;
	vector<double> p(n);
	rep(i, n) cin >> p[i];

	/* dp[i][j] = i 枚目までで、j 枚が表面になる確率 */
	vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0.0));
	dp[0][0] = 1.0;
	rep(i, n) {
		dp[i+1][0] = dp[i][0] * (1.0 - p[i]);
		rep(j, i + 1) {
			/* dp[i][j] =   i-1 枚目までで j-1 枚が表面になる確率 * i 枚目が表面になる確率
			              + i-1 枚目までで j   枚が表面になる確率 * i 枚目が裏面になる確率 */
			dp[i+1][j+1] = (dp[i][j] * p[i]) + (dp[i][j+1] * (1.0 - p[i]));
		}
	}

	double ret = 0.0;
	repd(i, n/2 + 1, n + 1) {
		ret += dp[n][i];
	}

	cout << std::setprecision(11) << ret << endl;

	return 0;
}


Measured memory_bytes: 70784
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int mod = 1e9 + 7;
//const int mod = 998244353;

const ll infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;


int main() {
  int m;
  cin >> m;
  vector<int> a(m);
  vector<int> b(m);
  vector<int> c(m,1);
  rep(i,m) cin >> a[i];
  rep(i,m) cin >> b[i];
  for(int i=1 ;i<m ; i++) {
    c[i]=c[i-1]*(i+1);
  }
  int acount=0;
  rep(i,m-1) {
    
    acount+=(a[i]-1)*c[m-i-2];
    rep(j,m-i-1) {
      if(a[i+j+1]>=a[i]) a[i+j+1]--;
    }
  }
  int bcount=0;
  rep(i,m-1) {
    
    bcount+=(b[i]-1)*c[m-i-2];
    rep(j,m-i-1) {
      if(b[i+j+1]>=b[i]) b[i+j+1]--;
    }
  }
  int ans=abs(acount-bcount);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{
  vector<pair<int, int> > scores;

  while (1) {
    pair<int, int> score;
    char temp;
    cin >> score.second >> temp >> score.first;
    if (score.first == 0 && score.second == 0) break;
    scores.push_back(score);
  }

  sort(scores.begin(), scores.end(), greater<pair<int, int> >());

  int q;
  while (cin >> q) {
    int rank = 0;
    int lastScore = 0;
    for (int i = 0; i < scores.size(); i++) {
      if (lastScore != scores[i].first) rank++;
      if (q == scores[i].second) break;
      lastScore = scores[i].first;
    }
    cout << rank << endl;
  }
}



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

int main(){
    int n2;
    int n1,S[100000];
    int T[100000],sum=0;
    cin >> n1;
    
    for(int i=0; i<n1; i++){
        cin >> S[i];
    }
    
    cin >> n2;
    for(int i=0; i<n2; i++){
        int y = max(n1,n2);
        cin >> T[i];
        for(int j=0; j<y; j++){
            if(T[i]==S[j]){
                sum++;
                break;
            }
        }
    }
    
    cout << sum << endl;
    
    return 0;
}

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

const int maxn(2005);
const int mxsz(1e7);

int n, x[maxn], pr[mxsz / 10], tot, pos[maxn], vis[maxn];
int first[maxn], cnt, idx, match[maxn], num;
bitset <mxsz + 5> ispr;

struct Edge {
	int to, next;
} edge[maxn * maxn];

inline void Add(int u, int v) {
	edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;
}

int Dfs(int u) {
	int e, v;
	for (e = first[u]; ~e; e = edge[e].next)
		if (vis[v = edge[e].to] != idx) {
			vis[v] = idx;
			if (!match[v] || Dfs(match[v]))	return match[v] = u, 1;
		}
	return 0;
}

int main() {
	memset(first, -1, sizeof(first));
	int i, j, ans, cnt0, cnt1;
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) scanf("%d", &x[i]);
	sort(x + 1, x + n + 1);
	for (i = 2; i <= x[n]; ++i) {
		if (!ispr[i]) pr[++tot] = i;
		for (j = 1; j <= tot && pr[j] * i <= x[n]; ++j) {
			ispr[pr[j] * i] = 1;
			if (!(i % pr[j])) break;
		}
	}
	ans = cnt0 = cnt1 = 0;
	for (i = j = 1; i <= n; i = j) {
		while (x[j] == x[i] + j - i) ++j;
		pos[++num] = x[i], pos[++num] = x[j - 1] + 1;
	}
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1) ++cnt1;
		else ++cnt0;
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1)
			for (j = 1; j <= num; ++j)
				if ((~pos[j] & 1) && abs(pos[j] - pos[i]) > 2 && !ispr[abs(pos[j] - pos[i])]) Add(i, j);
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1) ++idx, ans += Dfs(i);
	cnt0 -= ans, cnt1 -= ans;
	ans += (cnt0 / 2) * 2 + (cnt1 / 2) * 2;
	if (cnt0 & 1) ans += 3;
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;

int N, h[100000], dp[100010];

int main(){
	cin >> N;
	for(int i = 0; i < N; ++i) cin >> h[i];

	dp[0] = 0; dp[1] = abs(h[1] - h[0]);
	for(int i = 2; i < N; ++i){
		dp[i] = min(dp[i-2]+abs(h[i-2]-h[i]), dp[i-1]+abs(h[i-1]-h[i]));
	}
	cout << dp[N-1] << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
struct edge { int to, cost; };
typedef pair<int, int>P;


int main(){
	int N,K,R,S,P;
  	cin >>N>>K>>R>>S>>P;
  	string sth;
    cin >>sth;
  	int cr=0,cs=0,cp=0;
  	int memo[N];
  	rep(i,N){memo[i]=0;}
  rep(i,N){
    if(sth[i]=='r'){cp++;}
    if(sth[i]=='s'){cr++;}
    if(sth[i]=='p'){cs++;}
      
    if(i>=K){
   
    if(sth[i-K]=='r'&&sth[i]=='r'&&memo[i-K]!=1){cp--;memo[i]=1;}
    if(sth[i]=='s'&&sth[i-K]=='s'&&memo[i-K]!=1){cr--;memo[i]=1;}
    if(sth[i]=='p'&&sth[i-K]=='p'&&memo[i-K]!=1){cs--;memo[i]=1;}  
    }  
     
      
  }	
    cout<<(cp*P)+(cr*R)+(cs*S)<<endl; 
  	
  	
}


Measured memory_bytes: 896
//ABC122C
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <numeric>
using namespace std;

int main() {
	int n, q;
	string s;
	cin >> n >> q >> s;
	for(int i=0;i<n-1;i++){
		if(s.substr(i,2) == "AC"){
			s.at(i+1) = 'a';
		}
	}
	vector<int> count(n);
	count.at(0) = 0;
	for(int i=1;i<n;i++){
		if(s.at(i) == 'a'){
			count.at(i) = count.at(i-1) + 1;
		}else{
			count.at(i) = count.at(i-1);
		}
	}
	for(int i=0;i<q;i++){
		int l, r;
		cin >> l >> r;
		int ans = count.at(r-1) - count.at(l-1);
		cout << ans << endl;
	}
}

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

int64_t MOD = 1000000007;
int64_t MAX = 9223372036854775807;
double PI = 3.141592653589793;

int main()
{
    int N;
    cin >> N;
    int ans = 1;
    while (ans * ans <= N)
        ans++;
    cout << (int)pow(ans - 1, 2);
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce
from queue import Queue
from operator import mul
from functools import reduce
from functools import lru_cache

input = sys.stdin.readline

# N個整数
# a, b, c = list(map(int, input().split()))

# 1整数
n = int(input())
k = int(input())
x = int(input())
y = int(input())

# 空白区切りリスト整数
# b = list(map(int, input().split()))

# 空白区切り文字列
# t, d = input().split()


if n <= k:
    print(x * n)
else:
    print((x * k) + (y * (n - k)))


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


using namespace std;

int main(){
   int A, B, counter= 1,total ;
   cin>>A;
   cin>>B;
   total=A;
    if (A<B){
        while(total<B){
            total= total+(A-1);
            counter++;
        }
    cout<< counter<<endl;
    }
    else if (B==1){
        cout <<0<<endl;
    }
    else {
        cout<< 1<< endl;
   }

return 0;
    }











Measured memory_bytes: 256
N = int(input())
l = []
for _ in range(N):
    A = int(input())
    ll = []
    for _ in range(A):
        x, y = map(int, input().split())
        ll.append([x, y])
    l.append(ll)

b = 2 ** N
ans = 0

for i in range(2 ** N):
    flag = True
    for j in range(N):
        if i >> j & 1 == 1:
            for x, y in l[j]:
                if y == 1 and i >> (x - 1) & 1 != 1 or y == 0 and i >> (x - 1) & 1 == 1:
                    flag = False
    if flag:
        ans = max(ans, bin(i).count('1'))
        # print(bin(i))

print(ans)


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


void multiply()
{
	
	cpp_int a;
	 double b;
	cin >> a >> b;
	b = ((b)*(1000.0000000000000000));
	cpp_int bb = (cpp_int)b;
	cpp_int aa = a;
	cpp_int aans = (aa*bb);
	cpp_int t = aans/1000;
	cout << t << endl;
 
}
 
int32_t main()
{
	ios_base::sync_with_stdio(0);
	 cin.tie(0); 
	 cout.tie(0);
    
    	multiply();
    return 0;
}

Measured memory_bytes: 3844
#include <stdio.h>
char s[110];
int main(){
	long long k;
	scanf("%s%lld",s,&k);
	//k文字目まで全部1なら1、そうでないなら1でない最初の文字
	for(int i=0;i<k;i++){
		if(s[i]!='1'){
			putchar(s[i]);
			return 0;
		}
	}
	puts("1");
}

Measured memory_bytes: 128
//#pragma warning disable

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

public class Test
{
    public static void Main()
    {
        var line1 = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        var H = line1[0];
        var W = line1[1];

        var answer = Math.Min(
            SubTask(H, W),
            SubTask(W, H));

        Console.WriteLine(answer);
    }

    public static long SubTask(long H, long W)
    {
        long Diffmin = long.MaxValue;

        {
            // 縦3分割
            long max = ((H + 2) / 3) * W;
            long min = (H / 3) * W;

            Diffmin = Math.Min(Diffmin, max - min);
        }
        {
            // 縦に分割してから横(1)
            long[] area = new long[] {
                ((H + 1) / 3) * W,
                (H - (H + 1) / 3) * (W / 2),
                (H - (H + 1) / 3) * ((W + 1) / 2),
            };

            area = area.OrderBy(x => x).ToArray();
            Diffmin = Math.Min(Diffmin, area[2] - area[0]);
        }
        {
            // 縦に分割してから横(2)
            long[] area = new long[] {
                ((H + 2) / 3) * W,
                (H - (H + 2) / 3) * (W / 2),
                (H - (H + 2) / 3) * ((W + 1) / 2),
            };

            area = area.OrderBy(x => x).ToArray();
            Diffmin = Math.Min(Diffmin, area[2] - area[0]);
        }

        return Diffmin;
    }
}

Measured memory_bytes: 13396
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int inf=1<<29;
const int maxn=1e5+100;
int n,x;
int a[maxn];

inline int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }

int main() {
    scanf("%d%d",&n,&x);
    int t,ans=0;
    for (int i=0;i<n;i++) {
        scanf("%d",&t);
        // printf("%d\n", ans);
        if (i<=0) ans=abs(t-x);
        else ans=gcd(ans,abs(t-x));
    }
    printf("%d\n", ans);
    return 0;
}


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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n"
#define rep(i,n) for(int i=0; i<(n); ++i)

typedef pair<int, int> P;
typedef pair<string, int> Psi;





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

	int n,k; cin>>n>>k;

	string s; cin>>s;
	k--;
	if(s[k] =='A'){
		s[k] ='a';
	}else if (s[k] =='B') {
		s[k] ='b';
	}else {
		s[k] ='c';
	}

	writeln(s);




}



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

int main() {
  int n,N,r,s=0;
  cin>>n;
  N=n;
  while(n>0){
    r=n%10;
    s+=r;
    n/=10;
  }
  if(N%s==0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100001;

int par[MAX_N];
int ranks[MAX_N];
int diff_weight[MAX_N];

void init(int n){
  for(int i = 0; i < n; i++){
    par[i] = i; ranks[i] = 0; diff_weight[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  } else{
    int r = find(par[x]);
    diff_weight[x] += diff_weight[par[x]];
    return par[x] = r;
  }
}

int weight(int x){
  find(x);
  return diff_weight[x];
}

void unite(int x, int y, int w){
  w += weight(x); w -= weight(y);
  x = find(x); y = find(y);
  if(x == y) return;
  if(ranks[x] < ranks[y]) swap(x,y), w = -w;
  if(ranks[x] == ranks[y]) ranks[x]++;
  par[y] = x;
  diff_weight[y] = w;
}

bool same(int x, int y){
  return find(x) == find(y);
}

int diff(int x, int y){
  return weight(y) - weight(x);
}

int main(){
  int N, M, L, R, D;
  cin >> N >> M;
  init(N+1);
  for(int i = 0; i < M; i++){
    cin >> L >> R >> D;
    if(same(L, R)){
      if(diff(L, R) != D){
        cout << "No" << endl;
        return 0;
      }
    } else {
      unite(L, R, D);
    }
  }
  cout << "Yes" << endl;
  return 0;
}


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

int main(){
	int x,a,b;
	cin >> x >> a >> b;
	if(b - a > x)
	       cout << "dangerous" << endl;
	else if(b-a >0)
		cout << "safe" << endl;
	else 
	 	cout << "delicious" << endl;

	return 0;
}	


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

namespace A___Two_Rectangles
{
    class Program
    {
        static void Main(string[] args)
        {
            var A_B_C_D = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = A_B_C_D[0], B = A_B_C_D[1], C = A_B_C_D[2], D = A_B_C_D[3];

            Console.WriteLine(Math.Max(A * B, C * D));
        }
    }
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(int i=0;i<(int)n;i++)
ll mod=1e9+7;
#define PI acos(-1)
struct edge{int from, to;};

int main(){
    int a[3][3];
    rep(i,3) rep(j,3) cin>>a[i][j];
    int n;
    cin>>n;
    vector<int> b(n);
    rep(i, n) cin>>b[i];

    
    rep(k,n){
        rep(i,3){
            rep(j,3){
                if(a[i][j]==b[k]){
                    a[i][j]=-1;
                }
            }
        }
    }
    /*
    rep(i,3){
        rep(j,3){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    */

    bool bingo=false;
    if(a[1][1]==-1){
        if(a[0][0]==-1&&a[2][2]==-1) bingo=true;
        else if(a[0][1]==-1&&a[2][1]==-1) bingo=true;
        else if(a[1][0]==-1&&a[1][2]==-1) bingo=true;
        else if(a[0][2]==-1&&a[2][0]==-1) bingo=true;
    }
    else if(a[0][0]==-1){
        if(a[0][1]==-1&&a[0][2]==-1) bingo=true;
        else if(a[1][0]==-1&&a[2][0]==-1) bingo=true;
    }
    else if(a[2][2]==-1){
        if(a[0][2]==-1&&a[1][2]==-1) bingo =true;
        else if(a[2][0]==-1&&a[2][1]==-1) bingo=true;
    }
    if(bingo) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int main()
{
    int A, B;
    scanf("%d%d", &A, &B);

    int temp;
    if (A > B) {
        temp = B;
        B = A;
        A = temp;
    }
 
    if ((B - A) % 2 == 1) {
        printf("IMPOSSIBLE\n");
    } else {
        printf("%d\n", A + ((B - A) / 2));
    }
    return 0;
}

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

int main() {
  int A, B, C, X=0;
  cin >> A >> B >> C;
  rep(i, B){
    if(A*(i+1)%B==C){
      X=1;
      break;
    }
  }
  if(X==1) cout << "YES" << endl;
  else cout << "NO" << endl;
} 

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>

using namespace std;

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

  map<int, int> mp;
  mp[0]++;

  long long ans = 0;
  int cur = 0, base = 1;
  for (int i = s.length() - 1; i >= 0; i--) {
    cur += (s[i] - '0') * base;
    cur %= 2019;
    ans += mp[cur]++;
    base *= 10;
    base %= 2019;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3748
/*
  AOJ 
  title:#3128
  @kankichi57301
 */
#include <stdio.h>

int n;
int main()
{
  int i,c,c0,min_;
  scanf("%d ",&n);
  scanf("%d ",&c0);
  for(i=min_=1;i<n;i++)
    {
      scanf("%d",&c);
      if( c <= c0)
	min_++;
      c0=c;
    }

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



Measured memory_bytes: 2120
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
using namespace std;
inline void read(int &a)
{
	a=0;
	register char ch='\0';
	register int f=1;
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-f,ch=getchar();
	for(; isdigit(ch); ch=getchar())a=a*10+ch-'0';
	a*=f;
}
int main()
{
	int n;
	read(n);
	printf("%d\n",n/3);
	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#define MAX_N 100000
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

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

  int A[MAX_N];
  rep(i, N) { cin >> A[i]; }
  sort(A, A + N);

  int prev = A[0];
  int count = 1;
  int ans = 0;
  for (int i = 1; i < N; i++) {
    if (prev != A[i]) {
      if (count % 2)
        ans++;
      count = 0;
    }
    count++;
    prev = A[i];
  }
  if (count % 2)
    ans++;

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
A,B=map(int,input().split())
ans=0
for i in range(A,B+1):
    si=list(str(i))
    cnt=0
    for j in range(len(si)//2):
        if si[j]!=si[-1-j]:
            break
        else:
            cnt+=1
    if cnt==len(si)//2:
        ans+=1
print(ans)

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>

int fact[110];
int f2[110];

void foo(int i)
{
  int j;
  while(i>1){
    for(j=2;j<=100;j++){
      if( i % j == 0 ){
        fact[j] ++;
        i = i / j;
        break;
      }
    }
  }
}

int main()
{
  int n,i,j,k,n_fact;
  memset(&fact,0,sizeof(fact));
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    foo(i);
  }
  n_fact = 0;
  for(i=2;i<=n;i++){
    if(fact[i]>1){
      f2[n_fact++] = i;
    }
  }
  int res = 0;
  if( n_fact >=3 ){
    for(i=0;i<n_fact-2;i++){
      for(j=i+1;j<n_fact-1;j++){
        for(k=j+1;k<n_fact;k++){
          if( fact[f2[i]] >= 4 && fact[f2[j]] >= 4 && fact[f2[k]] >= 2 ) res++;
          if( fact[f2[i]] >= 4 && fact[f2[j]] >= 2 && fact[f2[k]] >= 4 ) res++;
          if( fact[f2[i]] >= 2 && fact[f2[j]] >= 4 && fact[f2[k]] >= 4 ) res++;
        }
      }
    }
    for(i=0;i<n_fact-1;i++){
      for(j=i+1;j<n_fact;j++){
        if( fact[f2[i]] >= 24 && fact[f2[j]] >= 2 ) res++;
        if( fact[f2[i]] >= 2 && fact[f2[j]] >= 24 ) res++;
        if( fact[f2[i]] >= 14 && fact[f2[j]] >= 4 ) res++;
        if( fact[f2[i]] >= 4 && fact[f2[j]] >= 14 ) res++;
      }
    }
    for(i=0;i<n_fact;i++){
      if( fact[f2[i]] >= 74 ) res++;
    }
  }
  printf("%d\n",res);
  return EXIT_SUCCESS;
}




Measured memory_bytes: 128
#include<stdio.h>
int main(){
	int c, r, x[101][101] = {}, i, j, k;
	scanf("%d %d", &c, &r);
	for(i=0; i<c; i++){
		for(j=0; j<r; j++){
			scanf("%d", &x[i][j]);
			x[i][r] += x[i][j];
		}
	}
	for(i=0;i<=r;i++){
		for(j=0;j<c;j++){
			x[c][i] += x[j][i];
		}
	}
	for(i=0;i<=c;i++){
		for(j=0;j<=r;j++){
			printf("%d", x[i][j]);
			if(j != r){
				printf(" ");
			}
		}
		printf("\n");
	}
}


Measured memory_bytes: 2124
#include<iostream>
#include<algorithm>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define RREP(i, a, n) for(int i=n-1; i>=a; i--)


int main()
{
	int N, K;
	int l[51];
	cin >> N >> K;
	REP(i, 0, N) cin >> l[i];

	sort(l, l + N);
	int sum = 0;
	REP(i, N - K, N) sum += l[i];
	
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    S=LI()
    T=LI()

    dp=[[0]*(M+1) for _ in range(N+1)]
    # dp[i][j]はSをi文字，Tをj文字見た時の通り数
    
    for i in range(N+1):
        dp[i][0]=1
        
    for j in range(M+1):
        dp[0][j]=1
    
    for i in range(N):
        for j in range(M):
            dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
            if S[i]!=T[j]:
                dp[i+1][j+1]-=dp[i][j]
            dp[i+1][j+1]%=mod
            
            
    print(dp[-1][-1])
            
                
            
    

    

main()


Measured memory_bytes: 94276
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
typedef long long ll;
typedef vector<ll> vl;
#define rp(i, f, t) for (int i = f; i < t; i++)
#define pr(i, f, t) for (int i = t - 1; i >= f; i--)
#define ca(n, a) rp(ca_i, 0, n) cout << a[ca_i] << ((ca_i == n - 1) ? "\n" : " ")
#define za(n, a) rp(za_i, 0, n) a[za_i] = 0
#define be(a) a.begin(), a.end()
#define ce(a) cout << (a) << endl
int main()
{
    ll n;
    cin >> n;
    ll a[n];
    rp(i, 0, n - 1) cin >> a[i];
    ll bk[n];
    za(n, bk);
    rp(i, 0, n - 1) bk[a[i] - 1]++;
    rp(i, 0, n) ce(bk[i]);
}

Measured memory_bytes: 6748
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    long n = sc.nextLong();
    long b = sc.nextLong();
    long r = sc.nextLong();

    long ret;
    long a = n / (b + r);
    long mod = n % (b + r);
    if (mod > b) {
      ret = a * b + b;
    } else {
      ret = a * b + mod;
    }
    System.out.println(ret);
  }
}


Measured memory_bytes: 21844
#include<stdio.h>

int n, i;
int b[2], s;
int main(void){
	scanf("%d", &n);
	scanf("%d", b);
	s=b[0];
	for(i=1; i<n-1; i++){
		scanf("%d", b+(i&1));
		if(b[0]>b[1]){s+=b[1];}else{s+=b[0];}
	}
	s+=b[n&1];
	printf("%d\n", s);
}


Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 200000 + 100;
int N, ans[maxn];
struct data { int v, p; }X[maxn];

const int cmp(const data &A, const data &B)
{ return A.v < B.v; }

void Init()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i)
		scanf("%d", &X[i].v), X[i].p = i;
}

void Solve()
{
	sort(X+1, X+N+1, cmp);
	int mid = N >> 1;
	for(int i = 1; i <= N; ++i)
		if(i <= mid) ans[X[i].p] = X[mid+1].v;
		else ans[X[i].p] = X[mid].v;
	for(int i = 1; i <= N; ++i)
		printf("%d\n", ans[i]);
}

int main()
{
	Init(), Solve();
}

Measured memory_bytes: 4480
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, n) for(int i = 1; i <= (int)(n); i++)
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll INF=(1LL<<62);
const double inf=pow(10,10);
const ld pi=acosl(1);
const ll mod = 1000000007;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};

int main(){
	string s;cin>>s;
	rep(i,s.size())cout<<"x";
	cout<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<string>
#include<vector>
#include<stack>
#include<iomanip>
#define rep(i,n) for(int i=0;i<((int)n);i++)
#define Rep(i,n0,n) for(int i=n0;i<((int)n);i++)
#define Com(i,j,n) for(int i=0;i<n-1;i++)for(int j=i+1;j<((int)n);j++)
#define W(x) cout<<x<<endl;
#define Debug(x) cout<<"#DEBUG "<<x<<endl;
#define INF (1<<29)
#define INF2 (long long)8*(long long)INF*(long long)INF
#define mod 1000000007
typedef long long ll;

using namespace std;


int min(int x,int y){if(y<x)return y;else return x;}
int max(int x,int y){if(y>x)return y;else return x;}
int fact(int x){int i=1;rep(j,x){i*=(j+1);} return i;}
long long fact(long long x){long long i=1;rep(j,x){i*=(j+1);} return i;}
int n;
long long max1,max2;
int main()
{
    cin>>n;
    char c[n];
    rep(i,n)
    {
        cin>>c[i];
    }
    stack<bool> st;
    bool fl1,fl2;
    if(n!=1)
    {
        rep(i,n-1)
        {
            if(c[i]==c[i+1])
            {
                st.push(true);
                i++;
            }
            else st.push(false);
        }
        fl1=false;
        long long ans=1;
        while(!st.empty())
        {
            fl2=st.top();
            st.pop();
            if(fl2)
            {
                if(fl1)
                {
                    ans*=3;
                    ans%=mod;
                }
                else
                {
                    ans*=2;
                    ans%=mod;
                }
            }
            else
            {
                if(fl1){}
                else
                {
                    ans*=2;
                    ans%=mod;
                }
            }
            fl1=fl2;
        }
        if(fl1)
        {
            ans*=3;
            ans%=mod;
        }
        else
        {
            ans*=3;
            ans%=mod;
        }
        W(ans)
    }
    else W(3)
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>

using namespace std;

long long kai[100009];
long long kaiinv[100009];
long long fact(long n,long r);
long long fact2(long long a, long n);

int main(){
	long n;
	long a[100009];
	long b[100000];
	long s[2];
	long d;

	for(long i=1;i<=100008;i++){
		kai[0] = 1;
		kai[i] = (i*kai[i-1]) % 1000000007;
	}
	for(long i=1;i<=100008;i++){
		kaiinv[i] = fact2(kai[i],1000000005);
	}

	scanf("%ld",&n);
	for(long i=0;i<=n;i++){
		scanf("%ld",&a[i]);
		b[a[i]-1]++;
	}
	for(long i=0;i<n;i++){
		if(b[i]==2) d = i+1;
	}
	//printf("%ld ",d);
	int count = 0;
	for(long i=0;i<=n;i++){
		if(a[i]==d){
			s[count] = i;
			count++;
		}
	}
	//printf("%ld %ld\n",s[0],s[1]);
	for(long i=1;i<=n+1;i++){
		long long ans = 0;

		ans += fact(n+1,i);
		ans -= fact(s[0]+n-s[1],i-1);
		ans += 1000000007;


		printf("%lld\n", (ans % 1000000007));
	}


	return 0;
}

long long fact2(long long a, long n){
	if(n == 0){
		return 1;
	}else if(n%2 == 1){
		return (fact2(a,n-1)*a)%1000000007;
	}else{
		long long b = fact2(a,n/2);
		return (b*b)%1000000007;
	}
}

long long fact(long n,long r){
	if(r<0) return 0;
	if(r>n){
		return 0;
	}
	if(r==0 || n==r){
		return 1;
	}else{
		return ((kai[n]*kaiinv[n-r]%1000000007)*kaiinv[r])%1000000007;
	}
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define MAX 10000000000;
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	long long a,b;
	cin>>a>>b;
	long long dp[a+1][b+1],a1[a+1],b1[b+1];
	r(i,a)cin>>a1[i+1];
	r(i,b)cin>>b1[i+1];
	r(i,a+1)r(j,b+1)dp[i][j]=MAX;
	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++){
			if(i==1)dp[i][j]=min(a1[i]*b1[j],dp[i][j-1]);
			else dp[i][j]=min(dp[i-1][j-1]+a1[i]*b1[j],dp[i][j-1]);
		}
	cout<<dp[a][b]<<endl;
}

Measured memory_bytes: 9360
#include <string>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,h[100005];
ll dp[100005];
#define ALL(v)  (v).begin(),(v).end()
std::set<int> st;
//#define MAX(a,b) if(a>b)
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))

    /*  ペア関連
    //vector<pair<long long, long long> > pairs(N);
    for(long long i=0; i<N; i++){
        long long a, b;
        cin >> a >> b;
        pairs[i] = make_pair(a, b);
    }
    
    //sort(pairs.begin(), pairs.end(),greater<pair<int,int> >());
	sort(pairs.begin(), pairs.end());
    */

 	//stack<int> sta;   
    //queue<int> que;


int main(){
	
	long long N,M,K;
	string s;
    long long sum,sum1;
	sum=0;
	sum1=0;
	int flg,flg1,cnt,cnt1;
	flg=0;
	flg1=0;
	cnt=0;
	cnt1=0;
	long long max;
	int max1;
	max=0;
	max1=0;
	int min;
	int min1;
	min=INF;
	min1=INF;

	int work1,work2,work3,work4;
	work1=0;
	work2=0;
	work3=0;
	work4=0;
    
	//std::cin >> N;
    //std::cin >> N >> M;
    //std::cin >> N >> M >> K;
    
	std::vector<long long> v(3);
	//std::vector<long long> w(N);
    //std::cin >> s;
    
    
    // 配列入力1
    
    for(long long i=0; i<3; i++){
		std::cin >> v[i];
	}
	
	// 配列入力2
	/*
	for(long long i=0; i<N; i++){
		std::cin >> w[i];
	}
	*/
    
	
	//通常
	/*
    for(long long i=0; i<N; i++){
		
	}
	*/
	

	//文字列入力
	/*
	for(long long i=0; i<s.length(); i++){
		
		if(s[i]!='1'){
	}
	*/

	
	
	//ソート
    std::sort(v.begin(),v.end());//昇順ソート
    //std::sort(v.begin(),v.end(),std::greater<long long>());//降順ソート
    //std::sort(w.begin(),w.end());//昇順ソート
    //std::sort(w.begin(),w.end(),std::greater<long long>());//降順ソート
    /*
    
    //S.substr(i, 5);
    //S.size();
    
    for(long long i=0; i<N; i++){
		std::cin >> v[i];
		if(st.find(v[i])==st.end()){
			st.insert(v[i]);
		}
		else{
			st.erase(v[i]);
		}
	}
	*/


	/*
	int a[4];
	int value;
	value=0;
	
	a[0] = (value % 10); 
	value /= 10;// 1桁目を取り出す
	a[1] = (value % 10); 
	value /= 10;// 2桁目を取り出す
	a[2] = (value % 10); 
	value /= 10;// 3桁目を取り出す
	a[3] = (value % 10); 
	value /= 10;// 4桁目を取り出す
    work1=a[0]+10*a[1];
    work2=a[2]+10*a[3];
    */
	
	
    if(1){
    	printf("%d",v[0]+v[1]);
    	//printf("%lld",N);
    	//puts("Yes");
    	//printf("%d",st.size());
    	//文字列の出力
    	//std::cout << s << std::endl;
    	//printf("%.12f\n",ret);
    	//cout << sum << endl;
	}
	else{
		//puts("No");
	}
	return 0;
}


Measured memory_bytes: 256
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
    ll n,m;
    cin>>n>>m;
    vl v;
    ll sum=0;
    rep(i,m)
    {
        ll c;
        cin>>c;
        sum+=c;
    }
    ll ans=n-sum;
    ans=max((ll)-1,ans);
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    //cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 15532
import math

def issq(x):
    sx = int(math.sqrt(x))
    return any([
        (sx - 1)**2 == x,
        sx**2 == x,
        (sx + 1)**2 == x,
    ])


def dist2(x, y):
    return sum((v - w)**2 for v, w in zip(x, y))


N, D = map(int, input().split())
X = []
for _ in range(N):
    X.append(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if issq(dist2(X[i], X[j])):
            ans += 1

print(ans)


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

long long int mod=1e9+7;

int main(){
  int n;
  cin>>n;
  vector<int> dp(100001,1e9);
  dp[0]=0;
  for(int i=0;i<dp.size()-1;i++){
    dp[i+1]=min(dp[i+1],dp[i]+1);
    int x=1;
    while(x+i<dp.size()){
      dp[i+x]=min(dp[i+x],dp[i]+1);
      x*=6;
    }
    x=1;
    while(x+i<dp.size()){
      dp[i+x]=min(dp[i+x],dp[i]+1);
      x*=9;
    }
  }
  cout<<dp[n]<<endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	string s;cin>>s;
	int cnt=0;
	for(int i=0,j=s.length()-1;i<=j;i++,j--)
	{	
		if(s[i]!=s[j])
		++cnt;
	}
	cout<<cnt;
}
int main()
{
//	int t;cin>>t;
//	while(t--)
	solve();
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int total = Integer.parseInt(sc.next());
        int oneYen = Integer.parseInt(sc.next());
        
        System.out.println((total%500)>oneYen?"No":"Yes");
    }
}


Measured memory_bytes: 20948
import java.util.*;
import static java.lang.System.*;
import java.math.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		boolean flag = true;
		int n = sc.nextInt();
		if (n % 2 == 1) {
			String s = sc.next();
			out.println("No");
		}else {
			char[] s = sc.next().toCharArray();
			int half = s.length / 2;
			for(int i = 0; i < half; i++) {
				if (s[i] != s[i + half]) {
					flag = false;
					break;
				}
			}	
			if (flag)out.println("Yes");
			else out.println("No");
		}		
	}
}

Measured memory_bytes: 22868
import sys
import socket
from collections import Counter

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('a1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    s = read_str()
    c = Counter(s)
    res = c['1']
    print(res)


main()


Measured memory_bytes: 3700