akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

// SegmentTree
template <class DataType>
class SegmentTree
{
public:
    using OpType = std::function<DataType(DataType, DataType)>;
    int N;
    std::vector<DataType> dat;
    DataType e; // identity element
    OpType op;

    SegmentTree(std::vector<DataType>& base,
        DataType e0, OpType op0): e(e0), op(op0)
    {
        N = 1;
        while(N < base.size()) N *= 2;
        dat.resize(2*N-1);
        for(int i=0; i<N; i++)
            dat[i+N-1] = (i<base.size()) ? base[i] : e;
        for(int i=N-2; i>=0; i--) dat[i] = op(dat[2*i+1], dat[2*i+2]);
    }
    SegmentTree(size_t sz,
        DataType e0, OpType op0): e(e0), op(op0)
    {
        N = 1;
        while(N < sz) N *= 2;
        dat.resize(2*N-1);
        for(auto& x: dat) x = e;
    }
    void update(int index, DataType value){
        int i = index + N-1;
        dat[i] = value;
        while(i > 0){
            i = (i-1) / 2;
            dat[i] = op(dat[2*i+1], dat[2*i+2]);
        }
    }
    DataType subQuery(int qleft, int qright, int tmp, int sleft, int sright){
        if(qleft <= sleft && sright <= qright) return dat[tmp];
        if(sright <= qleft || qright <= sleft) return e;

        int mid = (sleft + sright) / 2;
        return op(subQuery(qleft, qright, 2*tmp+1, sleft, mid),
            subQuery(qleft, qright, 2*tmp+2, mid, sright));
    }
    DataType query(int left, int right){
        return subQuery(left, right, 0, 0, N);
    }
    void print(){
        for(int i=N-1; i<2*N-1; i++) std::cout << dat[i] << " ";
        std::cout << std::endl;
    }
    DataType get(int index){
        return dat[index + N-1];
    }
};

int main()
{
    int N;
    cin >> N;
    vector<int> h(N), idx(N);
    vector<ll> a(N);
    for(auto& x: h) cin >> x;
    for(auto& x: a) cin >> x;
    for(int i=0; i<N; i++) idx[i] = i;
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return h[a] < h[b];
    });

    SegmentTree<ll> segtree(N, 0, [](ll a, ll b){
        return max(a, b);
    });
    for(auto& i: idx){
        ll m = segtree.query(0, i);
        segtree.update(i, m+a[i]);
    }

    cout << segtree.query(0, N) << endl;
}

Measured memory_bytes: 7424
#!/usr/bin/env python3


# Generated by 1.1.3 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():
    # Failed to predict input format
    N = int(input())
    if N == 1:
        print("Hello World")
    else:
        A = int(input())
        B = int(input())
        print(A+B)
    pass


if __name__ == '__main__':
    main()


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

typedef long long ll;
const int mod=1e9+7;

ll qpow(ll a,ll n){
    ll res=1;
    while(n){
        if(n&1)res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}

int n;

int main(){

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

    cin>>n;
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    cout<<(qpow(10,n)-qpow(9,n)*2+qpow(8,n)+mod*2)%mod<<endl;

    return 0;
}

Measured memory_bytes: 3652
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

//# include <ext/pb_ds/assoc_container.hpp>
//# include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;
 
//template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int u[N];
int ans, res;
int cur;
//	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//	shuffle(permutation.begin(), permutation.end(), rng);



int main () {
	cin >> k;
	cout << g[k-1];
	return Accepted;
}

// B...a

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

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

  string tmp = "";
  bool result = false;
  for(int i=0; i<6; i++){
    tmp = tmp + "hi";
    if(tmp == s){
      result=true;

    } 
  }

  if(result){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 10000
#define NIL -1


typedef struct Node{
	int p,l,r;
}Node;

Node T[MAX];
int n;

void preParse(int u);
void inParse(int u);
void postParse(int u);

int main(void){
	int i,v,l,r,root;
	
	scanf("%d", &n);
	for(i = 0;i < n; i++){
		T[i].p = NIL;
	}
	
	for(i = 0;i < n;i++){
		scanf("%d %d %d",&v,&l,&r);
		T[v].l = l;
		T[v].r = r;
		if(l != NIL)T[l].p = v;
		if(r != NIL)T[r].p = v;
	}
	
	for(i = 0;i < n;i++){
		if(T[i].p == NIL){
			root = i;
		}
	}
	
	printf("Preorder\n");
	preParse(root);
	printf("\n");
	printf("Inorder\n");
	inParse(root);
	printf("\n");
	printf("Postorder\n");
	postParse(root);
	printf("\n");
	
	return 0;
}

void preParse(int u){
	if(u == NIL)return;
	printf(" %d",u);
	preParse(T[u].l);
	preParse(T[u].r);
}

void inParse(int u){
	if(u == NIL)return;
	inParse(T[u].l);
	printf(" %d",u);
	inParse(T[u].r);
}

void postParse(int u){
	if(u == NIL)return ;
	postParse(T[u].l);
	postParse(T[u].r);
	printf(" %d",u);
}


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

int main() {
  int A,B;
  cin >> A >> B;
  if ( A == 1 && B == 2){
    cout << 3 << endl;
  }
  else if ( A == 1 && B == 3){
    cout << 2 << endl;
  }
  else if ( A == 2 && B == 1){
    cout << 3 << endl;
  }
  else if ( A == 2 && B == 3){
    cout << 1 << endl;
  }
  else if ( A == 3 && B == 1){
    cout << 2 << endl;
  }
  else if ( A == 3 && B == 2){
    cout << 1 << endl;
  }
}
    

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	int i;

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

	int K,T;
	cin >> K >> T;
	vector<int>a(T);
	for(i=0;i<T;i++) cin >> a[i];

	sort(a.begin(),a.end());
	int x=a[T-1],y=K-a[T-1];

	if(y>=x) cout << 0 << endl;
	else cout << x-y-1 << endl;

	return 0;
}


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

using namespace std;

typedef long long ll;

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;
}

