akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <boost/foreach.hpp>
using namespace std;
#define pi 2*asin(1.0)
#define MAX 10000000
#define MOD 1000000007
#define _GLIBCXX_DEBUG
 
vector<long> fac(MAX);
vector<long> finv(MAX);
vector<long> inv(MAX);
vector<long> Primelist;
//template functions
/////////////////////////
void Prinit(){
long PR=10000001;
vector<long> P(PR,0);
for(long i=2;i*i<PR;i++){
    if(P.at(i)==0){
        long j=i;
      j+=i;
        while(j<PR){
            P.at(j)=1;
             j+=i;         
        }
    }
}

for(long i=2;i*i<PR;i++){//Primelist.size()=446
    if(P.at(i)==0){
        Primelist.push_back(i);
    }
}
}

void Cominit(){
  fac.at(0)=fac.at(1)=1;
  finv.at(0)=finv.at(1)=1;
  inv.at(1)=1;
  for(long i=2;i<MAX;i++){
      fac.at(i)=(fac.at(i-1)*i)%MOD;
      inv.at(i)=MOD-inv.at(MOD%i)*(MOD/i)%MOD;
      finv.at(i)=finv.at(i-1)*inv.at(i)%MOD;
  }
}

long facComb(long N,long M){// nCm%
if(N<M) return 0;
if(N<0||M<0) return 0;
return fac.at(N)*(finv.at(M)*finv.at(N-M)%MOD)%MOD;
}

long Comb(long N,long M){// nCm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
for(long i=M;i>0;i--){
    ans=ans/i;
}
return ans;
}

long Perm(long N,long M){// nPm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
return ans;
}

long GCM(long A,long B){
            long W,r;
    if(A<B){

        W=B;
        B=A;
        A=W;
    }
    while(A%B!=0){
        r=A%B;
        A=B;
        B=r;
    }
    return B;
}
long LCM(long A,long B){
    return (A*B)/GCM(A,B);
}

long upDiv(long a,long b){
  return (a+b-1)/b;
}

long strtolong(string str){
istringstream ss;
ss=istringstream(str);
long num;
ss>>num;
return num;
}

long chartolong(char ch){
long num;
num=ch-'0';
return num;
}

string longtostr(long N){
    string str;
    str=to_string(N);
    return str;
}









/////////////////////////


//Answer


int main() {
Prinit();
long N,ans=1;
string S;
cin>>N>>S;
for(long i=1;i<N;i++){
if(S.at(i)!=S.at(i-1)){
    ans++;
}
}
cout<<ans<<endl;
}



Measured memory_bytes: 315648
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int A[16] = {4,1,4,1,2,1,2,1,4,1,4,1,2,1,2,1};
string B = "4141212141412121";
int s2i(string s){
	return atoi(s.c_str());
}
int main(){
	vector <int> C;
	int i,j, x[8] = {},s,m,p,tmp;
	for(i=0;i<8;i++)C.push_back(s2i(B.substr(i,8)));
	while(cin>>x[0]){
		m=x[0];
		for(i=1;i<8;i++){
			cin>>x[i];
			m+=x[i];
		}
		for(i=0;i<8;i++){
			s=0;
			for(j=0;j<8;j++){
				tmp=x[j]-A[i+j];
				s+=(tmp>0?tmp:0);
			}
			if(s<m){
				m=s;
				p=i;
			}
			else if(m==s&&C[i]<C[p])p=i;
		}
		for(i=0;i<8;i++)cout<<B[p+i]<<" \n"[i==7];
	}
}

Measured memory_bytes: 1212
h, w = map(int, input().split(" "))
s = []
s.append(["0"] * (w + 2))
for i in range(h):
  s.append(list("0"+input().replace(".","0").replace("#","1")+"0"))
s.append(["0"] * (w + 2))

ans = []
for i in range(1, h + 1):
  tmp = []
  for j in range(1, w + 1):
    if s[i][j] == "1":
      tmp.append("#")
    else:
      tmp2 = ""
      tmp2 += s[i-1][j-1]
      tmp2 += s[i-1][j]
      tmp2 += s[i-1][j+1]
      tmp2 += s[i][j-1]
      tmp2 += s[i][j+1]
      tmp2 += s[i+1][j-1]
      tmp2 += s[i+1][j]
      tmp2 += s[i+1][j+1]
      tmp.append(tmp2.count("1"))
  ans.append(tmp)

for i in range(h):
  for j in range(w):
    print(ans[i][j], end="")
  print()

Measured memory_bytes: 9276
/*      ░░█ ▄▀█ █   █▀ █░█ █▀█ █▀▀ █▀▀   █▀█ ▄▀█ █▀▄▀█  
        █▄█ █▀█ █   ▄█ █▀█ █▀▄ ██▄ ██▄   █▀▄ █▀█ █░▀░█     */


