akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	public static class UnionFind {
		int[] par; //

		public UnionFind(int n) {
			par = new int[n];
			for(int i = 0; i < n; i++){
				par[i] = -1;
			}
		}

		public int find(int x) {
			if(par[x] < 0){
				return x;
			}else{
				return par[x] = find(par[x]);
			}
		}

		public boolean union(int x, int y) {
			x = find(x);
			y = find(y);

			if(x != y){
				if(par[y] < par[x]){ // 多い方が根になるようにスワップする.
					int tmp = x;
					x = y;
					y = tmp;
				}
				par[x] += par[y];
				par[y] = x;
				return true;
			}else{
				return false;
			}
		}

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

		public int size(int x) {
			return -par[find(x)];
		}
	}
	
	public static int[][] move_dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

	public static void main(String[] args) throws IOException {
		try(final Scanner sc = new Scanner(System.in)){
			int[] arr = new int[4];
			for(int i = 0; i < 4; i++) { arr[i] = sc.nextInt(); }
			Arrays.sort(arr);
			
			if(arr[0] == 1 && arr[1] == 4 && arr[2] == 7 && arr[3] == 9) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}			
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 20948
#include <iostream>
#include <stack>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int main(int argc, const char * argv[]) {
    string s;
    cin>>s;
    int zero=0,one=0;
    for(int i=0;i<s.size();i++){
        if(s.at(i)=='0'){
            zero++;
        }else{
            one++;
        }
    }
    cout<<2*min(zero,one);
}

Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	static BufferedReader reader;
	
	public static void main(String[] args){
		reader = new BufferedReader(new InputStreamReader(System.in));
		String[] argA = readLine().split(" ");
		if(argA.length<2){return;}
		try{
			int N = Integer.parseInt(argA[0]);
			int M = Integer.parseInt(argA[1]);
			String[] argB = readLine().split(" ");
			if(argB.length!=M){return;}
			int[] X = new int[M];
			for(int i=0;i<M;i++){
				X[i]=Integer.parseInt(argB[i]);
			}
			
			if(M<N){System.out.print(0);return;}
			
			Arrays.sort(X);
			int[] L = new int[M-1];
			for(int i=0;i<M-1;i++){
				L[i] = X[i+1]-X[i];
				//System.out.println(L[i]);
			}
			Arrays.sort(L);
			int ans = 0;
			for(int k=0;k<M-N;k++){
				ans+=L[k];
			}
			System.out.print(ans);return;
		}catch(Exception e){
			e.printStackTrace();
		}
		return;
	}

	private static String readLine(){
		//BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		try{
			return reader.readLine();
		}catch(Exception e){
			return e.getMessage();
		}
	}
}

Measured memory_bytes: 37664
#include <iostream>

using namespace std;
const int MAXN=100005;
int a[MAXN];
int main()
{
    int n,k,sum=0,x;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]==1)
            x=i;
    }
    if(n<=k)
       cout<<1<<endl;
    else
    {
        if((n-k)%(k-1)==0)
            sum=(n-k)/(k-1);
        else
            sum=(n-k)/(k-1)+1;
        sum=sum+1;
        cout<<sum<<endl;
    }
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)

#define INF 99999999

using namespace std;