const int MAX_N = 100000;
const int MAX_M = 100000;
const int MAX_S = MAX_N + 1;

int N, M;
char S[MAX_S + 10];
vector<int> res;

bool solve(int prev, int cur) {
    while (cur >= 0) {
        while (S[cur] == '1') {
            cur--;
        }
        if (prev - cur > M) return false;

        if (res[res.size() - 1] + prev - cur <= M) {
            res[res.size() - 1] += prev - cur;
        } else {
            res.push_back(prev - cur);
        }
        prev = cur;
        cur--;
    }

    return true;
}

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

    int prev = -1;
    res.push_back(0);
    for (int i = N - 1; i >= N - min(N, M); i--) {
        if (S[i] == '0') {
            prev = i;
            res[0] = N - i;
        }
    }
    if (prev < 0) {
        cout << -1 << endl;
        return 0;
    }

    if (solve(prev, N - min(N, M) - 1)) {
        reverse(res.begin(), res.end());
        cout << res[0];
        for (int i = 1; i < (int) res.size(); i++) {
            cout << " " << res[i];
        }
        cout << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}


Measured memory_bytes: 1020
#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))
//-------------------------------------------------------

ll A,B;


bool isprime(ll v) {
	for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
	return (v!=1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	ll C=__gcd(A,B);
	
	if(C==1) {
		cout<<1<<endl;
	}
	else {
		
		set<ll> S;
		S.insert(1);
		if(isprime(C)) S.insert(C);
		
		for(ll a=1;a*a<=C;a++) if(C%a==0) {
			if(isprime(a)) S.insert(a);
			if(isprime(C/a)) S.insert(C/a);
		}
		cout<<S.size()<<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: 256
import static java.lang.System.*;
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int n = sc.nextInt();
		int[] ar = new int[n+1];
		int[] count = new int[10001];
		for (int i=1; i<n+1; i++) {
			int temp = sc.nextInt();
			ar[i] = temp;
			count[temp]++;
		}
		
		for (int i=1; i<10001; i++) {
			count[i] = count[i] + count[i-1];
		}

		int[] ans = new int[n+1];
		for (int i=n; i>=1; i--) {
			ans[count[ar[i]]] = ar[i];
			count[ar[i]]--;
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(ans[1]);
		for (int i=2; i<n+1; i++) sb.append(" "+ans[i]);
		out.println(sb);
	}
}


Measured memory_bytes: 547628
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define RFOR(i, s, n) for (int i = (n) - 1; i >= (s); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(a) a.begin(), a.end()
const long long MOD = 1e9 + 7, INF = 1e18;
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;}



signed main(){
	int N;
	cin>>N;
	vector<int>a(N);
	REP(i,N)cin>>a[i];
	int ans = 0;
	int ma = 0;
	RFOR(i,1,N){
		if(a[i]<=a[i-1])ans++;
		else ans = 0;
		CHMAX(ma,ans);
	}
	cout<<ma<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1e18;

struct SegmentTree{
private:
    int n;
    vector<int> node;
public:
    SegmentTree(int sz){
        n=1;
        while(n<sz)n*=2;
        node.resize(2*n-1);
        for(int i=0;i<n;i++){
            node[i+n-1]=INF;
        }
        for(int i=n-2;i>=0;i--){
            node[i]=min(node[2*i+1],node[2*i+2]);
        }
    }
    void update(int a,int x){
        a+=n-1;
        node[a]=x;
        while(a>0){
            a=(a-1)/2;
            node[a]=min(node[2*a+1],node[2*a+2]);
        }
    }
    int get(int a,int b=-1,int k=0,int l=0,int r=-1){
        if(b==-1)b=a+1;
        if(r==-1)r=n;
        if(b<=l||r<=a)return INT_MAX;
        if(a<=l&&r<=b){
            return node[k];
        }
        else{
            return min(get(a,b,2*k+1,l,(l+r)/2),get(a,b,2*k+2,(l+r)/2,r));
        }
    }
};

int main(){
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    SegmentTree seg(n+1);
    seg.update(n,0);
    for(int i=n-1;i>=0;i--){
        if(s[i]=='1')continue;
        int mn=seg.get(i,min(n+1,i+m+1));
        if(seg.get(i)>mn+1)seg.update(i,mn+1);
    }
    if(seg.get(0)==INF){
        cout<<-1<<endl;
        return 0;
    }
    int now=0;
    while(now!=n){
        for(int i=1;i<=m;i++){
            if(seg.get(now+i)==seg.get(now)-1){
                cout<<i<<" ";
                now=now+i;
                break;
            }
        }
    }
    cout<<endl;
}

Measured memory_bytes: 1664
def abc(A, B, C, D):
    # 答えの準備
    ans = 'No'
    
    # 比較
    while True:
        C -= B
        if C <= 0:
            ans = 'Yes'
            break
        A -= D
        if A <= 0:
            break
    
    # 答え
    return(ans)


# バッチスタート
if __name__ == "__main__":
    # 標準入力処理
    # 1行目の入力を空白で分割された4つの数値として扱う
    A, B, C, D = map(int, input().split())
    
    # 関数呼び出し
    f = abc(A, B, C, D)
    
    # 答えの出力
    print(f)


Measured memory_bytes: 9176
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int k = sc.nextInt();
        int sum = 0;
        if(a>=k) {
            sum = k;
            k=0;
        }else{
            sum = a;
            k -= a;
        }
        if(b>=k){
            k -= k;
        }else{
            k-=b;
        }
        if(k>0){
            sum -= k;
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 35516
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}

class UnionFind{
  vector<int> par,siz;
  //0-indexed
  void init(int n){
    component = n;
    par.resize(n);
    for(int i=0;i<n;++i)par[i]=i;
    siz.resize(n,1);
    msiz = 1;
  }
public:
  int msiz,component;
  UnionFind(int n_){init(n_);}
  int root(int x){
    if(par[x]==x)return x;
    return par[x] = root(par[x]);
  }
  void unite(int x,int y){
    x = root(x);
    y = root(y);
    if(x==y)return;
    siz[y] += siz[x];
    siz[x] = 0;
    par[x] = y;
    msiz = max(msiz,siz[y]);
    component--;
  }
  int size(int x){
    return siz[root(x)];
  }
  bool same(int x,int y){
    return root(x)==root(y);
  }
};


int main(){

  ll H,W,M;
  cin >> H >> W >> M;

  vector<P> h(300003),w(300003);
  map<P,ll> cnt;
  FOR(i,0,300002){
    h[i].second = i;
    w[i].second = i;
  }


  FOR(i,0,M){
    ll a,b;
    cin >> a >> b;
    h[a].first++;
    w[b].first++;
    cnt[{a,b}]++;
  }

  bool sub = true;
  SORT(h);REV(h);
  SORT(w);REV(w);

  FOR(i,0,300003){
    if(h[i].first < h[0].first)break;
    FOR(j,0,300003){
      if(w[j].first < w[0].first)break;
      if(cnt[{h[i].second,w[j].second}]==0){
        cout << h[0].first+w[0].first << endl;
        return 0;
      }
    }
  }

  cout << h[0].first+w[0].first-1 << endl;

}



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

typedef struct node{
  int key;
  struct node *parent;
  struct node *left;
  struct node *right;
} Node;

typedef Node *NodePointer;
NodePointer root = NULL;

NodePointer mNode(){
  NodePointer z = malloc(sizeof(Node));
  z->left = NULL;
  z->right = NULL;
  z->parent = NULL;
  z->key = 0;
  return z;
}

void insert(int key){

  NodePointer z = mNode();
  NodePointer y = NULL;
  NodePointer x = root;
  z->key = key;

  while(x != NULL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }
  z->parent = y;
  if(y == NULL) root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;
}

void inorder(NodePointer p){
  if(p != NULL){
    inorder(p->left);
    printf(" %d",p->key);
    inorder(p->right);
  }
}
void preorder(NodePointer x){
  if(x != NULL){
    printf(" %d",x->key);
    preorder(x->left);
    preorder(x->right);
  }
}

int find(NodePointer x, int key){

  if(x == NULL) return 0;
  else if(x->key == key) return 1;
  if(key < x->key)  return find(x->left,key);
  else  return find(x->right,key);

}

int main(void){

  int i,n,m,key;
  char str[20];

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",str);

    if(str[0] == 'i'){
      scanf("%d",&key);
      insert(key);
    }
    else if(str[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else{
      scanf("%d",&key);
      m = find(root,key);
      if(m == 1) printf("yes\n");
      else printf("no\n");
    }
  }
  return 0;
}



Measured memory_bytes: 20448
#include <iostream>
#include <vector>
#include <complex>
#include <map>
#include <algorithm>
using namespace std;

#define X(p)  ( (p).real() )
#define Y(p)  ( (p).imag() )

const double eps = 1e-10;
const double pi  = 3.14159265358979323846;

typedef double Num;
typedef complex<Num> Pt2;
typedef vector<Pt2> Polygon2;

struct Line2 : vector<Pt2> {
  Line2(Pt2 a, Pt2 b) { push_back(a); push_back(b); }
  Pt2 vec() { return (*this)[1]-(*this)[0]; }
};

Pt2  unit (Pt2 v)        { return v/abs(v);     }
Num  dist (Pt2 a, Pt2 b) { return abs(a-b);     }
Num  dot  (Pt2 a, Pt2 b) { return X(a*conj(b)); }
Num  cross(Pt2 a, Pt2 b) { return Y(conj(a)*b); }
bool equal(Num a, Num b) { return abs(a-b)<eps; }
bool equal(Pt2 a, Pt2 b) { return equal(X(a),X(b))&&equal(Y(a),Y(b)); }

bool intersectLS(Line2 s, Line2 t) {
  return cross(s.vec(), t[0]-s[0])
       * cross(s.vec(), t[1]-s[0]) < eps;
}

int main()
{
	int H,W,px=-1,py=-1,pd=-1;
	char e[602][602]={0};
	bool b[602][602]={0};

	cin>>H>>W;
	for(int y=1; y<=H; y++)
	for(int x=1; x<=W; x++)
	{
		char c; cin>>c;
		if(c=='#')
		{
			b[y][x] = 1;
			if(px==-1) { px=x; py=y; }
		}
	}

	for(int y=1; y<=H+1; y++)
	for(int x=1; x<=W+1; x++)
	{
		if(b[y][x]!=b[y-1][x  ]) e[y][x] |= 1;
		if(b[y][x]!=b[y  ][x-1]) e[y][x] |= 2;
	}

	Polygon2 g;
	while(true)
	{
		int d=-1;
		if     (e[py  ][px  ] & 1) { d=0; e[py  ][px  ]-=1; }
		else if(e[py  ][px  ] & 2) { d=1; e[py  ][px  ]-=2; }
		else if(e[py  ][px-1] & 1) { d=2; e[py  ][px-1]-=1; }
		else if(e[py-1][px  ] & 2) { d=3; e[py-1][px  ]-=2; }

		if(d==-1) break;
		if(d!=pd) g.push_back(Pt2(px-1,H+1-py));

		const int dx[] = {+1, 0,-1, 0};
		const int dy[] = { 0,+1, 0,-1};
		px+=dx[d]; py+=dy[d]; pd=d;
	}

	vector<Num> ang;
	map<Num,int> vtx;
	for(int i=0; i<g.size(); i++)
	{
		Num a=arg(g[i]), b=arg(g[(i+1)%g.size()]);
		ang.push_back(a);

		if(equal(a,b)) continue;
		if(a>b) swap(a,b);

		if(!vtx.insert(make_pair(a, 1)).second) vtx[a]++;
		if(!vtx.insert(make_pair(b,-1)).second) vtx[b]--;
	}

	sort(ang.begin(), ang.end());
	ang.erase(unique(ang.begin(), ang.end()), ang.end());

	int ans=0,cnt=0,idx=1;
	map<Num,int>::iterator it;
	for(it=vtx.begin(); it!=vtx.end(); it++)
	{
		while((ang[idx-1]+ang[idx])/2.0 < it->first && idx<ang.size())
		{
			ans=max(ans,cnt); idx++;
		}
		if(idx>=ang.size()) break;

		cnt += it->second;
	}

	cout << 1+ans/2 << endl;
}

Measured memory_bytes: 8392
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

int main() {
	int room[4][3][10];
	for(int i=0;i<4;i++) 
		for(int j=0;j<3;j++)
			for(int k=0;k<10;k++)
	    		room[i][j][k] = 0;
	    		
	int n;
	cin >> n;
	int  b,f,r,v;
	for(int i = 0; i < n; i++) {
		cin >> b >> f >> r >> v;
		room[b-1][f-1][r-1] += v;
	}
	
	for(int i=0;i<4;i++) {
		for(int j=0;j<3;j++) {
			for(int k=0;k<10;k++) {
				cout << " " << room[i][j][k];
			}
			cout << endl;
		}
		if (i<3) 
			cout << "####################" << endl;
	}
	return 0;
}




Measured memory_bytes: 3124
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main() {
  int N;

  cin >> N;

  for (int X=0; X<=N; X++) {
    if (X * 108 / 100 == N) {
      cout << X << endl;
      return 0;
    }
  }

  cout << ":(" << endl;

  return 0;
}


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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;
#define MAXN 101010
using namespace std;

int n;


struct BIT{
    // [1,n]
    int n; 
    vector<ll> bit;

    BIT(int _n){
        n = _n;
        bit = vector<ll>(n+1,0);
    }
    // sum of [1,i]
    ll sum(int i){
        ll s = 0;
        while(i>0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    // add x in i-th element
    void add(int i, ll x){
        while(i<=n){
            bit[i] += x;
            i += i & -i;
        }
    }
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 
	int M;
	cin >> n >> M;
	//vi a(MAXN , 0);
	vector<pii> seg[MAXN];
	rep(i , n){
		int l , r;
		cin >> l >> r;
		seg[r - l + 1].pb({l , r});
	}
	BIT bit(M + 1);
	int up_d = n;
	repi(d , M){
		for(pii i : seg[d]){
			bit.add(i.fi , 1);
			bit.add(i.se + 1 , -1);
			--up_d;
		}
		int ct = 0;
		for(int i = d ; i <= M ; i += d){
			ct += bit.sum(i);
		}
		die(up_d + ct);
	}
	return 0;
}

Measured memory_bytes: 8448
N = int(input())
A = list(map(int, input().split()))

if N == 0 and A[0] != 1:                            # N=0なら葉は1
    ans = -1
elif N != 0 and A[0] != 0:                          # N>0ならd=0の葉は0
    ans = -1
else:
    ans = 1                                         # 頂点合計
    node = 1                                        # 深さdの頂点
    lateFolia = sum(A)                              # 残りの葉
    preFolia = 0                                    # 深さd-1の葉

    for d in range(1, N+1):                         # d=0は初期値固定なのでd=1以降の計算
        folia = A[d]                                # 深さdの葉
        node = min((node-preFolia)*2, lateFolia)    # 深さdの頂点の上界 (以下の条件を満たすもの)
                                                    # ・深さd-1の頂点のうち葉ではないものの個数の2倍
                                                    # ・残りの葉の数 (*深さdも含む)

        if node < folia:                            # 頂点<葉はありえない
            ans = -1
            break

        ans += node                                 # 頂点合計を更新
        lateFolia -= folia                          # 残りの葉の数を更新
        preFolia = folia                            # 深さd-1の葉を記憶

print(ans)


Measured memory_bytes: 20136
#include <bits/stdc++.h>
using namespace std;
long long cnt[2100], tmp[2100] = {};
long long const mod = 2019;

void f() {
    for(int i=0; i<mod; ++i) {
        tmp[i] = cnt[i];
        cnt[i] = 0;
    }
    for(int i=0; i<mod; ++i) {
        cnt[i * 10 % mod] += tmp[i];
    }
}

int main() {
    string S;
    cin >> S;
    //string S = string(200000, '1');

    cnt[0] = 1;
    int cur = 0;
    long long res = 0;
    for(char c : S) {
        f();
        cur = (cur * 10 + (int)(c - '0')) % mod;
        res += cnt[cur];
        cnt[cur] += 1;
    }

    cout << res << '\n';
}

Measured memory_bytes: 3728
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int max = N/2;
		if(N%2 > 0) {
			max++;
		}
		if(max >= K) System.out.println("YES");
		else System.out.println("NO");
		
	}
	

}


Measured memory_bytes: 21460
use std::io::Read;

fn main() {
    let mut buf = String::new();

    std::io::stdin().read_to_string(&mut buf).unwrap();

    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let mut a: Vec<(usize, usize)> = vec![];

    for i in 0..n {
        a.push((i + 1, iter.next().unwrap().parse().unwrap()));
    }

    a.sort_by(|x, y| x.1.cmp(&y.1));

    for i in 0..n {
        print!("{} ", a[i].0);
    }
}


Measured memory_bytes: 8956
S = input()

bit = '0'
ans = [0, 0]
for i in S:
  if i == bit:
    ans[0] += 1
  if bit == '0':
    bit = '1'
  else:
    bit = '0'

bit = '1'
for i in S:
  if i == bit:
    ans[1] += 1
  if bit == '0':
    bit = '1'
  else:
    bit = '0'

print(min(ans))


Measured memory_bytes: 3188
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
typedef unsigned int ui;
int main(){
	int n, a, b, c, x,y;
	while (cin >> n >> a >> b >> c >> x) {
		if (n == 0)break;
		int check = 0;
		for (int i = 0; i < n; i++) {
			if (i > 0) {
				check++; x = (a*x + b) % c;
			}
			cin >> y;
			while (x != y&&check<=10000) {
				check++;
				x = (a*x + b) % c;
			}
		}
		if (check > 10000)cout << -1 << endl;
		else cout << check << endl;
	}
	return 0;
}


Measured memory_bytes: 2996
//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

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


Measured memory_bytes: 3624
import copy

N,M=map(int,input().split())
L=[list(map(str,input().split())) for i in range(M)]

for x in range(M):
    L[x][0]=int(L[x][0])

#print(N,M)
#print(L)

S=[]
component=[0,0]
for j in range(N):
    S.append(copy.deepcopy(component))

#print(S)

for k in range(1,M+1):
    if L[k-1][1]=='AC':
        if S[L[k-1][0]-1][0]==0:
            S[L[k-1][0]-1][0]=1
    else:
        if S[L[k-1][0]-1][0]==0:
            S[L[k-1][0]-1][1]+=1
    #print(S)

ansAC=0
ansWA=0

for l in range(N):
    ansAC+=S[l][0]
    if S[l][0]==1:
        ansWA+=S[l][1]

print(ansAC,ansWA)




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

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

    string s;
    cin >> s;
    if(s[0] == s[1] or s[1] == s[2] or s[2] == s[3]){
        cout << "Bad" << endl;
    }else{
        cout << "Good" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,c1,c2,c3,x[100010];
int main()
{
	int i,s,a,b,j,k;
	while(cin>>n)
	{
		c1=c2=c3=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&x[i]);
			if(!(x[i]%4)){c1++;continue;}
			if(!(x[i]%2)){c2++;continue;}
			c3++;
		}
		if(c2)c3++;
		if(c3<=c1+1)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <time.h>
#pragma warning(disable:4996) 

typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

typedef pair<ll,int> P;
vector<ll> dijkstra(int s, const vector<vector<pair<int,int> > >& G){
    priority_queue< P, vector<P>, greater<P> > que;
    vector<ll> d(G.size(), LINF);
    d[s] = 0;
    que.push(P(0, s));
    while(!que.empty()){
        int curr  = que.top().second;
        ll  dcurr = que.top().first;
        que.pop();
        if(d[curr] < dcurr) continue;
        int i;
        for(i=0; i<(int)G[curr].size(); i++){ 
            int next = G[curr][i].first;
            ll  dist = G[curr][i].second;
            if(d[next] > d[curr] + dist){
                d[next] = d[curr] + dist;
                que.push(P(d[next], next));
            }
        }
    }
    return d;
}

char str[1005][1005];

int ddx[4] = { 1 - 1,0,0 };
int ddy[4] = { 0,0,1,-1 };

#define POSI(x,y) ((x)*w+(y))
void solve()
{
    int h, w, cx, cy, dx, dy;
    scanf("%d%d%d%d%d%d", &h, &w, &cx, &cy, &dx, &dy); cx--; cy--; dx--; dy--;
    int i, j;
    for (i = 0; i < h; i++) {
        scanf("%s", str[i]);
    }

    vector<vector<pair<int, int> > > g(h*w);
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (str[i][j] == '#') continue;

            int p, q;
            for (p = -2; p <= 2; p++) {
                for (q = -2; q <= 2; q++) {
                    int i2 = i + p, j2 = j + q;
                    if (i2 < 0 || i2 >= h || j2 < 0 || j2 >= w) {
                        continue;
                    }
                    if (str[i2][j2] == '#') continue;
                    if (abs(p) + abs(q) == 1) {
                        g[POSI(i, j)].push_back(make_pair(POSI(i2, j2), 0));
                    }
                    else if (abs(p) + abs(q) > 0) {
                        g[POSI(i, j)].push_back(make_pair(POSI(i2, j2), 1));
                    }
                }
            }
        }
    }

    vector<ll> dist = dijkstra(POSI(cx, cy), g);
    if (dist[POSI(dx, dy)] == LINF) {
        printf("-1\n");
    }
    else {
        printf("%lld\n", dist[POSI(dx, dy)]);
    }
    return;
}

int main()
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for (t = 0; t < T; t++) {
        //printf("Case #%d: ", t + 1);
        solve();
    }
#endif
    return 0;
}


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

#define WHITE 0
#define RED   1
#define BLUE  2
#define EMPTY 3
#define rotate_swap(x,a,b,c,d) swap(x.a,x.b);swap(x.b,x.c);swap(x.c,x.d);

class Dice{
public:
  char top,front,right;
};

class state{
public:
  int y,x;
  Dice d[3][3];
  state(){}
  state(int ty,int tx);
  bool operator<(const state & a)const;

};

state::state(int ty,int tx){
  y=ty;
  x=tx;
  rep(i,3){
    rep(j,3){
      d[i][j].top  =WHITE;
      d[i][j].right=BLUE;
      d[i][j].front=RED;
    }
  }
}

void rotate_r(Dice &x){
  swap(x.top,x.right);
}

void rotate_l(Dice &x){
  swap(x.top,x.right);
}

void rotate_f(Dice &x){
  swap(x.top,x.front);
}

void rotate_b(Dice &x){
  swap(x.top,x.front);
}


int require(state &a,int tar[3][3]){
  int ret=0;
  rep(i,3){
    rep(j,3){
      if (i == a.y && j == a.x){
	if (tar[i][j] != EMPTY)ret++;
      }else if (tar[i][j] != a.d[i][j].top)ret++;
    }
  }
  return max(0,ret-1);
}

bool isok(state  &a,int tar[3][3]){
  rep(i,3){
    rep(j,3){
      if (i == a.y && j == a.x){
	if (tar[i][j] != EMPTY)return false;
      }else if (tar[i][j] != a.d[i][j].top)return false;
    }
  }
  return true;
}

int dx[]={0,0,1,-1};//
int dy[]={1,-1,0,0};//
int opp[] ={1,0,3,2};
int ans;
void move(state &a,int tar[3][3],int cnt,int prev){
  int h = require(a,tar);
  if (isok(a,tar)){
    ans=min(ans,cnt);
    return;
  }
  if (cnt + h >= ans)return;


  rep(i,4){
    if (opp[i]==prev)continue;
    state next=a;
    next.x+=dx[i];
    next.y+=dy[i];
    if (next.x==-1||next.x==3||next.y==-1||next.y==3)continue;
    next.d[a.y][a.x]=next.d[next.y][next.x];
    if (i == 0)rotate_b(next.d[a.y][a.x]);
    if (i == 1)rotate_f(next.d[a.y][a.x]);
    if (i == 2)rotate_l(next.d[a.y][a.x]);
    if (i == 3)rotate_r(next.d[a.y][a.x]);
    move(next,tar,cnt+1,i);
  }
}

main(){
  int x,y;
  while(cin>>x>>y && x){
    x--;y--;
    int tar[3][3];
    state ini(y,x);
    
    rep(i,3){
      rep(j,3){
	char tmp;
	cin>>tmp;
	if (tmp == 'W'){
	  tar[i][j]=WHITE;
	}else if (tmp == 'E'){
	  tar[i][j]=EMPTY;
	}else if (tmp == 'B'){
	  tar[i][j]=BLUE;
	}else if (tmp == 'R'){
	  tar[i][j]=RED;
	}
      }
    }

    ans = 31;
    move(ini,tar,0,-1);
    if (ans == 31)cout << -1 << endl;
    else cout << ans << endl;
  }
}

Measured memory_bytes: 864
n,k = map(int,input().split())

ab = []
for i in range(n):
  ta,tb = map(int,input().split())
  ab.append([ta,tb])

ab = sorted(ab,key=lambda x:x[0])

count = k
for i in range(n):
  count -= ab[i][1]
  if count <= 0:
    print(ab[i][0])
    break

Measured memory_bytes: 22144
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pllll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int, int> > vii;
typedef vector< pair<long long, long long> > vllll;
typedef map<int, int> mii;
typedef map<long long, long long> mllll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0ll)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
#define bitsum(x) __builtin_popcount(x)
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a / gcd(a, b) * b;
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
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;
}

