akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    int c[n+1]={};
    REP(i,1,n-1){
        if(s[i-1]=='A'&&s[i]=='C')c[i+1]++;
    }
    REP(i,1,n){
        c[i]+=c[i-1];
    }
    rep(_,q){
        int l,r;
        cin>>l>>r;
        cout<<c[r]-c[l]<<endl;
    }
}

Measured memory_bytes: 1872
#include <bits/stdc++.h>
#include <fstream>
#define ll long long
#define ld long double
//#define int long long
#define MOD 1000000007
#define mod 1000000007
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define vvi vector<vi>
#define mp make_pair
#define endl "\n"
using namespace std;
int gcd(int a, int b)
{
    // Everything divides 0
    if (a == 0)
       return b;
    if (b == 0)
       return a;

    // base case
    if (a == b)
        return a;

    // a is greater
    if (a > b)
        return gcd(a-b, b);
    return gcd(a, b-a);
}
bool allprime[1000001]={0};

vector<int> sieve_of_primes_upto_10e6()
{
    int n=1000007;
    vector<int> set_of_primes;
    set_of_primes.push_back(2);int p;
    for(p=3;p*p<=n;p+=2)
    {
        if(allprime[p]==0)
        {
            set_of_primes.push_back(p);
            for(int i=p*p;i<=n;i+=p)
            {
                allprime[i]=1;
            }
        }
    }
    for(p;p<=n;p+=2)
    {
        if(allprime[p]==0)
        {
            set_of_primes.push_back(p);
        }
    }
    return set_of_primes;
}
void solve1();
void solve()
{
    int T;cin>>T;
    for(int z=1;z<=T;z++)
    {
        solve1();
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve1();
    return 0;
}
int vis[1000007]={0};
void solve1()
{
    int n;cin>>n;
    int arr[n];
    cin>>arr[0];
    int c=arr[0];
    for(int i=1;i<n;i++)
    {
        cin>>arr[i];
        c=__gcd(c,arr[i]);
    }
    if(c>1)
    {
        cout<<"not coprime"<<endl;return;
    }
    vi vec=sieve_of_primes_upto_10e6();
    for(int i=0;i<n;i++)
    {
        if(arr[i]!=1&&vis[arr[i]]>0)
        {
            cout<< "setwise coprime"<<endl;return;
        }
        int j=0;
        while(arr[i]>=vec[j]*vec[j])
        {
            if(vis[vec[j]]==0)
            {while(arr[i]%vec[j]==0)
            {
                arr[i]/=vec[j];vis[vec[j]]++;
            }}
            else if(arr[i]%vec[j]==0)
            {
                cout<< "setwise coprime"<<endl;return;
            }
            j++;
        }
        if(vis[arr[i]]==0)vis[arr[i]]++;
        else if(arr[i]!=1)
        {
            cout<< "setwise coprime"<<endl;return;
        }
    }
    /*for(int i=0;i<10;i++)
    {
        cout<<vis[i]<<" ";
    }*/
    cout<<"pairwise coprime"<<endl;
}



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

int main(void){
  int N, K;
  int ans;
  cin >> N >> K;
  for(int i = 0; i < N; i++){
    if(i == 0) ans = K;
    else ans *= (K - 1);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

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

    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    scanf("%d", &x);
    scanf("%d", &y);

    int sum;
    if(x <= y){
        if(a + b >= c * 2){
            sum = b * (y - x) + c * 2 * x;
            if (b >= c * 2){
                sum = c * 2 * y;
            }
        }else{
            sum = a * x + b * y;
        }
    }else{
        if(a + b >= c * 2){
            sum = a * (x - y) + c * 2 * y;
            if(a >= c * 2){
                sum = c * 2 * x;
            }
        }else{
            sum = a * x + b * y;
        }
    }

    printf("%d\n", sum);
}


Measured memory_bytes: 888
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	int a, b;
  cin>>a>>b;
  cout<<(a+b)%24<<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 RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> P;
typedef map<int,int> mp;

const int MOD = 1e9 + 7;


int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    string s, t;
    cin >> s >> t;

    cout << t << s << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
AB = [[int(_) for _ in input().split()] for i in range(N - 1)]

from collections import defaultdict

rs = defaultdict(set)

for a, b in AB:
    rs[a].add(b)
    rs[b].add(a)

from heapq import *

cs = [0] * (N + 1)
cs[1] = 1
cs[N] = 2

h = []
heappush(h, (1, 1))
heappush(h, (2, N))

bcount = 0

while h:
    t, x = heappop(h)
    bcount += t % 2
    for n in rs[x]:
        if cs[n] == 0:
            cs[n] = t + 2
            heappush(h, (t + 2, n))

if bcount > N - bcount:
    print("Fennec")
else:
    print("Snuke")


Measured memory_bytes: 53804
/// However long the night,
///     The dawn will break
/// ICPC next year

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e5+5 ;

int n ;
long long m[N] ,x[N] ;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%lld",m+i);
    int sign = 1 ;
    x[n-1] = 2ll*m[n-1] ;
    for(int i=n-2;i>=0;--i){
        x[n-1] += 2ll*sign*m[i] ;
        sign *= -1 ;
    }
    x[n-1] /= 2 ;
    for(int i=n-2;i>=0;--i){
        x[i] = 2ll*m[i] - x[i+1] ;
    }
    for(int i=0;i<n;++i)printf("%lld ",x[i]);
    return 0;
}


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define BiSearchRangeNum(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y)turn idx;
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;
};


static const int MAX = 400;
static const ll INFTY = 1e15;