// [abc053_b.cpp] => [27-07-2020 @ 22:15:49] 
// Author & Template by : Udit "luctivud" Gupta
// https://www.linkedin.com/in/udit-gupta-1b7863135/


#include <bits/stdc++.h>
// #include <iostream>
// #include <string>
// #include <vector>
// #include <algorithm>
// #include <sstream>
// #include <queue>
// #include <deque>
// #include <bitset>
// #include <iterator>
// #include <list>
// #include <stack>
// #include <map>
// #include <set>
// #include <functional>
// #include <numeric>
// #include <utility>
// #include <limits>
// #include <time.h>
// #include <math.h>
// #include <stdio.h>
// #include <string.h>
// #include <stdlib.h>
// #include <assert.h>

using namespace std;

typedef long long int lld;
typedef unsigned long long int llu;
typedef vector<int> v_int;
typedef vector<lld> v_lld;
typedef vector<llu> v_llu;
typedef pair<int, int> p_int;
typedef pair<lld, lld> p_lld;


#define   INDEPENDENT_CASES()  cin >> (T3X0); T353 = T3X0; while(T3X0--)
#define          _input(V3C0)  for(auto &V3C0_IT7 : (V3C0)) cin >> (V3C0_IT7)
#define     mems(A77AY, V4LU)  memset((A77AY), (V4LU), sizeof((A77AY)))
#define   CH3K(IT7, EN4, S7P)  (((S7P)<0) ? (IT7)>(EN4) : (IT7)<(EN4))
#define for4(IT7,ST4,EN4,S7P)  for(auto IT7=(ST4); CH3K(IT7,EN4,S7P); (IT7)+=(S7P))
#define    FORE4CH(IT7, V3C0)  for(auto IT7=(V3C0).begin(); IT7!=(V3C0).end(); IT7++)


// template<typename T> void _SC4N(T &x) { 
//     x = 0; bool neg = 0; 
//     register T c = getchar();
//     if (c == '-') neg = 1, c = getchar();
//     while ((c < 48) || (c > 57)) c = getchar();
//     for ( ; c < 48||c > 57 ; c = getchar());
//     for ( ; c > 47 && c < 58; c = getchar() ) x= (x << 3) + ( x << 1 ) + ( c & 15 );
//     if (neg) x *= -1;
// }





void solveEachTest(lld T35TC453N = 1) {
    // auto S34t = chrono:: high_resolution_clock::now(); 

    string s; cin >> s;

    lld n = (lld)s.length();
    lld i = 0, j = n-1;
    for(; i<n; i++) if (s[i] == 'A') break;
    for(; j>=0; j--) if (s[j] == 'Z') break;

    cout << j-i+1;

    cout << "\n"; 

    // auto S34p = chrono::high_resolution_clock::now(); 
    // auto D34n = chrono::duration_cast<chrono::microseconds>(S34p - S34t);
    // cout << "Time Elapsed: " << D34n.count() / (long double) 1e6 << " seconds" << endl; 
    return;
}


signed main() {

    // ios_base::sync_with_stdio(false); cin.tie(0);

    lld T3X0 = 0, T353 = 1;

    // INDEPENDENT_CASES()
        solveEachTest(T353 - T3X0);
    return 0;
}


Measured memory_bytes: 3668
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

#include "bits/stdc++.h"
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> a(N);

	REP(i, N) {
		cin >> a[i];
	}

	sort(a.begin(), a.end());

	int r = 0;
	REP(i, N - 1) {
		if (abs(2 * r - a[N - 1]) > abs(2 * a[i] - a[N - 1])) {
			r = a[i];
		}
	}

	cout << a[N - 1] << " " << r << endl;

	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 200005;

int main()
{
	int n,a[5]={0};
	string s;
	cin>>n;
	while(n--){
		cin>>s;
		if(s=="AC")
			a[0]++;
		else if(s=="WA")
			a[1]++;
		else if(s=="TLE")
			a[2]++;
		else if(s=="RE")
			a[3]++;
	}
	printf("AC x %d\n",a[0]);
	printf("WA x %d\n",a[1]);
	printf("TLE x %d\n",a[2]);
	printf("RE x %d\n",a[3]);
	return 0;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n, d;
	cin>>n>>d;
	int res = 0;
	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		cnt++;
		if(cnt == 2 * d + 1){
			res++;
			cnt = 0;
		}
	}
	if(cnt != 0)res++;
	cout<<res<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

