akhauriyash/Code-Regression huggingface dataset:
// writer: w33z8kqrqk8zzzx33
#include <bits/stdc++.h>
using namespace std;

// begin fast read template by CYJian (source: https://www.luogu.com.cn/paste/i11c3ppx)

namespace io {
	const int __SIZE = (1 << 21) + 1;
	char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
	#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
	inline void gc (char &x) { x = Gc(); }
	inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
	inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
		for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
	template <class I> inline bool gi (I &x) { _eof = 0;
		for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
		for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
	template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;

// end fast read template by CYJian

#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;

uint8_t can[30][200005];
int p2;
int a[200005], b[200005];
int n;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    gi(n);
	p2 = 1; rep(i, n-1) p2 = 2*p2%MOD;
	rep(i, n) gi(a[i]);
	rep(i, n) gi(b[i]);
	rep(l, 30) {
		int bv = 0;
		rep(i, n) bv = (bv*2+(bool)(b[i]&(1<<l)))%MOD;
		rep(x, 2) {
			int av = 0;
			rep(i, n) av = (av*2+(x^(bool)(a[i]&(1<<l))))%MOD;
			rep(k, n) {
				if(av == bv) can[l][k]=(x+1);
				av = (av+MOD-p2*(x^(bool)(a[k]&(1<<l))))%MOD;
				av = (av*2+(x^(bool)(a[k]&(1<<l))))%MOD;
			}
		}
	}
	rep(k, n) {
		int x = 0;
		rep(l, 30) {
			if(!can[l][k]) { x = -1; break; }
			x |= ((can[l][k]-1)<<l);
		}
		if(x != -1) print(k), pc(' '), print(x), pc('\n');
	}
}


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

int main(){
    int n,k;
    cin >> n >> k;
    ll a[n];
    rep(i,n){
        ll temp;
        cin >> temp;
        a[i] = temp;
    }
    ll ans = 3000000000000;
    for (int bit = 0; bit < (1<<n); ++bit) {
        vector<int> S;
        //bool ok = true;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // 列挙に i が含まれるか
                S.push_back(i);
            }
        }
      if(k == 1){
        cout << 0 << endl;
        return 0;
      }
      else if(S.size() == k){
        ll least=0;
        ll temp = 0;
        int count = 0;
        int index = S[count];
        rep(i,n){
          if(i - index == 0){
            //cout << count << endl;
              //temp += max(0,least - a[index]);
            if(least+1 >= a[index]){
              temp = temp + least +1- a[index];
            }
              count++;
              index = S[count];
            least = max(least+1,a[i]);
          }
          else least = max(least,a[i]);
          //if(a[i] > least+1) least = a[i];
          if(count == k) break;
        }
        ans = min(ans,temp);
      }
    }
    cout << ans << endl;
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> adj_list(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        --a;
        --b;
        adj_list[a].push_back(make_pair(b, w%2));
        adj_list[b].push_back(make_pair(a, w%2));
    }
    vector<int> color(n, -1);
    function<void (int, int)> dfs = [&](int i, int c) {
        if (color[i] != -1) {
            return;
        }
        color[i] = c;
        for (auto e : adj_list[i]) {
            dfs(e.first, (c + e.second) % 2);
        }
    };
    dfs(0, 0);
    for (auto c : color) {
        cout << c << "\n";
    }
    return 0;
}


Measured memory_bytes: 8960
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

#define PSI pair<string,int>

vector<PSI> book;

