akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> P;
#define int long long
#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#ifdef DEBUG
std::ostream& dout = cout;
#else
stringstream dout;
#endif
template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}

signed main(signed argc, char* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int MOD = 1000000007;
    set<char> st;
    rep(i,3){
        char c;
        cin>>c;
        st.insert(c);
    }
    if(st.size()==1){
        cout<<"No"<<endl;
    }
    else cout<<"Yes"<<endl;
}


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

using namespace std;

typedef long long int ll;

int main()
{
	ll n, a, b; cin >> n >> a >> b;
	if (a == 0)
		cout << 0;
	else
	{
		ll row = a + b;
		ll times = n / row;
		ll total = times * a;
		ll remain = n - (row * times);
		total += min(a, remain);
		cout << total;
	}
	return 0;
}

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

int main(void){
    int n, max=0;
    string s;
    cin >> n >> s;
    for(int i=1;i<n;++i){
        int se[500], ans=0;
        for(char c='a';c<='z';++c) se[c] = 0;
        string x, y;
        x = s.substr(0, i);
        y = s.substr(i, (n-i));
        for(int j=0;j<x.size();++j){
            ++se[x[j]];
        }
        for(char c='a';c<='z';++c){
            if(se[c]==0) continue;
            for(int j=0;j<y.size();++j){
                if(c==y[j]){
                    ++ans;
                    break;
                }
            }
        }
        if(max < ans) max = ans;
    }
    cout << max << endl;
}


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