int main() {
    LL k, a, b;
    cin >> k >> a >> b;
    if (a >= b) {
        cout << 1 + k << endl;
    } else {
        LL cnt = 1;
        if (cnt <= a) {
            LL t = min(a-cnt, k);
            cnt += t;
            k -= t;
        }
        if (b-a>=2) {
            cnt += k / 2 * (b - a);
            if (k & 1) cnt++;
        } else {
            cnt += k;
        }
        cout << cnt << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int64_t i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define VIN(n,v) for(int64_t i=0;i<(n);i++){cin >> (v).at(i);}

using namespace std;
typedef int64_t I;
typedef pair<I,I> P;
typedef vector<I> V;

I MOD = pow(10,9)+7;

// 最大公約数
I gcd(I a, I b) {
  return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
I lcm(I a, I b) {
  return a * b / gcd(a, b);
}

int ctoi(char c){
  return c - '0';
}

int main(){
  I n;
  cin >> n;
  V a(n),b(n);
  VIN(n,a);
  VIN(n,b);
  REP(i,n){
    if (a.at(i) > b.at(i)){
      cout << -1 << endl;
      return 0;
    }
    I prev;
    I next;
    if (i==0){
      prev = n-1;
      next = 1;
    }else if (i==n-1){
      prev = n-2;
      next = 0;
    }else{
      prev = i-1;
      next = i+1;
    }
    if (a.at(i) != b.at(i) && a.at(prev) + a.at(i) + a.at(next) > b.at(i)){
      cout << -1 << endl;
      return 0;
    }
  }
  I t=0;
  while (true){
    bool chk = true;
    REP(i,n){
      I prev;
      I next;
      if (i==0){
        prev = n-1;
        next = 1;
      }else if (i==n-1){
        prev = n-2;
        next = 0;
      }else{
        prev = i-1;
        next = i+1;
      }
      if (b.at(prev) + b.at(next) <= (b.at(i) - a.at(i))){
        t += (b.at(i)-a.at(i)) / (b.at(prev) + b.at(next));
        b.at(i) -= (b.at(i)-a.at(i)) / (b.at(prev) + b.at(next)) * (b.at(prev) + b.at(next));
        chk = false;
      }
    }
    if (chk == true) break;
  }
  bool chk2 = true;
  REP(i,n){
    if (a.at(i) != b.at(i)) chk2 = false;
  }
  if (chk2){
    cout << t << endl;
  }else{
    cout << -1 << endl;
  }
  return 0;
}



Measured memory_bytes: 3328
#define USE_MATH_DEFINES 1
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 998244353ll
#define INF 1000000000000000000ll
#define EPS 1e-9

#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock

typedef long long         ll;
typedef long double       ld;
typedef pair <ll,ll>      pl;
typedef tuple <ll,ll,ll>  tl;

ll N, X, Y, M, D[2][100005], S1[100005], S2[100005], B1[100005], B2[100005], C;
vector <ll> adj[100005], ans1, ans2;
bool pos;

void dia (ll run, ll cur) {
	for (ll nex : adj[cur]) {
		if (D[run][nex] == -1) {
			D[run][nex] = D[run][cur] + 1;
			dia(run, nex);
		}
	}
}

void chk1 (ll cur, ll par) {
	ll pre = ++C;
	for (ll nex : adj[cur]) {
		if (nex != par) chk1(nex, cur);
	}
	S1[cur] = C - pre + 1;
	ll big = 0;
	B1[cur] = -1;
	for (ll nex : adj[cur]) {
		if (nex != par && S1[nex] > 1) {
			big++;
			B1[cur] = nex;
		}
	}
	if (big >= 2) pos = false;
}

void chk2 (ll cur, ll par) {
	ll pre = ++C;
	for (ll nex : adj[cur]) {
		if (nex != par) chk2(nex, cur);
	}
	S2[cur] = C - pre + 1;
	ll big = 0;
	B2[cur] = -1;
	for (ll nex : adj[cur]) {
		if (nex != par && S2[nex] > 1) {
			big++;
			B2[cur] = nex;
		}
	}
	if (big >= 2) pos = false;
}

void gen1 (ll cur) {
	//cout << "running gen " << cur << "\n";
	ll ch = (cur == X) ? adj[cur].size() : (adj[cur].size()-1);
	for (ll i = C + 1; i <= C + ch - 1; i++) ans1.push_back(i);
	ans1.push_back(C);
	C += ch;
	if (B1[cur] != -1) gen1(B1[cur]);
}

void gen2 (ll cur) {
	//cout << "running gen " << cur << "\n";
	ll ch = (cur == Y) ? adj[cur].size() : (adj[cur].size()-1);
	for (ll i = C + 1; i <= C + ch - 1; i++) ans2.push_back(i);
	ans2.push_back(C);
	C += ch;
	if (B2[cur] != -1) gen2(B2[cur]);
}

bool less1() {
	for (ll i = 0; i < N; i++) {
		if (ans1[i] < ans2[i]) return true;
		if (ans1[i] > ans2[i]) return false;
	}
	return false;
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	for (ll i = 1; i <= N-1; i++) {
		ll a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	memset(D, -1, sizeof D);
	D[0][1] = 0;
	dia(0, 1);
	
	X = -1;
	M = -1;
	for (ll i = 1; i <= N; i++) {
		if (D[0][i] > M) {
			X = i;
			M = D[0][i];
		}
	}
	
	D[1][X] = 0;
	dia(1, X);
	
	Y = -1;
	M = -1;
	for (ll i = 1; i <= N; i++) {
		if (D[1][i] > M) {
			Y = i;
			M = D[1][i];
		}
	}
	
	pos = true;
	
	C = 0;
	chk1(X, -1);
	
	C = 0;
	chk2(Y, -1);
	
	if (pos) {
		C = 1;
		gen1(X);
		ans1.push_back(N);
		C = 1;
		gen2(Y);
		ans2.push_back(N);
		if (less1()) {
			cout << ans1[0];
			for (ll i = 1; i < (ll)ans1.size(); i++) cout << ' ' << ans1[i];
		} else {
			cout << ans2[0];
			for (ll i = 1; i < (ll)ans2.size(); i++) cout << ' ' << ans2[i];
		}
	} else {
		cout << -1;
	}
	
    return 0;
}

Measured memory_bytes: 20596
#include<bits/stdc++.h>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef std::vector<long long> vl;
typedef std::vector<std::vector<long long>> vvl;
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}


ll gcd(ll n, ll m) {
    ll tmp;
    while (m!=0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }
    return n;
}
 
ll lcm(ll n, ll m) {
    return abs(n) / gcd(n, m)*abs(m);//gl=xy
}

using namespace std;

void solve()
{
  int k, a, b;
  cin >> k >> a >> b;
  for (int i = a; i <= b;++i){
    if(i%k==0){
      cout << "OK\n";
      return;
    }
  }
  cout << "NG\n";
}

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



Measured memory_bytes: 3668
#include <iostream>                                             
using namespace std;                                            
                                                                
int main(void) {                                                
  char ch;                                                      
  int count[26]={};                                             
  while (cin >> ch) {                                           
    if (islower(ch)) {                                          
      int num = ch-'a';                                         
      count[num]++;                                             
    } else if (isupper(ch)) {                                   
      int num = ch-'A';                                         
      count[num]++;                                             
    }                                                           
  }                                                             
  for (int i=0; i<26; i++) {                                    
    cout << char(i+'a') << " : " << count[i] << endl;           
  }                                                             
  return 0;                                                     
}                                                               
                                  

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

int main(){
    int H, N;
    cin >> H >> N;
    int A[N], B[N];
    rep(i, N) cin >> A[i] >> B[i];
    vector<int> dp(H+1, 2000000000);
    dp[0] = 0;
    rep(i, N) rep(j, H){
        int jt = min(j+A[i], H);
        dp[jt] = min(dp[jt], dp[j] + B[i]);
    }
    cout << dp[H] << endl;
    return 0;
}

Measured memory_bytes: 3668
#include <stdio.h>

int a, b, c;
int main(){
	scanf("%d %d %d", &a, &b, &c);
	if(a<b && b<c){
		printf("%d %d %d\n", a, b, c);
	}else if(a <= c && c <= b){
		printf("%d %d %d\n", a, c, b);
	}else if(b <= a && a <= c){
		printf("%d %d %d\n", b, a, c);
	}else if(b <= c && c <= a){
		printf("%d %d %d\n", b, c, a);
	}else if(c <= b && b <= a){
		printf("%d %d %d\n", c, b, a);
	}else if(c <= a && a <= b){
		printf("%d %d %d\n", c, a, b);
	}
	return 0;
}



Measured memory_bytes: 2092
use std::collections::BinaryHeap;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn main() {
    let input = read_vec::<usize>();
    let (n, m) = (input[0], input[1]);
    let mut bh = BinaryHeap::with_capacity(n);

    let ax = read_vec::<usize>();
    for a in ax {
        bh.push(a);
    }

    for _ in 0..m {
        if let Some(x) = bh.pop() {
            bh.push(x/2);
        }
    }

    let ans: usize = bh.into_iter().sum();

    println!("{}", ans);
}

Measured memory_bytes: 10492
#dp educational contest a frog1 漸化式
n=int(input())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
    if i==1:
        dp[i]=abs(h[i]-h[i-1]) #０番目と１番目の差
    else:
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
ans=dp[n-1]
print(ans)

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

char bit[26];

int main() {
	string s;
	string t;

	cin >> s >> t;

	int ans = 0;
	for( int i = 0; i < s.size() - 1; i++ ) {
		auto pos = s.find(s[i]);
		if( pos != string::npos ) {
			if( t[i] != t[pos] ) {
				ans = 1;
			}
		}
	}
	if( ans == 0 ) {
		for( int i = 0; i < s.size(); i++ ) {
			bit[s[i] - 'a']++;
		}
		int scnt = 0;
		for( int i = 0; i < 26; i++ ) {
			if( bit[i] ) {
				scnt++;
			}
		}
		memset( bit, 0, sizeof(bit) );
		for( int i = 0; i < s.size(); i++ ) {
			bit[t[i] - 'a']++;
		}
		int tcnt = 0;
		for( int i = 0; i < 26; i++ ) {
			if( bit[i] ) {
				tcnt++;
			}
		}
		if( scnt != tcnt ) {
			ans = 1;
		}
	}

	if( ans == 0 ) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 776
#include<bits/stdc++.h>
using namespace std;
 
#define lli long long int
#define FOR(a,b) for(i=a;i<b;i++)
int main(){
    lli n,i;
    cin >> n;
    lli s = n-1;
    FOR(1,1000010){
        if(n%i==0)
            s = min(s, n/i+i-2);
    }
    cout << s << endl;
}

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

int main(){
	
	long long int t;
	long long int num=0;
	cin>>t;
	map<string,int> a;
	while(t--){
		string s;
		cin>>s;
		sort(s.begin(),s.end());
		//printf("%d",);
		num+=a[s]++;
	}
	cout<<num<<endl;
}











Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<ll,ll>
#define poly vector<ll>
#define mem(a) memset((a),0,sizeof(a))
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x.size()))
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
ll rnd(){
	ull ans=0;
	For(i,0,4)ans=ans<<15^rand();
	return ans%((ull)1<<63);
}
const int N=5005,mod=1e9+7;
ll f[N],g[N],pw[N],ppw[N];
int main(){
	#ifdef Brollan
		freopen("1.in","r",stdin);
	#endif
	int n=read(),m=read();
	f[m]=1;
	For(i,pw[0]=1,m)pw[i]=pw[i-1]*2%mod;
	For(i,ppw[0]=1,m)ppw[i]=ppw[i-1]*(mod+1)/2%mod;
	For(i,1,n){
		ll sum=0;
		Rep(j,m,1){
			g[j]=(f[j]*(j+1)+sum*ppw[j]%mod*j)%mod;

			sum=(sum+f[j]*pw[j-1])%mod;
			g[j]%=mod;
		}
		swap(f,g);
	}
	ll ans=0;
	For(i,0,m)ans+=f[i];
	cout<<ans%mod<<endl;
}


Measured memory_bytes: 3780
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll mod = 1e9 + 7;
ll n, k, dp[100010], ans;
VI e[100010];

void dfs(int now, int past){
    ll cnt = e[now].size() - (past != -1);
    if (past == -1) REP(x,cnt) ans = (ans * (k - 1 - x)) % mod;
    else REP(x,cnt) ans = (ans * (k - 2 - x)) % mod;
    for (int next : e[now]){
        if (next == past) continue;
        dfs(next, now);
    }
}

int main() {
    cin >> n >> k;
    REP(i,n-1){
        int u = in() - 1, v = in() - 1;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    ans = k;
    dfs(0, -1);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;
using Graph =vector<vector<lint>>;

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

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}
lint lcm(lint a,lint b){
      return a/__gcd(a,b)*b;
  }
  lint c[10][10];
  int main(){
   lint ans=0;
      lint N;
      cin>>N;
      repp(i,1,N+1){
          string s=to_string(i);
          if(s[0]==s[s.size()-1]){
              lint g=s[0]-'0';
              c[g][g]++;
          }
        else if(s[0]=='0'||s[s.size()-1]=='0')continue;
        else {
            char x=s[0];
            char y=s[s.size()-1];
            lint v=x-'0';
            lint d=y-'0';
            c[v][d]++;
            }
        }
      
     // cout<<ans<<endl;
      
     
      rep(i,10){
          rep(j,10){
              ans+=c[i][j]*c[j][i];
          }
      }
    cout<<ans;
  }
  

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << 63) - 1;
const LL mod = 1000000007;
const int N = 1e5 + 5;
const double Pi = acos(-1.0);
const int maxn = 2e5 + 5;
LL a[maxn],b[maxn];
LL c[maxn];
int main() {
#ifdef local
    freopen("in", "r", stdin);
    //  freopen("w","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i = 0;  i < n; i++){
        cin>>a[i]>>b[i];
    }
    LL res = 0;
    for(int i = n - 1; i >= 0; i--){
        if((a[i] + res)%b[i] == 0)continue;
        LL ne = b[i] - (a[i] + res)%b[i];
        res += ne;
    }
    cout<<res<<endl;
}


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

int N;
int A[111], B[111];

int main() {
   cin >> N;
   for (int i = 0; i < N; i++) {
      cin >> A[i];
   }
   for (int i = 0; i < N; i++) {
      cin >> B[i];
   }

   int ans = 0;
   for (int i = 0; i < N; i++) {
      int sum = 0;
      for (int j = 0; j <= i; j++) {
         sum += A[j];
      }
      for (int j = i; j < N; j++) {
         sum += B[j];
      }
      ans = max(ans, sum);
   }

   cout << ans << endl;

   return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    int H, W; cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    int out = -1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '#') continue;

            int tmax = -1;
            vector<vector<int>> D(H, vector<int>(W, -1));
            D[i][j] = 0;
            queue<pair<int, int>> Q;
            Q.emplace(i, j);
            while (!Q.empty()) {
                auto cord = Q.front();
                Q.pop();

                int x = cord.first, y = cord.second;
                if (x - 1 >= 0 && S[x - 1][y] == '.' && D[x - 1][y] == -1) {
                    D[x-1][y] = D[x][y] + 1; Q.emplace(x-1, y);
                }
                if (x + 1 < H && S[x + 1][y] == '.' && D[x + 1][y] == -1) {
                    D[x+1][y] = D[x][y] + 1; Q.emplace(x+1, y);
                }
                if (y - 1 >= 0 && S[x][y-1] == '.' && D[x][y-1] == -1) {
                    D[x][y-1] = D[x][y] + 1; Q.emplace(x, y-1);
                }
                if (y + 1 < W && S[x][y+1] == '.' && D[x][y+1] == -1) {
                    D[x][y+1] = D[x][y] + 1; Q.emplace(x, y+1);
                }
            }

            for (int ii = 0; ii < H; ii++) {
                for (int jj = 0; jj < W; jj++) tmax = max(tmax, D[ii][jj]);
            }

            out = max(out, tmax);
            
        }
    }

    cout << out << endl;

    return 0;
}


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

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var nk = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var n = nk[0];
        var k = nk[1];
        var s = Console.ReadLine().Trim().ToCharArray();

        s[k - 1] = char.ToLower(s[k - 1]);
        Console.WriteLine(new string(s));
    }
}