int main(void){
	int x;
	char tmp[1024];
	while(scanf("%s%d",tmp,&x)!=EOF){
		string a;
		a = tmp;
		book.push_back(PSI(a,x));
	}
	
	sort(book.begin(),book.end());
	
	for(int i = 0; i < book.size(); i++){
		vector<int> ans;
		puts(book[i].first.c_str());
		ans.push_back(book[i].second);
		while(i+1<book.size() && book[i+1].first==book[i].first){
			i++;
			ans.push_back(book[i].second);	
		}
		sort(ans.begin(),ans.end());
		for(int j = 0; j < ans.size(); j++){
			if(j != 0)printf(" ");
			printf("%d",ans[j]);
		}puts("");
		
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define faster_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
#define bug(a)       cerr << #a << " : " << a << endl;
template<class T>void ExEuclid(T n, T m, T &a, T &b, T &gcd){if(m==0){gcd=n;a=1;b=0;return;}ExEuclid(m,n%m,a,b,gcd);T x=a;a=b;b=x-(n/m)*a;}
template<class T>T gcd(T n, T m){if(m==0){return n;}gcd(m,n%m);}
template<class T>T lcm(T n, T m){return (n*m)/gcd(n,m);}
template<class T>string to_string(T n){string s="";while(n)s+=((n%10)+'0'),n/=10;reverse(s.begin(),s.end());return s;}
template<class T>ll to_int(T s){ll num=0,power=0;for(int i=s.size()-1; i>=0; i--)num+=(pow(10.0,power++)*(s[i]-'0'));return num;}
template<class T>bool is_mod(T n, T m){if(n%m==0)return true;return false;}
template<class T>bool is_upper(T s){for(int i=0; i<s.size(); i++)if(s[i]>90 || s[i]<65)return false;return true;}
template<class T>bool is_lower(T s){for(int i=0; i<s.size(); i++)if(s[i]>122 || s[i]<97)return false;return true;}
template<class T>T mod(T n, T m){return ((n%m)+m)%m;}
template<class T>T Big_mod(T base, T power, T MOD){
    if(power==1)return base;
    if(power & 1)return ((base%MOD)*(Big_mod(base,power-1,MOD))%MOD)%MOD;
    else {T temp=(Big_mod(base,power>>1,MOD));return ((temp%MOD)*(temp%MOD))%MOD;}
}



int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    faster_io;
    ll n;
    cin>>n;
    ll x[n+5],y[n+5],ans=0;
    for(int i=0; i<n; i++)cin>>x[i];
    for(int i=0; i<n; i++)cin>>y[i];
    for(int i=0; i<n; i++){
        ans+=max(ll(0),x[i]-y[i]);
    }

    cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int i,flg = 0;
    char s[20],t[20];
    scanf("%s", s);
    scanf("%s", t);
    for(i = 0;s[i] != '\0';i ++){
        if(s[i] != t[i]){
            flg = 1;
            break;
        }
    }
    if(flg == 0){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 1616
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)
# print(A)

ans = A[0]
for i in range(1, N-1):
    # print(i)
    index = (i + 1) // 2
    # print("index: {} v: {}".format(index, A[index]))
    ans += A[index]

print(ans)

Measured memory_bytes: 31524
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using ll = long long;
using Double = long double;
const Int INF = 1LL<<55;
const Int mod = (1e9)+7;
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
ostream& operator<<(ostream& o,T t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){Int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

class RMQ{
public:
  typedef long long ll;
  ll INF = 1LL<<55;
  Int n,n_;
  vector<P> dat;
  Int toMax;

  //初期化
  RMQ(){n=-1;}
  RMQ(Int n_,Int toMax = 0):n_(n_),toMax(toMax){
    n=1;
    while(n<n_)n*=2;
    dat.resize(2*n-1,P(INF,INF));
  }
  
  //k番目の値をaに変更
  void update(Int k,P a){
    //if(toMax) a *= -1;
    k+=n-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }
  
  //[a,b)の最小値を求める query(a,b,0,0,n)
  P find(Int a,Int b,Int k,Int l,Int r){
    if(r<=a||b<=l)return P(INF,INF);
    if(a<=l&&r<=b)return dat[k];
    P vl = find(a,b,k*2+1,l,(l+r)/2);
    P vr = find(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }

  P find(Int a,Int b){
    assert(a <= b), assert(a <= n_ && b <= n_), assert(a >= 0 && a >= 0);
    return /*(toMax? -1:1) * */ find(a,b,0,0,n);
  }
};



Int sim(Int n,Int K,Int Q, vector<Int> A,Int limit){
  priority_queue<Int,vector<Int>, greater<Int> > num;
  vector<Int> B;
  for(Int i=0;i<n;i++) {
    if(A[i] < limit){
      while((Int)num.size() >= K) B.push_back(num.top()), num.pop();
      while(!num.empty()) num.pop();
    }
    else num.push(A[i]);
  }
  while((Int)num.size() >= K) B.push_back(num.top()), num.pop();
  sort(B.begin(), B.end());
  if((Int)B.size() < Q) return INF;
  return B[Q-1] - B[0];
}

signed main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  
  Int n, K, Q;
  cin>>n>>K>>Q;
  vector<Int> A(n);
  cin>>A;

  Int ans = INF;
  for(Int i=0;i<n;i++){
    Min(ans, sim(n,K,Q,A,A[i]));
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;
 
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(20);
  
  int n,m;
  cin >> n >> m;
  vector<int> a(m);
  REP(i,m) cin >> a[i];

  int ans = n;
  REP(i,m){
    ans -= a[i];
  }

  cout << max(ans, -1ll) << endl;
  

  return 0;
}


Measured memory_bytes: 3696
PROGRAM GreedyTakahashi
      IMPLICIT NONE
      integer(16) :: a,b,k
      integer(16) :: sub1
      
      read*,a,b,k
      
      if( a+b<=k )then
        print*,0,0
      else if( a<=k )then
        print*,0,b-(k-a)
      else if( a>k )then
        print*,(a-k),b
      endif
      
      
      
      
      END PROGRAM

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

typedef long long ll;
typedef pair< int, int > PII;
typedef pair< ll, ll > PLL;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define PI 3.14159265358979323846
#define INF 1000000006
#define LINF 1000000000000000006
#define DINF 1e300
#define FI first
#define SE second
#define X FI
#define Y SE
#define PB push_back
#define MP make_pair

const int N = 1e5 + 10;

string s;

void init() {
  cin >> s;
}
void solve() {
  ll ans = LINF, ta = 0;
  
  char start = s[ 0 ];
  for ( int i = 1 ; i < s.size() ; ++i ) { 
    if ( s[ i ] != start ) {
      ++ta;
      start = s[ i ];
    } 
  }
  ans = min( ans, ta );
  ta = 0;
  start = s[ s.size() - 1 ];
  for ( int i = s.size() - 2 ; i >= 0 ; --i ) {
    if ( s[ i ] != start ) {
      ++ta;
      start = s[ i ];
    }
  }
  ans = min( ans, ta );
  cout << ans << endl;
}
int main() {
  IOS;
  int __ = 1;
  //cin >> __;
  while ( __-- ) {
    init();
    solve();
  }
  return 0;
}


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

const int A = 1001001;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> c(A);
  rep(i,n) {
    cin >> a[i];
    c[a[i]]++;
  }
  
  bool pairwise = true;
  for(int i = 2; i < A; i++) {
    int cnt = 0;
    for(int j = i; j < A; j += i) {
      cnt += c[j];
    }
    if (cnt > 1) pairwise = false;
  }
  if (pairwise) {
    cout << "pairwise coprime" << endl;
    return 0;
  }
  
  int g = 0;
  rep(i,n) g = gcd(g,a[i]);
  if (g == 1) {
    cout << "setwise coprime" << endl;
    return 0;
  }
  cout << "not coprime" << endl;
  return 0;
}


Measured memory_bytes: 11116
from queue import deque

n, m, k = map(int, input().split())

friends = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].append(b)
    friends[b].append(a)

checked = [False] * n
groups = []
for i in range(n):
    if checked[i]:
        continue
    checked[i] = True

    que = deque([i])
    group = [i]
    while que:
        now = que.popleft()
        friends_now = friends[now]
        for friend in friends_now:
            if checked[friend] == False:
                checked[friend] = True
                group.append(friend)
                que.append(friend)
    groups.append(group)

# print(groups)

D = dict()
for i in range(len(groups)):
    for j in groups[i]:
        D[j] = i

# print(D)

block = [0] * n
for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if D[c] == D[d]:
        block[c] += 1
        block[d] += 1

for i in range(n):
    group_i = D[i]
    print(len(groups[group_i]) - block[i] - len(friends[i]) - 1)

Measured memory_bytes: 48652
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int a,b,c;
    string ans="NO";
    cin >>a>>b>>c;
    if(a==5&&b==5&&c==7)ans="YES";
    if(a==5&&b==7&&c==5)ans="YES";
    if(a==7&&b==5&&c==5)ans="YES";
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#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> a(n+1), b(n+1);
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;

        a[p] = 30000 * p;
        b[p] = 30000 * (n - p) + i;
    }

    for(int i = 1; i < n; i++){
        cout << a[i] << " ";
    }
    cout << a[n] << endl;
    for(int i = 1; i < n; i++){
        cout << b[i] << " ";
    }
    cout << b[n] << endl;

    return 0;
}


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