ll N, M, L, Q;
ll fuel[MAX][MAX];
ll dist[MAX][MAX];
ll s[105000], t[105000];
ll A[100000], B[100000], C[100000];

void input() {
  cin >> N >> M >> L;
  for (int i = 1; i <= M; i++) cin >> A[i] >> B[i] >> C[i];
  cin >> Q;
  for (int i = 1; i <= Q; i++) cin >> s[i] >> t[i];
}

void solve() {
  input();
  // 初期化
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      fuel[i][j] = INFTY;
      dist[i][j] = INFTY;
    }
    fuel[i][i] = 0;
    dist[i][i] = 0;
  }

  // 初期node間距離代入
  for (int i = 1; i <= M; i++) {
    chmin(fuel[A[i]][B[i]], C[i]);
    chmin(fuel[B[i]][A[i]], C[i]);
  }

  // フロイド法によって全点間の最短距離を算出
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      for (int k = 1; k <= N; k++) {
        chmin(fuel[j][k], fuel[j][i] + fuel[i][k]);
      }
    }
  }

  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      if (i == j) continue;
      // 距離がL以下(つまり進める)の場合, 距離を1とする
      if (fuel[i][j] <= L) chmin(dist[i][j], 1LL);
    }
  }

  // 上のようにL以下の距離を1として処理した後, フロイド方を行う
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      for (int k = 1; k <= N; k++) {
        chmin(dist[j][k], dist[j][i] + dist[i][k]);
      }
    }
  }

  for (int i = 1; i <= Q; i++) {
    if (dist[t[i]][s[i]] < INFTY) cout << dist[t[i]][s[i]] - 1 << endl;
    else cout << -1 << endl;
  }
  return;
};

int main() {
  solve();
  return 0;
};


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

#define FOR(i, a, b) for (int i = a; i < (int) b; i++) 
#define F0R(i, a) FOR (i, 0, a)
#define GO(to, a) for (auto to : a)

#define f first
#define s second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;

const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};

const int m[] = {+31, +29, +31, +30, +31, +30, +31, +31, +30, +31, +30, +31};

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int h, n;
	cin >> h >> n;
	int tot = 0;
	F0R (i, n) {
		int foo;
		cin >> foo;
		tot += foo;
	}
	cout << (tot >= h ? "Yes" : "No") << '\n';
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int mex=5001;
#define ll long long 
#define test int t;cin>>t;while(t--)
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i,a,n) for(int i=a;i<n;i++)
#define rfo(i,a,b) for(int i=a;i>=b;i--)
#define bg begin()
#define en end()
#define fi first
#define se second
#define ub upper_bound
#define lb lower_bound
#define pb push_back
#define veci vector<int>
#define veclli vector<long long int> 
#define all(x) x.begin(),x.end()
#define sci(x) scanf("%d",&x);
#define scc(x) scanf("%c",&x);
#define scs(x) scanf("%s",x);
#define debug(arr,n) for(int i=0;i<n;i++) printf("%d ",arr[i]);
#define sz(x) x.size()
#define loop(x) for(auto it=x.begin();it!= x.end();it++) 
 
 ll int dp[5001][5001]={0};
int main()
{
  int n,k;
  cin>>n>>k;
  fo(i,0,n+1)
  dp[i][0]=1;
  fo(j,1,k+1)
  fo(i,1,n+1)
  dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;

  fo(i,1,k+1)
  {
    ll int an=(dp[k-1][i-1]*dp[n-k+1][i])%mod;
    cout<<an<<" ";
  }


 // cout<<cnt<<endl;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstdlib> 
#include <string.h>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <ctime>
#include <algorithm>
#include <cmath>
#define PI 3.1415926535897932384626433832795l
#define IOS ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define deci(n) cout<<fixed<<setprecision(n);
#define F first
#define S second
#define mk make_pair
#define pb push_back
#define ALPHA 27
#define ll long long int
#define ld long double
#define mmset(arr, n) memset(arr, n, sizeof arr)
#define debug(x) cerr << '#' << ' ' << x << '\n'
#define len(s) s.length()
#define ForA(i,a,b) for(int i = a; i < b; i++)
#define ForA1(i,a,b) for(int i = b - 1; i >= a; i--)
#define ForB1(i,a,b) for(int i = b; i > a; i--)
#define ForB(i,a,b) for(int i = a; i <= b; i++)
#define INT_SIZE 18 
#define maxn 3010
#define Maxn 100010

using namespace std;

const ll INF = (ll)(8e18);
const ll MOD = 1000000007;

ll a[maxn], dp[maxn][maxn], prefix[maxn];

int main()
{
    IOS;        
    ll n; cin >> n;
    ForB(i,1,n) cin >> a[i];
    ForB(i,1,n) prefix[i] += prefix[i - 1] + a[i];
    ForB(i,1,n) dp[i][i] = a[i];
    ForB(i,2,n){
        ForB(j,1,n - i + 1){
            int l = i + j - 1;
            dp[j][l] = max(dp[j][l], a[l] + 
                          prefix[l - 1] - prefix[j - 1] - dp[j][l - 1]); 
            dp[j][l] = max(dp[j][l], a[j] + 
                          prefix[l] - prefix[j] - dp[j + 1][l]);                
        }
    }
    cout <<  dp[1][n] + dp[1][n] - prefix[n] << '\n';
    #ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
    return 0 ;
}


Measured memory_bytes: 70016
#include <stdio.h>

int main()
{
int p[31]={0};
int w,n,a,b;
char e;
int tmp;
tmp=0;
scanf("%d",&w);scanf("%d",&n);
for(int i=0;i<w;i++)
p[i]=i+1;
for(int i=0;i<n;i++)
{
scanf("%d,%d",&a,&b);
tmp=p[a-1];p[a-1]=p[b-1];p[b-1]=tmp;

}

for(int i=0;i<w;i++)
printf("%d\n",p[i]);

return 0;
}

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

const int MOD = 1000000007;
typedef long long ll;
typedef long double ld;

struct Vec {
  ld x, y;
} v[105];

clock_t begin_time;

ld sq(ld x) {return x*x;}

ld gt() {
  return ld(clock()-begin_time)/CLOCKS_PER_SEC;
}

int main() {
  begin_time = clock();
  int n; cin >> n;
  for (int i = 0; i < n; i++) cin >> v[i].x >> v[i].y;
  
  ld ans=0;

  while (gt()<1.8) {
    random_shuffle(v,v+n);
    ld x=0,y=0;
    for (int i=0;i<n;i++){
      if (sq(x+v[i].x)+sq(y+v[i].y)>sq(x)+sq(y)) x+=v[i].x,y+=v[i].y;
      ans=max(ans,sq(x)+sq(y));
    }
  }
  cout<<fixed<<setprecision(15)<<sqrt(ans)<<endl;
}

Measured memory_bytes: 384
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]

    x = N // K


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