int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 0;
  // ll n;
  // cin >> n;
  ll n, k;
  cin >> n >> k;
  // ll n, m, k;
  // cin >> n >> m >> k;
  ans += pow(n / k, 3);
  if(k % 2 == 0) {
    int num = n / k;
    if(n % k >= k / 2) num++;
    ans += pow(num, 3);
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  ll INF = 2000000000000000000;
  vll a(n);re(i, n) std::cin >> a[i];
  vvl dp = VV(n/2+1, 5, -INF, ll);

  for(int i=1;i<=n/2;i++){
    for(int j=0;j<5;j++){
      if((i-1)*2+j>=n) continue;
      ll num = a[(i-1)*2 + j];
      if(i==1){
        dp[1][j] = num;
      }else{
        for(int k=0;k<=j;k++) {
          dp[i][j] = max(dp[i][j], dp[i-1][k] + num);
        }
      }
    }
  }
  ll ans = -INF;
  for(int i=0;i<5;i++) ans = max(ans, dp[n/2][i]);
  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 11584
K, N = map(int,input().split())
A = [int(i) for i in input().split()]
dt = [0]*N
for i in range(len(A)-1):
  dt[i] = abs(A[i+1]-A[i])
dt[-1] = (K-A[-1])+A[0]
print(sum(dt)-max(dt))


Measured memory_bytes: 26444
#ABC071 D - Coloring Dominoes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n=int(input())
s1=list(input())
s2=list(input())
i=0
mod=1000000007
 
ans=0
p=0
while i<n:
    if s1[i]==s2[i]:
        # 今回パターン1
        if p==0:
            ans=3
        elif p==1:
            ans*=2
            ans=ans%mod
        elif p==2:
            ans*=1
            ans=ans%mod
        i+=1
        p=1
    else:
        # 今回パターン2
        if p==0:
            ans=6
        elif p==1:
            ans*=2
            ans=ans%mod
        elif p==2:
            ans*=3
            ans=ans%mod
        i+=2
        p=2
print(ans)



Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
int main() 
{

    int n;
    cin>>n;
    cout<<24-n+24<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
  int kotae=0;
  int A[3];
  for(int i=0;i<3;i++){
    cin >> A[i];
  }

  sort(A,A+3);
  kotae=A[0]+A[1];

  cout << kotae << endl;


  return 0;
}


Measured memory_bytes: 256
//Created Time:2019年12月18日 星期三 10时13分52秒
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define N 200005

using namespace std;

int n, m, cnt;
int a[N], b[N], c[N], d[N];
bool vis[N];
long long k;

vector < int > g[N];

int read();

int main(){
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read(), c[i] = i;
	for(int i = n; i; --i) a[i] -= a[i - 1];
	m = read(); cin >> k;
	for(int i = 1; i <= m; ++i)
		b[i] = read(), swap(c[b[i]], c[b[i] + 1]);
	for(int i = 1; i <= n; ++i){
		if(vis[i]) continue;
		int now = i; ++cnt;
		while(!vis[now]) 
			g[cnt].push_back(now), vis[now] = true, now = c[now];
	}
	for(int i = 1; i <= cnt; ++i){
		int sz = g[i].size(), tmp = k % sz;
		for(int j = 0; j < sz; ++j)
			d[g[i][(j - tmp + sz) % sz]] = g[i][j];
	}
	long long ans = 0;
	for(int i = 1; i <= n; ++i)
		ans += a[d[i]], printf("%.1lf\n",(double)ans);
	return 0;
}

int read(){
	int x = 0, f = 0; char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) f |= (ch == '-');
	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return f ? -x : x;
}


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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
// 出力は.xで！！！！