const int N = (int)2e5;

int is_prime[N+5];

int start() {
    for (int i=0; i<N+3; i++) is_prime[i] = 1;
    is_prime[0] = is_prime[1] = 0;

    for (int num=2; num<=N; num++) if (is_prime[num]) {
        for (int i=2*num; i<=N; i+=num) is_prime[i] = 0;
    }

    return 0;
}

int main() {
    start();

    int a; scanf("%d", &a);
    for (; is_prime[a] == 0; a++);
    printf("%d\n", a);
    return 0;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long Y = sc.nextLong();
        sc.close();

        long num_10000 = -1;
        long num_5000 = -1;
        long num_1000 = -1;

        long target = Y - 1000 * N;
        long tmp = -1;

        for (int i = 0; i <= N; i++) {
            if ((target - 9000 * i) % 4000 == 0) {
                tmp = (target - 9000 * i) / 4000;
                if ((tmp >= 0) && (N - tmp - i) >= 0) {
                    num_10000 = i;
                    num_5000 = tmp;
                    num_1000 = N - num_10000 - num_5000;
                    break;
                }
            }
        }

        System.out.println(num_10000 + " " + num_5000 + " " + num_1000);
    }
}

Measured memory_bytes: 21204
ans = []
while True:
    lst = []
    try:
        lst = raw_input().split()
    except EOFError:
        break
    lst[0] = float(lst[0])
    lst[1] = float(lst[1])
    if lst[0] < 35.5 and lst[1] < 71.0:
        ans.append("AAA")
    elif lst[0] < 37.5 and lst[1] < 77.0:
        ans.append("AA")
    elif lst[0] < 40.0 and lst[1] < 83.0:
        ans.append("A")
    elif lst[0] < 43.0 and lst[1] < 89.0:
        ans.append("B")
    elif lst[0] < 50.0 and lst[1] < 105.0:
        ans.append("C")
    elif lst[0] < 55.0 and lst[1] < 116.0:
        ans.append("D")
    elif lst[0] < 70.0 and lst[1] < 148.0:
        ans.append("E")
    else:
        ans.append("NA")
for i in ans:
    print i

Measured memory_bytes: 4300
var input = require('fs').readFileSync('/dev/stdin', 'utf8').split(/\n/g);
var n = input[0] - 0;
var k = input[1] - 0;
var list = [];
for (var i = 0; i <= n; i++) {
    var l = (1 << i) + k * (n - i);
    list.push(l);
}
console.log(Math.min.apply(null, list));

Measured memory_bytes: 7372
#include <iostream>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <list>
#include <stack>
#include <climits>
#include <unordered_set>
#define m7 1000000007
#define m9 1000000009
#define ll long long
#define pii pair<int,int>
#define F first
#define S second

using namespace std;
int main()
{
	int dp[100007], H[100007], n,k;
	cin >> n>>k;
	for (int i = 0; i < n; i++) {
		cin >> H[i];
		dp[i] = INT_MAX;
	}
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j + i < n && j <= k; j++)
			dp[i + j] = min(dp[i + j], dp[i] + abs(H[i] - H[i+j]));

	}
	cout << dp[n - 1];
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 1005;
const int mo = 1e9+7;