if __name__ == '__main__':
    main()


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001

set<char> r{'y', 'u', 'i', 'o', 'p', 'h', 'j', 'k', 'l', 'n', 'm'};

int main(){
    cin.sync_with_stdio(false);
    string s;
    while(cin >> s, s[0] != '#') {
        int cnt = 0, lr = 0;
        if (r.count(s[0])) lr = 1;
        repl(i, 1, s.size()) {
            int tmp = 0;
            if (r.count(s[i])) tmp = 1;
            if (tmp != lr) cnt++;
            lr = tmp;
        }
        cout << cnt << endl;
    }

    return 0;
}

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

int main(){
	
	char str1[200],str2[100];
	
	scanf("%s %s",str1,str2);
	sprintf(str1, "%s%s", str1, str1);
	if (strstr(str1, str2)==NULL)printf("No\n");
	else printf("Yes\n");
	
	return 0;
}



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

#define ll long long
#define ld long double
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long

using namespace std;
const int INF = 2e16;
const int MB = 20;
const int MOD = 1e9 + 7;


void solve() {
	int n;
	cin >> n;
	vector<vector<int>> left(n), right(n);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		if (u > v) swap(u, v);
		left[v].push_back(u);
		right[u].push_back(v);
	}

	int ans = 0, sum = 0, now = 0;
	for (int i = 0; i < n; i++) {
		now += 1 - (int)left[i].size();
		sum += now;
	}

	for (int i = 0; i < n; i++) {
		ans += sum;
		sum -= (n - i);
		for (int j : right[i]) {
			sum += (n - j);
		}
	}
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	srand(time(0));
	int t = 1;
	//int t;
	//cin >> t;
	while (t--) solve();
}

Measured memory_bytes: 24948
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define mp make_pair
#define np next_permutation
#define pb push_back
#define all(x) (x.begin(),x.end())
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
 
#define fi first
#define se second 
using namespace std;
const int maxn=1e4+5;
const int maxl=26;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
 
int cnt[maxn],ans[maxn];
void solve(){
	rep(i,1,300) cnt[i]++;
	rep(i,2,300){
		for(int j=1;j*i<=300;j++){
			cnt[i*j]++;
		}
	}
	int ccnt=0;ans[0]=0;
	rep(i,1,300) {
		if(cnt[i]==8 and (i&1)){
			ans[i]=++ccnt;
		}
		else ans[i]=ccnt;
	}
	rep(i,1,300) {
//		cout<<"ans["<<i<<"]="<<ans[i]<<endl;
	}
}
 
int a,b;
int main(){
	ios::sync_with_stdio(false); 
	solve();
	int n;
	while(cin>>n)
		cout<<ans[n]<<endl;
} 

Measured memory_bytes: 256
a,b,c = map(int,input().split())
k = int(input())
for i in range(k):
         if b <= a:
                  b *= 2
                  k -= 1
for i in range(k):
         if c <= b:
                  c *= 2
if a < b and b < c:
         print ("Yes")
else:
         print("No")
         



Measured memory_bytes: 9092
#include <bits/stdc++.h>
using namespace std;
long long dp[100000], h[100000];
long long calc(int u, int n)
{
    if(u == n-1) return 0;
    if(u == n-2) return abs(h[n-2] - h[n-1]);

    if(dp[u] != -1)
        return dp[u];

    dp[u] = abs(h[u]-h[u+1])+calc(u+1, n);
    dp[u] = min(dp[u], abs(h[u]-h[u+2])+calc(u+2, n));
    return dp[u];
}

int main( )
{
    memset(dp, -1, sizeof(dp));
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    cout << calc(0, n) << endl;
}

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

ll sum(ll n) {
    ll sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    ll k;
    cin >> k;
    ll ans = 1, toAdd = 1;
    while (k--) {
        cout << ans << endl;
        if (sum(ans + toAdd) * (ans + toAdd * 10) < sum(ans + toAdd * 10) * (ans + toAdd))
            toAdd *= 10;
        ans += toAdd;
    }
}


