akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

template <ll mod>
struct ModCombination{
    ll N;
    vector<ll> fact,inv,finv;

    ModCombination(ll n):N(n){
        fact.assign(n+1, 1);
        inv.assign(n+1, 1);
        finv.assign(n+1,1);
        for(int i=1;i<n;i++){
            fact[i+1] = fact[i]*(i+1)%mod;
            inv[i+1] = inv[mod%(i+1)]*(mod-mod/(i+1))%mod;
            finv[i+1] = finv[i]*inv[i+1]%mod;
        }
    }

    ll P(ll n,ll k){
        return (fact[n]*finv[n-k]%mod);
    }
};

int main(){
  int N;cin>>N;
    ModCombination<MOD> c(N+1);
  vector<pair<int,bool>> x(2*N);
  repeat(b,2){
    repeat(i,N){
      cin >> x[b*N+i].first;
      x[b*N+i].second = b;
    }
  }
  sort(x.begin(),x.end());
  ll ans=1;
  int cnt[2]={0,0};
  repeat(i,2*N){
    cnt[x[i].second]++;
    if(i==2*N-1||x[i].second!=x[i+1].second){
      int mi = min(cnt[0],cnt[1]);
      ans = (ans*c.P(cnt[!x[i].second],mi))%MOD;
      cnt[0] -= mi;
      cnt[1] -= mi;
    }
  }
  cout << ans <<endl;
}


Measured memory_bytes: 4224
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner scn = new Scanner(System.in);
		String s = scn.next();
		String[] list = s.split("");
      	int count = 0;
		for(int i=0; i<s.length(); i++){
			if(!(list[i].equals(list[s.length()-1-i]))) count++;
		}
      	System.out.println(count/2);
	}
}


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

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

    int h, w, a, b;
    cin >> h >> w >> a >> b;

    int x = h / a;
    int y = w / b;
    cout << h * w - x * a * y * b << endl;

    return 0;
}


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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

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

int N;
int ps[110];
int A, B;
int cnt[3];

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

    std::cin >> N;

    std::cin >> A >> B;

    for(int i=0;i<N;++i){
        std::cin >> ps[i];

        if(ps[i] <= A){
            cnt[0] += 1;
        }else if(ps[i] <= B){
            cnt[1] += 1;
        }else{
            cnt[2] += 1;
        }
    }

    int res = *std::min_element(cnt, cnt+3);
    std::cout << res << std::endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
queue<long long>q;
vector<long long>v;
int main()
{
	for(int i=1;i<=9;i++){q.push(i);v.push_back(i);}
	int kk;cin>>kk;
	for(int i=1;i<=100000;i++)
	{
		long long x=q.front();
		int k=x%10;
		q.pop();
		v.push_back(10*x+k);q.push(10*x+k);
		if(k!=0){v.push_back(10*x+k-1);q.push(10*x+k-1);}
		if(k!=9){v.push_back(10*x+k+1);q.push(10*x+k+1);}
 	}
	sort(v.begin(),v.end());
	cout<<v[kk-1]<<' ';
}

Measured memory_bytes: 7628
<?php
  	fscanf(STDIN,"%d",$x);
  	//fscanf(STDIN,"%d %d",$a,$b);

  	//$list = explode(" ",trim(fgets(STDIN)));
	$sum=100;
	$nen=0;
	for($i=0;$sum<$x;$i++){
      $sum=$sum+(int)($sum*0.01);
     
      $nen++;
    }
      
      echo $nen."\n";

Measured memory_bytes: 16048
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
 
struct Ses{
    int st, en, si;
};
 
int main(){
    string str;
    cin >> str;
    int n = str.size();
    int Ma = 0;
    stack<Ses> S;
    stack<int> slope;
    Ses temp; 

    for(int i = 0; i < n; i++){
        if(str[i] == '\\'){
            slope.push(i);
        } else if(str[i] == '/'){
            if(!slope.empty()){
                int b = slope.top();
                slope.pop();
                temp.st = b;
                temp.en = i;
                temp.si = i-b;
                Ma += temp.si;
                while( !S.empty() ){
                    if(temp.st < S.top().st){
                        temp.si += S.top().si;
                        S.pop();
                    } else {
                        break;
                    }
                }
                S.push(temp);
            }
        }
    }
    cout << Ma << endl;
    int m = S.size(), A[m];
    cout << m;
    for(int i = 0; i < m; i++){
        A[m - i - 1] = S.top().si;
        S.pop();
    }
    for(int i = 0; i < m; i++)
        cout << " " << A[i];
    cout << endl;
}

Measured memory_bytes: 1312
#include <iostream>
#include <algorithm>
using namespace std;
int n, q, xa, ya, xb, yb, x[5555], y[5555]; pair<int, int> p[5555];
int main() {
	scanf("%d%d", &n, &q);
	for(int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second);
	sort(p, p + n);
	for(int i = 0; i < n; i++) x[i] = p[i].first, y[i] = p[i].second;
	for(int i = 0; i < q; i++) {
		scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
		int l = lower_bound(x, x + n, xa) - x;
		int r = lower_bound(x, x + n, xb + 1) - x;
		int c = 0;
		for(int j = l; j < r; j++) {
			if(ya <= y[j] && y[j] <= yb) c++;
		}
		printf("%d\n", c);
	}
}

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