int main(void){
	int a, b, x,B;
	int ans = INF;
	cin >> a >> b >> x;
	for (int i = 0;i<int(x / 1000) + 2;i++) {
		B = int((x - i * 1000) / 500);
		if (i * 1000 + B * 500 >= x && B>=0) {
			if (ans > (a * i + b * B)) {
				ans = a * i + b * B;
			}
			//cout << ans << i << B << endl;
			//cout << "1" << endl;
		}
		else if (ans > (a * i) && i * 1000>= x && B<0) {
			ans = a * i;
			//cout << ans << i << B << endl;
			//cout << "4" << endl;
		}
		else {
			if (ans > (a * (i + 1) + b * B) && a<=b && B >= 0) {
				ans = (a * (i + 1) + b * B);
				//cout << ans << i+1 << B << endl;
				//cout << "2" << endl;
			}
			else if (ans > (a * i + b * (B + 1)) && a > b && B >= 0) {
				ans = a * i + b * (B + 1);
				//cout << ans << i << B+1 << endl;
				//cout << "3" << endl;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
   int N;
   std::cin >> N;
   int T;
   double A;
   std::cin >> T >> A;
   std::vector<int> H(N);
   for (int i=0; i<N; i++){
      std::cin >> H.at(i);
   }
   double min;
   int minN;
   for (int i=0; i<N; i++){
      double temp = T - H.at(i) * 0.006;
      if (temp > A)
         temp = temp - A;
      else
         temp = A - temp;
      std::cerr << temp << std::endl;
      if (i == 0){
         min = temp;
         minN = i;
      } else{
         if (temp < min){
            min = temp;
            minN = i;
         }
      }
   }
   std::cout << minN+1 << std::endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
    int a,b,k;
    int max;
    int count = 0;
    //vector<int> ans;
    int ans[1000]={0};

    cin >> a >> b >> k;

    if(a>b) max = a;
    else max = b;

    for(int i=1;i<=max;i++){
        if(a%i==0 && b%i==0){
            ans[count] = i;
            count++;
        }
    }

    printf("%d\n",ans[count - k]);
    return 0;
}

Measured memory_bytes: 256
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))

#################

N = I()
a = III()

small = a[0]
large = a[0]

for i in range(1,N):
    if a[i]>small:
        large = a[i]
        break
    if a[i]<small:
        large = small
        small = a[i]
        break

if small != large:
    if large!=small+1:
        print('No')
        exit()
    small_num = 0
    large_num = 0
    for i in range(N):
        if a[i]==small:
            small_num += 1
        else:
            large_num += 1
    num = large_num
    val = large-small_num
    if 2*val<=num and val>=1:
        print('Yes')
    else:
        print('No')
else:
    num = N
    val = large
    if val+1==num:
        print('Yes')
    elif 2*val<=num:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 53156
#include<iostream>
using namespace std;
typedef long long ll;

int main(){
    ll a, b, c, d, g;
    cin >> a >> b >> g >> c >> d >> g >> g;
    ll ans = (ll)b+a/2*2+c/2*2+d/2*2;
    switch(a%2+c%2+d%2){
        case 3:
            ans += 3;
            break;
        case 2:
            ans += (a%2==0&&a>0)||(c%2==0&&c>0)||(d%2==0&&d>0);
            break;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<set>
#include<tuple>
#include<bitset>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
ll dp[10000005];
int main() {
	int n;
	cin >> n;
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	cout << dp[n] << endl;
	return 0;
}


Measured memory_bytes: 3104
from collections import defaultdict

N, A = map(int, input().split())
X = list(map(int, input().split()))
for i in range(N):
    X[i] -= A

dp = defaultdict(int)
dp[0] = 1

for x in X:
    
    for j, c in list(dp.items()):
        dp[j + x] += c

print(dp[0]-1)


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
int H, W;
string s[1024];

int di[4] = {1, 0, -1, 0};
int dj[4] = {0, -1, 0, 1};

int main(){
  cin >> H >> W;
  for(int i=1;i<=H;i++){
    cin >> s[i];
    s[i] = "*" + s[i] + "*";
  }
  for(int j=0;j<W+2;j++){
    s[0] += '*';
    s[H+1] += '*';
  }
  
  
  queue<int> q;
  for(int i=0;i<=H;i++)for(int j=0;j<=W;j++){
    if (s[i][j]=='#'){
      q.push(i); q.push(j); q.push(0);
    }
  }
  int ans = 0;
  while (!q.empty()){
    int ci = q.front(); q.pop();
    int cj = q.front(); q.pop();
    int ct = q.front(); q.pop();
    ans = max(ans, ct);
    
    for(int i=0;i<4;i++){
      int ni = ci + di[i];
      int nj = cj + dj[i];
      if (s[ni][nj]=='.'){
        s[ni][nj] = '#';
        q.push(ni); q.push(nj); q.push(ct+1);
      }
    }
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 14480
#include <iostream>
using namespace std;
int main(void){
    long long N,K,M,L,i,j;
    cin>>N>>K;
    if(K>(N-1)*(N-2)/2){
        cout<<-1<<endl;
        return 0;
    }
    M=N-1+(N-1)*(N-2)/2-K;
    cout<<M<<endl;
    for(i=1;i<N;i++){
        cout<<1<<" "<<i+1<<endl;
    }
    L=(N-1)*(N-2)/2;
    for(i=1;i<N-1&&L>K;i++){
        for(j=2;j<N-i+1&&L>K;j++){
            cout<<j<<" "<<j+i<<endl;
            L--;
        }
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdint.h>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-12;
static const double PI = acos(-1.0);
static const ll MOD = 1000000007;

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define DEBUG(x) cout << #x << ": " << x << endl

int main() {
  int N;
  int K;
  cin >> N >> K;
  vector<bool> has_snack(N, false);
  REP(i, K) {
    int d;
    cin >> d;
    REP(j, d) {
      int A;
      cin >> A;
      has_snack[A - 1] = true;
    }
  }
  int count = 0;
  REP(i, N) {
    if (!has_snack[i]) {
      count++;
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 3196
#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<climits>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    int f=1,x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
#define MAXN 1000
#define INF 0x3f3f3f3f
int n,len,x[MAXN+5],y[MAXN+5],d[35];
void Print(int X,int Y){//贪心策略
    for(int i=1;i<=len;i++){
        if(abs(X)>abs(Y)){
            if(X>0) putchar('R'),X-=d[i];
            else putchar('L'),X+=d[i];
        }
        else{
            if(Y>0) putchar('U'),Y-=d[i];
            else putchar('D'),Y+=d[i];
        }
    }
    puts("");
    return ;
}

int main(){
    bool f[2]={0};
    n=read();
    for(int i=1;i<=n;i++)
        x[i]=read(),y[i]=read(),f[(x[i]+y[i])%2]=1;
    if(f[0]&&f[1]){//判断奇偶有无解
        puts("-1");
        return 0;
    }
    for(int i=30;i>=0;i--)
        d[++len]=(1<<i);
    if(f[0]) d[++len]=1;//奇偶处理
    printf("%d\n",len);
    for(int i=1;i<len;i++)
        printf("%d ",d[i]);
    printf("%d\n",d[len]);
    for(int i=1;i<=n;i++)
        Print(x[i],y[i]);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>//文字列
#include<cstdlib>
#include<algorithm>
#include<cctype>
#include<vector>
#include<iomanip>//小数点以下桁指定

using namespace std;

int main(){

	int n, m, x, y;
	cin >> n >> m >> x >> y;
	int xn, ym;
	int xmax = x;
	int xmin = x;
	int ymax = y;
	int ymin = y;

	for (int i = 0; i<n; i++){
		cin >> xn;
		if (xn>xmax){
			xmax = xn;
		}
		if (xn<xmin){
			xmin = xn;
		}
	}

	for (int i = 0; i<m; i++){
		cin >> ym;
		if (ym>ymax){
			ymax = ym;
		}
		if (ym<ymin){
			ymin = ym;
		}
	}
	if (xmin <= ymin&&ymin <= xmax){
		cout << "War" << endl;
	}
	else if (ymin <= xmin&&xmin <= ymax){
		cout << "War" << endl;
	}
	else if (ymin <= xmin&&ymax <= ymax){
		cout << "War" << endl;
	}
	else if (xmin <= ymin&&ymax <= xmax){
		cout << "War" << endl;
	}
	else cout << "No" << " " << "War" << endl;


}



Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
tmp=-5
res=0
for i in range(n):
  res += b[a[i]-1]
  if tmp==a[i]-2:
    res += c[a[i]-2]
  tmp=a[i]-1
print(res)

Measured memory_bytes: 3064
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    a[0]=0;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    a[n+1]=0;
    int ans=0;
    for (i=0;i<=n;i++)
    {
        ans+=abs(a[i+1]-a[i]);
    }
    for (i=1;i<=n;i++)
    {
        printf("%d\n",ans-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]));
    }
    return 0;
} 


Measured memory_bytes: 1664
l = []
while True:
    h, w = map(int, input().split())
    if h == 0 and w == 0:
        break
    l.append((h, w))

for h, w in l:
    for i in range(h):
        if i % 2 == 0:
            e = '#'
            o = '.'
        else:
            e = '.'
            o = '#'
        for j in range(w):
            if j % 2 == 0:
                print(e,end='')
            else:
                print(o,end='')
        print('')
    print('')


Measured memory_bytes: 7012
#include<bits/stdc++.h>
#define ll long long
#define mo 1000000007
#define pll pair<ll,ll>
using namespace std;
ll f[105];
vector<pll> s[105];
void dfs(int x,ll a,ll b){
	if (x>88) return;
	if (a>=f[x]&&b>=f[x+1]) return;
	s[x].push_back(pll(a,b));
	dfs(x+1,b,b+a); dfs(x+1,b,b*2+a);
}
int main(){
	f[0]=f[1]=1;
	for (int i=2;i<=95;i++)
		f[i]=f[i-1]+f[i-2];
	dfs(1,1,1);
	int Q;
	scanf("%d",&Q);
	while (Q--){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		if (x>y) swap(x,y);
		int ans=0; ll sum=0;
		for (int i=1;i<=100;i++)
			if (f[i]>x||f[i+1]>y){
				ans=i-1;
				break;
			}
		if (ans<=1){
			if (x==1) sum=y%mo;
			else if (x==2) sum=4;
			printf("1 %lld\n",sum);
			continue;
		}
		for (int i=0;i<s[ans].size();i++){
			pll p=s[ans][i];
			if (p.second<=x&&y>=p.first)
				sum=(sum+(y-p.first)/p.second)%mo;
			if (p.second<=y&&x>=p.first)
				sum=(sum+(x-p.first)/p.second)%mo;
		}
		printf("%d %lld\n",ans,sum);
	}
}

Measured memory_bytes: 4224
#include<iostream>
#include<vector>
using namespace std;
void shuffle();
void riffleShuffle();
int n,m,k,i;
vector<int>deck;
int main()
{
  cin>>n;
  for(i=0;i<2*n;i++)deck.push_back(i+1);
  cin>>m;
  while(m-->0){
    cin>>k;
    if(k)shuffle();
    else riffleShuffle();
  }


  for(i=0;i<2*n;i++)cout<<deck[i]<<endl;
}

void shuffle()
{
  int i;
  vector<int>deck1(k),deck2(deck.size()-k);
  for(i=0;i<k;i++)deck1[i]=deck[i];
  for(i=0;i<deck.size()-k;i++)deck2[i]=deck[i+k];
  for(i=0;i<deck.size()-k;i++)deck[i]=deck2[i];
  for(i=0;i<k;i++)deck[i+deck.size()-k]=deck1[i];
  return;
}

void riffleShuffle()
{
  int i;
  vector<int>deck1(deck.size()/2),deck2(deck.size()/2);
  for(i=0;i<deck.size()/2;i++)deck1[i]=deck[i];
  for(i=0;i<deck.size()/2;i++)deck2[i]=deck[i+deck.size()/2];
  for(i=0;i<deck.size();i++)deck[i]=i&1?deck2[i/2]:deck1[i/2];
  return;
}

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

int main(){
    int n, i, sum = 0;
    cin >> n;
    vector <int> l(n, 0);
    for ( i = 0; i < n; i++){
        cin >> l[i];
    }

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

    for (i = 1; i < n; i++){
        sum += l[i];
        // cout << l[i] << endl;
    }
    if(l[0] < sum) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
/*-----rk_98-----*/
#include<bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define mod 1000000007
#define eps 1e-9
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
using namespace std;
int main()
{
    //fast();
    ll n;
    cin>>n;
    ll h[n] , a[n];
    for( ll i = 0 ; i < n ; i++)
    	cin >> h[i];
    for( ll i = 0 ; i < n ; i++)
    	cin >> a[i];

    ll base = 1;
    while( base <= n) base *= 2;
    vector<ll> st(2 * base);
    ll dp[ n + 2 ] = { 0 };
    for( ll i=0 ; i< n ; i++)
    {
    	ll x = h[i] + base;
        ll best =0 ;
        while(x>1)
        {
            if(x % 2 == 1)
                best = max( best , st[x-1]);
            x/=2;
        }
        dp[ h[i] ] = best + a[i];
        for(ll j = base + h[i] ; j>=1 ; j/=2)
        {
            st[j] = max(st[j] , dp[h[i]] );
        }
    }
    ll ans =0 ;
    for(ll i =0 ; i < n + 2 ; i++)
        ans = max( ans , dp[i] );
    cout<<ans<<endl;
}


Measured memory_bytes: 9088
# -*- coding: utf-8 -*-
# F

from collections import deque
import sys

N, M = map(int, input().split())
S = list(input())[::-1]

d = deque()
res = []
prev_idx = 0

while True:
    found = False
    idx = prev_idx
    for m in range(M):
        idx += 1
        if S[idx] == '0':
            # print(idx)
            d.append(m+1)
            found = True
            prev_idx = idx
        if idx == N:
            res.append(str(d.pop()))
            print(' '.join(res[::-1]))
            sys.exit()
    if not found:
        print(-1)
        sys.exit()
    res.append(str(d.pop()))




Measured memory_bytes: 53608
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
char S[200011];

void MAIN() {
    scanf("%s", S);
    N = strlen(S);
    LL ans = 0;

    for (int i=0; i<N;) {
	int j = i;
	int cnt = 0;
	while (j < N) {
	    if (S[j] == 'A') { cnt++; j++; }
	    else if (S[j] == 'B' && S[j+1] == 'C') { ans += cnt; j+=2; }
	    else { j++; break; }
	}

	i = j;
    }

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

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  ll n;
  cin >> n;
  ll ans = 0;
  FOR(i, 1, n + 1) {
    if (i % 3 != 0 && i % 5 != 0) {
      ans += i;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
#include<iostream>

using namespace std;

const int MAX_N=1e5+2000;
const long long INF=1e18+3;
long long dp[MAX_N];
long long h[MAX_N];

int main(){
  int n;
  cin>>n;
  int k;
  cin>>k;
  for(int i=0;i<n;i++){
    cin>>h[i];
  }
  for(int i=0;i<MAX_N;i++)dp[i]=INF;
  dp[0]=0;
  for(int i=1;i<=k;i++){
    dp[i]=abs(h[i]-h[0]);
  }
  for(int i=k+1;i<n;i++){
    for(int j=1;j<=k;j++){
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i]);
    }
  }
  cout<<dp[n-1]<<endl;

}


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

int main(){
    int n;
    cin>>n;
    vector<ll>a(n);
    rep(i,n)cin>>a[i];
    map<ll,ll>mp;
    rep(i,n){
        mp[a[i]]++;
    }
    ll cnt=0;
    for(auto p:mp){
        if(p.second%2==1)cnt+=1;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 7296
#include <iostream>
using namespace std;
int main(void){
  char a[100000],b[100000],c;
  int m,n,f;
  while(1){
    cin>>n;
    if(!n)
      break;
    for(int i=0;i<n;i++)
      cin>>a[i]>>b[i];
    cin>>m;
    for(int j=0;j<m;j++){
      f=1;
      cin>>c;
      for(int k=0;k<n;k++){
	if(c==a[k]){
	  f=0;
	  cout<<b[k];
	  break;
	}
      }
      if(f)
	cout<<c;
    }
    cout<<endl;
  }
  return 0;
}

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

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define db(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define db(...) 42
#endif

using ll = long long;

int main() {
  ll n, x;
  cin >> n >> x;
  ll ans = 0;
  ll p = 0;
  for (int i = 0; i < n; i++) {
    int c;
    cin >> c;
    if (c + p > x) {
      ans += (c + p) - x;
      c -= (c + p) - x;
    }
    p = c;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = int(input())
    xy = XLMIIS(N)
    

    def distance(x1,y1,x2,y2):
        return ((x1-x2)**2 + (y1-y2) ** 2) ** 0.5

    def f(n):
        ans = n
        if n <= 0:
            return 1
        for i in range(1,n):
            ans *= i
        return ans
    

    sumdis = 0
    for i in range(N):
        for j in range(i+1,N):
            sumdis += distance(xy[i][0],xy[i][1],xy[j][0],xy[j][1])
    summ = sumdis  / N * 2
    print(summ)


if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
import java.util.Scanner

import scala.collection.Searching._
import scala.annotation.tailrec
import scala.collection.immutable.{NumericRange, Queue}
import scala.collection.mutable
import scala.io.StdIn.readLine

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  @tailrec
  private def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {
  def solve(sc: => Scanner): Unit = {
    val A, B = sc.nextLong
    println((A, B) match {
      case (1, 1) => 1
      case (x, 1) => x - 2
      case (1, y) => y - 2
      case (x, y) => (x - 2) * (y - 2)
    })
  }

  def gcd(i: Long, j: Long): Long = {
    if (i < j) (gcd(j, i)) else (if (j == 0) (i) else (gcd(j, i % j)))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

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

int base;
int tod(int b,int ka,int t,int w,int ki){
	ka+=b*20;t+=ka*20;w+=18*t;ki+=20*w;
	return base+ki;
}
bool is_uruu(int y){
	return y%4==0&&(y%100!=0||y%400==0);
}
int mn[]{31,28,31,30,31,30,31,31,30,31,30,31};
int calc(int y,int m,int d){
	int res=(y-1)*365;
	for(int i=4;i<y;i+=4){
		if(is_uruu(i))res++;
	}
	for(int i=1;i<m;i++){
		res+=mn[i-1];if(is_uruu(y)&&i==2)res++;
	}
	return res+d;
}
int tod(int y,int m,int d){
	return calc(y,m,d)-base;
}
void tom(int day){
	int b,ka,t,w,ki;
	ki=day%20;day/=20;
	w=day%18;day/=18;
	t=day%20;day/=20;
	ka=day%20;day/=20;
	b=day%13;
	printf("%lld.%lld.%lld.%lld.%lld\n",b,ka,t,w,ki);
}
void tos(int day){
	int y,m;
	for(y=1;365+is_uruu(y)<day;y++)day-=365+is_uruu(y);
	for(m=1;mn[m-1]+(m==2&&is_uruu(y))<day;m++)day-=mn[m-1]+(m==2&&is_uruu(y));
	printf("%lld.%lld.%lld\n",y,m,day);
}
signed main() {
	base=calc(2012,12,21);
	string s;
	while(cin>>s,s!="#"){
		s+='.';
		vector<int>v;
		string t;
		for(char c:s){
			if(c=='.')v.push_back(stoi(t)),t="";
			else t+=c;
		}
		if(v.size()==3)tom(tod(v[0],v[1],v[2]));
		else tos(tod(v[0],v[1],v[2],v[3],v[4]));
	}
}

Measured memory_bytes: 3348
#include <bits/stdc++.h>
using namespace std;
long long mypow(long long x, int n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
int main(){
    double n, k;
    cin >> n >> k;
    
    double ans=0;
    for(int i=1; i<=n; ++i){
        ans += (double)1/mypow(2,ceil(log2(k)-log2(i)));
    }
    
    cout << fixed << setprecision(14);
    cout << ans/n << endl;
}

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

namespace tenka1_2017_b
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int ret = int.MaxValue;
            for (int i = 0; i < n; i++)
            {
                int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
                ret = Math.Min(ret, x.Sum());
            }
            Console.WriteLine(ret);
        }
    }
}

Measured memory_bytes: 17448
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

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

    vector<int> v;
    v.push_back(1);
    int a = 6;
    while(a <= n){
        v.push_back(a);
        a *= 6;
    }
    a = 9;
    while(a <= n){
        v.push_back(a);
        a *= 9;
    }
    sort(v.begin(), v.end());

    vector<int> dp(n+1, INF);
    dp[0] = 0;

    rep(i, (int)v.size()){
        for(int j = v[i]; j <= n; j++){
            dp[j] = min(dp[j - v[i]]+1, dp[j]);
        }
    }
    cout << dp[n] << endl;

    return 0;
}


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


int main()
{
	int r, c;
	int sum = 0;
	int rc[100][100];
	int rsum[100];
	int csum[100];

	for (int i = 0; i < 100; i++){
		rsum[i] = 0;
		csum[i] = 0;
	}

	cin >> r >> c;

	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			cin >> rc[i][j];
			rsum[i] = rsum[i] + rc[i][j];
			csum[j] = csum[j] + rc[i][j];
		}
	}

	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			cout << rc[i][j] << " ";
		}
		cout << rsum[i] << endl;
	}
	for (int i = 0; i < c; i++){
		cout << csum[i] << " ";
		sum = sum + csum[i];
	}
	cout << sum << endl;
	
	return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef   long long int ll;
typedef unsigned long long int sll;
typedef  double ld;
#define A 1000000007ll
#define B 998244353ll
#define C 1000000000000000000ll
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI 3.1415926535

ll dp[405][405],sum[405][405];

int main() 
{
    FAST;
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<405;i++)
        for(int j=0;j<405;j++)
        	dp[i][j]=10000000000000ll;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum[i][i]=a[i];
        dp[i][i]=0;
    }
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            sum[i][j]=sum[i][j-1]+a[j];
    for(int i=1;i<n;i++)
        for(int j=0,k=i;j<n && k<n;j++,k++)
            for(int p=j;p<k;p++)
            	dp[j][k]=min(dp[j][p]+dp[p+1][k]+sum[j][k],dp[j][k]);
    cout<<dp[0][n-1];
    return 0;
}

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

using namespace std;

#define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
#define endl "\n"
#define dump(x) cerr << "~ " << #x << " = " << x << endl


int main() {

	fast_cin;
	
    int n,x,t;
    cin >> n >> x >> t;

    int ans = (n+x-1)/x;
    ans *= t;
	
	cout << ans << endl;
	
	return 0;
}

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

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

const int N = 3e3 + 5;
pair<int, int> arr[N];
int f[N];

int main()
{
	int n = read();
	int T = read();
	for (int i = 1; i <= n; ++i) arr[i] = {read(), read()};
	sort(arr + 1, arr + n + 1);
	
	memset(f, -0x3f, sizeof(f));
	int ans = f[0] = 0;
	for (int i = 1; i <= n; ++i)
	{
		int a = arr[i].first;
		int b = arr[i].second;
		for (int j = 0; j < T; ++j) 
			ans = max(ans, f[j] + b);
		for (int j = T - 1; j >= a; --j)
			f[j] = max(f[j], f[j - a] + b);
	}
	printf("%d\n", ans);
	
	return 0;
}


Measured memory_bytes: 256
import 'dart:io';
 
void main(List<String> args) {
  List<int> A = stdin.readLineSync().split(' ').map((i) => int.parse(i)).toList();
  stdout.write(A[2]);
  stdout.write(' ');
  stdout.write(A[0]);
  stdout.write(' ');
  print(A[1]);
}

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

int main() {
	int  a,b;
	string s;
	cin >> a >> b;
	cin >> s;

	if (s.length() != a+b+1) {
		cout << "No" << endl;
		return 0;
	}
	for (int i=0; i<a; i++) {
		if ((s[i] < '0') || ('9' < s[i])) {
			cout << "No" << endl;
			return 0;
		}
	}
	if (s[a] != '-') {
		cout << "No" << endl;
		return 0;
	}
	for (int i=a+1; i<a+b+1; i++) {
		if ((s[i] < '0') || ('9' < s[i])) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
 
int main() {
  
  int N;
  cin >> N;

  vector<long long> A(N),num(N+1);
  for(int i = 0;i < N;i++) {
    cin >> A[i];
    num[A[i]]++;
  }

  long long sum = 0;
  for(int i = 1;i <= N;i++) sum += num[i]*(num[i]-1)/2;

  for(int i = 0;i < N;i++) {
    int n = num[A[i]];
    sum -= n-1;
    cout << sum << endl;
    sum += n-1;
  }



}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<int(min({a*c,b})/a)<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll MAX = 1000100;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];


void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}


long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  int X,Y;
  cin >> X >> Y;

  COMinit();

  for(int a = 0;a <= X;a++){
    int b = Y - 2 * a;
    if(X == (a + 2 * b) && b >= 0){
      cout << COM(a+b,b) << endl;
      return 0;
    }
  }

  cout << 0 << endl;
}

Measured memory_bytes: 23808
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.begin(),v.end(),std::greater<llong>());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef vector<llong> V;

#define _ cin.tie(0);ios::sync_with_stdio(false);
int n,k;
int main(){ _;
  cin>>n>>k;
  V l(n);
  REP(i,n) cin>>l[i];
  VSORTR(l);
  llong ans=0;
  REP(i,k) ans+=l[i];
  cout<<ans<<endl;
  

  return 0;
}


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

using namespace std;

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

int main(){
    string str;cin>>str;
    for(int i=0;i<str.length();i+=2){
        cout<<str[i];
    }
    cout<<endl;
    return 0;
       

}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi 2*acos(0.0)
#define f first
#define s second
#define pb push_back
#define gap ' '
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define mod 1000000007
#define N 200005
ll n,m;
ll a[N],b[N];
int main()
{
    fastio;
    cin>>n>>m;
    b[0]=n;
    for(int i=1,j=n-1;i<=n;i++,j--)
    {
        a[i]=i+a[i-1];
        b[i]=j+b[i-1];
//        cout<<a[i]<<gap<<b[i]<<endl;
    }
    ll ans=0;
    for(int i=m-1;i<=n;i++)
    {
        ans=(ans+b[i]-a[i]+1)%mod;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 6776
#include<bits/stdc++.h>
#define ll long long
#define ljc 924844033
/*
it's benn a long day,我没写NTT
https://www.luogu.org/blog/wohaocaia/solution-at2064 
*/
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
struct edge{
	int to,nxt;
}e[400001];
ll sz[400001],tot,head[2200001];
inline void made(int from,int to){
	e[++tot].to=to;e[tot].nxt=head[from];head[from]=tot;
}
ll n,w[2200001],C[1000001],inv[1000001],fac[1000001],r[2200001],f[2200001],g[2200001];
inline ll fast_pow(ll a,ll b,ll p){
	ll t=1;a%=p;
	while (b){
		if (b&1LL) t=t*a%p;
		b>>=1LL;a=a*a%p;
	}
	return t;
}
inline void NTT(ll *f,ll lim,ll id){
	w[0]=1;
	for (int i=0;i<lim;i++){
		if (i>r[i]) swap(f[i],f[r[i]]);
	}
	for (int len=1;len<lim;len<<=1){
		ll gen=fast_pow(5,(ljc-1)/(len<<1)*id+ljc-1,ljc);
		for (int i=1;i<len;i++) w[i]=w[i-1]*gen%ljc;
		for (int i=0;i<lim;i+=len<<1){
			ll *f1=f+i,*f2=f1+len;
			for (int j=0;j<len;j++){
				ll x=f1[j],y=f2[j]*w[j]%ljc;
				f1[j]=(x+y)%ljc;
				f2[j]=(x-y+ljc)%ljc;
			}
		}
	}
	if (id==1) return;
	ll INV=fast_pow(lim,ljc-2,ljc);
	for (int i=0;i<lim;i++) f[i]=f[i]*INV%ljc;
}
void dfs(int u,int fa){
	sz[u]=1;
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if (v==fa) continue;
		dfs(v,u);sz[u]+=sz[v];g[sz[v]]++;
	}
	g[n-sz[u]]++;
}
inline ll getC(ll n,ll m){
	return fac[n]*inv[m]%ljc*inv[n-m]%ljc;
}
signed main(){
	n=read();
    fac[0]=inv[0]=inv[1]=1;
    for (ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%ljc;
    for (ll i=2;i<=n;i++) inv[i]=(ljc-(ljc/i)*inv[ljc%i]%ljc)%ljc;
    for (ll i=1;i<=n;i++) inv[i]=inv[i-1]*inv[i]%ljc;
    for (int i=1;i<n;i++){
    	int x=read(),y=read();
    	made(x,y);made(y,x);
	}
	dfs(1,0);
	g[0]=0;
	for (int i=1;i<=n;i++) C[i]=n*getC(n,i)%ljc;
	for (int i=1;i<=n;i++) g[i]=g[i]*fac[i]%ljc;
	for (int i=0;i<=n;i++) f[i]=inv[i];
	reverse(g,g+1+n);
	ll lim=1,len=0;
	n++;
	while (lim<=(n<<1)) lim<<=1,len++;
	for (int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
	NTT(f,lim,1);NTT(g,lim,1);
	for (int i=0;i<lim;i++) f[i]=f[i]*g[i]%ljc;
	NTT(f,lim,-1);
	n--;
	for (int i=1;i<=n;i++) f[i]=f[i]*inv[n-i]%ljc;
	for (int i=1;i<=n;i++) printf("%lld\n",(C[i]-f[n-i]+ljc)%ljc);
    return 0;
}



Measured memory_bytes: 52096
# 2019/03/27
# AtCoder Beginner Contest 108 - B

# Input
xy = list(map(int, input().split()))

# Calc
xa = xy[2]-xy[0]
ya = xy[3]-xy[1]

x3 = xy[2]-ya
y3 = xy[3]+xa
x4 = x3-xa
y4 = y3-ya

# Output
print(x3,y3,x4,y4)


Measured memory_bytes: 2940
n=int(input())
s=[ input() for i in range(n)]
m=int(input())
t=[ input() for i in range(m)]
ans=dict()
for i in s:
  if not(i in ans):
    ans[i]=1
  else:
    ans[i]+=1
for i in t:
  if not(i in ans):
    ans[i]=-1
  else:
    ans[i]-=1
hantei=0
for i in ans:
  if ans[i]>hantei:
    hantei=ans[i]
print(hantei)




Measured memory_bytes: 3064
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        h: usize, w: usize,
        n: usize,
        a: [usize; n],
    }
    let mut tile = vec![];
    for i in 0..n {
        for j in 0..a[i] {
            tile.push(i + 1);
        }
    }

    for i in 0..h {
        let mut row = vec![];
        for j in 0..w {
            let acc = tile.pop().unwrap();
            row.push(acc);
        }
        if i % 2 == 1 {
            row.reverse();
        }
        for j in 0..w - 1 {
            print!("{} ", row[j]);
        }
        println!("{}", row[w - 1]);
    }
}


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

using namespace std;
typedef long long ll;
int main() {
  int N;
  cin >> N;
  //頂点入れ
  vector<int> d(N);
  for (int i = 0; i < N; i++) {
    cin >> d[i];
  }
  //頂点の最初が0
  if (d[0] != 0) {
    cout << 0 << endl;
    return 0;
  }
  //最初以外が0なら0
  for (int i = 1; i < N; i++) {
    if (d[i] == 0) {
      cout << 0 << endl;
      return 0;
    }
  }

  sort(d.begin(),d.end());
  //d[N-1]が一番遠い点
  vector<int> kosuu(d[N-1]+1);
  for (int i = 0; i < N; i++) {
    kosuu[d[i]]++;
  }
  ll sum = 1;
  ll totyuu = 1;
  for (int i = 1; i < d[N-1]+1; i++) {
    if (kosuu[i] == 0) {
      cout << 0 <<endl;
      return 0;
    }
    totyuu = 1;
    for(int j = 0; j < kosuu[i]; j++){
      totyuu *= kosuu[i-1];
      totyuu %= 998244353;
    }
    sum *= totyuu;
    sum %= 998244353;
    //cout << i << " " << sum << endl;
  }
  cout << sum << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>

using namespace std;
using ll = long long;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double PI = 4.0 * atan(1.0);

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, a, n) for (int i = a; i <= (n); ++i)

int main() {
    int s; cin >> s;
    map<int, string> mp;
    mp[2] = "hon";
    mp[4] = "hon";
    mp[5] = "hon";
    mp[7] = "hon";
    mp[9] = "hon";
    mp[0] = "pon";
    mp[1] = "pon";
    mp[6] = "pon";
    mp[8] = "pon";
    mp[3] = "bon";
    int tmp = s % 10;
    cout << mp[tmp] << endl;
    return 0;
}


Measured memory_bytes: 3612
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0; 
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //
void solve(){
	int n = read.to!int;
	long[] as = readln.chomp.split.map!(to!long).array;
	
	int ans;
	foreach(i; 0 .. n - 2){
		if(as[i] < as[i + 1] && as[i + 1] < as[i + 2]
			|| as[i] > as[i + 1] && as[i + 1] > as[i + 2]) ans += 1;
	}
	
	ans.writeln;
}


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

using namespace std;

const int N = 234567, M = 2345, mod = 1e9 + 7;

void add(int& x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

void sub(int& x, int y) {
  x -= y;
  if (x < 0) {
    x += mod;
  }
}

int mul(int x, int y) {
  return (long long) x * y % mod;
}

template<typename T>
class my_array {
 public:
  T a[M << 1];

  T& operator [] (int x) {
    return a[x + M];
  }
};

int n, a[N], b[N], fac[M << 2], ifac[M << 2], inv[M << 2];
my_array<my_array<int>> dp;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fac[0] = ifac[0] = inv[1] = 1;
  for (int i = 1; i < (M << 2); ++i) {
    if (i > 1) {
      inv[i] = mul(mod - mod / i, inv[mod % i]);
    }
    fac[i] = mul(fac[i - 1], i);
    ifac[i] = mul(ifac[i - 1], inv[i]);
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
    ++dp[-a[i]][-b[i]];
  }
  int limit = 2000;
  for (int i = -limit; i <= limit; ++i) {
    for (int j = -limit; j <= limit; ++j) {
      add(dp[i + 1][j], dp[i][j]);
      add(dp[i][j + 1], dp[i][j]);
    }
  }
  auto binom = [&] (int n, int m) {
    return mul(fac[n], mul(ifac[m], ifac[n - m]));
  };
  int answer = 0;
  for (int i = 1; i <= n; ++i) {
    add(answer, dp[a[i]][b[i]]);
    sub(answer, binom(a[i] + b[i] << 1, a[i] << 1));
  }
  cout << mul(answer, mod + 1 >> 1) << '\n';
  return 0;
}

Measured memory_bytes: 77696
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

using Graph = vector< vector<int> >;
int deg[100010];

int solve(Graph &G, int cur, int par=-1) {
    int ret = 0, appear_zero = 0;
    for(auto to : G[cur]) {
        if(to == par) continue;
        int val = solve(G, to, cur);
        if(val != 0) ret += val;
        else {
            if(appear_zero) {
                ret++;
            }
            else {
                appear_zero = true;
            }
        }
    }

    return ret;
}

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

    Graph G(N);
    for(int i=0; i<N-1; i++) {
        int u, v; cin >> u >> v;
        deg[u]++; deg[v]++;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int root = -1, max_deg = 0;
    for(int i=0; i<N; i++) {
        if(max_deg < deg[i]) {
            max_deg = deg[i];
            root = i;
        }
    }

    cout << max(1LL, solve(G, root)) << endl;
    return 0;
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll ; 
typedef long double ld ;
typedef pair<ll , ll> pll ;

const ll N = 2e5 + 30 , Mod = 1e9 + 7 ;
const ll SQ = 330 ;

int main () {
    ios::sync_with_stdio(0), cin.tie(0) ;
   	string s; 
   	cin >> s ;
   	ll n = s.size() ;
	ll ans = 0 ;
	for (int i = 0 ; i < n - 1; i ++) {
		if (s[i] == s[i + 1]) {
			if(s[i] == '0') s[i + 1] = '1' ;
			else s[i + 1] = '0' ;
			ans ++ ;
		}
	}
	cout << ans ;
    
    return (0) ;
}

Measured memory_bytes: 512