Measured memory_bytes: 3596
import java.util.Scanner;
class Main{
    public static void main(String[] args){
	String s;
	int flag;
	Scanner in = new Scanner(System.in);
	while(true){
	    s = in.next();
	    if(s.equals("#"))break;
	    char ch[] = s.toCharArray();
	    int coun=0;
	    if((ch[0]>='a' && ch[0]<='g') || (ch[0]>='q' && ch[0]<='t') ||(ch[0]>='v' && ch[0]<='x') || ch[0] == 'z')flag=0;
	    else flag=1;
	    for(int i=0;i<s.length();i++){
		if( ( (ch[i]>='a' && ch[i]<='g') || (ch[i]>='q' && ch[i]<='t') ||(ch[i]>='v' && ch[i]<='x') || ch[i] == 'z') && flag == 1 ){coun++;
		    flag = 0;
		    continue;
		}	else if( !((ch[i]>='a' && ch[i]<='g') || (ch[i]>='q' && ch[i]<='t') ||(ch[i]>='v' && ch[i]<='x') || ch[i] == 'z') && flag == 0){coun++;
		    flag = 1;
		    continue;
		}
	    }
	    System.out.println(coun);
	}
    }
}

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

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	ll N,M;
	cin>>N>>M;
    vector<ll> A(N);

    rep(i,N){
        cin>>A[i];
    }
    sort(A.begin(),A.end());
    typedef pair<ll,ll> P;
    vector<P> BC(M);
    ll b,c;
    rep(i,M){
        cin>>b>>c;
        BC[i] = P{b,c};
    }
    sort(BC.begin(),BC.end(),[](P p1,P p2){return p1.second >p2.second;});
    vector<ll> new_num(N);
    ll ind = 0;
    rep(i,M){
        b = BC[i].first;
        c = BC[i].second;
        rep(j,b){
            new_num[ind]=c;
            ++ind;
            if(ind==N) break;
        }
        if(ind==N) break;
    }
    ll ans = 0;
    rep(i,N){
        ans += A[i];
    }
    ll max_ans = ans;

    rep(i,N){
        ans -= A[i];
        ans += new_num[i];
        max_ans = max(ans,max_ans);
    }
    cout<<max_ans<<"\n";

	return 0;
}

Measured memory_bytes: 3456
#include <stdio.h>
#include <string.h>
 
int main(void)
{
    unsigned char num1[100],num2[100];
    int ia,ib,i,j,k,l,num,ex,large,small;
    int size1,size2;
    int sum[100];
    scanf("%d",&num);
    for (l = 0; l < num; ++l)
    {
        scanf("%s",num1);
        scanf("%s",num2);
        size1 = strlen(num1);
        size2 = strlen(num2);
        if (size2 >= size1)
        {
            large = (size2 - 1);
            small = (size1 - 1);
        }
        else if (size1 >= size2)
        {
            large = (size1 - 1);
            small = (size2 - 1);
        }
        if (large >= 80)
        {
            printf("overflow\n");
            continue;
        }
        for(ia = 0; ia < 100; ia++)
        {
            if(num1[ia+1] == '\0')break;
             
            ex = num1[ia];
            num1[ia] = num1[ia+1];
            num1[ia+1] = ex;
        }
        for (j = ia; j > 0 ; --j)
        {
            for (k = 0; k < j-1; ++k)
            {
                ex = num1[k];
                num1[k] = num1[k+1];
                num1[k+1] = ex;
            }
        }
        j=0;
        k=0;
        for(ib = 0; ib < 100; ib++)
        {
            if(num2[ib+1] == '\0')break;
             
            ex = num2[ib];
            num2[ib] = num2[ib+1];
            num2[ib+1] = ex;
        }
        for (j = ib; j > 0 ; --j)
        {
            for (k = 0; k < j-1; ++k)
            {
                ex = num2[k];
                num2[k] = num2[k+1];
                num2[k+1] = ex;
            }
        }
        j=0;
        k=0;
        if (ia == 0 && ib == 0)
        {
            printf("%d\n", (num1[0]-48) + (num2[0]-48));
            continue;
        }
        if (ia != ib)
        {
            for (j = small + 1; j <= large ; ++j)
            {
                if (ia < ib)
                {
                    num1[j] = '0';
                }
                else if (ib < ia)
                {
                    num2[j] = '0';
                }
            }
        }
        for (i = 0; i <= large+1; ++i)
        {
            sum[i] = 0;
        }
        i = 0;
        for (i = 0; i <= large; ++i)
        {
            sum[i] += ((num1[i]-'0') + (num2[i]-'0'));
            if (sum[i] >= 10)
            {
                sum[i] -= 10;
                sum[i+1] += 1;
 
                if (i == large)
                {
                    large += 1;
                    break;
                }
            }
        }
        if (large >= 80)
        {
            printf("overflow\n");
            continue;
        }
        for (i = large; i >= 0; --i)
        {
            printf("%d", sum[i]);
        }
        printf("\n");
        i = 0;
    }
    return 0;
}



Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
const int SIZE1 = 103;
const int SIZE2 = 1e5 + 120;
const int MOD = 1e9 + 7;

int kids[SIZE1];
int dp[SIZE1][SIZE2];
int pom[SIZE1][SIZE2];

int n, k;

    void input(){
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
            cin >> kids[i];
    }

    void preproces(){
        for(int i = 0; i <= n; i++){
            dp[i][0] = 1;
            pom[i][0] = 1;
        }
        for(int i = 0; i <= k; i++)
            pom[0][i] = 1;
    }

    void debug(){
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++)
                cout << pom[i][j] << " ";
                cout << "\n";
        }
        cout << "\n" << "\n";
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++)
                cout << dp[i][j] << " ";
                cout << "\n";
        }
        return;
    }