int n,m;
struct Edge{
	int x,y,v;
	Edge(const int x_=0,const int y_=0,const int v_=0){x=x_;y=y_;v=v_;}
}ed[N*2];
LL X;
int h[N],tot;
struct edge{
	int x,v,nxt;
}e[N*2];

bool cmp(Edge a,Edge b){return a.v<b.v;}

int fa[N];

void inse(int x,int y,int v){e[++tot].x=y;e[tot].v=v;e[tot].nxt=h[x];h[x]=tot;}

bool vis[N];
int co[N];
int dep[N];

void dfs(int x){
	vis[x]=1;
	for(int p=h[x];p;p=e[p].nxt)
	if (!vis[e[p].x]){
		fa[e[p].x]=x;
		co[e[p].x]=e[p].v;
		dep[e[p].x]=dep[x]+1;
		dfs(e[p].x);
	}
}

int getfather(int x){return fa[x]==x?x:fa[x]=getfather(fa[x]);}

int main(){
	n=get();m=get();
	scanf("%lld",&X);
	fo(i,1,m)ed[i].x=get(),ed[i].y=get(),ed[i].v=get();
	if (n<3)return printf("0\n"),0;
	sort(ed+1,ed+1+m,cmp);
	LL sum=0;
	fo(i,1,n)fa[i]=i;
	fo(i,1,m){
		int x=ed[i].x,y=ed[i].y,v=ed[i].v;
		int tx=getfather(x),ty=getfather(y);
		if (tx==ty)continue;
		sum=sum+v;
		fa[tx]=ty;
		inse(x,y,v),inse(y,x,v);
	}
	if (sum>X)return printf("0\n"),0;
	fa[1]=0;
	dep[1]=1;
	dfs(1);
	int cnt0=0,cnt1=0;
	fo(i,1,m){
		int x=ed[i].x,y=ed[i].y,v=ed[i].v;
		if (fa[x]==y||fa[y]==x)continue;
		int mx=0;
		for(int tx=x,ty=y;tx!=ty;){
			if (dep[tx]<dep[ty])swap(tx,ty);
			mx=max(mx,co[tx]);
			tx=fa[tx];
		}
		if (sum-mx+v<X)continue;
		if (sum-mx+v==X)cnt0++;
		else cnt1++;
	}
	LL ans=1;
	if (sum<X){
		fo(i,1,cnt0)ans=ans*2%mo;
		ans--;
		fo(i,1,cnt1)ans=ans*2%mo;
		ans=ans*2%mo;
	}
	else{
		cnt0+=n-1;
		fo(i,1,cnt0)ans=ans*2%mo;
		ans=(ans+mo-2)%mo;
		fo(i,1,cnt1)ans=ans*2%mo;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 384
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  # 負け：0 勝ち：1
  dp=[0]*(k+1)
  for i in range(k+1):
    for x in l:
      y=i+x

      if y<=k:
        if dp[y]==0:
          dp[y]=abs(dp[i]-1)
  # print(dp)

  if dp[k]==1:
    return 'First'
  return 'Second'

# main()
print(main())


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

int main(){
    int n;
    cin>>n;
    vector<vector<int>> d(n,vector<int>(2));
    rep(i,n)cin>>d[i][0]>>d[i][1];
    string ans="No";
    for(int i=2;i<n;i++){
        if(d[i-2][0]==d[i-2][1]&&d[i-1][0]==d[i-1][1]&&d[i][0]==d[i][1]) ans="Yes";
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define int long long
#define double long double
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define inf 1000000000000000007
#define f first
#define s second
#define mini(c,a,b) *min_element(c+a,c+b)
#define maxi(c,a,b) *max_element(c+a,c+b)
#define P pair<int,int>
//printf("%.12Lf\n",);
int keta(int x){
	rep(0,i,30){
		if(x<10){
			return i+1;
		}
		x=x/10;
	}
}
int gcd(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return bb;
		}	
		bb=bb%aa;
		if(bb==0){
			return aa;
		}
	}
}	
int lcm(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return x/bb*y;
		}	
		bb=bb%aa;
		if(bb==0){
			return x/aa*y;
		}
	}
}
bool p(int x){
	if(x==1)return false;
	rep(2,i,sqrt(x)+1){
		if(x%i==0&&x!=i){
			return false;
		}
	}	
	return true;
}
int max(int a,int b){
	if(a>=b)return a;
	else return b;
}
int min(int a,int b){
	if(a>=b)return b;
	else return a;
}	
int n2[41];		
int nis[41]; 
int nia[41];
int mody[41];
int nn;
int com(int n,int y){
	int ni=1;
	for(int i=0;i<41;i++){
		n2[i]=ni;
		ni*=2;
	}
	int bunsi=1,bunbo=1;
	rep(0,i,y)bunsi=(bunsi*(n-i))%mod;
	rep(0,i,y)bunbo=(bunbo*(i+1))%mod;
	mody[0]=bunbo;
	rep(1,i,41){
		bunbo=(bunbo*bunbo)%mod;
		mody[i]=bunbo;
	}
	rep(0,i,41)nis[i]=0;
	nn=mod-2;
	for(int i=40;i>=0;i-=1){
		if(nn>n2[i]){
			nis[i]++;
			nn-=n2[i];
		}
	}
	nis[0]++;
	rep(0,i,41){
		if(nis[i]==1){
			bunsi=(bunsi*mody[i])%mod;
		}
	}
	return bunsi;
}
int yakuwa(int n){
	int sum=0;
	rep(1,i,sqrt(n+1)){
		if(n%i==0)sum+=i+n/i;
		if(i*i==n)sum-=i;
	}
	return sum;
}	
bool integer(double n){
	if(n==long(n))return true;
	else return false;	
}
int pow(int b,int a){	
	int aa=1;
	rep(0,i,a)aa*=b;	
	return aa;
}
int sankaku(int a){
	return a*(a+1)/2;
} 
bool search(int x){
	int n;
	int a[n];
	int l=0,r=n;
	while(r-l>=1){
		int i=(l+r)/2;
		if(a[i]==x)return true;
		else if(a[i]<x)l=i+1;
		else r=i;
	}
	return false;
}
int a[114514];
signed main(){
	ic(n) ic(m)
	c(min(n%m,m-n%m))
}


Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int n;