flag = True
ans_list = []
N = 1
while(flag == True):
	N = INT()
	if N == 0:
		flag = False
	else:
		A = LIST()
		A.sort()
		ans = abs(A[0] - A[1])
		for i in range(N - 1):
			ans = min(ans, abs(A[i] - A[i + 1]))
		ans_list.append(ans)

		# ans = abs(A[0] - A[1])
for ans in ans_list:
	print(ans)
	



Measured memory_bytes: 6868
#include <stdio.h>

int main(int argc, char **argv)
{
	int a,b,c;
	scanf("%d",&a);
	scanf("%d",&b);
	c = a % 500;
	if(b>=c)
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <math.h>
#include <utility>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main(){
	while(true) {
		int n;
		cin >> n;
		int m;
		cin >> m;
		if ( n == 0 ) break;
		int k;
		vector<int> roadh;
		vector<int> listh;
		for ( int i = 0; i < n; i++ ) {
			cin >> k;
			roadh.push_back(k);
			k = 0;
			for ( int j = i; j >= 0; j-- ) {
				k += roadh[j];
				listh.push_back( k );
			}
		}
		vector<int> roadw;
		vector<int> listw;
		for ( int i = 0; i < m; i++ ) {
			cin >> k;
			roadw.push_back(k);
			k = 0;
			for ( int j = i; j >= 0; j-- ) {
				k += roadw[j];
				listw.push_back( k );
			}
		}
		sort( listh.begin(), listh.end() );
		sort( listw.begin(), listw.end() );
		int start = 0;
		int sum = 0;
		int cnt = 0;
		for ( int i = 0; i < listh.size() ; i++ ) {
			if ( i != 0 ) {
				if ( listh[i] == listh[i-1] ) {
					sum += cnt;
					continue;
				}
			}
			cnt = 0;
			for ( int j = start; j < listw.size(); j++ ) {
				if ( listh[i] == listw[j] ) {
					cnt++;
				}else if ( listh[i] < listw[j] ) {
					start = j;
					break;
				}
			}
			sum += cnt;
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 22668
N = int(input())
P = list(map(int, input().split()))

def init_min(init_min_val):
    #set_val
    for i in range(N):
        seg_min[i+num_min-1]=init_min_val[i]    
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
    
def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res

#####単位元######
ide_ele_min = 10**10

#num_min:n以上の最小の2のべき乗
num_min =2**(N-1).bit_length()
seg_min=[ide_ele_min]*2*num_min
init_min(P)

answer = 1

for i in range(1, N):
    MIN = query_min(0, i)
    if MIN > P[i]:
        answer += 1

print(answer)

Measured memory_bytes: 24744
import copy

def judge1(masu,h,w):
    if (masu[0]>=0)&(masu[0]<h)&(masu[1]>=0)&(masu[1]<w):
        return True
    else:
        return False
    
def judge2(masu,s):
    if s[masu[0]][masu[1]] == '.':
        return True
    else:
        return False
    
def tsugi(i,j,h,w,s2):
    ans=[]
    for masu in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
        if judge1(masu,h,w):
            if judge2(masu,s2):
                ans.append(masu)
    return ans
    


def solve(i,j,s,h,w):
    ma = 0
    s2 = copy.deepcopy(s)
    if s2[i][j]=='.':
        s2[i][j]='#'
        nex = tsugi(i,j,h,w,s2)
        while len(nex)!=0 :
            ma+=1
            nex2=[]
            for n in nex:
                nex2[len(nex2):] = tsugi(n[0],n[1],h,w,s2)
                s2[n[0]][n[1]]='#'
            nex = set(nex2)
    return ma


h,w=map(int,input().split())
s = []
ma = 0
for i in range(h):
    s.append(list(input()))
for i in range(h):
    for j in range(w):
        ans = solve(i,j,s,h,w)
        ma = max(ma,ans)
print(ma)



Measured memory_bytes: 57692
#include<iostream>
#include<string>
using namespace std;
int main(){
	string a,b="C",c="F";
	cin>>a;
	int k1=a.find(b);
	a.erase(0,k1);
	int k2=a.find(c)+k1;
	if(k1<k2)cout<<"Yes";
	else cout<<"No"; 
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 100004
#define mp make_pair
#define pb push_back
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	long long n,k,i;
	cin>>n;
	n*=2;
	for(i=1;i<100000;i++){
		if(i*(i+1)>=n){
			break;
		}
	}
	cout<<i<<endl;
	return 0;
}

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

using namespace std;
using ll = long long;

template<class T> ostream& operator<<(ostream& os, const vector<T> arr){ for(ll i = 0; i < (ll)arr.size(); i++)cout << arr[i] << (i == (ll)arr.size() -1 ? "" : " "); return os;}
const ll MAX = 1000;

int main()
{
    ll n, k; cin >> n >> k;
    vector<ll> a(n);
    for(ll i = 0; i < n; i++)cin >> a[i];

    for(ll I = 0; k && I < MAX; I++) {
        vector<ll> imos(n + 1);
        for(ll i = 0; i < n; i++) {
            imos[max(i - a[i],0LL)] += 1;
            imos[min(i + a[i] + 1, (ll)n)] -= 1;
        }
        for(ll i = 0; i < n; i++){
            imos[i + 1] += imos[i];
            a[i] = imos[i];
        }
        k--;
    }

    cout << a << endl;
}   

Measured memory_bytes: 6424
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
int a,b,c;
cin>>a>>b>>c;
vector<char> ans;
map<char,int> mp;
mp['A']=a;
mp['B']=b;
mp['C']=c;
string str[n];
for(int i=0;i<n;i++)
{
    cin>>str[i];
}
if(a==0&&b==0&&c==0)
{
    cout<<"No"<<endl;
    return 0;
}

for(int i=0;i<n-1;i++)
{
 char val=str[i][0];
 char res=str[i][1];
 if(mp[val]==0)
 {
     mp[val]+=1;
     ans.pb(val);
     mp[res]-=1;
 }
 else if(mp[res]==0)
 {
     mp[res]+=1;
     ans.pb(res);
     mp[val]-=1;
 }
 else
 {
     if(val==str[i+1][0]||val==str[i+1][1])
     {
         mp[val]+=1;
         mp[res]-=1;
         ans.pb(val);
     }
     else
     {
         mp[val]-=1;
         mp[res]+=1;
         ans.pb(res);
     }
 }
 if(mp['A']<0||mp['B']<0||mp['C']<0)
    {
        cout<<"No"<<endl;
        return 0;
    }
}
char val=str[n-1][0];
 char res=str[n-1][1];
if(mp[val]==0)
 {
     mp[val]+=1;
     ans.pb(val);
     mp[res]-=1;
 }
 else
 {
     mp[res]+=1;
     ans.pb(res);
     mp[val]-=1;
 }
if(mp['A']<0||mp['B']<0||mp['C']<0)
    {
        cout<<"No"<<endl;
        return 0;
    }
cout<<"Yes"<<endl;
for(int i=0;i<ans.size();i++)
    cout<<ans[i]<<endl;
    return 0;
}


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

int main(){
  int n;
  cin>>n;
  ll ans=0,vec[n];
  for(int i=0;i<n;i++){
    cin>>vec[i];
  }
  ll sum=0,sumb=0;
  for(int i=0;i<n;i++){
    sum+=vec[i];
    if(i%2==0){
      if(sum<1){
        sumb+=1-sum;
        sum=1;
      }
    }
    if(i%2==1){
      if(sum>-1){
        sumb+=sum+1;
        sum=-1;
      }
    }
  }
  ans=sumb;
  sumb=0;
  sum=0;
  for(int i=0;i<n;i++){
    sum+=vec[i];
    if(i%2==0){
      if(sum>-1){
        sumb+=sum+1;
        sum=-1;
      }
    }
    if(i%2==1){
      if(sum<1){
        sumb+=1-sum;
        sum=1;
      }
    }
  }
  cout<<min(ans,sumb)<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define PI acos(-1)
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<typename T> using v2 = vector<vector<T>>;
template<typename T> using v3 = vector<vector<vector<T>>>;
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int MOD = 998244353;
const int INF = 1e9 + 200;
const ll INFLL = 2e18 + 200;

int main() {
    int H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;
    int start = H1 * 60 + M1;
    int end = H2 * 60 + M2;
    cout << (end - start) - K << endl;
}


Measured memory_bytes: 3624
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int A[51][51];
int B[51][51];
int C[51][51];
int R[53][53];
int a[53][53];
int H,W,h,w;

void view(){
  for(int i=0;i<=H;i++){
    for(int j=0;j<=W;j++){
      printf("%2d ",R[j][i]);
    }
    puts("");
  }
}
void init(){
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      a[j+1][i+1] = A[j][i];
    }
  }
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      R[j][i] = R[j-1][i]+a[j][i];
    }
  }
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      R[j][i] += R[j][i-1];
    }
  }
}
int get(int x,int y,int x2,int y2){
  //  printf("%d - %d - %d + %d\n",R[x2][y2+1] , R[x2][y+1] , R[x][y2+1] , R[x][y+1]);
  return R[x2][y2] - R[x2][y] - R[x][y2] + R[x][y];
}
int main(){
  cin >> H >> W;
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      cin >> A[j][i];
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      cin >> B[j][i];
  cin >> h >> w;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      cin >> C[j][i];

  init();
  // view();
  int res;
  bool flag = false;

  for(int y=0;y<H-h+1;y++){
    for(int x=0;x<W-w+1;x++){
      bool f = true;
      for(int y2=0;y2<h;y2++){
	if(!f)break;
	for(int x2=0;x2<w;x2++){
	  if( B[x+x2][y+y2] != C[x2][y2] ){
	    f=false; break;
	  }
	}
      }
      if( f ){
	if( !flag ){
	  //	  printf("%d %d %d %d\n",x,y,x+w,y+h);
	  res = get(x,y,x+w,y+h);
	  flag = true;
	} else {
	  res = max(res,get(x,y,x+w,y+h));
	}
      }
    }
  }
  if ( flag )
    cout << res << endl;
  else puts("NA");
}