int main()
{
    int a,b;
    cin>>a>>b;
    if(a==b){
        cout<<"Draw";
    }
    else if(a==1){
        cout<<"Alice";
    }
    else if (b==1){
        cout<<"Bob";
    }
    else if(a>b){
        cout<<"Alice";
    }
    else{
        cout<<"Bob";
    }

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

#define ll long long

#ifndef ONLINE_JUDGE
#define debug(format, ...) fprintf(stderr, \
    "%s:%d: " format "\n", __func__, __LINE__,##__VA_ARGS__)
#else
#define debug(format, ...)
#define NDEBUG
#endif

vector<int> pos;
vector<int> neg;

#define MOD 1000000007
#define mul(a, b) (((ll)(a) * (ll)(b)) % MOD)

struct Val {
    long double lgv;
    ll modv;
    int sign;
};

Val operator*(Val a, Val b)
{
    Val ans;
    ans.lgv = a.lgv + b.lgv;
    ans.sign = a.sign * b.sign;
    ans.modv = mul(a.modv, b.modv);
    return ans;
}

Val make_val(int x)
{
    Val res;
    if (x == 0) {
        res.lgv = 0.0; res.sign = 0;
    } else if (x < 0) {
        res.lgv = log((long double)(-x)); res.sign = -1;
    } else {
        res.lgv = log((long double)x); res.sign = 1;
    }
    res.modv = ((x % MOD) + MOD) % MOD;
    return res;
}

bool operator<(Val a, Val b)
{
    if (a.sign != b.sign) return a.sign < b.sign;
    if (a.sign == 0) {
        return false;
    } else if (a.sign == 1) {
        return a.lgv < b.lgv;
    } else {
        return a.lgv > b.lgv;
    }
}

vector<Val> pprod_pos;
vector<Val> pprod_neg;
vector<Val> sprod_pos;
vector<Val> sprod_neg;

void make_prod(vector<int>& from, vector<Val>& prefix, vector<Val>& suffix)
{
    prefix.push_back(make_val(1));
    for (int i = 0; i < from.size(); i++) {
        prefix.push_back(prefix.back() * make_val(from[i]));
    }
    suffix.push_back(make_val(1));
    for (int i = (int)(from.size()) - 1; i >= 0; i--) {
        suffix.push_back(suffix.back() * make_val(from[i]));
    }
}

int main()
{
    int n, k; scanf("%d%d", &n, &k);
    bool has_zero = false;
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        if (x > 0) pos.push_back(x);
        if (x < 0) neg.push_back(x);
        if (x == 0) has_zero = true;
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
    make_prod(pos, pprod_pos, sprod_pos);
    make_prod(neg, pprod_neg, sprod_neg);
    Val ans;
    ans.lgv = 1e20;
    ans.sign = -1;
    for (int i = 1; i <= pprod_pos.size(); i++) {
        int j = k + 2 - i;
        if (j <= 0) continue;
        if (j > pprod_neg.size()) continue;
        ans = max(ans, pprod_pos[i-1] * pprod_neg[j-1]);
        ans = max(ans, pprod_pos[i-1] * sprod_neg[j-1]);
        ans = max(ans, sprod_pos[i-1] * pprod_neg[j-1]);
        ans = max(ans, sprod_pos[i-1] * sprod_neg[j-1]);
    }
    if (has_zero) ans = max(ans, make_val(0));
    printf("%lld", ans.modv);
    return 0;
}


Measured memory_bytes: 22268
#include<stdio.h>
void gcd(int x,int y);

int main(){
  int x,y;

  scanf("%d %d", &x, &y);
  gcd(x,y);

  return 0;
}

void gcd(int x,int y){
  int r, tmp;

  if(x > y){
    tmp=x;
    x=y;
    y=tmp;
  }

  while(x%y!=0){
    r=x%y;
    x=y;
    y=r;
  }

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



Measured memory_bytes: 2140
//q067.cpp
//Mon Aug 31 23:49:05 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007
#define rep(i,n) for (int i=0;i<(n);++i)

using namespace std;
using ll=long long;
typedef pair<ll,ll> P;

//Union-Find木
int par[1000100]; //親。1個上の親でしか無いことに注意。グループの根はfindで呼び出す。
int treerank[1000100]; //木の深さ

void init(int n){
	for (int i=0;i<n;i++){
		par[i] = i;
		treerank[i] = 0;
	}
}

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

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if (x == y) {
		return;
	} 

	if (treerank[x] < treerank[y]){
		par[x] = y;
	} else {
		par[y] = x;
		if (treerank[x] == treerank[y]){
			treerank[x]++;
		}
	}
}

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

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

	vector<P> node(n);
	vector<P> x;
	vector<P> y;
	rep(i,n) {
		cin >> node[i].first >> node[i].second;
		x.push_back(P(node[i].first,i));
		y.push_back(P(node[i].second,i));
	}

	sort(x.begin(),x.end());
	sort(y.begin(),y.end());

	vector<P> cost;
	vector<P> road;
	int c = 0;
	rep(i,n-1){
		road.push_back(P(x[i].second,x[i+1].second));
		cost.push_back(P(min(abs(x[i].first-x[i+1].first),abs(node[x[i].second].second-node[x[i+1].second].second)),c));
		c++;
		road.push_back(P(y[i].second,y[i+1].second));
		cost.push_back(P(min(abs(y[i].first-y[i+1].first),abs(node[y[i].second].first-node[y[i+1].second].first)),c));
		c++;
	}

	init(c);
	sort(cost.begin(),cost.end());

	ll ans = 0;
	rep(i,c){
		ll id = cost[i].second;
		if(!same(road[id].first,road[id].second)){
			ans += cost[i].first;
			unite(road[id].first,road[id].second);
		}
	}

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

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


int main() {
  int N,M;
  cin>>N>>M;
  int n=N;
  vector<vector<char>> d(N, vector<char>(M));
  while(n--){
    string S;
    cin>>S;  
    for(int j=0; j<S.size();j++){
      d[N-n-1][j]=S.at(j);
    }
  }
  vector<vector<char>> ans(N, vector<char>(M));
  for(int i=0; i<N;i++){
    for(int j=0; j<M;j++){
      char an='0';
      if(d[i][j]=='#'){
        ans[i][j]='#';
      }
      
      else{
        for(int dx=-1; dx<=1;dx++){
          for(int dy=-1; dy<=1;dy++){
            int nx=i+dx,ny=j+dy;
            if (0<=nx&&nx<N&&0<=ny&&ny<M&&d[nx][ny]=='#'){
              if(an=='0'){
                an='1';
              }
              else if(an=='1'){
                an='2';
              }
              else if(an=='2'){
                an='3';
              }
              else if(an=='3'){
                an='4';
              }
              else if(an=='4'){
                an='5';
              }
              else if(an=='5'){
                an='6';
              }
              else if(an=='6'){
                an='7';
              }
              else if(an=='7'){
                an='8';
              }
              
            }
          }
        }
        
        
        ans[i][j]=an;
      }
    }
  }
        
 
  for(int i=0; i<N;i++){
    for(int j=0; j<M;j++){
      cout<<ans[i][j];
    }
    cout<<endl;
  }

}



Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line1 = br.readLine();
        String line2 = br.readLine();
        String str;
        
        int num = Integer.parseInt(line1);
        String aryNum[] = new String[num];
        aryNum = line2.split(" ");
        
        for (int i = num - 1; i > -1; i--) {
            System.out.print(aryNum[i]);
            if(i != 0){
                System.out.print(" ");
            }
        }

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

Measured memory_bytes: 24044
#include <bits/stdc++.h>
using namespace std;
int main(){
 
 int N;
 cin >> N;
 int A,B;
 cin >> A >> B;
 vector<int>P(N);
 for(int i=0; i<N; i++){
  cin >> P.at(i);
 }
 int AP = 0;
 int BP = 0;
 int CP = 0;
 
 for(int i=0; i<N; i++){
 if(P.at(i)<=A){
  AP += 1;
 }
 else if(A < P.at(i) && P.at(i)<=B){
  BP += 1;
 }
 else if(B < P.at(i)){
  CP += 1;
 } 
}

int big = min(AP,min(BP,CP));
 cout << big << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;

int main()
{
    string S;
    cin >> S;
    if (S[5] == '0' && S[6] <= '4')
    {
        cout << "Heisei" << endl;
    }
    else
    {
        cout << "TBD" << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>
#include <random>
#include <list>
#include <numeric>



#define rep(i,p,q) for(i = p;i < q;i++)
#define ll long long

using namespace std;


//34 A
int main(void) {
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	string s;
	cin >> s;
	a--;
	b--;
	c--;
	d--;

	if (d < c) {
		string dots = "...";
		size_t t,p;
		bool can = false;
		int index = b-1;
		while (index < s.size() && ( t = s.substr(index,s.length() - index).find(dots)) != string::npos) {
			int realIndex = t + index;
			if (b-1 <= realIndex && realIndex <= d-1)can = true;
			if (can || d < realIndex)break;
			index = realIndex+1;
		}
		string sharps = "##";
		index = a;
		while (index < s.size() && (p = s.substr(index,s.length() - index).find(sharps)) != string::npos) {
			int realIndex = p + index;
			if ((a < p && p < c)) can = false;
			if (!can)break;
			index = realIndex + 1;
		}
		
		if (can)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else {
		bool can = true;
		string sharps = "##";
		size_t p;
		int index = a;
		while (index < s.size() && (p = s.substr(index,s.size() - index).find(sharps)) != string::npos) {
			int realIndex = p + index;
			if (((a < realIndex && realIndex < c)) || (b < realIndex && realIndex < d)) {
				can = false;
				break;
			}
			index = realIndex + 1;
		}
		if (can)cout << "Yes" << endl;
		else cout << "No" << endl;
	}


}

Measured memory_bytes: 772
#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ins insert
typedef std::pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int N=2e5+5;

int n,a[N];

ll sum[N],ans=0x7f7f7f7f7f7f7f7fLL;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		if((sum[i]<<1)>=sum[n]){
			ans=min(ans,(sum[i]<<1)-sum[n]);
		}
		else{
			ans=min(ans,sum[n]-(sum[i]<<1));
		}
	}
//	for(int i=1;i<=n;i++){
//		printf("%lld%c",sum[i]," \n"[i==n]);
//	}
	printf("%lld\n",ans);
	return 0;
} 

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define MOD 1000000007ULL;
#define rep(i,n) for(int i=0;i<n;i++)


int main() {
	char S[222];
  	cin>>S;
  	int n=strlen(S);
  
  	for(int i=n-2;i;i-=2){
      if(strncmp(S,S+i/2,i/2)==0) {
        cout<<i<<endl;
      	return 0;
      }
    }
  	
  	return 0;
}

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

int main(){
int N,M;
  cin>>N>>M;
  int K;
  int A[N][40];
  vector<int>count(40);
  for(int i=0; i<N; i++){
    cin>>K;
   for(int j=0; j<K; j++){
    cin>>A[i][j];
    count[A[i][j]]++;
   }
  }
   
  int ans=0;
  for(int i=0; i<=M; i++){
   if(count[i]==N){ans++;}
  }
  
  cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

int main()
{
  i64 T;
  cin >> T;
  for (i64 _ = 0; _ < T; _++)
  {
    i64 N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    i64 ans = 1e18;
    priority_queue<pair<i64, i64>, vector<pair<i64, i64>>, greater<pair<i64, i64>>> que;
    map<i64, i64> memo;
    que.push({0, N});
    i64 cost[6] = {0, 0, A, B, 0, C};
    while (que.size())
    {
      pair<i64, i64> p = que.top();
      que.pop();
      i64 v = p.first, n = p.second;
      if (ans <= v)
        break;
      if (n <= 1e18 / D)
        ans = min(ans, v + n * D);
      for (i64 i : {2, 3, 5})
      {
        i64 m = n % i;
        i64 v2 = v + m * D + cost[i];
        if (v2 < ans && (memo.count(n / i) == 0 || v2 < memo[n / i]))
        {
          que.push({v2, n / i});
          memo[n / i] = v2;
        }
        v2 = v + (i - m) * D + cost[i];
        if (v2 < ans && (memo.count(n / i + 1) == 0 || v2 < memo[n / i + 1]))
        {
          que.push({v2, n / i + 1});
          memo[n / i + 1] = v2;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 4584
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  int ans = 0;
  int unhappy = 0;
  rep(i, N) {
    if(S[i] == 'L') {
      if(i != 0 && S[i-1] == 'L') ans++;
      else unhappy++;
    } else {
      if(i != N-1 && S[i+1] == 'R') ans++;
      else unhappy++;
    }
  }
  cout << min(ans+2*K, N-1) << endl;
  return 0;
}


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

bool ispal(string s,int start,int n)
{

    int l=start;
    int h=n-1;
    while(h>l)
    {
        if(s[l++]!=s[h--])  return false;
    }
    return true;
}



int main()
{

    string s;
    cin>>s;
    int flag=0;
    int n=s.length();
    //cout<<n<<endl;

    if(ispal(s,0,n)  && (ispal(s,0,((n-1)/2) ) && ispal(s,((n+3)/2) - 1,n)) )  flag=1;
    //cout<<ispal(s,0,n)<<endl;
    //cout<<(n-1)/2<<" " << (n+3)/2-1<<endl;
    //cout<<ispal(s,0,((n-1)/2) )<<endl;
    //cout<<ispal(s,(n+3)/2 - 1,n)<<endl;

    if(flag==1) cout<<"Yes"<<endl;
    else    cout<<"No"<<endl;


}


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

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define rep(i,a,b) for(i=a;i<b;i++)
#define pii pair<ll , ll>
#define all(x) x.begin(),x.end()
#define nl "\n"
#define ump unordered_map
#define mtv(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)

vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out( 
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cout << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    stringstream ss; ss << H;
    cout << args[idx] << "- " << ss.str() << ", ";
    debug_out(args, idx + 1, LINE_NUM, T...);
}

const ll N = 1e5 + 5, mod = 1e9 + 7;
ll dp[N][15],n;
string s;

ll dfs(ll index, ll cur){
    if(index == n){
        return (cur == 5);
    }
    auto &ans = dp[index][cur];
    if(ans != -1)return ans;
    if(s[index] != '?'){
        return ans = dfs(index + 1, ((cur*10) + (s[index]-'0')) %13);
    }
    ans = 0;
    for(ll i = 0; i <= 9; i++){
        ans += dfs(index+1, ((cur*10) + (i)) %13);
        ans %= mod;
    }
    return ans;
}

void doit(){
    cin >> s;
    n = s.size();
    memset(dp,-1,sizeof(dp));
    cout << dfs(0,0) << nl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin >> t;
    for(ll i = 1; i <= t; i++){
        doit();
    }
}


Measured memory_bytes: 21724
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <math.h>
using namespace std;


int main ()
{


int h,n;
cin >> h >> n;

int f,sum=0;

while(n-->0)
{

	 cin >> f;
	 sum+=f;

}

 if(sum-h>=0)
{
	 cout << "Yes" << endl;
}
else
{
	  cout << "No" << endl;
}
	return 0;
}











Measured memory_bytes: 3092
#include<iostream>
using namespace std;
int X ,Y;

bool dfs(int i,int sum){
    if(i == X) return sum == Y;
    if(dfs(i + 1, sum+2)) return true;
    if(dfs(i + 1, sum+4)) return true;

    return false;
}

int main(){
    cin >> X >> Y;
    if(Y >= X*2 && Y <= X*4 && Y % 2 == 0){
        if(dfs(0,0)) cout << "Yes";
    }
    else cout << "No";
}


Measured memory_bytes: 3616
N = gets.to_i
H = gets.split.map(&:to_i)

max = 0
(1 ... N).inject(0) do |m,i|
  if H[i-1] >= H[i]
    max = m + 1 if m + 1 > max
    m + 1
  else
    0
  end
end
puts max


Measured memory_bytes: 8580
#include<bits/stdc++.h>
using namespace std;
char HW[101][101];
int H,W,dl[101][101],flg[101][101];
void ku(){
    for(int i=0;i<H;i++){
        for(int o=W-1;o>=0;o--){ HW[i][o+1]=HW[i][o]; }
        HW[i][0]='.';
    }
}
void ko(int oi){
    for(int i=0;i<H;i++){
        for(int o=W-1;o>=0;o--){
            if(HW[i][o]=='c'&&dl[i][o]!=0&&flg[i][o]==0){dl[i][o]=oi;flg[i][o]++;}
        }
    }
}

int main(){
    cin>>H>>W;
    for(int i=0;i<H;i++){
        for(int o=0;o<W;o++){
            dl[i][o]=-1;
        }
    }
    for(int i=0;i<H;i++){
        for(int o=0;o<W;o++){
            scanf(" %c",&HW[i][o]);
            if(HW[i][o]=='c')dl[i][o]=0;
        }
    }
    for(int i=1;i<W+1;i++){
        ku();
        ko(i);
    }
    for(int i=0;i<H;i++){
        for(int o=0;o<W;o++){
            printf("%d",dl[i][o]);if(o!=W-1){cout<<" ";}
        }
        cout<<endl;
    }

}

Measured memory_bytes: 3380
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func oneInt() int {
	var a int
	fmt.Scan(&a)
	return a
}
func oneStr() string {
	var a string
	fmt.Scan(&a)
	return a
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func scanNums() (nums []int) {
	s := nextLine()
	numStr := strings.Split(s, " ")

	for _, n := range numStr {
		i, _ := strconv.Atoi(n)
		nums = append(nums, i)
	}
	return nums
}

func scanStrings() (strs []string) {
	s := nextLine()
	list := strings.Split(s, " ")
	strs = append(strs, list...)
	return strs
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func sortAsc(a []int) []int {
	sort.Ints(a)
	return a
}

func sortDesc(a []int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	if a == 0 && b == 0 {
		return 0
	}
	return a * b / gcd(a, b)
}

func main() {
	N := oneInt()
	X := oneInt()
	var Ls []int
	for index := 0; index < N; index++ {
		Ls = append(Ls, oneInt())
	}

	var sum int

	for i, v := range Ls {
		sum += v
		if sum > X {
			fmt.Print(i+1)
			return
		}
	}
    fmt.Print(len(Ls) +1)
}


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

int main() {
	string s;
	cin>>s;
	int l=s.length(),k;
	for(int i=l-1;i>=0;i--)
	{
		if(s[i]=='F')
		{
			k=i;
			break;
		}
	}
	for(int i=0;i<k;i++)
	cout<<s[i];
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>

using namespace std;

struct Heap{
	int Array[2000000];
	int tamanho;
	
	int pai(int input){
		return (input - 1)/2;
	}
	
	int filhoEsquerdo(int input){
		return (2*input + 1);
	}
	
	int filhoDireito(int input){
		return (2*input + 2);
	}
	
	// Arruma após inserção
	void HeapifyRemover(int arrumar){
		int esquerdo = filhoEsquerdo(arrumar);
		int direito = filhoDireito(arrumar);
		
		int maior = arrumar;
		
		//Vejo quem é maior
		if (esquerdo < tamanho && Array[esquerdo] > Array[arrumar]){
			maior = esquerdo;
		}
		if (direito < tamanho && Array[direito] > Array[maior]){
			maior = direito;
		}
		if (maior != arrumar){
			swap(Array[arrumar], Array[maior]);
			HeapifyRemover(maior);
		}
	}
	
	void HeapifyInserir(int arrumar){
		if (arrumar && Array[pai(arrumar)] < Array[arrumar]){
			swap(Array[pai(arrumar)], Array[arrumar]);
			HeapifyInserir(pai(arrumar));
		}
	}
	
	void inserirHeap(int valor){
		Array[tamanho] = valor;
		tamanho++;
		HeapifyInserir(tamanho-1);
	}
	
	void printaRaiz(){
		printf("%i\n", Array[0]);
	}
	
	int removerRaiz(){
		Array[0] = Array[tamanho-1];
		Array[tamanho-1] = 0;
		tamanho--;
		HeapifyRemover(0);
	}
};

int main(){
	Heap heap;
	string operacao; int valor;
	while(cin >> operacao){
		if (operacao == "insert"){
			cin >> valor;
			heap.inserirHeap(valor);
		} else if (operacao == "extract"){
			heap.printaRaiz();
			heap.removerRaiz();
		} else {
			break;
		}
	}
	return 0;
}



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

#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define SP << " " <<

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vec;
typedef vector<P> pvec;
typedef vector<vector<int>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<int> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<int,vector<int>,greater<int>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;

const vector<int> DX = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> DY = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const ll INF = (1LL << 60); // 1152921504606846976
const double PI = (3.141592653589794);
const double EPS = (0.0000000001); // 10^(-10)

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> inline T ceil(T a, T b) {return T((a + b - 1) / b);}
template<class T> inline T round(T a, T b) {return T(a / b);}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template <class T> inline void out(T &a) { bool flag=true; for(auto&x:a){if(flag) {flag=false;} else{ cout << ' '; } cout<<x; } cout << endl; }



//----------------------------------------------------------------
int nmax=200000; // 2*(10^5)
vvec G(nmax);


struct BIT{
private:
  vector<int> bit;
  int num;

public:
  BIT(vector<int> v){
    num = v.size();
    bit.resize(num);
    REP(i,num) bit[i] = v[i];
  }

  int sum(int i){
    int s = 0;
    while(i > 0){
      s += bit[i];
      i -= i & -i;
    }
    return s;
  }

  void add(int i, int x){
    while(i <= num){
      bit[i] += x;
      i += i & -i;
    }
  }
};


void solve4ts()
{
    
    int n,k;
    cin>>n>>k;

    vector<int> a(n+1);
    rep(i,n) cin >> a[i+1];
    rep(i,n) a[i+1]+=a[i];
    rep(i,n+1){
        a[i]-=k*i;
    }
    map<int,int> mp;
    rep(i,n+1){
        mp[a[i]]++;
    }

    int idx=0;
    for(auto& x : mp){
        x.sc=idx;
        idx++;
    }

    vec node(n+10);
    BIT bit(node);
    int ans=0;

    for(int i=0;i<=n;i++){
        int find=mp[a[i]];
        find++;
        ans+=bit.sum(find);
        bit.add(find,1);
    }
    cout<<ans<<endl;
}
//-----------------------------------------------------------------

signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15);
    int repeat = 1;
    // cin >> repeat;
    while(repeat--) solve4ts();
}

Measured memory_bytes: 23680
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fore(x, c) for(auto &&x : c)
#define rep(i, a, n) for(int i = a, i##len = (int)(n); i < i##len; ++i)
#define rrep(i, a, n) for(int i = (int)(n - 1); i >= a; --i)
#define sz(c) ((int)c.size())
#define contains(c, x) (c.find(x) != end(c))
#define inseg(l, x, r) ((l) <= (x) && (x) < (r))
#define dump(...)
#define pb push_back
#define eb emplace_back
#define _ 0
const signed INF_ = 1001001001; const long long INF = 1001001001001001001LL;
const int DX[9] = {0,1,0,-1,1,1,-1,-1,0}, DY[9] = {-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is, vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
  is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a, const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a, const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap = priority_queue<T, deque<T>, greater<T>>;
struct before_main_function {
  before_main_function() {
      cin.tie(nullptr); ios::sync_with_stdio(false);
      cout << setprecision(15) << fixed;
  }
} before_main_function;
// clang-format on
//------------------8<------------------------------------8<--------------------

signed main() {
  int N, K;
  cin >> N >> K;
  vi p(N);
  cin >> p;
  sort(all(p));
  int ans = 0;
  rep(i, 0, K) ans += p[i];
  cout << ans << endl;
  return (0 ^ _ ^ 0);
}



Measured memory_bytes: 3652
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int A[100010];
int X[100010];
int N;

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

	cin >> N;
	int t = 0;
	rep(i, 0, N)
	{
		cin >> A[i];
		if (i == N - 1)
		{
			t += A[i];
		}
		else
		{
			if (i % 2 == 0)
			{
				t -= A[i];
			}
			else
			{
				t += A[i];
			}
		}
	}

	X[N - 1] = t;
	rrep(i, 0, N - 1)
	{
		X[i] = 2 * A[i] - X[i + 1];
	}

	rep(i, 0, N)
	{
		cout << X[i];
		if (i == N - 1)
		{
			cout << endl;
		}
		else
		{
			cout << ' ';
		}
	}

	return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;

vector <int> g[100005], tps, rev[100005];
bool used[100005];
int parent[100005], posit[100005];

void topsort(int v)
{
    used[v] = true;
    for (int i = 0; i < (int) g[v].size(); i++)
    {
        int u = g[v][i];
        if (!used[u]) topsort(u);
    }
    tps.pb(v);
    return;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n + m; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        rev[b].pb(a);
    }

    for (int i = 1; i <= n; i++)
        if (!used[i]) topsort(i);

    for (int i = 0; i < n; i++) posit[tps[i]] = i;
    for (int i = 0; i < n; i++)
    {
        int v = tps[i], mx = 0;
        for (int j = 0; j < (int) rev[v].size(); j++)
        {
            int u = rev[v][j];
            if (mx == 0 || posit[mx] > posit[u]) mx = u;
        }
        parent[v] = mx;
    }
    for (int i = 1; i <= n; i++) cout << parent[i] << '\n';
    return 0;
}



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

// chmin, chmax関数
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

//---------------------------

int main(){
    ll l;
    cin >> l;
    double x = (double)l/3.0;
    cout << setprecision(12) << x*x*x << endl;
    return 0;
}

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

int main() {
  int N,M;
  cin >> N >> M;
  vector<vector<int> > s(M);
  vector<int> p(M);
  for(int i=0;i<M;i++){
    int k;cin >> k;
    for(int j=0;j<k;j++){
      int iti;cin >> iti;
      s.at(i).push_back(iti-1);
    }
  }

  for(int i=0;i<M;i++) cin >> p.at(i);

  int ans=0;
  for(int i=0;i<(1<<N);i++){
    int flag=1;
    for(int j=0;j<M;j++){
      int cnt=0;
      for(int k=0;k<s[j].size();k++){
        cnt ^= ((i >> s[j][k]) & 1);
      }
      if(cnt!=p.at(j)){
        flag=0;break;
      }
    }
    if(flag) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n=gets.to_i
a=gets.split.map &:to_i
cnt=0
(0..n-1).each do |i|
  min=i
  (i..n-1).each do |j|
    if a[min] > a[j]
      min=j
    end
  end
  if i!=min
    a[i], a[min] = a[min], a[i]
    cnt+=1
  end
end
puts a*' '
puts cnt

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

namespace arc093_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] sa = new int[n + 1];
            sa[0] = Math.Abs(x[0]);
            for (int i = 1; i < n; i++)
            {
                sa[i] = Math.Abs(x[i - 1] - x[i]);
            }
            sa[n] = Math.Abs(x[n - 1]);
            long sum = sa.Sum();
            Console.WriteLine(sum - (sa[0] + sa[1]) + Math.Abs(x[1]));
            for (int i = 2; i <= n - 1; i++)
            {
                Console.WriteLine(sum - (sa[i - 1] + sa[i]) + Math.Abs(x[i - 2] - x[i]));
            }
            Console.WriteLine(sum - (sa[n - 1] + sa[n]) + Math.Abs(x[n - 2]));
        }
    }
}

Measured memory_bytes: 26460
n,a,b,c = map(int,input().split())
s = [input() for i in range(n)]+[0]
# if [a,b,c].count(0) >= 2:
#     print("No")
ans = ""

# print("Yes")
for i in range(n):
    if s[i] == "AB":
        if a==1 and b==1 and s[i+1] =="BC":
            ans+="B"
            b+=1
            a-=1
        elif a<=b:
            ans+="A"
            a+=1
            b-=1
        else:
            ans+="B"
            b+=1
            a-=1
    if s[i] == "AC":
        if a==1 and c==1 and s[i+1] =="BC":
            ans+="C"
            c+=1
            a-=1
        elif a<=c:
            ans+="A"
            a+=1
            c-=1
        else:
            ans+="C"
            c+=1
            a-=1       
    if s[i] == "BC":
        if b==1 and c==1 and s[i+1] =="AC":
            ans+="C"
            c+=1
            b-=1
        elif b<=c:
            ans+="B"
            b+=1
            c-=1
        else:
            ans+="C"
            c+=1
            b-=1   
    if a<0 or b<0 or c<0:
        print("No") 
        exit()
print("Yes")
for i in ans:
    print(i)   

Measured memory_bytes: 138020
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
char s[maxn];
int n,ans1=0x7fffffff,ans2=0x7fffffff,a[maxn],p,sum;
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;++i){
		if(s[i]!=s[i-1])++p;
		++a[p];
	}
	if(p==1){
		cout<<n<<endl;
		return 0;
	}
	for(int i=1;i<=p;i+=2){
		ans1=min(ans1,max(sum,n-sum-a[i]));
		sum+=a[i]+a[i+1];
	}
	sum=a[1];
	for(int i=2;i<=p;i+=2){
		ans2=min(ans2,max(sum,n-sum-a[i]));
		sum+=a[i]+a[i+1];
	}
	cout<<max(ans1,ans2)<<endl;
	return 0;	
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<bitset>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<list>
#include<queue>
#include<map>
#include<numeric>
using namespace std;
#define rep(i,x) for(int i=0;i<x;i++)
#define re(i,x,y) for(int i=x;i<y;i++)
int INF=1e9;
const long long mod=1e9+7;
typedef long long ll;

int main(){
  int N,K;
  cin>>N>>K;
  vector<int>A(N);
  for(int i=0;i<N;i++){
      cin>>A[i];
  }
  int min=INF,num;
  for(int i=0;i<N;i++){
      if(A[i]=1){
          num=i;
      }
  }
  int ans=0;
  ans+=(num/(K-1));
  int M=ans*(K-1);
  if((N-1-M)%(K-1)==0){
      ans+=(N-1-M)/(K-1);
  }
  else{
      ans+=(N-1-M)/(K-1)+1;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cmath>
using namespace std; 
typedef long long ll;
ll n,r,b;
ll guessm(ll m){
	if(m==0)return 0;
	if(n%m!=n/m)return 0;
	return m;
}
int main(){
	cin>>n;
	r=0;
	b=(ll)sqrt(n);
	for(ll i=2;i<=b;i++){
		if(n%i==0){
			r+=guessm(i-1);
			r+=guessm(n/i-1);
		}
	}
	r+=guessm(n-1);
	if(b*b==n)r-=guessm(b-1);
	cout<<r<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

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

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

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

int N;
int A[100011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);
    sort(A, A+N);

    bool yes = true;
    if (A[0] + 1 < A[N-1]) {
	yes = false;
    } else if (A[0] == N-1) {
	yes = true;
    } else if (A[0] == A[N-1]) {
	yes = (A[0] * 2 <= N);
    } else {
	int c = A[N-1];
	int s = count(A, A+N, A[0]);
	yes = (s < c && 2*(c-s) <= N-s);
    }
    puts(yes? "Yes": "No");
}

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



Measured memory_bytes: 640
/* ex5_3
   moka223711 */

#include <stdio.h>
#define ROW 101 // マス目の行の上限
#define COL 101 // マス目の列の上限

int main(void){
    // br = black_row, bc = black_column
    // 黒が少なくとも1マス含まれている行,列を記録する 0で初期化
    int row, col, i, j, br[ROW]={0}, bc[COL]={0};
    // マス目の配色を受け取る2次元配列
    char sq[ROW][COL];
    scanf("%d %d", &row, &col);
	
    for(i = 0; i < row; i++){
        for(j = 0; j < col; j++){
            // マス目の配色を受け取り、黒が1マスでも含まれている行と列はbr[i], bc[j]を1に変える
            scanf(" %c", &sq[i][j]);
            if(sq[i][j]=='#'){
                br[i] = 1;
                bc[j] = 1;
            }
        }
    }
    for(i = 0; i < row; i++){
        // 上から1行ずつ出力していく
        // 黒が1マスも含まれない行(すべて白の行)は飛ばす
        if(br[i] == 0)
            continue;
        // このfor文が実行される行には黒が少なくとも1マス含まれている
        for(j = 0; j < col; j++){
            // 黒が1マスも含まれない列(すべて白の列)は飛ばす
            if(bc[j] == 0)
                continue;
            // マス目を出力
            printf("%c", sq[i][j]);
        }
        // 改行を出力
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 128
N = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
#最小公倍数を割った商の和を求める
import fractions
lcm = a[0]
for i in range(1,N):
    lcm = lcm * a[i] // fractions.gcd(lcm,a[i])
ans = 0
for i in range(N):
    ans += lcm//a[i]
print(ans%mod)

Measured memory_bytes: 5684
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 998244353;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl
  
const ll MAX_N = 1e6 + 10;
ll prv[MAX_N], when[MAX_N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll n, x, m;
    ll beg;
    cin >> n >> x >> m;
    beg = x;
    for(int i = 0; i < MAX_N; i ++) {
    	prv[i] = -1;
    }
    ll sum = x, cnt = 0;
    prv[x] = sum;
    when[x] = ++ cnt;
    ll offset, length, sumoffset, sumcycle;
    while(true) {
    	x = (x * x) % m;
    	if(prv[x] != -1) {
    		offset = when[x] - 1;
    		length = (cnt + 1) - when[x];
    		sumoffset = prv[x] - x;
    		sumcycle = sum + x - prv[x];
    		break;
    	}
    	cnt ++;
    	sum = sum + x;
    	prv[x] = sum;
    	when[x] = cnt;
    }
    ll ans = (n - offset) / length * sumcycle; 
   	n = (n - offset) % length + offset;
   	x = beg;
   	for(int i = 0; i < n; i ++) {
   		ans += x;
   		x = (x * x) % m;
   	}
    cout << ans << endl;
    return 0;
}


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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  map<int,int> memo;
  ll n; cin>>n;
  vector<int> A(n);
  rep(i,n){
    ll a; cin>>a;
    A.at(i)=a;
    memo[a]++;
  }
  ll ans=0;
  rep(i,n+1){
    ll num=memo[i];
    ans+=num*(num-1)/2;
  }
  rep(i,n){
    ll m=A.at(i);
    ll k=memo[m];
    cout<<ans-k*(k-1)/2+(k-2)*(k-1)/2<<endl;
  }
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
 
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long
 
const int N=1e3+5,MAX=3e7,MOD=1e9+7;
 
using namespace std;
 
int n,m;

string a[N];
ll memo[N][N];

bool valid(int i,int j){

	 return ( i>=0 && j>=0 && i<n && j<m && a[i][j]!='#' );
}

ll solve(int i ,int j){

	 if(i==n-1 && j==m-1)return 1;

	 ll &ret = memo[i][j];

	 if(ret != -1)return ret;

	 ret = 0;

	 if(valid(i+1,j))ret = (ret+solve(i+1,j))%MOD;
	 if(valid(i,j+1))ret = (ret+solve(i,j+1))%MOD;

	 return ret;
}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //#ifndef ONLINE_JUDGE
      //freopen("test.txt","r",stdin);
    //#endif
    
    cin>>n>>m;

    for(int i=0;i<n;i++)cin>>a[i];

    memset(memo,-1,sizeof(memo));

    printf("%lld\n",solve(0,0));
     
}

Measured memory_bytes: 9344
import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

N = q
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 10**9 + 1)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]



import bisect

for i, (x, start, last) in enumerate(stx):
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, (i, x))

for i, j in enumerate(d):
    res = query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)
    



Measured memory_bytes: 111068
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5+10;

int n, m;
vector<int> adj[N];
int deg[N];
int dp[N];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v; cin >> u >> v; u--; v--;
    adj[u].push_back(v);
    deg[v]++;
  }
  queue<int> q;
  for (int i = 0; i < n; i++) {
    if (!deg[i]) q.push(i);
  }
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
      dp[v] = max(dp[v], dp[u]+1);
      if (!--deg[v]) q.push(v);
    }
  }
  cout << *max_element(dp, dp + N) << nl;
  return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define REP(i,n) for(int i = 0;i < n; i++)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e18;
 
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
 
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;}
template<typename T>vector<T>
make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}
 