Measured memory_bytes: 11348
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define sz(a) ((int)a.size())
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijoMOD(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=yakusu[i];
  }
  return num;
}

int H,W;
vs s(50);
vi dv ={-1,0,1,0};vi du={0,-1,0,1};
int cnt=1;
int dfs(int u,int v){
  s[u][v]='.';
  
  rep(i,4){
   
      int nu =u +du[i],nv=v+dv[i];
      if(nu<0||nu>=H||nv<0||nv>=W)continue;
      if(s[nu][nv]=='.')continue;
      cnt ++;
      dfs(nu,nv);
    
  }
  return cnt;

}
int keta_wa(int x){
  int tot=0;
  while(x>0){
    tot +=x%10;
    x/=10;
  }
  return tot;
}

//vc alp ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//vc Alp ={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
//cout<<""<<endl;
int main(){
  int N;cin>>N;
  cout<<N*(N+1)/2<<endl;
}



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

int main() {
  int a,b;
  cin >> a >> b;
  
  if((a+b)%2 == 0){
    cout << (a+b)/2 << endl;
  }
  else if((a+b)%2 != 0){
    cout << (a+b)/2+1 << endl;
  }
  
}

Measured memory_bytes: 256
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
s = sorted(inplL(n))

tmp = ''
ans = []
anscnt = -1
for i in range(n):
    if tmp == s[i]:
        ans[anscnt][1] += 1
    else:
        ans.append([s[i],1])
        anscnt += 1
    tmp = s[i]