Measured memory_bytes: 1212
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

  string s;
  cin >> s;

  int ans = 0;
  int now = 0;
  REP(i, N){
    if(s[i] == 'I'){
      now++;
      chmax(ans, now);
    }else now--;
  }

  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
 
using namespace std;
using namespace __gnu_pbds;
 
#define debug(s) cout << #s << " = " << s << endl
#define all(v) (v).begin(), (v).end()
#define mem(a,val) memset(a, val, sizeof a)
 
#define maxn 100010
#define INF 1e15
#define ff first
#define ss second
#define endl '\n'
typedef long long ll;
 
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  cout << max(a + b, max(a * b, a - b)) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int n;
int main(){
    cin>>n;
    rep(i,10){
        rep(j,10){
            if(i*j==n){
                cout<<"Yes"<<endl;
                return 0;
            }
        }

    }
    cout<<"No"<<endl;
    return 0;
}




Measured memory_bytes: 256
N = int(raw_input())
A = map(int,raw_input().split())

B = []
for i in range(N):
    B.append(A[i]-i-1)
    
B.sort()


count = 0
b=B[N/2]
for i in range(N):
    count += abs(B[i]-b)
print count
    

Measured memory_bytes: 22228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const int mod = 1e9 + 7;

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

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = 0, d = 0;
    ll r = 0, g = 0, b = 0;
    for (int i = 0; i < n; i++)
    {
        if (s.at(i) == 'R')
        {
            r++;
        }
        else if (s.at(i) == 'G')
        {
            g++;
        }
        else
        {
            b++;
        }
    }
    ans = r * g * b;

    for (int i = 0; i < n - 2; i++)
    {
        char fst = s.at(i);
        for (int j = i + 1; j < n - 1; j++)
        {
            char sec = s.at(j);
            if (fst == sec)
            {
                continue;
            }
            else
            {
                if (2 * j - i < n)
                {
                    char thr = s.at(2 * j - i);
                    if (fst != thr && sec != thr)
                    {
                        d++;
                    }
                }
                else
                {
                    break;
                }
            }
        }
    }

    ans -= d;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