int main(){
  int n,k; cin >> n >> k;
  vector<vector<int> > ki(n);
  rep(i,n-1){
    int a,b; cin >> a >> b;
    a--; b--;
    ki[a].push_back(b);
    ki[b].push_back(a);
  }
  vector<int> ko(n,0);
  queue<P> nord;
  nord.push(P(0,-1));
  mint ans=1;
  while(!nord.empty()){
    int now=nord.front().first;
    int par=nord.front().second;
    nord.pop();
    if(par==-1) ans*=k;
    else{
      int num=2;
      if(par==0) num=1;
      ans*=k-(num+ko[par]);
      ko[par]++;
    }
    rep(i,ki[now].size()){
      if(ki[now][i]==par) continue;
      nord.push(P(ki[now][i],now));
    }
    //cout << ans.x << endl;
  }
  cout << ans.x << endl;
return 0;
}

Measured memory_bytes: 7288
N = int(input())
fact = {}
for p in range(1,N+1):
    pf={}
    m=p
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1

    for key,value in pf.items():
        if key in fact.keys():
            fact[key] += value
        else:
            fact[key] = value

L = list(fact.values())
n75 = 0
n25 = 0
n15 = 0
n5 = 0
n3 = 0
n1 = 0
for m in L:
    m += 1
    if m>=75:
        n75+=1
    if m>=25:
        n25+=1
    if m>=15:
        n15+=1
    if m>=5:
        n5+=1
    if m>=3:
        n3+=1
    if m>=1:
        n1+=1