ans.sort(key=lambda x: x[1],reverse=True)

tmp = 0
ret = []
for i in range(len(ans)):
    if i == 0 or tmp == ans[i][1]:
        ret.append(''.join(ans[i][0]))
        tmp = ans[i][1]
    elif tmp != ans[i][1] :
        break

ret.sort()
for i in range(len(ret)):
    print(ret[i])

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> v(m);
  rep(i, m) cin >> v[i];

  vector<ll> dp(n+10, 0);
  rep(i, m) dp[v[i]] = -1; 
  dp[0] = 1;
  rep(i, n){
    if (dp[i] == -1) continue;
    if (dp[i+1] != -1) dp[i+1] = (dp[i+1] + dp[i]) % 1000000007;
    if (dp[i+2] != -1) dp[i+2] = (dp[i+2] + dp[i]) % 1000000007;
  }
  cout << dp[n] << endl;
  return 0;
}

Measured memory_bytes: 4180
#include<bits/stdc++.h>
#define cases long long t;cin>>t;while(t--)
#define f_io ios::sync_with_stdio(false); cin.tie(0)
#define foi(a,n) for(long long i=a;i<n;i++)
#define foj(a,n) for(long long j=a;j<n;j++)
#define fok(a,n) for(long long k=a;k<n;k++)
#define ll long long
#define MOD 1000000007
#define INF 1000000000
using namespace std;