using namespace std;
int main() 
{
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	if(a+b>c+d){
    	cout << "Left" << endl;
    }
	else if(a+b<c+d){
    	cout << "Right" << endl;
    }
	else{
    	cout << "Balanced" << endl;
    }
	return 0;
}


Measured memory_bytes: 256
t_health, t_strength, a_health, a_strength = (int(i) for i in input().split())

while t_health > 0 and a_health > 0:
  a_health -= t_strength
  if a_health <= 0:
    print('Yes')
    break
  t_health -= a_strength
  if t_health <= 0:
    print('No')
    break


Measured memory_bytes: 9016
#include<iostream>

using namespace std;

int main(void){
  int N;
  cin >> N;
  int ans = 0;
  for(int n = 1; n <= N; n += 2){
    int c = 0;
    for(int i = 1; i <= n; i++){
      if(n % i == 0) c++;
    }
    if(c == 8) ans++;
  }
  cout << ans << endl;
  return 0;
}


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

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

    for(int i=0; i<=N; i++){
        if(i%3!=0 && i%5!=0){
            ans += i;
        }
    }

    cout << ans << endl;
}

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

#include <boost/algorithm/string/classification.hpp>  // is_any_of
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/math/tools/minima.hpp>
#include <boost/multi_array.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/optional.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>

const int MOD = 1e9 + 7;
#define rep(i, n) for (int i = 0; i < (n); ++i)

namespace adaptor = boost::adaptors;
using namespace std;
using boost::irange;
using boost::algorithm::join;
using boost::algorithm::replace_all;
using boost::algorithm::split;
using boost::math::tools::brent_find_minima;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;

// TOP
void Main()
{
	int n;
	cin >> n;

	ll sum;
	sum = 0;
	rep(i, n)
		sum += i;
	cout << sum << endl;
}
// END

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 256
A = list(map(int, input().split()))
if A.count(A[0]) == 3:
    print("1")
elif A.count(A[0]) == 2:
    print("2")
elif A.count(A[0]) == 1:
    if A.count(A[1]) == 1:
        print("3")
    else:
        print("2")


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

signed main(){
	int n;
	std::cin >> n;
	std::vector<ll> a(n);
	for(int i = 0; i < n; i++) std::cin >> a[i];
	ll ans = 1000;
	for(int i = 0; i < n - 1; i++){
		if(a[i] < a[i + 1]){
			ans += (a[i + 1] - a[i]) * (ans / a[i]);
		}
	}
	std::cout << ans << std::endl;
}

Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
#define EF emplace_front
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

const int MAX = 55;
const int MAX_VAL = 1e6;
int N;
LL a[MAX];