template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}

/*bool operator<(const data &d)const{
	return hoge;
}*/

int d[101][101];
void warshall_floyd(int n) { // nは頂点数
  for (int i = 0; i < n; i++)      // 経由する頂点
    for (int j = 0; j < n; j++)    // 開始頂点
      for (int k = 0; k < n; k++)  // 終端
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}

int N,M,L,K,A,H;

int solve(){
	vector<int>isSisetu(N,0);
	isSisetu[A] = isSisetu[H] = 1;
	rep(i,0,101)rep(j,0,101){
		if(i==j)d[i][j] = 0;
		else d[i][j] = INF;
	}
	REP(i,L){
		int t;
		cin>>t;
		isSisetu[t]=1;
	}
	REP(i,K){
		int a,b,c;
		cin>>a>>b>>c;
		d[a][b] = c;
		d[b][a] = c;
	}
	warshall_floyd(N);
	vector<pint>g[101];
	/*
	rep(i,0,N){
		rep(j,0,N){
			if(j)cout<<" ";
			cout<<d[i][j];
		}
		cout<<endl;
	}
	*/
	rep(i,0,N){
		rep(j,i+1,N){
			if(d[i][j]<=M&&isSisetu[i]&&isSisetu[j]){
				g[i].push_back({j,d[i][j]});
				g[j].push_back({i,d[i][j]});
				//cout<<i<<" "<<j<<" "<<d[i][j]<<endl;
			}
		}
	}
	vector<int>dist(N,INF);
	dist[A] = 0;
	priority_queue<pint,vector<pint>,greater<pint>>que;
	que.push({0,A});
	while(!que.empty()){
		int now = que.top().se;
		int cost = que.top().fi;
		que.pop();
		if(dist[now]!=cost)continue;
		for(auto e:g[now]){
			if(e.se+cost>=dist[e.fi])continue;
			dist[e.fi]=e.se+cost;
			que.push({dist[e.fi],e.fi});
		}
	}
	if(dist[H]==INF)return -1;
	return dist[H]+max(0ll,dist[H]-M);
}
 