bool isPrime(int x){
	for(int i = 2; i * i <= x; i++)
		if(x % i == 0)
			return false;
	return true;
}

int main(){
	scanf("%d", &n);
	for(int i = 11; n; i += 10){
		if(isPrime(i)){
			printf("%d ", i);
			n--;
		}
	}
	return 0;
}


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

int main(){
 int N;
 cin >> N;
 vector<int> vec;
 for(int i = 1; i <= N; i++){
   if(i % 2 == 1) vec.push_back(i);
 }
 int count = 0, count2 = 0;
 for(int i = 0; i < vec.size(); i++){
   count = 0;
   for(int j = 1; j <= N; j++){
     if(vec.at(i) % j == 0) count++;
   }
   if(count == 8) count2++;
 }
 cout << count2 << endl;
}


Measured memory_bytes: 3632
a, b, c, x = gets.to_i, gets.to_i, gets.to_i, gets.to_i
cnt = 0

(a+1).times do |i|
  (b+1).times do |j|
    (c+1).times do |k|
      cnt += 1 if i * 500 + j * 100 + k * 50 == x
    end
  end
end

puts cnt

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<int> H(N);
    for(int i = 0; i < N; i++) cin >> H[i];
    int cnt = 0;
    int ans = 0;
    for(int i = 0; i < N - 1; i++){
        if(H[i] >= H[i + 1]) cnt++;
        else cnt = 0;
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3788
//by azidoazideazide(c2n14)
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm> //#include<map>
#include<vector>
using namespace std;
typedef long long ll;
//#include<fstream>
//ifstream fin("rps.in");
//ofstream fout("rps.out");
#define pb push_back
vector<int> v;
int main(){
	ios::sync_with_stdio(0);
	int n;
    while(cin>>n){
        v.pb(n);
    }
    sort(v.begin(),v.end(),[=](int a, int b){return(a>b);});
    cout<<v[0]<<endl<<v[1]<<endl<<v[2]<<endl;
return 0;
}


Measured memory_bytes: 3128
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

void solve(std::string S){
    cout<< S.substr(0, 3)<<endl;
}
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 3132
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main()
{
    ll n,m,k;
    cin>>n>>m>>k;
    ll a[n],b[m];
    for(int i=0;i<n;i++)
    cin>>a[i];
    for(int i=0;i<m;i++)
    cin>>b[i];
    for(int i=1;i<n;i++)
        a[i]=a[i-1]+a[i];
    for(int i=1;i<m;i++)
        b[i]=b[i-1]+b[i];
    ll ans = max(upper_bound(a,a+n,k) - a , upper_bound(b,b+m,k) - b);
    for(int i=0;i<n;i++)
    {
        int ele1=a[i];
        if(ele1 > k)
            break;
        if(ele1==k)
        {
            ans = max((ll)i+1,ans);
            break;
        }
        int ele2=k-a[i];
        int pos = upper_bound(b,b+m,ele2) - b;
        ans=max(ans,(ll)i+1+pos);
    }
    cout<<ans<<endl;
}

//#include<iostream>
//typedef long long int ll;
//using namespace std;
//int main()
//{
//    ll n,m,k;
//    cin>>n>>m>>k;
//    ll a[n],b[m];
//    for(int i=0;i<n;i++)
//    cin>>a[i];
//    for(int i=0;i<m;i++)
//    cin>>b[i];
//    ll count=0;
//    ll p1=0,p2=0;
//    while(p1<n || p2<m)
//    {
//        if(p1 == n)
//        {
//            if(k- b[p2] >= 0)
//            {
//                count++;
//                k=k-b[p2];
//                p2++;
//            }
//            else
//                p2++;
//        }
//        else if(p2 == m)
//        {
//            if(k- a[p1] >= 0)
//            {
//                count++;
//                k=k-a[p1];
//                p1++;
//            }
//            else
//                p1++;
//        }
//        else
//        {
//            if(a[p1]<=b[p2])
//            {
//                if(k- a[p1] >= 0)
//                {
//                    count++;
//                    k=k-a[p1];
//                    p1++;
//                }
//                else
//                p1++;
//            }
//            else if(a[p1]>b[p2])
//            {
//                if(k- b[p2] >= 0)
//                {
//                    count++;
//                    k=k-b[p2];
//                    p2++;
//                }
//                else
//                p2++;
//            }
//        }
//    }
//    cout<<count<<endl;
//}


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

int main(){
    string a[7] = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
    string s;
    cin >> s;
    for(int i = 0; i < 7; i++){
        if(s == a[i]){
            cout << 7-i << endl;
        }
    }
}

Measured memory_bytes: 256
//
// Created by hide on 2020/05/15.
//

//参考：http://ehafib.hatenablog.com/entry/2015/12/23/164517
//インクルード(アルファベット順,bits/stdc++.hは使わない派閥)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素


int main(){
    int N;
    cin >> N ;
    vector<int> A(N);
    REP(i,N){
        cin >> A[i];
    }

    ll answer = 0;
    REP(i,N){
        answer += A[i]-1;
    }

    cout << answer << endl;

}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
s = [0] * n
ans = 0
for i in range(n):
     s[a[i]-1] +=1
for i in range(n):
     ans += s[i] * (s[i] - 1) // 2
for i in range(n):
     print(ans - (s[a[i]-1]-1) * s[a[i]-1] // 2 +(s[a[i]-1]-1) * (s[a[i]-1] - 2) // 2)

Measured memory_bytes: 83788
[a, b, c, k] = [int(t) for t in open(0).read().split()]
array = [(a, 1), (b, 0), (c, -1)]
ans = 0
while k > 0 and array:
    tmp = array.pop(0)
    ans += tmp[1] * min(tmp[0], k)
    k -= min(tmp[0], k)
print(ans)

Measured memory_bytes: 9200
import java.util.Scanner;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int antena[] = new int[5];
		for(int i = 0; i < 5; i++){
			antena[i] = sc.nextInt();
		}
		int k = sc.nextInt();
		boolean a = false;
		out : for(int i = 0; i < 4; i++){
			for(int j = i+1; j < 5; j++){
				if((antena[i] - antena[j] > k) || (antena[i] - antena[j] < -k)){
					a = true;
					break out;
				}
			}
		}
		if(!a){
			System.out.println("Yay!");
		}else{
			System.out.println(":(");
		}
	}
}