cnt = []
cnt.append(n75)
cnt.append(n25*(n3-1))
cnt.append(n15*(n5-1))
cnt.append(( n5*(n5-1)//2 )*(n3-2))
# print(n1,n3,n5,n15,n25,n75)
# print(cnt)
print(sum(cnt))

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

int main()
{
  int n, a[110];
  cin >> n;
  bool ok = true;
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    if (a[i] % 2 == 0)
    {
      if (a[i] % 3 != 0 && a[i] % 5 != 0) //否定を取った方がいい
        ok = false;
    }
  }
  if (ok)
     cout << "APPROVED" << endl;
  else
     cout << "DENIED" << endl;
}

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

using namespace std;
typedef unsigned long long ullong;

ullong power(ullong x, ullong n, ullong M){
	ullong res = 1;
	if(n > 0){	
		res = power(x, n / 2, M);
		if(n % 2 == 0) res = (res * res) % M;
		else res = (((res * res) % M) * x) % M;
	}
	return res;
}

int main(){
	int m, n;
	cin >> m >> n;
	cout << power(m, n, 1000000007) << endl;
	return 0;
}

Measured memory_bytes: 3112
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct HPQ{
	int h, p, q;
};

int main(void){
	while(1){
		int n, m, a; cin >> n >> m >> a;
		if(!n && !m && !a) break;
		vector<HPQ> hpq(m);
		int max_h = -1;
		for(int i=0; i<m; i++){
			cin >> hpq[i].h >> hpq[i].p >> hpq[i].q;
			max_h = max(max_h, hpq[i].h);
		}
		sort(hpq.begin(), hpq.end(), [](auto const& l, auto const& r){
			return l.h > r.h;
			});
		//cout << hpq[0].h << hpq[0].p << hpq[0].q << endl;

		int j = 0;
		int pos = a;
		for(int i=max_h; i>=0; i--){
			if(j >= hpq.size()) break;
			while(i == hpq[j].h){
				if(pos == hpq[j].q) pos = hpq[j].p;
				else if(pos == hpq[j].p) pos = hpq[j].q;
				j++;
				if(j >= hpq.size()) break;
			}
		}
		cout << pos << endl;
	}
}


Measured memory_bytes: 3032
#include <bits/stdc++.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

ll mod(ll a, ll b){
  ll ret=a%b;
  if(ret<0) ret+=b;
  return ret;
}

ll modpow(ll a,ll b,ll c){
  ll res=1;
  while(b>0){
    if(b&1) res=mod(res*a,c);
    a=mod(a*a,c);
    b>>=1;
  }
  return res;
}

int GCD(int x,int y){
  if(x<y){
    swap(x,y);
  }
  while(x%y!=0){
    int temp=x;
    x=y;
    y=temp%y;
  }
  return y;
}

int digitsum(int x){
  int sum=0;
  while(x>0){
    sum+=(x%10);
    x/=10;
  }
  return sum;
}

int main() {
  string s;
  cin>>s;
  int f=s.size();
  if(s[f-1]=='s') cout<<s+"es"<<endl;
  else cout<<s+"s"<<endl;
  return 0;
}

Measured memory_bytes: 3636
import numpy as np
W, H, N = map(int, input().split())
x = []
y = []
a = []
for _ in range(N):
    b, c, d = map(int, input().split())
    x.append(b)
    y.append(c)
    a.append(d)
A = np.zeros((H, W))

for i in range(N):
    if a[i] == 1:
        for j in range(x[i]):
            for k in range(H):
                A[k][j] = 1
    elif a[i] == 2:
        for j in range(x[i],W):
            for k in range(H):
                A[k][j] = 1
    elif a[i] == 3:
        for j in range(y[i]):
            for k in range(W):
                A[j][k] = 1
    elif a[i] == 4:
        for j in range(y[i], H):
            for k in range(W):
                A[j][k] = 1

print(np.sum(A==0))


Measured memory_bytes: 19492