int main(){

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

    input();
    preproces();
    //debug();

    for(int i = 1; i <= n; i++){
        //debug();
        for(int j = 1; j <= k; j++){
            if(j - kids[i] <= 0)    dp[i][j] = pom[i-1][j];
            else                    dp[i][j] = (pom[i-1][j] - pom[i - 1][j - kids[i] - 1] + MOD) % MOD;
        }
        for(int j = 1; j <= k; j++)
            pom[i][j] = (pom[i][j-1]+dp[i][j])%MOD;
    }
    //debug();
    return cout << dp[n][k]%MOD, 0;
}

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

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

#include <cassert>
#include <functional>

typedef long long ll;
using namespace std;

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

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v);

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

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

void _tostr_rec(ostringstream &oss) {
  oss << "\b\b \b";
}

template<typename Head, typename... Tail>
void _tostr_rec(ostringstream &oss, Head &&head, Tail &&... tail) {
  oss << head << ", ";
  _tostr_rec(oss, forward<Tail>(tail)...);
}

template<typename... T>
string _tostr(T &&... args) {
  ostringstream oss;
  int size = sizeof...(args);
  if (size > 1) oss << "{";
  _tostr_rec(oss, forward<T>(args)...);
  if (size > 1) oss << "}";
  return oss.str();
}
#endif

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


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

  int ans1 = 0, ans2 = 0;

  for (int i = 0; i < S.size(); i++) {
    ans1 += (i % 2) + '0' == S[i];
    ans2 += (i + 1) % 2 + '0' == S[i];
  }

  cout << min(ans1, ans2) << endl;

  return 0;
}

Measured memory_bytes: 3756
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
using namespace std;

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

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair

const int M = 101;
int A, B;
int d[M][M];
int a[M][M];

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	scanf("%d%d", &A, &B);
	for (int i = 1; i <= A; i++)
		for (int j = 1; j <= B; j++)
			scanf("%d", &d[i][j]);
	for (int x = 0; x < M; x++)
		for (int y = 0; y < M; y++) {
			a[x][y] = 0;
			for (int i = 1; i <= A; i++)
				for (int j = 1; j <= B; j++) {
					a[x][y] = max(a[x][y], d[i][j] - i * x - j * y);
				}
		}
	for (int i = 1; i <= A; i++)
		for (int j = 1; j <= B; j++) {
			bool ok = false;
			for (int x = 0; x < M; x++)
				for (int y = 0; y < M; y++) {
					if (a[x][y] + i * x + j * y == d[i][j])
						ok = true;
				}
			if (!ok) {
				printf("Impossible\n");
				return 0;
			}
		}
	printf("Possible\n");
	printf("%d %d\n", 2 * M, 2 * M - 2 + M * M);
	for (int i = 0; i < M - 1; i++) {
		printf("%d %d X\n", 1 + i, 1 + i + 1);
		printf("%d %d Y\n", 1 + M + i + 1, 1 + M + i);
	}
	for (int x = 0; x < M; x++)
		for (int y = 0; y < M; y++)
			printf("%d %d %d\n", 1 + x, 1 + M + y, a[x][y]);
	printf("1 %d\n", M + 1);

	return 0;
}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int N;
  cin>>N;
  vector<int>A(N+1);
  A[0]=0;
  for(int i=1;i<=N;i++)cin>>A[i];
  vector<int>c(N+1);
  for(int i=0;i<N+1;i++){
    if(i==N)c[N]=abs(A[N]);
    else c[i]=abs(A[i]-A[i+1]);
  }
  ll ans=0;
  for(auto it:c)ans+=it;
  for(int i=1;i<N+1;i++){
    int mc,pc;
    if(i==N)mc=c[N]+c[N-1],pc=abs(A[N-1]);
    else mc=c[i-1]+c[i],pc=abs(A[i-1]-A[i+1]);
    cout<<ans-mc+pc<<endl;
  }
  return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;;
int main(){
  int N,jug=0;
  cin >> N;
  vector<int> su(N);
  for(int i=0;i<N;i++)cin >> su[i];
  for(int i=1;i<N-1;i++){
    if(su[i]>su[i-1]&&su[i+1]>su[i]||su[i]>su[i+1]&&su[i-1]>su[i])jug++;
  }
  cout << jug << endl;
}
 

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF INT_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

struct RSQSeg{
  vector<ll>node;
  int n;
  RSQSeg(vector<ll>v){
    int sz=v.size();
    n=1;while(n<sz)n*=2;
    node.resize(2*n-1,0);
    for(int i=0;i<sz;i++)node[n-1+i]=v[i];
    for(int i=n-2;i>=0;i--)node[i]=node[2*i+1]+node[2*i+2];
  }
  void add(int x,ll v){
    x+=n-1;
    node[x]+=v;
    while(x>0){
      x=(x-1)/2;
      node[x]=node[2*x+1]+node[2*x+2];
    }
  }
  ll getsum(int a,int b,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return node[k];
    ll vl=getsum(a,b,2*k+1,l,(r+l)/2);
    ll vr=getsum(a,b,2*k+2,(r+l)/2,r);
    return vl+vr;
  }
};

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

  int n,q;
  cin>>n>>q;
  RSQSeg seg(vector<ll>(n,0));
  for(int i=0;i<q;i++){
    ll query,x,y;
    cin>>query>>x>>y;
    if(query)cout<<seg.getsum(x-1,y)<<endl;
    else seg.add(x-1,y);
  }
  return 0;
}



Measured memory_bytes: 5732
#include <iostream>
#include <vector>

constexpr int mod = 1'000'000'007; // '

int main(void){
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false);
    int n; std::cin >> n;
    long long int res = 0, sum = 0;
    for(int i = 0; i < n; ++i){
        int a; std::cin >> a;
        res += sum * a; res %= mod;
        sum += a; if(sum >= mod) sum -= mod;
    }
    std::cout << res << '\n';
    return 0;
}

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