Measured memory_bytes: 21844
/**
 * Title: D - Sum of Large Numbers
 * Url: https://atcoder.jp/contests/abc163/tasks/abc163_d
 */
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main() {

    int n, k;
    cin >> n >> k;
    vector<ll> s(n+1);
    s[0]=0;
    for(int i=1; i<=n; i++) {
        s[i] = s[i-1]+i;
    }
    ll ans = 0;
    for(int i=k;i<=n+1; i++) {
        if(i==n+1) {
            ans += 1;
            ans %= 1000000007;
        } else {
            ans += (s[n]-s[n-i])-s[i-1]+1;
            ans %= 1000000007;
        }
        
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4752
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  int cnt=0;
  cin>>s;
  char tmp=s[0];
  for(int i=1;i<s.length();i++){
    if(tmp!=s[i]){
      cnt++;
      tmp=s[i];
    }
  }
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i <= (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

int main()
{
	long long N;
	cin >> N;
	long long A[N], dA[N];
	long long sum = 0;//Aの和
	long long x = 0;//取った回数
	REP(i,N){
		cin >> A[i];
		sum+=A[i];
	}
	if((2*sum)%(N*(N+1)) != 0){
		cout << "NO" << endl;
		return 0;
	}else{
		x = sum/(N*(N+1)/2);
		REP(i,N){
			dA[i] = A[(i+1)%N]-A[i];
			if((x-dA[i])%N != 0 || (x-dA[i])<0){
				cout << "NO" << endl;
				return 0;
			}
		}
		cout << "YES" << endl;
	    return 0;
	}
}

Measured memory_bytes: 1792
// 標準入力
var fs = require('fs'),
length = fs.fstatSync(process.stdin.fd).size,
buffer = new Buffer(length),
bytesRead = fs.readSync(process.stdin.fd, buffer, 0, length, 0),
input = buffer.toString('utf8', 0, bytesRead).split('\n');
main();
  
// ここから
function main(){
  for(var line = 1, maxLines = input[0] - 0; line <= maxLines; line++){
    var inputArray = input[line].split(" ").sort(function(a,b){return a-b});
    var longest = inputArray[2];
    var middle = inputArray[1];
    var shortest = inputArray[0];
 
      console.log((longest*longest == middle*middle + shortest*shortest) ? 'YES' : 'NO');
  }
}

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

int main() {
  int n, k;
  string s;
  cin >> n >> k >> s;
  int cnt = 0;
  int pre = 1;
  vector<int> his;
  for (int i = 0; i < n; i++) {
    if (('0' + pre) == s[i]) {
      cnt++;
    } else {
      his.push_back(cnt);
      cnt = 1;
      pre = (pre + 1) % 2;
    }
  }
  if (cnt > 0) {
    his.push_back(cnt);
  }
  if (his.size() % 2 == 0) {
    his.push_back(0);
  }

  int right = 0;
  int sum = 0;
  int ans = 0;
  for (int left = 0; left < his.size(); left+=2) {
    while(right < min((int)his.size(), left + 2 * k + 1)) {
      sum += his[right];
      right++;
    }
    ans = max(ans, sum);
    if (left == right) right++;
    else sum -= his[left] + his[left + 1];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
 
  // 入力 (2重ループを用いる)
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  
  int count = 0;
  
  for(int i=0; i<a.size(); i++){
    if((i+1)%2 == 1 && a.at(i)%2 == 1)count++;
  }

  cout << count << endl;
  return 0; 
}

Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main(){
  int n,x;
  cin >> n;

  for(int i=1;i<=n;i++){
    x=i;
    if(x%3==0){
      cout << " " << i;
      continue;}
    while(1){
      if(x==0)break;

    if(x%10==3){
             cout << " " << i;
             break;}
      x/=10;
      if(x)continue;

    }
  }
  cout << endl;
 return 0;

}

Measured memory_bytes: 1164
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = S()
rx=x.replace("1","2").replace("0","1").replace("2","0")
D = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if n // i % 2:
            D += [i]
        if i != n // i and i % 2:
            D += [n // i]

D.sort()
cnt = [0]*len(D)
ans=0
for k in range(len(D)):
    t=x[:D[k]]
    rt=rx[:D[k]]
    f=(t+rt)*(n//D[k]//2)+t
    cnt[k]=cnt[k]+int(f<=x)+int(t,2)
    cnt[k]%=mod
    ans += cnt[k]*D[k]*2
    ans%=mod
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
            cnt[kk]%=mod

print(ans)


Measured memory_bytes: 108420
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, a, n) for (int i = a; i < (n); i++)
#define all(in) in.begin(), in.end()
const int INF = 1e9;
const int MOD = 1e9 + 7;
int main() {
    int N;
    string S;
    cin >> N >> S;
    int ans = 0, x = 0;
    rep(i, N) {
        if (S[i] == 'I') {
            x++;
        } else {
            x--;
        }
        ans = max(ans, x);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define RREP(i,s,n) for(lli i=s;i>=n;i--)
#define MOD 1000000007
#define NUM 2520
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define INF (1LL<<50)

signed main(){

	lli n,a,b;
	cin>>n>>a>>b;

	lli cnt = a+b;
	lli k = n/cnt;

	if(n%cnt <= a){
		cout<<a*k + n%cnt<<endl;
	}
	else{
		cout<<a*(k+1)<<endl;
	}


	return 0;
}

Measured memory_bytes: 256
//* AuThOr GaRyMr *//
#include<bits/stdc++.h>
#define rb(a,b,c) for(LL a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB(a) push_back(a)
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
//vector<int> FROM[200000+10];
map<int,int> LAS_app;
vector<int > GUI_LV;
map<int,int> FIR_app;
int each_fir[200000+10];
//vector<int> dp[200000+10];
int a[200000+10];
int each_2[200000+10];
map<int,int> MM;
int main(){
	LL n,k;
	cin>>n>>k;
	rb(i,1,n) cin>>a[i];
	rl(i,n,1){
		if(LAS_app[a[i]]){
//			dp[i]=dp[LAS_app[a[i]]+1];
			each_fir[i]=each_fir[LAS_app[a[i]]+1];
			each_2[i]=each_2[LAS_app[a[i]]+1];
		}
		else{
//			dp[i]=dp[i+1];
//			dp[i].PB(a[i]);
			each_fir[i]=a[i];
			each_2[i]=i;
		}
		LAS_app[a[i]]=i;
	}
	
	rb(i,1,n){
		if(!FIR_app[a[i]])
		FIR_app[a[i]]=i;
	}
	int NOW=-INF;
	FIR_app[NOW]=0;
	vector<int> EMPM;
//	MM[n+1]=1;
	while(1){
//			cout<<NOW<<" FROM:"<<FIR_app[NOW]+1<<endl;
			if(MM[FIR_app[NOW]+1]) break;
			MM[FIR_app[NOW]+1]=1;
			GUI_LV.PB(each_2[FIR_app[NOW]+1]);
			if(each_fir[FIR_app[NOW]+1]){//cout<<FIR_app[NOW]+1<<":"<<each_fir[FIR_app[NOW]+1]<<"CMP"<<dp[FIR_app[NOW]+1][dp[FIR_app[NOW]+1].size()-1]<<endl;
				NOW=each_fir[FIR_app[NOW]+1];//dp[FIR_app[NOW]+1][dp[FIR_app[NOW]+1].size()-1]; 
			}
			else{
				NOW=0;
			}
	}
	int IS=k%(GUI_LV.size());
	IS--;
	if(IS<0){
		IS=GUI_LV.size()-1;
	}
//	cout<<<<endl;
//	cout<<IS<<"&"<<GUI_LV.size()<<endl;
	int TOTO=GUI_LV[IS];
//	cout<<TOTO<<endl;
//	cout<<TOTO<<endl;
	if(TOTO){
		int last[200000+10]={0},nex[200000+10]={0};
		rl(i,n,TOTO){
			nex[i]=last[a[i]];
			last[a[i]]=i;
		}
//		cout<<"*"<<nex[19]<<endl;
		rb(i,TOTO,n){
			if(!nex[i]){
				cout<<a[i]<<" ";
			}
			else{
				i=nex[i];
			}
		}
	}
	return 0;
}


Measured memory_bytes: 34292
n, x = map(int, input().split())
def layers(l):
    return 2 ** (l + 2) - 3
def patties(l):
    return 2 ** (l + 1) - 1
def doit(l, x):
    if x >= layers(l):
        return patties(l)
    y = layers(l - 1)
    ret = 0
    if x >= 1:
        ret += doit(l - 1, x - 1)
    if x >= y + 2:
        ret += 1
        ret += doit(l - 1, x - y - 2)
    return ret
print(doit(n, x))


Measured memory_bytes: 38256
/* Filename: CodeFestival2016Final_A.java
 * Author: Mushiyo
 */

import java.util.Scanner;

public class Main {

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

		while (input.hasNext()) {
			int H = input.nextInt();
			int W = input.nextInt();
			
			int row = 0;
			int col = 0;
			for(int i  = 0; i < H; ++i){
				for(int j = 0; j < W; ++j){
					String cell = input.next();
					
					if(cell.equals("snuke")){
						row = i + 1;
						col = j;
					}
				}
			}
			
			System.out.println(String.format("%c%d", col + 'A', row));
		}
	}

}


Measured memory_bytes: 10452
#include <stdio.h>
#define MAXN 100000
int main(void)
{
	int N;
	int i;
	int M[MAXN+1];
	int H[MAXN];
	long int cnt;

	scanf("%d",&N);	

	for(i=0;i<N+1;i++){
		scanf("%d",&M[i]);
	}

	for(i=0;i<N;i++){
		scanf("%d",&H[i]);
	}

	cnt=0;	
	for(i=0;i<N;i++){
		if(M[i]>=H[i]){
			cnt+=H[i];
		}else{
			cnt+=M[i];
			H[i]-=M[i];
			if(M[i+1]>=H[i]){
				cnt+=H[i];
				M[i+1]-=H[i];
			}else{
				cnt+=M[i+1];
				M[i+1]=0;
			}
		}
	}

	printf("%ld\n",cnt);

	return 0;
}	






Measured memory_bytes: 896
N, M = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
O = Array.new(M) { gets.split.map(&:to_i) }
A.sort!
O.sort_by! {|o| o[1] }.reverse!
i, j = 0, 0
while i < N && j < M
  break if O[j][1] < A[i]
  A[i] = O[j][1]
  i += 1
  O[j][0] -= 1
  j += 1 if O[j][0] == 0
end
p A.inject(:+)

Measured memory_bytes: 20752
import java.util.*;

public class Main {
    static long[] as, bs;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        as = new long[n];
        bs = new long[n];
        for (int i = 0; i < n; i++)
            as[i] = sc.nextLong();
        for (int i = 0; i < n; i++)
            bs[i] = sc.nextLong();
        long sumA = Arrays.stream(as).sum();
        long sumB = Arrays.stream(bs).sum();
        /*
        List<Long> aList = new ArrayList<>();
        List<Long> bList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (as[i] != bs[i]) {
                aList.add(as[i]);
                bList.add(bs[i]);
            }
        }
        */

        long diffNum = 0;
        for (int i = 0; i < n; i++) {
            if (as[i] > bs[i]) {
                diffNum -= (as[i] - bs[i]);
            } else if (as[i] < bs[i]) {
                diffNum += (bs[i] - as[i]) / 2;
            }
        }
        if (diffNum >= 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

        /*
        for (int i = 0; i <= sumB - sumA; i++) {
            if (aList.equals(bList)) {
                System.out.println("Yes");
                return;
            }
            if (i == sumB - sumA) break;
            boolean flaga = false;
            boolean flagb = false;
            for (int j = 0; j < aList.size(); j++) {
                if (flaga && flagb) break;
                if (!flaga && aList.get(j) < bList.get(j)) {
                    flaga = true;
                    aList.set(j, aList.get(j) + 2);
                }
                if (!flagb && aList.get(j) > bList.get(j)) {
                    flagb = true;
                    bList.set(j, bList.get(j) + 1);
                }
            }
        }
        System.out.println("No");
        */
    }
}


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

long long n,m,q;
long long a[55],b[55],c[55],d[55];
long long ans,sum;
long long A[11];

void dfs(int i){
	if(i==n){
		long long sum=0;
		for(int j=0;j<q;j++){
			if(A[b[j]]-A[a[j]]==c[j]) sum+=d[j];
		}
		ans=max(ans,sum);
		return;
	}
	for(int j=A[i];j<=m;j++){
		A[i+1]=j;
		dfs(i+1);
	}
}

int main() {
	cin >> n >> m >> q;
	for(int i=0;i<q;i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	A[0]=1;
	dfs(0);
	cout << ans << endl;
	return 0;
}


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

#define MAX 101

int K;
int t[MAX * (MAX-1) / 2];

int main(void){
  while(scanf("%d",&K), K){
    int tmp = 0;
    for(int i=0;i<K*(K-1)/2;i++){
      scanf("%d",&t[i]);
      tmp += t[i];
    }
    cout<<tmp/(K-1)<<endl;

    /*
    if(K == 2){
      printf("%d\n",t[0]);
      continue;
    }

    int ans = 0;
    for(int i=0,j=0;j<K-2;i+=2,j++){
      int sum = t[i+1] + (t[i] + t[i+2] - t[i+1]) / 2;
      if(i != 0){
        sum -= t[i];
      }
      ans += sum;
    }
    printf("%d\n",ans);
    */
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	int res = 0;
	int a = 0;
	int sum = 0;
	int mn = (int)1 << 50;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		if (A[i] < 0)a++;
		sum += abs(A[i]);
		mn = min(mn, abs(A[i]));
	}

	if (a % 2 == 1) {
		res = sum - 2 * mn;
	}
	else {
		res = sum;
	}





	cout << res << endl;
}

Measured memory_bytes: 1024
N, K = map(int, input().split())
S = str(input())

if S[K-1] == "A":
  print(S[:K-1]+"a"+S[K:])
elif S[K-1] == "B":
  print(S[:K-1]+"b"+S[K:])
else:
  print(S[:K-1]+"c"+S[K:])

Measured memory_bytes: 3060