int main(void) {
    cin >> N;
    LL ma = -MAX_VAL, mi = MAX_VAL;
    int maId = -1, miId = -1;
    REP(i, N) {
        cin >> a[i];
        if (chmax(ma, a[i])) {
            maId = i;
        }
        if (chmin(mi, a[i])) {
            miId = i;
        }
    }
    deque<PII> ans;
    if (mi <= 0 && ma <= 0) {
        REP(i, N - 1) {
            ans.EF(i + 1, i);
        }
    } else if (mi >= 0 && ma >= 0) {
        REP(i, N - 1) {
            ans.EB(i, i + 1);
        }
    } else {
        // mi < 0 && ma > 0
        if (llabs(mi) <= llabs(ma)) {
            REP(i, N) {
                ans.EB(maId, i);
            }
            REP(i, N - 1) {
                ans.EB(i, i + 1);
            }
        } else {
            REP(i, N - 1) {
                ans.EF(i + 1, i);
            }
            REP(i, N) {
                ans.EF(miId, i);
            }
        }
    }

    cout << ans.size() << endl;
    FORE(e, ans) {
        cout << e.first + 1 << " " << e.second + 1 << endl;
    }

    FORE(e, ans) {
        a[e.second] += a[e.first];
    }
    cerr << (is_sorted(a, a + N) ? "YES" : "NO") << endl;
    REP(i, N) {
        cerr << a[i] << " ";
    }cerr << endl;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
edge = set()
h = 0
w = 0

for i in range(N):
    if A[i] in edge:
        if A[i] > h:
            h,w = A[i],h
        elif A[i] > w:
            w = A[i]
        edge.remove(A[i])
    else:
        edge.add(A[i])

print(h*w)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>

#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i, s, n) for(int i=s; i<n; i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
//	std::cout<<std::fixed<<std::setprecision(10);


int main() {
  string S;
  cin >> S;
  if(S=="AAA" || S=="BBB") {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }

  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int main(){
	priority_queue<int>q;
	int m,n,t;
	cin >>n>>m;
	for(int i=0;i<n;i++){
		cin>>t;
		q.push(t);
	}
	long long sum=0;
	while(m){
		t=q.top()/2;
		q.pop();
		q.push(t);
		m--;
	}
	while(!q.empty()){
		sum+=q.top();
		q.pop();
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n, k; cin >> n >> k;
    set<int> st;
    rep(i,k) {
        int d; cin >> d;
        rep(i,d) {
            int a; cin >> a;
            st.insert(a);
        }
    }
    cout << n - st.size() << endl;
}

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

void cycle(string &str){
    int n = str.size();
    int last_w = str[n-1];
    for(int i=n-1;i>=0;i--){
        str[i] = str[i-1];
    }
    str[0] = last_w;
}

int main(){
    string s,t;
    cin >> s >> t;
    int n = t.size();
    string ans = "No";
    int i = 0;
    while(i != n){
        if(t == s){
            ans = "Yes";
            break;
        }
        cycle(t);
        i++;
    }
    cout << ans << endl;
}


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

int main() {
    int64_t a,b,n;
    cin >> a >> b;
    n = b-a;
    cout << n*(n+1)/2-b << endl;
}

Measured memory_bytes: 3612
import java.util.*;

class Main{

    int n;
    String[] a, b;
    String start, goal;

    void solve(){
        Scanner sc = new Scanner(System.in);

        while(true){
            n = sc.nextInt();
            if(n==0) break;
            a = new String[n];
            b = new String[n];
            for(int i=0; i<n; i++){
                a[i] = sc.next();
                b[i] = sc.next();
            }
            start = sc.next();
            goal = sc.next();

            System.out.println(bfs());
        }
    }

    int bfs(){
        //pos, line
        Queue<String[]> q = new LinkedList<String[]>(); 
        HashSet<String> set = new HashSet<String>();
        q.add(new String[]{"0", start});
        set.add(start);

        while(q.size()>0){
            String[] qq = q.poll();
            int pos = Integer.parseInt(qq[0]);
            String line = qq[1];

            if(line.equals(goal)) return pos;

            for(int j=0; j<n; j++){
                StringBuffer sb = new StringBuffer();
                for(int i=0; i<line.length(); i++){
                    if(i+a[j].length()<=line.length() && a[j].equals(line.substring(i, i+a[j].length()))){
                        sb.append(b[j]);
                        i = i+a[j].length()-1;
                    }else sb.append(line.substring(i,i+1));
                }
                String newS = sb.toString();
                if(line.equals(newS) || !set.add(newS) || newS.length()>=101) continue;
                q.add(new String[]{String.valueOf(pos+1), newS});
            }
        }
        return -1;
    }

    public static void main(String[] args){
        new Main().solve();
    }
}

Measured memory_bytes: 92720
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int main()
{
  int n, x;
  cin >> n >> x;

  int m[n];
  int min_m = INT_MAX;

  for (int i = 0; i < n; i++) {
    cin >> m[i];
    // 一番素を消費しないドーナツのインデックスを保存する
    if (m[i] < min_m) min_m = m[i];
    x -= m[i];
  }

  cout << n + x / min_m << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int main() {
	int n, m;
	cin >> n >> m;
	vector<P>ba(m);
	vector<int>bridge;
	for (int i = 0; i < m; i++) {
		cin >> ba[i].second >> ba[i].first;
	}
	int ans = 1;
	sort(ba.begin(), ba.end());
	bridge.push_back(ba[0].first - 1);
	for (int i = 1; i < m; i++) {
		if (ba[i].second > bridge[bridge.size() - 1]) {
			ans++;
			bridge.push_back(ba[i].first - 1);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <queue>
#include <set>
#include <list>
#include <deque>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <iterator>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define powr(x,n,p) for(int axy=0 ; axy<p ; axy++){x=x*n;}
#define YES printf("YES\n")
#define Yes printf("Yes\n")
#define yes printf("yes\n")
#define NO printf("NO\n")
#define No printf("No\n")
#define no printf("no\n")
#define nl printf("\n")
#define fr0(n,q) for(q=0 ; q<n ; q++)
#define fr1(n,q) for(q=1 ; q<=n ; q++)
#define mp make_pair
#define scl(x) scanf("%lld",&x)
#define sci(x) scanf("%d",&x)
#define lst(x) x[x.size()-1]
#define llst(x) x[x.size()-2]
#define md 1000000007
#define check(x,y) (x&(1<<y))
#define set(x,y) x=x|(1<<y)
using namespace std;
int dp[3005][3005];
string s,t,ans;
int k;
int solve(int i, int j){
	if(i>=s.size() || j>=t.size()) return dp[i][j]=0;
	if(dp[i][j]!=-1) return dp[i][j];
	int ret;
	if(s[i]==t[j]) ret=1+solve(i+1,j+1);
	else{
		ret=solve(i,j+1);
		int x=solve(i+1,j);
		if(x>ret) ret=x;
	}
	return dp[i][j]=ret;
}
void build(int i,int j){
	if(dp[i][j]<=0) return ;
	if(s[i]==t[j]){
		ans.pb(s[i]);
		build(i+1,j+1);
	}
	else{
		if(dp[i+1][j]>dp[i][j+1]) build(i+1,j);
		else build(i,j+1);
	}
}
int main()
{
	cin>>s>>t;
	int i,j;
	fr0(3005,i){
		fr0(3005,j) dp[i][j]=-1;
	}
	k=solve(0,0);
/*	for(i=0 ; i<=s.size() ; i++){
		for(j=0 ; j<=t.size() ; j++) cout<<dp[i][j]<<"   ";
		nl;
	}*/
	build(0,0);
	cout<<ans;
	nl;
	return 0;
}


Measured memory_bytes: 39228
#include<bits/stdc++.h>
using namespace std;
long long  n,m;
int main(){
	cin>>n>>m;
	if(2*n==m) cout<<n<<endl;
	if(n*2>m){
		cout<<m/2<<endl;
	}
	if(n*2<m){
		long long sum=0;
		sum+=n;
		m=m-n*2;
		cout<<sum+m/4<<endl;
	}
	return 0;
} 

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

int main() {
	string S;
	cin >> S;
	long long p = 0, cnt = 0;
	for (int i = 0; i < (int)S.size(); i++) {
		if (S.at(i) == 'W') {
			cnt += (i - p);
			p++;
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 640
#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>;
using vv = vector<vector<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 long long inf = 1ll << 60;
const long long mod = 1000000007;

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

int main() {
    cout.precision(17);
    int a,b,h,m;cin >> a >> b >> h >> m;
    double pi = 3.14159265358979;
    double a_t = 1/12.0*2*pi*h+1/(12.0*60)*2*pi*m;
    double b_t = (1/60.0) * m * 2 * pi;
    cout << sqrt(pow(a*cos(a_t)-b*cos(b_t),2)+pow(a*sin(a_t)-b*sin(b_t),2));
    return 0;
}


Measured memory_bytes: 4164
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int p,r,T;
int N[300][300];
vector<int> L,P,R;

bool isAvoidable(int t){
    int H[p][r];
    fill(H[0],H[p],0);
    vector<int> LL=L;
    for(int i=0;i<t;i++){
        H[P[i]][R[i]]++;
        LL[R[i]]--;
    }
    vector<int> satisfied(p);
    for(int i=0;i<p;i++){
        satisfied[i]=true;
        for(int j=0;j<r;j++){
            if(N[i][j]!=H[i][j]){
                satisfied[i]=false;
                break;
            }
        }
        if(satisfied[i]){
            for(int j=0;j<r;j++){
                LL[j]+=H[i][j];
            }
        }
    }
    bool updated=true;
    while(updated){
        updated=false;
        for(int i=0;i<p;i++){
            if(satisfied[i]) continue;
            bool satisfiable=true;
            for(int j=0;j<r;j++){
                if(H[i][j]+LL[j]<N[i][j]){
                    satisfiable=false;
                    break;
                }
            }
            if(satisfiable){
                satisfied[i]=true;
                for(int j=0;j<r;j++){
                    LL[j]+=H[i][j];
                }
                updated=true;
            }
        }
    }
    bool ret = true;
    for(int i=0;i<p;i++){
        if(!satisfied[i]){
            ret=false;
            break;
        }
    }
    return ret;
}

int main(){
    cin>>p>>r>>T;
    L.resize(r);
    for(int i=0;i<r;i++) cin>>L[i];
    for(int i=0;i<p;i++){
        for(int j=0;j<r;j++){
            cin>>N[i][j];
        }
    }
    P.resize(T); R.resize(T);
    for(int i=0;i<T;i++){
        cin>>P[i]>>R[i];
        P[i]--; R[i]--;
    }
    if(!isAvoidable(0)){
        cout<<0<<endl;
        return 0;
    }
    if(isAvoidable(T)){
        cout<<-1<<endl;
        return 0;
    }
    int lo=0,up=T;
    while(up-lo>=2){
        int mid = (lo+up)/2;
        if(isAvoidable(mid)){
            lo=mid;
        }else{
            up=mid;
        }
    }
    cout<<up<<endl;

    return 0;
}

Measured memory_bytes: 5216
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define maxn 1000006
#define mod 1000000007
#include <bits/stdc++.h>
using namespace std;

string s;
ll n, dp[maxn][2];

ll rec(ll pos, ll flag){
    if(dp[pos][flag] != -1) return dp[pos][flag];
    if(pos == n) return 0;
    ll x = s[pos] - '0';
    if(flag) x ++;
    ll res = min(x + rec(pos+1, 0), 10 - x +  rec(pos+1, 1));
    return dp[pos][flag] = res;
}

int main() {
    memset(dp, -1, sizeof dp);
    cin >> s;
    reverse(s.begin(), s.end());
    s += '0';
    n = s.size();
    cout << rec(0, 0) << endl;


    return 0;
}

/*
.......................
.......................
..... MY CODES ARE ....
... UGLIER THAN YOU ...
.......................
.......................
*/


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

// @@ !! LIM(f:updMaxMin)
// --> f:updMaxMin
// ---- inserted function updMaxMin from util.cc
template<typename T>
bool updMax(T& tmax, const T& x) {
  if (x > tmax) { tmax = x; return true;  }
  else          {           return false; }
}
template<typename T>
bool updMin(T& tmin, const T& x) {
  if (x < tmin) { tmin = x; return true;  }
  else          {           return false; }
}
// ---- end updMaxMin
// @@ !! LIM  -- end mark --

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  vector<ll> t(N), v(N);
  for (ll i = 0; i < N; i++) {
    ll x; cin >> x;
    t.at(i) = 2 * x;
  }
  for (ll i = 0; i < N; i++) {
    ll y; cin >> y;
    v.at(i) = 2 * y;
  }
  vector<ll> cumt(N+1);
  for (ll i = 0; i < N; i++) cumt.at(i+1) = cumt.at(i) + t.at(i);
  ll T = cumt.at(N);
  vector<ll> vv(T+1, 1e9);
  for (ll i = 0; i < N; i++) {
    for (ll p = cumt.at(i); p >= 0; p--) {
      updMin(vv.at(p), v.at(i) + (cumt.at(i) - p));
    }
    for (ll p = cumt.at(i+1); p <= T; p++) {
      updMin(vv.at(p), v.at(i) + (p - cumt.at(i+1)));
    }
    for (ll p = cumt.at(i); p <= cumt.at(i+1); p++) {
      updMin(vv.at(p), v.at(i));
    }
  }
  for (ll p = T; p >= 0; p--) {
    updMin(vv.at(p), T-p);
  }
  for (ll p = 0; p <= T; p++) {
    updMin(vv.at(p), p);
  }


  double ans = 0;
  for (ll i = 0; i < T; i++) {
    ans += double(vv.at(i) + vv.at(i+1)) / 8.0;
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    debug("debug test\n");
    int n,m;
    string s;cin>>s;
    string f = "", b = "";
    int q;cin>>q;
    int r = 1;
    rep(i, q){
        int type;cin>>type;
        if(type==1){
            r *= -1;
        }else{
            int ff;char c;cin>>ff>>c;
            if(ff==2)ff = -1;
            if(ff*r==1){
                f+=c;
            }else{
                b+=c;
            }
        }
    }
    //cout << s << endl;
    //cout << f << endl;
    //cout << b << endl;
    reverse(all(f));
    string ans = f + s+ b;
    if(r==-1){reverse(all(ans));}
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1300
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

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

using namespace std;

int H,W;
int ban[100][100];
char aaa;
int kuromasu;

int main(){
  cin >> H >> W;
  kuromasu = 0;
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      cin >> aaa;
      if(aaa == '.') ban[i][j] = -1;
      if(aaa == '#'){
        ban[i][j] = -5;
        kuromasu ++;

      }
    }
  }
  int sy = 1;
  int sx = 1;
  int ny;
  int nx;
  ban[1][1]=0;

  queue < pair<int,int> > que;
  que.push(pair<int,int> (sy,sx) );

  while(que.size()>0){
    ny = que.front().first;
    nx = que.front().second;
    que.pop();
    if(ny==H&&nx==W){
      cout << H*W - kuromasu - ban[ny][nx]-1 << endl;
      return 0;
    }
    if(ban[ny+1][nx]==-1){
      ban[ny+1][nx] = ban[ny][nx]+1;
      que.push(pair<int,int> (ny+1,nx) );
    }
    if(ban[ny-1][nx]==-1){
      ban[ny-1][nx] = ban[ny][nx]+1;
      que.push(pair<int,int> (ny-1,nx) );
    }
    if(ban[ny][nx+1]==-1){
      ban[ny][nx+1] = ban[ny][nx]+1;
      que.push(pair<int,int> (ny,nx+1) );
    }
    if(ban[ny][nx-1]==-1){
      ban[ny][nx-1] = ban[ny][nx]+1;
      que.push(pair<int,int> (ny,nx-1) );
    }
  }
  cout << -1 << endl;
  return 0;
}


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

#define ALL(a) (a).begin(), (a).end()
#define llong long long

using namespace std;

signed main(){
	map<int, bool> p;
	for(int i = 0; i*7+1 < 300000; i++){
		p[i*7+1] = true;
		p[i*7+6] = true;
	}
	p.erase(1);
	map<int, set<int> > q;
	for(auto e : p){
		if(e.second){
			for(int i = 2; i*e.first < 300000; i++){
				if(p.find(i*e.first) != p.end()){
					p[i*e.first] = false;
					if(q.find(i*e.first) == q.end()) q[i*e.first] = set<int>();
					q[i*e.first].insert(e.first);
				}
			}
		}
	}

	while(true){
		int n; cin >> n;
		if(n == 1)break;
		cout << n << ":";
		if(q.find(n) == q.end()){
			cout << " " << n;
		}
		else{
			for(auto e : q[n]){
				cout << " " << e;
			}
		}
		cout << endl;
	}
	return 0;
}




Measured memory_bytes: 18728
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(N):
    A = list(map(int,input().split()))
    tmp = C
    for j in range(M):
        tmp += A[j]*B[j]
    if tmp > 0:
        ans += 1
print(ans)

    


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 
int N, a;
  cin >> N;
int d[100010] = {};
int ma = 0;  
 
  for(int i = 0;i < N;i++){
  cin >> a;
    if(a > ma) ma = a;
    d[a]++;
  }
  
int ans = 0;
  if(ma == 0) ans = d[0];
  else{
  for(int i = 1;i <= ma;i++){
  ans = max(ans,d[i-1] + d[i] + d[i+1]);
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<62;
const int IINF = 1000000000;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;

int main(){
    int N; cin >> N;
    vector<pair<int,int>> AB(N);
    rep(i,N) cin >> AB[i].first >> AB[i].second;

    sort(AB.rbegin(), AB.rend());

    cout << AB[0].first + AB[0].second << endl;    

}


Measured memory_bytes: 4044
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,d,x;
  cin >> n;
  cin >> d >> x;
  vector<int> vec(n);
  int i;
  for(i=0;i<n;i++){
    cin >> vec.at(i);
  }
  int sum=0;
  for(i=0;i<n;i++){
    int count=1,eat=1;
    for(int j=0;j<d;j++){
      count+=vec.at(i);
      if(count>d){
        break;
      }
      eat++;
    }
    sum+=eat;
  }
  cout << sum+x;
}
  
  

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

int main(){
	while(1){
		int x, y;
		cin >> x >> y;
		if(x==0 && y==0) break;
		
		if(x>y){
			int tmp = x;
			x = y;
			y = tmp;
		}
		cout << x << " " << y <<endl;
	}
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)


// Write From This Line
int main()
{
	int n, p;
	cin >> n >> p;
	string s;
	cin >> s;

	if( 10 % p == 0) {
		ll ans = 0;
		rep(l,n){
			if ( (s[l] - '0') % p == 0){
				ans += l + 1;
			}
		}
		cout << ans << endl;
		return 0;
	}
	ll ans = 0;
	vector<int> d(n+1); // 累積和用のテーブル
	int ten = 1;
	for(int i = n - 1; i >= 0; i--) {
		int a = (s[i] - '0') * ten % p;
		d[i] = (d[i+1] + a) % p; 
		ten *= 10;
		ten %= p;
	}
	vector<int> cnt(p+1);
	rep(i,n+1){
		ans += cnt[d[i]]++;
	}
	cout << ans << endl;
}


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

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int MOD = 1e9+7;
int pow_mod(int n, int m){
	int ans = 1;
	while(m > 0){
		if(m & 1) ans = (ans * n) % MOD;
		n = (n * n) % MOD;
		m >>= 1;
	}
	return ans;
}

signed main(){
	int n;
	cin >> n;
	if(n == 1){
		cout << 0 << endl;
		return 0;
	}
	int a = pow_mod(8, n);
	int b = (MOD + pow_mod(9, n) - a) % MOD * 2 % MOD;
	int ans = (MOD*2+pow_mod(10, n) - a - b) % MOD;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3588
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE OverloadedStrings #-}
import Control.Monad
import Control.Monad.ST
import Control.Monad.Primitive
import Data.Maybe
import Data.Char
import Data.Array
import Data.Array.ST
import Data.STRef
import Data.List
import Data.STRef
import Text.Printf
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM

modifyHouse [b,f,r,v] house = house // [((b,f,r), vNew)]
  where
    vNow = house ! (b,f,r)
    vNew = vNow + v

modifyHouseLoop lists house = loop lists house
  where
    loop [] h     = h
    loop (l:ls) h = loop ls h'
      where
        h' = modifyHouse l h

main = do
  n <- readLn
  bfrv <- replicateM n $ fmap (map read . words) getLine :: IO [[Int]]
  let house = listArray ((1,1,1),(4,3,10)) $ repeat 0
      -- bfrv = [[1,1,3,8],[3,2,2,7],[4,3,8,1]]
      house_after = modifyHouseLoop bfrv house

  forM_ [1..4] $ \b -> do
    unless (b == 1) $ putStr "####################"
    forM_ [1..3] $ \f -> do
      unless (b == 1 && f == 1) $ putStrLn ""
      forM_ [1..10] $ \r -> do
        putStr " "
        putStr . show $ house_after ! (b,f,r)
        when (r == 10 && f == 3) $ putStrLn ""



Measured memory_bytes: 4616
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

long long ans[200005];

int main(){
    int n , m;
    cin>>n>>m;
    if (n <= m) printf("0\n");
    else{
        for (int i = 0; i < n; i++){
            scanf("%lld",&ans[i]);
        }
        sort(ans,ans+n);
        long long result = 0;
        for (int i = 0; i < n - m;i ++){
            result =result + ans[i];
        }
        printf("%lld\n",result);
    }

}


Measured memory_bytes: 1920