public class Main{
	public static void main(String[] args){


		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
		String[] s_array;
		String s;
		StringBuffer buf=new StringBuffer();

		try{
			while(true){
		s=reader.readLine();
		if(s==null)break;
		buf.append(s);

		}
		s_array=buf.toString().split("");

		Alphabet(s_array);

		}catch(IOException e){
			System.out.println(e);
		}

	}

	//?????????????????????????????§1????????????????????????????????????????????£??\??????

	private static void Alphabet(String[] s_array){

		int[] alp=new int[26];
		Arrays.fill(alp, 0);

		for(int i=0;i<s_array.length;i++){
			s_array[i]=s_array[i].toLowerCase();

			switch(s_array[i]){

			case("a"):
				alp[0]+=1;break;
			case("b"):
				alp[1]+=1;break;
			case("c"):
				alp[2]+=1;break;
			case("d"):
				alp[3]+=1;break;
			case("e"):
				alp[4]+=1;break;
			case("f"):
				alp[5]+=1;break;
			case("g"):
				alp[6]+=1;break;
			case("h"):
				alp[7]+=1;break;
			case("i"):
				alp[8]+=1;break;
			case("j"):
				alp[9]+=1;break;
			case("k"):
				alp[10]+=1;break;
			case("l"):
				alp[11]+=1;break;
			case("m"):
				alp[12]+=1;break;
			case("n"):
				alp[13]+=1;break;
			case("o"):
				alp[14]+=1;break;
			case("p"):
				alp[15]+=1;break;
			case("q"):
				alp[16]+=1;break;
			case("r"):
				alp[17]+=1;break;
			case("s"):
				alp[18]+=1;break;
			case("t"):
				alp[19]+=1;break;
			case("u"):
				alp[20]+=1;break;
			case("v"):
				alp[21]+=1;break;
			case("w"):
				alp[22]+=1;break;
			case("x"):
				alp[23]+=1;break;
			case("y"):
				alp[24]+=1;break;
			case("z"):
				alp[25]+=1;break;
			default:break;
			}//switch

		}//for

		System.out.println("a : "+alp[0]);
		System.out.println("b : "+alp[1]);
		System.out.println("c : "+alp[2]);
		System.out.println("d : "+alp[3]);
		System.out.println("e : "+alp[4]);
		System.out.println("f : "+alp[5]);
		System.out.println("g : "+alp[6]);
		System.out.println("h : "+alp[7]);
		System.out.println("i : "+alp[8]);
		System.out.println("j : "+alp[9]);
		System.out.println("k : "+alp[10]);
		System.out.println("l : "+alp[11]);
		System.out.println("m : "+alp[12]);
		System.out.println("n : "+alp[13]);
		System.out.println("o : "+alp[14]);
		System.out.println("p : "+alp[15]);
		System.out.println("q : "+alp[16]);
		System.out.println("r : "+alp[17]);
		System.out.println("s : "+alp[18]);
		System.out.println("t : "+alp[19]);
		System.out.println("u : "+alp[20]);
		System.out.println("v : "+alp[21]);
		System.out.println("w : "+alp[22]);
		System.out.println("x : "+alp[23]);
		System.out.println("y : "+alp[24]);
		System.out.println("z : "+alp[25]);
	}//Alphabet????????????
}

Measured memory_bytes: 25248
n = int(input())
A = list(map(int, input().split()))

B = [1]
for i in range(n):
    B.append((B[i]-A[i])*2)

C = [A[n]]

for i, s in enumerate(B):
    if i == len(B)-1:
        a = 1
    elif B[i] <= 0:
        print(-1)
        exit()
if B[-1]-A[n] < 0:
    print(-1)
    exit()

for i in range(n):
    C.append(C[i]+A[n-1-i])
C = C[::-1]

num = 0
frag = 0
for i in range(n):
    if B[i] >= C[i]:
        frag = 1
    if frag == 0:
        num += B[i]
    else:
        num += C[i]
num += C[n]
print(num)


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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A.at(i);
  }
  int mx = *max_element(A.begin(), A.end());
  int mn = *min_element(A.begin(), A.end());
  cout << mx - mn << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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; }



int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  vector<ll> maxa(n, n), ans = a;
  rep(i, k) {
    if (ans == maxa) break;
    vector<ll> cnt(n + 1, 0);
    rep(i, n) {
      ll s = i - ans[i];
      chmax(s, 0LL);
      ll e = i + ans[i] + 1;
      chmin(e, n);
      cnt[s]++;
      cnt[e]--;
    }
    vector<ll> nxt(n, 0);
    ll rescnt = 0;
    rep(i, n) {
      rescnt += cnt[i];
      nxt[i] = rescnt;
    }
    ans = nxt;
  }
  rep(i, n) cout << ans[i] << ' ';
  cout << '\n';


  




  
  return 0;
}

Measured memory_bytes: 11116
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        x -= a;
        while(x >= b) {
            x -= b;
        }
        System.out.println(x);
    }
}


Measured memory_bytes: 22484
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
void chmax(LL& a, LL b) {
	a = max(a, b);
}
//////////////
vector<LL> kai(200001);
vector<LL> kai_inv(200001);

LL powMod(LL num, LL n, LL mod = (LL)MOD) {//(num**n)%mod
	num %= mod;//
	if (n == 0) {
		return (LL)1;
	}
	LL mul = num;
	LL ans = (LL)1;
	while (n) {
		if (n & 1) {
			ans = (ans * mul) % mod;
		}
		mul = (mul * mul) % mod;
		n >>= 1;
	}
	return ans;
}
LL mod_inverse(LL num, LL mod = MOD) {
	return powMod(num, MOD - 2, MOD);
}