signed main(){
	IOS();
	vector<int>ans;
	while(cin>>N>>M>>L>>K>>A>>H,N||M||L||K||A||H){
		ans.push_back(solve());
	}
	for(auto e:ans){
		if(e==-1)cout<<"Help!"<<endl;
		else cout<<e<<endl;
	}
}


Measured memory_bytes: 3332
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

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

	int n, m, i, j, k;
	cin >> n >> m;
	vector<string> s(n + 2);
	for (i = 1; i <= n; i++) {
		cin >> s[i];
		s[i] = "#" + s[i] + "#";
	}
	s[0] = "";
	for (i = 0; i < m + 2; i++) s[0] = s[0] + "#";
	s[n + 1] = s[0];
	for (auto p : s) cout << p << "\n";

	return 0;
}


Measured memory_bytes: 256
N, M, X = [int(i) for i in input().split()]
Cn = []
Anm = []
for n in range(N):
  Xn = [int(i) for i in input().split()]
  Cn.append(Xn[0])
  Anm.append(Xn[1:])

min_cost = 1e100
for i in range(2**N):
  is_buy = [i >> m  & 1 for m in range(N)]
  ms = [0] * M 
  cost = 0
  for n in range(N):
    if is_buy[n] == 1:
      cost += Cn[n]
      for m in range(M):
        ms[m] += Anm[n][m]
  if min(ms) >= X:
    min_cost = min(cost, min_cost)
if min_cost == 1e100:
  print(-1)
else:
  print(min_cost)
      
  
  
        



Measured memory_bytes: 9228