int main()
{
    f_io;
    ll d,t,s;
    cin >> d >> t >> s;
    double tm = d/(double)s;
    if(tm<=t)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}


Measured memory_bytes: 3648
#!/usr/bin/env python3


def maximize_product(a, b, c, d):
    return max(a * c, a * d, b * c, b * d)


def main():
    a, b, c, d = (int(z) for z in input().split())
    res = maximize_product(a, b, c, d)
    print(res)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9172
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <random>
#include <ctime>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define ld long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast_io cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ld eps = (ld)1 / 1e10;
ll inf = 1e18, mod2 = 998244353, mod1 = 1e9 + 7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ll a[200001];
unordered_map<ll, ll> ump;

int main()
{
    fast_io;
    ll n, i, s = 0, k;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (ump.find(a[i]) == ump.end()) ump.insert({a[i], 0});
        ump[a[i]]++;
    }
    for (auto f: ump)
        s += f.second * (f.second - 1);
    for (i = 1; i <= n; i++)
    {
        k = ump[a[i]];
        cout << (s - k * (k - 1) + (k - 1) * (k - 2)) / 2 << '\n';
    }
    return 0;
}

Measured memory_bytes: 9160
#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, K;
  cin >> N >> M >> K;
  vector<ll> A(N+1,0), B(M+1,0);
  rep(i,N) cin >> A[i+1];
  rep(i,M) cin >> B[i+1];

  rep(i, N) A[i+1] += A[i];
  rep(i, M) B[i+1] += B[i];

  int ans = 0;
  int i_A = 0, i_B = M;
  while (i_A <= N) {
    int time = A[i_A];
    while (i_B >= 0 && time + B[i_B] > K) i_B--;
    if (i_B == -1) break;
    ans = max(ans, i_A + i_B);
    i_A++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6400
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <vector>
using namespace std;

struct pond {
    int startPos;
    int volume;
};

int main() {
    int n, q;
    cin >> n;
    int s[n];
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }
    cin >> q;
    int t[q];
    for(int i = 0; i < q; i++){
        cin >> t[i];
    }
    
    long cnt = 0;
    for(int i = 0; i < q; i++){
        for(int j = 0; j < n; j++){
            if(t[i] == s[j]){
                cnt++;
                break;
            }
        }
    }
    
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 1196
#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(defmacro dp (name args memo-size &body body)
  (let ((memo (gensym)))
    `(let ((,memo (make-array ,memo-size :initial-element nil)))
       (defun ,name ,args
         (or (aref ,memo ,@args)
             (setf (aref ,memo ,@args)
                   ,@body))))))

(defun split (x str)
  (let ((pos (search x str))
        (size (length x)))
    (if pos
      (cons (subseq str 0 pos)
            (split x (subseq str (+ pos size))))
      (list str))))

(defmacro collect-times (time body)
  `(loop repeat ,time collect ,body))

(defun read-times (time)
  (collect-times time (read)))

(defun main(likes)
  (length (reduce #'intersection likes)))

(let* ((n (read))
       (m (read))
       (likes (collect-times n (read-times (read)))))
  (princ (main likes)))


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

using namespace std;

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

	vector<int> P;
	int total_p = 0;
	for (int i = 0; i < N; i++) {
		int p;
		cin >> p;
		total_p += p;
		P.push_back(p);
	}

	sort(P.begin(), P.end());
	reverse(P.begin(), P.end());

	cout << total_p - P[0] / 2 << endl;
}




Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int all;
    int s;
    int m;
    int h;
    cin >> all;
    s = all % 60;
    m = (all / 60)%60;
    h = (all /60)/60;
    std::cout << h << ":" << m << ":" << s <<std::endl;
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define INF 1000000007
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define print(x) cout << x << "\n"
#define print2(x, y) cout << x << " " << y << "\n"
#define printv(vec) rep(lp, vec.size()) cout << vec[lp] << " "; print("\n"); 
#define show(x) cerr << #x << " = " << x << "\n";
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
typedef long long ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;

const int mod = 998244353;
class mint {
public:
    ll x;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res /= a;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

ll modpow(ll a, ll n){
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

void Main(){
 
	ll N, X, M;
	cin >> N >> X >> M;
	
	vl acc(1);
	map<ll, ll> mp;
	ll ans = 0;
 
	rep(i, N){
 
		if(mp[X]){
			
			if(!X){
				print(ans);
				return;
			}
			
			ll loop_start = mp[X]; // loop の開始地点
			ll loop_length = i - loop_start; // loop の長さ
			ll roop_cnt = (N - i) / loop_length; // N 回回るときのループ回数(初回の検出時を除く)
			ll loop_mod = (N - i) % loop_length; // 最後のループの余り
			ll accs = acc[i] - acc[i - loop_length]; // 1ループで得られる得点
			ans += accs * roop_cnt; // ループ中に得られる得点
			ans += acc[loop_start + loop_mod] - acc[loop_start]; // 余りで得られる得点
			break;
			
		}
 
		mp[X] = i;
		ans += X;
		acc.push_back(acc[i] + X);
		X = (X * X) % M;
	}
 
	print(ans);	
 
}

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	Main();
	return 0;
	
}





Measured memory_bytes: 6728
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <utility>
#include <set>
#include <map>
#include <tuple> 
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
using namespace  std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(long long (i)=0, i_bound = (long long)(n); (i)<i_bound; ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
const long long MOD = 998244353LL;
const long long INF = 1234567891234567890LL;
template<typename T>
long long pow(T n, T x, T MOD=(T)998244353LL){
    if(n==0) return 0;
    long long res = 1LL;
    while(x){
        if(x%2==1) res = (res*n) % MOD;
        x = x>>1;
        n= (n*n) % MOD;
    }
    return res%MOD;
}
int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);
    ll N; cin>>N;
    vector<ll> D(N);
    REP(i, N) cin>>D[i];
    long long res = 1;
    map<ll, ll> m;
    for(int i=0; i<N; i++){
        m[D[i]]++;
    }
    if(D[0]!=0 or m[0]>1){
        cout << 0 <<endl;
        return 0;
    }
    ll mn = 0;
    REP(i, N) mn = max(mn, D[i]);
    for(ll l=1; l<=mn; l++){
        res = (res*pow(m[l-1], m[l]))%MOD;
    }
    cout << res%MOD << endl;
    return 0;
}

Measured memory_bytes: 7296
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline

def main():
    s = input()
    a_num = s.count('a')
    b_num = s.count('b')
    c_num = s.count('c')
    if abs(a_num - b_num) <= 1 and abs(b_num - c_num) <= 1 and abs(a_num - c_num) <= 1:
        print('YES')
    else:
        print('NO')



def divide_list(l, args):
    result = []
    pre = 0
    for i, a in enumerate(args):
        if i != 0:
            pre = args[i-1]
        result.append(l[pre:a])
        if i == len(args) - 1:
            result.append(l[a:])
    return result

def divide_two(n):
    c = 0
    while True:
        if c >= 2:
            break
        if n % 2 != 0:
            break
        n //= 2
        c += 1
    return c

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()


Measured memory_bytes: 64364
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename T>
using pque = priority_queue<T, vector<T>, greater<T>>;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

int main(){
	int h, a; scanf("%d%d", &h, &a);
	int ans = 0;
	while(h > 0) h -= a, ans += 1;
	printf("%d\n", ans);
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223372036854775807
#define INF 2147483647
#define MOD 1000000007
using namespace std;


struct UF
{
    long         num;
    vector<long> par;
    vector<long> rank;

    UF(long n): num(n)
    {
        par.resize(n);
        rank.resize(n);
        long i;
        for(i=0; i<n; i++) {
            par[i]=i;  rank[i]=1;
        }
    }
	
    long find(long x)
    {
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }

    void unite(long x, long y)
    {
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]) {
            par[x]=y;
        }
        else {
            par[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }

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

    long ngroup()
    {
        long count=0;
        long i;
        for(i=0; i<num; i++) {
            if(par[i]==i) count++;
        }
        return count;
    }
};


int main(int argc, char* argv[])
{
    long n, m;
    scanf("%ld%ld", &n, &m);

    vector<long> a(m), b(m);

    long i;
    for(i=0; i<m; i++) {
        scanf("%ld%ld", &a[i], &b[i]);
    }

    long count=0;
    long k;
    for(k=0; k<m; k++) {
        UF  uf(n);
        for(i=0; i<m; i++) {
            if(i!=k) {
                uf.unite(a[i]-1, b[i]-1);
            }
        }
        if(uf.ngroup() == 2) {
            count ++;
        }
    }

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

    return 0;
}


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

const string NO = "IMPOSSIBLE";

void solve(long long A, long long B){
    if ((A + B) % 2) cout << NO << '\n';
    else cout << (A + B) / 2 << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int INTMAX = 2147483647;
const int INTMIN = -2147483648;
const unsigned int UINTMAX = 4294967295;
const long LONGMAX = 9223372036854775807;
const long LONGMIN = -9223372036854775808;
const unsigned long ULONGMAX = 18446744073709551615;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define UNIQ(c) (c).erase(unique((c).begin(), (c).end()), (c).end());
#define Yn(b) puts(b?"Yes":"No")
#define YN(b) puts(b?"YES":"NO")

bool isprime(int p) {
  if (p==1) return false;
  FOR(i,2,p) {
    if (p%i==0) return false;
  }
  return true;
}

int dig(int n, int a) {return n/(int)pow(10,a)%10;}
int digl(long n, int a) {return n/(long)pow(10,a)%10;}
int digsum(int n) {int r=0;REP(i,10){r+=dig(n,i);}return r;}
int digsuml(long n) {int r=0;REP(i,19){r+=digl(n,i);}return r;}
int dignum(int n) {return n?to_string(n).length():0;}
int dignuml(long n) {return n?to_string(n).length():0;}

int main(){
  string s,c;
  cin >> s;
  int m=0;
  c = "CODEFESTIVAL2016";
  REP(i,s.length()){
    if(s[i]!=c[i])m++;
  }
  cout << m;
}

Measured memory_bytes: 256