LL nCk(LL N, LL k, LL mod = MOD) {
	LL ans = 1;
	if (k == 0 || k == N) {
		return 1;
	}
	ans = (kai[N] * kai_inv[N - k]) % mod;
	ans = (ans * kai_inv[k]) % mod;
	return ans;
}

LL cal(LL H, LL W,LL K) {
	LL ans = 0;
	LL base = nCk(H * W - 2, K - 2);
	base = (base * H) % MOD;
	base = (base * H) % MOD;
	for (LL i = 0; i < W; ++i) {
		ans += i * (W - i);
		ans %= MOD;
	}
	/*
	for (int w1 = 0; w1 < W; ++w1) {
		for (int w2 = w1; w2 < W; ++w2) {
			ans += abs(w1 - w2);
			ans %= MOD;
		}
	}
	*/
	ans = (ans * base) % MOD;
	return ans;
}
void solve() {
	LL N, M, K;
	cin >> N >> M >> K;

	kai[0] = 1; //kai_inv[0] = mod_inverse(1);
	kai[1] = 1; kai_inv[1] = mod_inverse(1);

	for (int i = 2; i <= 200000; ++i) {
		kai[i] = (kai[i - 1] * i) % MOD;
		kai_inv[i] = mod_inverse(kai[i]);
	}
	LL ans = (cal(N, M, K) + cal(M, N, K)) % MOD;
	cout << ans << endl;
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 3328
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from collections import defaultdict
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    S=[0]*(n+1)
    for i in range(n):
        S[i+1]=S[i]+A[i]
    D=defaultdict(int)
    for s in S:
        D[s%m]+=1
    ans=0
    for val in D.values():
        ans+=val*(val-1)//2
    print(ans)
resolve()

Measured memory_bytes: 62576
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

s =input().split()
A = int(s[0])
B = int(s[1])
C = int(s[2])
D = int(s[3])

CD = lcm(C,D)
ac = (A-1)//C
bc = B//C
ad = (A-1)//D
bd = B//D
acd = (A-1)//CD
bcd = B//CD

cnt = B - bc - bd + bcd - (A-1) + ac + ad - acd
print(cnt)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const long long mod = 1e9+7;
long long power(long long a, long long b, long long m = mod) {
    if(b < 0) {
        return power(power(a, -b), mod-2);
    }
    long long x = 1;
    while(b) {
        if(b & 1) {
            x = 1ll * x * a % m;
        }
        a = 1ll * a * a % m;
        b /= 2;
    }
    return x;
}
const int N = 3e5+9;
ll sm_sum = 0, lg_sum = 0;
multiset<int> small, large;
void insl(int x) {
    large.insert(x);
    lg_sum += x;
}
void inss(int x) {
    small.insert(x);
    sm_sum += x;
}
void rmvl() {
    auto it = large.begin();
    lg_sum -= *it;
    inss(*it);
    large.erase(it);
}
void rmvs() {
    auto it = --small.end();
    sm_sum -= *--small.end();
    insl(*it);
    small.erase(--small.end());
}
signed main() {  
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    

    int q; cin >> q;
    ll sum = 0;
    while(q--) {
        int ty; cin >> ty;
        if(ty == 1) {
            int u, v; cin >> u >> v;
            sum += v;
            if(!small.empty() && *--small.end() >= u) {
                rmvs();
                inss(u);
            } else {
                insl(u);
            }
            if((int) large.size() > (int) small.size()+1) {
                rmvl();
            }
        } else {
            // 
            int n = small.size() + large.size();
            ll ansx = 0, ansv = 0;
            if(n & 1) {
                ansx = *large.begin();
                ansv -= ansx;
            } else {
                ansx = *--small.end();
            }
            // cout << "$" << lg_sum << " " << sm_sum << " " << ansx << endl;
            ansv += lg_sum - sm_sum;
            cout << ansx << " " << ansv+sum << "\n";
        }
    }
    






    return 0;
    
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n)repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
typedef pair<int,int> P;
typedef pair<int, P> PP;
#define all(v) v.begin(),v.end()
#define fi first
#define se second
const int inf = 1e9;

struct edge{int v,p;};
bool cmp(edge x, edge y){
	if(x.v == y.v)return x.p < y.p;
	else return x.v > y.v;
}
int ans[100001];
edge a[100002];
signed main(){
	int n;
	scanf("%lld", &n);
	rrep(i,n){
		int x;
		scanf("%lld", &x);
		a[i] = (edge){x,i};
	}
	sort(a+1, a+n+1, cmp);
	
	a[n+1] = (edge){0, 0};
	int k = inf;
	rrep(i,n){
		edge e = a[i];
		edge e2 = a[i+1];
		k = min(k, e.p);
		ans[k] += (e.v-e2.v)*i;
	}
	rrep(i,n)printf("%lld\n", ans[i]);
	return 0;
}

Measured memory_bytes: 3456
/* --- author: dxm --- */
#include<bits/stdc++.h>
using namespace std;

#define INF 1e9
#define Inf 1e18
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fst first
#define snd second
typedef long long ll;
inline void Fail(){printf("0");exit(0);}

const int maxn=100005;
int n,m,q;
string s,t;
int sum[maxn][2];
char c[maxn];

int main(){
	scanf("%s",c);s=c;n=s.size();
	scanf("%s",c);t=c;m=t.size();
	sum[0][0]=(s[0]=='A'?1:2);
	REP(i,n-1)sum[i][0]=(sum[i-1][0]+(s[i]=='A'?1:2))%3;
	sum[0][1]=(t[0]=='A'?1:2);
	REP(i,m-1)sum[i][1]=(sum[i-1][1]+(t[i]=='A'?1:2))%3;
	scanf("%d",&q);
	while(q--){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		a--;b--;c--;d--;
		int x=(sum[b][0]-(!a?0:sum[a-1][0])+3)%3;
		int y=(sum[d][1]-(!c?0:sum[c-1][1])+3)%3;
		printf(x==y?"YES\n":"NO\n");
	}
	return 0;
}

/*
Input:
-----------------
Output:
*/

Measured memory_bytes: 1664
#include <iostream>

using namespace std;

int main()
{
    char k;
    cin>>k;
    if(k == 'a' || k == 'e' || k == 'i' || k == 'o'|| k == 'u')
    {
        cout<<"vowel"<<endl;
    }
    else
    {
        cout<<"consonant"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
def f(n):
    if n < 0:
        return 0
    i = n % 4
    if i == 0:
        return n
    elif i == 1:
        return 1
    elif i == 2:
        return n + 1
    else:
        return 0

a,b = map(int,input().split())
print((f(a-1)^f(b)))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,i,j,sum=0,k=0,l=0,c=0;
    cin >> n >> m;
    int a[n];
    for(i=0; i<n; i++)
    {
        cin >> a[i];
        sum+=a[i];
    }
    for(i=0; i<n; i++)
    {
        if(a[i]>=sum/(4.0*m))
        {
            c++;
        }
    }
    if(c>=m)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


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

int a, b, q;
vector<ll> s, t;

ll mindis(ll x, int i, int j){
    ll res = 3e10;
    res = min(res, max(s[i] - x, t[j] - x));
    res = min(res, max(x - s[i - 1], x - t[j - 1]));
    res = min(res, 2 * min(x - t[j - 1], t[j] - x) + min(x - s[i - 1], s[i] - x));
    res = min(res, min(x - t[j - 1], t[j] - x) + 2 * min(x - s[i - 1], s[i] - x));
    return res;
}

int main(){
    cin >> a >> b >> q;
    s.resize(a + 2);
    t.resize(b + 2);
    s[0] = -2e10;
    s[a + 1] = 3e10;
    t[0] = -2e10;
    t[b + 1] = 3e10;

    rep(i, a) cin >> s[i + 1];
    rep(i, b) cin >> t[i + 1];

    rep(num, q){
        ll x;
        cin >> x;
        int i = lower_bound(s.begin(), s.end(), x) - s.begin();
        int j = lower_bound(t.begin(), t.end(), x) - t.begin();
        cout << mindis(x, i, j) << endl;
    }
}


Measured memory_bytes: 4768
#include <iostream>
#include <vector>
 
int main() {
  const unsigned long long MOD = 1000000007;
  unsigned long N;
  unsigned long long A, B, C, D;
  std::cin >> N >> A >> B >> C >> D;
  std::vector<unsigned long long> inv(N + 1);
  inv[1] = 1;
  for (unsigned i = 2; i <= N; ++i) { inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD; }
  std::vector<unsigned long long> fact(N + 1);
  fact[0] = 1;
  for (unsigned i = 1; i <= N; ++i) { fact[i] = fact[i - 1] * i % MOD; }
  std::vector<unsigned long long> inv_fact(N + 1);
  inv_fact[0] = 1;
  for (unsigned i = 1; i <= N; ++i) { inv_fact[i] = inv_fact[i - 1] * inv[i] % MOD; }
  std::vector<std::vector<unsigned long long>> dp(N + 1, std::vector<unsigned long long>(N + 1, 0));
  for (unsigned i = 0; i <= N; ++i) { dp[0][i] = 1; }
  for (unsigned i = 1; i <= N; ++i) {
    for (auto j = A; j <= B; ++j) {
      dp[i][j] = dp[i][j - 1];
      if (i / j < C) { continue; }
      unsigned long long tmp = 1;
      for (unsigned k = 0; k < C - 1; ++k) {
        tmp *= inv_fact[j];
        tmp %= MOD;
      }
      for (auto k = C; k <= std::min(i / j, D); ++k) {
        tmp *= inv_fact[j];
        tmp %= MOD;
        auto acc = dp[i - k * j][j - 1];
        //choose{i}{k*j} * frac{(k*j)!}{j!**k*k!}
        //i!(k*j)! / (k*j)!(i-k*j)!(j!)**k(k!)
        //i! / (i-k*j)!(j!)**k(k!)
        acc *= fact[i];
        acc %= MOD;
        acc *= inv_fact[i - k * j];
        acc %= MOD;
        acc *= tmp;
        acc %= MOD;
        acc *= inv_fact[k];
        acc %= MOD;
        dp[i][j] += acc;
        dp[i][j] %= MOD;
      }
    }
  }
  std::cout << dp[N][B];
  return 0;
}

Measured memory_bytes: 8192
#include <iostream>
#include <map>
#include <string>
using namespace std;

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

	map<string, bool> gift_map;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		gift_map[s] = true;
	}
	cout << gift_map.size() << endl;
	//int count = 0;
	//for (auto itr = gift_map.begin(); itr != gift_map.end(); itr++) {
	//	count++;
	//}
	//cout << count << endl;
	return 0;
}

Measured memory_bytes: 19108
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,max=0,count = 0;
    char s[n];
    cin>>n>>s;
    for(int i =0;i<n;i++)
    {
        if (s[i] == 'I')
            count += 1;
        else if (s[i] == 'D')
            count -= 1;
        if (count >max)
          max = count;
    }   
    cout<<max;;
}

Measured memory_bytes: 256