akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

int main() {
	int n;
	scanf("%d", &n);
	ll a = 1, b = 1;
	while(n--) {
		ll x, y;
		scanf("%lld%lld", &x, &y);

		ll k = max(1ll, max((a-1ll)/x+1ll, (b-1ll)/y+1ll));
		a = k*x, b = k*y;
	}

	printf("%lld\n", a+b);
    
    return 0;
}


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

int main() {
    int n, m;
    cin >> n;
    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];
    cin >> m;
    vector<vector<int>> p(m, vector<int>(2));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 2; j++) cin >> p[i][j];
    }
    for (int j = 0; j < m; j++) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (p[j][0]-1 == i) ans += p[j][1];
            else ans += t[i];
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>

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

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

   if (a > b){
      x = a;
      a = b;
      b = x;
   }

   if (b > c){
      x = b;
      b = c;
      c = x;
   }

   if (a > b){
      x = a;
      a = b;
      b = x;
   }

   printf("%d %d %d\n", a, b, c);

   return 0;
}


Measured memory_bytes: 2080
#include <iostream>
#include <math.h>
#include <vector>
#define ll long long
using namespace std;
ll mod = 1000000007;


ll factorial[200010];
ll fact_inv(ll a);


int main(){

    ll H,W,A,B;
    cin >> H >> W >> A >> B;


    //make x!
    factorial[0] = 1;
    for(int i=1; i<200010; ++i){
        factorial[i] = i*factorial[i-1]%mod;
    }

    ll ans=0;
    
    for(ll k=0; k<=W-B-1; ++k){
        ll add_ans = factorial[H-A-1+B+k] 
                    * fact_inv(H-A-1) % mod 
                    * fact_inv(B+k) % mod
                    * factorial[A+W-B-2-k] % mod
                    * fact_inv(A-1) % mod
                    * fact_inv(W-B-1-k) % mod;
        ans += add_ans % mod;
    }
    //cout << factorial[H-A-1+B] << " " << fact_inv(H-A-1) << " " << fact_inv(B) << endl;
    //cout << factorial[A+W-B-2] << " " << fact_inv(A-1) << " " << fact_inv(W-B-1) << endl;
    cout << ans % mod <<endl;
    


    return 0;
}

ll fact_inv(ll a){
    ll x = factorial[a];
    ll powpow2[100];//a^(2^0), a^(2^1), a^(2^2), ....
    ll ret=1;

    //powpow2のテーブル埋め
    powpow2[0] = x;
    for(int i=1; i<100; ++i){
        powpow2[i] = powpow2[i-1] * powpow2[i-1] % mod;
    }

    for(int i=mod-2; i>0; i -= i&-i){
        ll pow_idx = log2(i&-i);
        ret = ret * powpow2[pow_idx] % mod;
    }

    return ret;
}



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

int main(){
	int n;
	cin>>n;
	int x=n%1000;
	if(x==0){
		printf("%d\n",x);
	}
	else{
	int y=1000-x;
	printf("%d\n",y);
}
}

Measured memory_bytes: 3748
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::vector<int64_t> A(N+1), B(N+1), C(N+1);
  for(int i = 0; i <= N; ++i) std::cin >> A[i];
  if(N == 0){
    if(A[0] != 1) fin(-1);
    fin(1);
  }
  B[N] = 0;
  for(int i = N-1; i >= 0; --i) B[i] = B[i+1]+A[i+1];
  B[0] = 1 - A[0];
  for(int i = 0; i < N; ++i) {
    // B[i+1] <= 2B[i] - A[i+1]
    B[i+1] = std::min(B[i+1], B[i]*2-A[i+1]);
    if(B[i+1] < 0) fin(-1);
  }
  int64_t ans = 0;
  for(int i = 0; i <= N; ++i) ans += A[i]+B[i];
  fin(ans);
  return 0;
}


Measured memory_bytes: 5964
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,cnt[70];
ll a[100100],p[70];

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

ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

void insert(ll x)
{
	per(i,60,0)
	{
		if ((x>>i)&1)
		{
			if (!p[i]) {p[i]=x;return;}
			else x^=p[i];
		}
	}
}

ll query()
{
	ll ans=0;
	per(i,60,0) if ((ans^p[i])>ans) ans^=p[i];
	return ans;
}

int main()
{
	n=read();
	rep(i,1,n) 
	{
		a[i]=readll();
		rep(j,0,60) if ((a[i]>>j)&1) cnt[j]++;
	}
	ll ans=0;
	rep(i,0,60)
		if (cnt[i]&1)
		{
			ans+=(1ll<<i);
			rep(j,1,n) 
				if ((a[j]>>i)&1) a[j]^=(1ll<<i);
		}
	rep(i,1,n) insert(a[i]);
	ans+=query()*2;
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n); std::vector<int> b(--n);
	for(int i = 0; i < n; i++) scanf("%d", &b[i]);

	int ans = 0;
	std::vector<int> a(1, b[0]);
	for(int i = 0; i < n - 1; i++) a.push_back(std::min(b[i], b[i + 1]));
	for(auto v: a) ans += v;
	printf("%d\n", ans + b.back());
	return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn._
import scala.annotation.tailrec
  
object Main {
  
  //f(x) => (-1,0,1)
  @tailrec
  def binarySearch(f: Int => Int,l: Int, r: Int): Int = {
    if(r-l<=1)f(l)
    else if(f((l+r)/2) < 1)binarySearch(f,(l+r)/2,r)
    else binarySearch(f,l,(l+r)/2)
  }
 
  def main(args: Array[String]): Unit = {
    val n = readInt
    val list = readLine.split(" ").map(_.toInt)
  
    val f = (ar: Seq[Int]) => (a: Int) => (x: Int) => ar(x)-a
  
    val q = readInt
    val qlist = readLine.split(" ").map(_.toInt)
    val res = for(e <- qlist)yield binarySearch(f(list)(e),0,n)
    println(res.count(_ == 0))
  }
}

Measured memory_bytes: 88496
<?php
fscanf(STDIN, "%s", $source);
$yesoreno = 0;

for ($i = 0; $i < strlen($source); $i++)
{
	if($i % 2 == 0)//キスウバンメ
	{
		if(substr($source, $i, 1) == "L")
		{
			$yesoreno = 1;
		}
	}
	else//グウスウバンメ
	{
		if(substr($source, $i, 1) == "R")
		{
			$yesoreno = 1;
		}
	}
}

if($yesoreno == 0)
{
	echo("Yes");
}
else
{
	echo("No");
}

Measured memory_bytes: 3700
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = sc.nextInt();
        Arrays.sort(arr);
        double res = 0;
        double tmp = (double)(arr[0] + arr[1])/2;
        for(int i = 2; i < N; i++) {
            if(arr.length == 2) break;
            tmp = (tmp + arr[i]) / 2;
        }
        System.out.println(tmp);
    }
}


Measured memory_bytes: 36056
//OM
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <sstream>
#include <algorithm>
using  namespace  std;

#define  x first
#define  y second
#define  pb push_back
#define  mp make_pair
#define  PI (acos(-1.0))
#define  mem(a,b) memset(a,b,sizeof(a))
#define  Sort(x) sort(x.begin(),x.end())
#define  FOR(i, b, e) for(int i = b; i <= (int)(e); i++)
#define  FORR(i, b, e) for(int i = b; i >=(int)(e); i--)
#define  FORI(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define  pr(x) cout<<x<<"\n"
#define  prs(x) cout<<x<<" "
#define  pr2(x,y) cout<<x<<" "<<y<<"\n"
#define  pr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n"
#define  ppr(a) cout<<a.x<<" "<<a.y<<"\n"

typedef  long long ll;
typedef  pair <int, int> pii;
typedef  pair <double , double> pdd;
typedef  vector <int> vi;
typedef  vector <pii> vpii;

//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};
//int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction

#define  EPS 1e-9
#define  MAX 100007
ll a[MAX];
ll b[MAX];
int main()
{
    int T,n;
    scanf("%d",&n);
    FOR(i,1,n)scanf("%lld",&a[i]);
    ll sum=0,ans=0;
    FOR(i,1,n){
        if(a[i]==0){
            ans+=sum/2;
            sum=0;
            continue;
        }
        sum+=a[i];
    }
    ans+=sum/2;
    pr(ans);
    return 0;
}



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

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    for (int i=0;i<n;i++){
        cin>>a.at(i);
        // cout<<a.at(i)<<endl;
    }
    sort(a.begin(),a.end());
  	reverse(a.begin(),a.end());
    // for (int i=0;i<n;i++){
    //     cout<<a.at(i)<<endl;
    // }
    int alice=0,bob=0;
    for (int i=0 ;i<n;i+=2){
        bob+=a.at(i);
        // cout<<bob<<endl;
    }
    for (int i=1; i<n;i+=2){
        alice+=a.at(i);
        // cout<<alice<<endl;
    }
    cout<<max(bob-alice,alice-bob)<<endl;
    
    return 0;
}


Measured memory_bytes: 3500
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;
 
// debugger
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define debug(stuff) cout << #stuff << ": " << stuff <<endl
#define debugc(stuff) cout << #stuff << ": "; for(auto x: stuff) cout << x << " "; cout << endl;
// 
 
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(), v.end() 
 
#define print(stuff) cout << stuff << endl
#define printc(stuff) for(auto x: stuff) cout << x << " "; cout << endl;
#define printPrec(stuff) cout << fixed << setprecision(15) << stuff << endl;
#define len length
#define ret0 return 0
#define ret return 
 
 
#define ll long long
#define ld long double
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fill(ar, x) memset(ar, x, sizeof ar)
 
#define vl vector<ll> 
#define sl set<ll>
#define pll pair<ll, ll>
#define mll map<ll, ll> 
#define pq priority_queue<ll>
 
// typedef tree<ll,null_type,less<ll>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;
 
#define inf (long long int) 1e18
#define eps 0.000001
#define mod 1000000007
#define mod1 998244353
#define MAXN (ll)2e5+5
#define N (1ll<<10)
#define pi 3.141592653589793238462643

void solve(){
    ll n;
    cin>>n;
    ll a[n];
    loop(i,0,n) cin>>a[i];
    ll ans = inf;
    for(ll i=-1000; i<=1000; i++){
        ll val = 0;
        for(ll j=0; j<n; j++){
            val += (a[j]-i)*(a[j]-i);
        }
        ans = min(ans, val);
    }
    print(ans);
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
 
    ll t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
        
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
    char ch = getchar();
    int x = 0, flag = 1;
    for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
    for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int Maxn = 1000009, Mod = 1e9 + 7;

struct matrix {
	int a[3][3];
	matrix(int flag = 0) {
		if (flag == 1) 
			rep (i, 0, 2)
				rep (j, 0, 2) a[i][j] = (i == j);
		if (flag == 0) 
			rep (i, 0, 2)
				rep (j, 0, 2) a[i][j] = 0;
	}
	matrix operator * (const matrix &b) const {
		matrix c(0);
			rep (i, 0, 2)
				rep (j, 0, 2)
					rep (k, 0, 2)
					(c.a[i][j] += 1ll * a[i][k] * b.a[k][j] % Mod) %= Mod;
		return c;
	}
};

matrix fpm(matrix base, int tims) {
	matrix r(1);
	while (tims) {
		if (tims & 1) r = r * base;
		base = base * base;
		tims >>= 1;
	}
	return r;
}

matrix Ans, f1, f2;
int n, m, a[Maxn];

void init() {
	n = read(), m = read();
	rep (i, 1, m) a[i] = read(); 
	a[++m] = n; a[++m] = 0;
	sort(a + 1, a + m + 1);
}

void solve() {
	Ans.a[0][0] = 1; Ans.a[0][1] = 0; Ans.a[0][2] = 0;
	Ans.a[1][0] = 0; Ans.a[1][1] = 1; Ans.a[1][2] = 0;
	Ans.a[2][0] = 0; Ans.a[2][1] = 0; Ans.a[2][2] = 1;
	f1.a[0][0] = 1; f1.a[0][1] = 0; f1.a[0][2] = 1;
	f1.a[1][0] = 2; f1.a[1][1] = 1; f1.a[1][2] = 2;
	f1.a[2][0] = 1; f1.a[2][1] = 1; f1.a[2][2] = 2;
	f2.a[0][0] = 1; f2.a[0][1] = 0; f2.a[0][2] = 0;
	f2.a[1][0] = 2; f2.a[1][1] = 1; f2.a[1][2] = 0;
	f2.a[2][0] = 1; f2.a[2][1] = 1; f2.a[2][2] = 1;
	int now = 0; // dp a[i] - now times
	rep (i, 1, m) {
		Ans = fpm(f1, a[i] - now) * Ans;
		if (i == m) break;
		Ans = f2 * Ans; now = a[i] + 1;
	}
	printf("%d\n", Ans.a[2][0]);
}

int main() {
	//freopen("E.in", "r", stdin);
	//freopen("E.out", "w", stdout);

	init();
	solve();

#ifdef Qrsikno
    debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}



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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);

int main(int argc, char* argv[]) {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> h(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &h[i]);
  }

  ll ans = 0;
  while (accumulate(all(h), 0) != 0) {
    int l = -1, r = -1;
    rep(i, 0, N) {
      if (l < 0 && h[i] > 0) {
        l = i;
        continue;
      }

      if (l >= 0 && h[i] == 0) {
        r = i;
        break;
      }
    }

    if (r == -1) r = N;
    for (; l < r; l++) h[l]--;
    ans++;
  }

  put(ans);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

template <class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) { return (a * b) / gcd(a, b); }

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rgi register int
#define ll long long
namespace IO {
#define _CCF_ 8388608
// #define getchar() (_Ip1==_Ip2&&(_Ip2=(_Ip1=_I)+fread(_I,1,1<<21,stdin),_Ip1==_Ip2)?EOF:*_Ip1++)
// #define putchar(c) (_Op-_O<_CCF_)?(*_Op++=c):(fwrite(_O,_Op-_O,1,stdout),_Op=_O,*_Op++=c)
	char _I[_CCF_],*_Ip1=_I,*_Ip2=_I,_O[_CCF_],*_Op=_O;
	int _f,_ch,_On[32],_Oh; long long _k;
	template<typename _T> inline void read(_T&_x){
		_x=_f=_ch=0; while(!isdigit(_ch)) _f|=(_ch=='-'),_ch=getchar();
		while(isdigit(_ch)) _x=(_x<<1)+(_x<<3)+(_ch^'0'),_ch=getchar();
		_f&&(_x=-_x);}
	template<typename _T> inline void write(_T _x){
		if(_x==0) return putchar('0'),void(); if(_x<0) putchar('-'),_x=-_x;
		while(_x>0) _k=_x/10,_On[++_Oh]=(_x-(_k<<1)-(_k<<3))^'0',_x=_k;
		while(_Oh>0) putchar(_On[_Oh]),--_Oh;}
	inline void _Exit0() {fwrite(_O,_Op-_O,1,stdout),exit(0);}
} using namespace IO;
const int maxn=500004,mod=998244353;

int inv[maxn];
inline int powmod(ll a,int b) {
	ll res=1;
	while(b>0) {
		if(b&1) (res*=a)%=mod;
		(a*=a)%=mod,b>>=1;
	} return res;
}
inline int calc(int n,int m) {
	ll res=0,fact=1,bn=1,bm=1,pn=powmod(n+1,m),pm=powmod(m+1,n);
	for(rgi i=0;i<=n;++i) {
		(res+=((i&1)?(mod-1ll):1ll)*fact%mod*bn%mod*bm%mod*pn%mod*pm)%=mod;
		(bn*=(ll)(n-i)*inv[i+1]%mod)%=mod,(bm*=(ll)(m-i)*inv[i+1]%mod)%=mod;
		(pn*=inv[n+1])%=mod,(pm*=inv[m+1])%=mod;
		(fact*=i+1)%=mod;
	} return res;
}
signed main() {
	// rgi T,n,m,a,b; read(T);
	// inv[1]=1; for(rgi i=2;i<maxn;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	// while(T--) {
	// 	read(n),read(m),read(a),read(b);
	// 	if(a!=0&&(a==b||a==-b)) write(calc(n,m));
	// 	else write((a?powmod(m+1,n):1)*(b?powmod(n+1,m):1)%mod);
	// 	putchar('\n');
	// } _Exit0();
	int n,m; read(n),read(m);
	inv[1]=1; for(rgi i=2;i<maxn;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	write(calc(std::min(n,m),std::max(n,m))),_Exit0();
}

Measured memory_bytes: 5484
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll n,m,ans=0,a,b,c;
  cin >> n >> m;
  priority_queue<P> q;
  for(int i=0; i<n; i++) {
    cin >> a;
    q.push({a,1});
  }
  for(int i=0; i<m; i++) {
    cin >> b >> c;
    q.push({c,b});
  }
  for(int i=0; i<n; i++) {
    P p=q.top();
    q.pop();
    ans+=p.first,p.second--;
    if(p.second>0) {
      q.push(p);
      p.second--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 2420
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
constexpr ll MOD = 1000000007LL;

int main(void) {
    int N, M;
    vector<int> L(100010), R(100010);
    cin >> N >> M;
    for (int i=0;i<M;i++) cin >> L[i] >> R[i];

    int left = 1, right = N;
    for (int i=0;i<M;i++) {
        left = max(left, L[i]);
        right = min(right, R[i]);
    }
    cout << max(0,right - left + 1) << endl;

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x)
{
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
ll n,k,val[4],tot[4],cnt;
map<ll,bool> mp;
bool fla;
bool check(){
	if(n%3!=0) return (cnt==1) && (val[1]==0);
	if(cnt==1) return (val[1]==0);
	if(cnt==2){
		if(val[1]==0) return (tot[1]==n/3);
		else if(val[2]==0) return (tot[2]==n/3);
		else return false;
	}
	if(cnt==3) return (tot[1]==tot[2]) && (tot[1]==tot[3]) && ((val[1]^val[2])==val[3]);
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(ri i=1;i<=n;++i){
		read(k);
		if(!mp[k]){
			if(cnt==3) fla=1;
			else val[++cnt]=k,mp[k]=1,tot[cnt]=1;
		}
		else{for(ri j=1;j<=cnt;++j) if(val[j]==k) tot[j]++;}
	}
	if(!fla&&check()) printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 5120
#include<fstream>
#include<string>
#include<iostream>
#include<sstream>
#include<iterator>
#include<cmath>
#include<stdio.h>

using namespace std;

int main(){
 int n = 0;
 char s[3];
 char t[3];
 scanf("%s", s);
 scanf("%s", t);
 int i;
 for(i=0;i<3;i++){
  if(s[i]==t[i])n++;
  }
  cout << n << endl;
  return 0;
}
  

Measured memory_bytes: 256
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

int main(void){
    int N, K; cin >> N >> K;
    vector<int> p(N);
    for (auto& pi : p)
        cin >> pi;
    sort(p.begin(), p.end());
    int res = 0;
    for (int i = 0; i < K; ++i)
        res += p[i];
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
int main(void)
{
    int n, k;
    if (scanf("%d %d", &n, &k) == EOF) {
        printf("Failed to read integer.\n");
        return -1;
    }

    int member[n];
    int count = 0;
    for(int i = 0; i < n; i++){
        if (scanf("%d", &member[i]) != EOF) {
            count += (member[i] >= k) ? 1 : 0;
        } else {
            printf("Failed to read integer.\n");
            return -1;
        }
    }
    printf("%d\n", count);
    return 0;
}

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

void Solve(){
  UL S[100000] = {};
  UL n, q; cin >> n >> q;
  string s; cin >> s;
  for(UL i = 1; i < n; i++){
    if(s[i-1] == 'A' && s[i] == 'C') S[i] = 1;
    S[i] += S[i-1];
  }
  rep(i, q){
    UL a,b; cin >> a >> b;
    cout << S[b-1] - S[a-1] << endl;
  }
}
int main(){
  Solve(); return 0;
}

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

const ll mod = 1e9 + 7;
#define MAX 3000000

ll mpow(ll x, ll n) {
    ll res = 1;
    while (n != 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n = n >> 1;
    }
    return res;
}
ll fac(ll i) {
    static ll fatorial[MAX + 1] = {0};

    if (fatorial[i])
        return fatorial[i];
    else if (i == 0)
        return fatorial[0] = 1;
    else
        return fatorial[i] = fac(i - 1) * i % mod;
}
ll ifac(ll i) {
    static ll ifactorial[MAX + 1] = {0};

    if (ifactorial[i])
        return ifactorial[i];
    else if (i == 0)
        return ifactorial[0] = 1;
    else
        return ifactorial[i] = ifac(i - 1) * mpow(i, mod - 2) % mod;
}
ll comb(ll a, ll b) {
    if (a == 0 && b == 0) return 1;
    if (a < b || a < 0) return 0;
    ll tmp = ifac(a - b) * ifac(b) % mod;
    return tmp * fac(a) % mod;
}

int main() {
    ll x, y;
    cin >> x >> y;
    ll a = x / 2;
    for (int i = 0; i <= a; i++) {
        if (i + 2 * (x - 2 * i) == y) {
            cout << comb(x - i, i) << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 20864
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int main(void){
    int a;
    cin >> a;
    if(a%2 == 0){
        cout << a/2 <<endl;
    }else{
        cout<< a/2 + 1 << endl;
    }
    return 0;
    
}


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

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

Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        mut xy: [(i64, i64); n],
    }
    xy.sort();
    let mut a = vec![];
    let mut b = vec![];
    for &(x, y) in xy.iter() {
        a.push(x + y);
        b.push(x - y);
    }
    let a = a.iter().max().unwrap() - a.iter().min().unwrap();
    let b = b.iter().max().unwrap() - b.iter().min().unwrap();
    println!("{}", std::cmp::max(a, b));
}


Measured memory_bytes: 15040
#include<bits/stdc++.h>
 using namespace std;
 int main() 
{ string s; 
int a,b,c,i,n,j,t;
 double g,h,o; 
map<int,int> ma; map<int,int> :: iterator it; 
vector<int> v; h=0; 
cin>>a; b=a; if(a%2==0){ a = a/2; g= a*1.0/b*1.0; cout<<setprecision(9)<<fixed<<g<<endl; } else{ a = a/2; a++; g= a*1.0/b*1.0; cout<<setprecision(9)<<fixed<<g<<endl; } }

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

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if ((a+b)>(c+d)){
    cout << "Left" << endl;
  }
  else if((a+b)<(c+d)){
    cout << "Right" << endl;
  }
  else{
    cout << "Balanced" << endl;
  }
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
inline int read()
{
	char x = getchar();
	int lin = 0, f = 1;
	while(x < '0' || x > '9')
	{
		if(x == '-') f = -1;
		x = getchar();
	}
    while(x >= '0' && x <= '9')
	{
		lin = lin * 10 + x - '0';
		x = getchar();
	}
	return lin * f;
}
#define PII pair<int,int>
#define fir first
#define sec second
#define ma(a,b) make_pair(a,b)
int n,s[maxn],q[maxn],ans;
int main(){
	n = read();
	for(int i = 1; i <= n; i++)
	{
		s[i] = read();
		q[i] = s[i];
	}
	sort(q + 1,q + 1 + n);
	for(int i = 1; i <= n; i++)
	{
		int ne = lower_bound(q + 1,q + 1 + n,s[i]) - q;
		if(abs(i - ne) & 1) ++ans;
	}
	if(ans & 1) ++ans;
	cout << ans / 2;
}

Measured memory_bytes: 1024
using System;

class mainClass
{
    //入力
    static int a = int.Parse(Console.ReadLine());
    static int b = int.Parse(Console.ReadLine());
    static int c = int.Parse(Console.ReadLine());
    static int x = int.Parse(Console.ReadLine());
    static int cnt = 0;
    //出力

    static void Main()
    {
        for( var i=0; i<= a; i++)
        {
            for(var j=0; j<=b; j++)
            {
                for(var k=0; k<=c; k++)
                {
                    if ((i*500+j*100+k*50) == x )
                    { cnt++; }
                }
            }
        }
        Console.WriteLine(cnt);
    }
}



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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    long long sum = 0;
    for (int i = 1; i < n; ++i) {
        if (a[i - 1] <= a[i]) continue;

        sum += a[i - 1] - a[i];
        a[i] = a[i - 1];
    }
    cout << sum << endl;
}


Measured memory_bytes: 4048
#include <stdio.h>

int main(void)
{
  int cell[1000],dice[1000],N,M,piece,i,j,k,ans;

  for(;;){
    scanf("%d %d", &N, &M);
    if(N==0&&M==0) break;

    piece=0;
    for(i=0;i<N;i++){
      scanf("%d", &cell[i]);
    }
    for(j=0;j<M;j++){
      scanf("%d", &dice[j]);
    }
    for(k=0;k<M;k++){
      piece=piece+dice[k];
      if(cell[piece]>=0){
	piece=piece+cell[piece];
      } else if(cell[piece]<0){
	piece=piece-abs(cell[piece]);
      }

      if(piece>=N-1){
	ans=k+1;
	break;
      }
    }

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

  return 0;
}


Measured memory_bytes: 608
import java.util.Scanner;

public class  Main{
	public static void main(String[] args)
	{
		Scanner sc =new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		int total=a*100+b*10+c;
		
		if(total%4==0) System.out.println("YES");
		else System.out.println("NO");
	}
} 

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <functional>
#include <stdio.h>
#include <math.h>
#include <string>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>

#define rep(i, m, n) for (int (i)(m); (i)<(n); ++(i))
#define repr(i, m, n) for (int (i)(m - 1); (i)>=(n); --(i))
#define repv(i, v) for (unsigned (i)(0); (i)<(v.size()); ++(i))
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define sortgi(v) sort(all(v), greater<int>())
#define sortgd(v) sort(all(v), greater<double>())
#define sortgll(v) sort(all(v), greater<ll>())
#define debug(x) cerr << #x << ": " << x << '\n'

using namespace std;
using pii = pair<int, int>;
using pss = pair<string, string>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using ll = long long;
using pllll = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using pqi = priority_queue<int>;
using pqd = priority_queue<double>;
using pqll = priority_queue<ll>;
using pqvi = priority_queue<vi>;
using pqvll = priority_queue<vll>;

int main() {
	string s;
	cin >> s;
	bool b = false;
	bool b1 = false;
	int l;
	if (s[0] == 'A') {
		rep(i, 2, s.size() - 1) {
			if (s[i] == 'C') {
				if (b1) {
					b1 = false;
					break;
				}
				l = i;
				b1 = true;
			}
		}
		if (b1) {
			b = true;
			rep(i, 1, s.size()) {
				if (i != l && s[i] < 97) {
					b = false;
					break;
				}
			}
		}
	}
	if (b) {
		cout << "AC" << endl;
	}
	else {
		cout << "WA" << endl;
	}
}


Measured memory_bytes: 256
a=[]
b=[]
x=[]

for i in range(1,31):
    a.append(i)
#print("@",a)

for n in range(28):
    b.append(int(input()))
    
#print("@",b)

x=list(set(a)-set(b))
#print("@",x)

print(min(x))
print(max(x))


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

using namespace std;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {
    if (v.empty()) {
        ostr << "{ }";
        return ostr;
    }
    ostr << "{" << v.front();
    for (auto itr = ++v.begin(); itr != v.end(); itr++) {
        ostr << ", " << *itr;
    }
    ostr << "}";
    return ostr;
}

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

  long long N;
  N = S.size();

  long long ans = 0;
  for (int i = 0; i < N - 1; ++i){
    if (S.at(i) != S.at(i + 1)) {;}
    else if (S.at(i) == '0'){
      S.at(i + 1) = '1';
//  cout << S << endl;
      ans++;
    }
    else if (S.at(i) == '1'){
      S.at(i + 1) = '0';
//  cout << S << endl;
      ans++;
    }
  }

  cout << ans << endl;




  return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int main()
{
    string s;
    bool b=0;
    cin>>s;
    if(s.length()==6 && s[2]==s[3] && s[4]==s[5]){
    	for(int i=0;i<6;i++){
    		if(s[i]<97){
    			cout<<"No";
    			b=1;
    			break;
			}
		}
		if(b==0){
			cout<<"Yes";
		}
	}
	else{
		cout<<"No";
	}
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    
//system("pause");
return 0;

}


Measured memory_bytes: 256
const input = require("fs").readFileSync("/dev/stdin", "utf8")
const lines = input.split('\n')
const [N, M] = lines[0].split(' ').map(Number)
const H = lines[1].split(' ').map(Number)

const map = Array(N + 1).fill(null).map(_ => [])

for (let i = 0; i < M; i++) {
    const [a, b] = lines[i + 2].split(' ').map(Number)
    map[a].push(H[b - 1])
    map[b].push(H[a - 1])
}

let count = 0
for (let i = 1; i <= N; i++) {
    if (H[i - 1] > Math.max(...map[i])) {
        count++
    }
}

console.log(count)

Measured memory_bytes: 95028
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys
from itertools import combinations_with_replacement


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n,m,q = _ia()
    a = []
    for _ in range(q):
        ai, bi, ci, di = _ia()
        a.append((ai-1, bi-1, ci, di))

    mx = 0
    for d in combinations_with_replacement([i for i in range(1,m+1)], n):
        tmp = 0
        for ai, bi, ci, di in a:
            if d[bi] - d[ai] == ci:
                tmp += di
        if tmp >= mx:
             mx = tmp
    return mx


if __name__ == "__main__":
    print(main())


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

int main() {
    int n, m, l;
    cin >> n >> m >> l;
    int i, j, k;
    long int arr1[n][m], arr2[m][l], arr3[n][l] = {};

    for(i=0; i<n; ++i) {
        for(j=0; j<m; ++j) {
            cin >> arr1[i][j];
        }
    }

    for(i=0; i<m; ++i) {
        for(j=0; j<l; ++j) {
            cin >> arr2[i][j];
        }
    }

    for(i=0; i<n; ++i) {
        for(j=0; j<l; ++j) {
            for(k=0; k<m; ++k) {
                arr3[i][j] += arr1[i][k] * arr2[k][j];
            }
        }
    }

    for(i=0; i<n; ++i) {
        cout << arr3[i][0];
        for(j=1; j<l; ++j) {
            cout << ' ' << arr3[i][j];
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3320
#include <iostream>
using namespace std;
const int Max = 110000;
int main(){
	int h, n;
	int data[Max];
	cin >> h >> n;
	auto ans = 0;
	for(int i = 0; i < n; i++){
		cin >> data[i];
		ans = ans + data[i];
	}
	if(ans >= h){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int main(){
   int N,a[10],i,temp=0,sum=0,cost;
   scanf("%d",&N);
   for(i=0;i<N;i++){
    scanf("%d",&a[i]);
    if(a[i]>temp){
    temp=a[i];}
    sum+=a[i];}
   cost=sum-temp+(temp/2);
   printf("%d\n",cost);
   return 0;}


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

int main(){
	string s;
	cin>>s;
	string t;
	cin>>t;
	bool y=1;
	for(int i=0;i<s.length();i++){
		if(s[i]!=t[i]){
			y=0;
			break;
		}
	}
	if(y)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 3592
n, k = list(map(int, input().split()))
d = []
sweets_matrix = []

for i in range(k):
    d.append(int(input()))
    sweets_matrix.append(list(map(int, input().split())))

sunuke = [0] * n

for i in range(k):
    for j in range(d[i]):
        sunuke[sweets_matrix[i][j]-1] += 1

print(len([i for i in sunuke if i == 0]))

Measured memory_bytes: 9200
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

H,W,K=rl()
DIV =  1000000007

rc = K-1
dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0]=1
bar = [1, 1+0, 1+1, 2+1, 3+2, 5+3, 8+5, 13+8, 21+13]

for h in range(1,H+1):
    for w in range(W):
        if w != 0:
            dp[h][w] += dp[h-1][w-1]*bar[w-1]*bar[W-w-1]
        dp[h][w] += dp[h-1][w]*bar[w]*bar[W-w-1]
        if w != W-1:
            dp[h][w] += dp[h-1][w+1]*bar[w]*bar[W-w-2]

print(dp[H][K-1]%DIV)

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

#define vec              vector<int>
#define vecll            vector<ll>
#define vecd             vector<double>
#define vecst            vector<string>
#define vecb             vector<bool>
#define v2(v,n,m,init)   vector<vector<int>>  v(n, vector<int>(m, init))
#define vb2(v,n,m,init)  vector<vector<bool>> v(n, vector<bool>(m, init))
#define vll2(v,n,m,init) vector<vector<ll>>   v(n, vector<ll>(m, init))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
template <typename T>
bool chmax(T &a, const T& b){if(a<b){a=b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a>b){a=b; return true;} return false;}
//------------------------------------------------------------------

int main(void){
  ll n, x, m;
  cin >> n >> x >> m;

  vecll tasu(m);
  rep(i,m){
    tasu[i] = (i*i)%m;
  }
  map<int, int> mp;
  vector<int> v;
  ll nxt=x;
  int ct=0;
  while(1){
    if(mp[nxt]>0) break;
    //prt(nxt);
    v.push_back(nxt);
    ct++;
    mp[nxt]++;
    nxt = (nxt*nxt)%m;
  }

  ll ans=0;
  ll circle=0;
  int chk;
  bool found=false;
  rep(i,v.size()){
    if(n<=0) break;
    if(!found && nxt!=v[i]){
      ans += v[i];
      n--;
    } else if(!found && nxt==v[i]){
      circle += v[i];
      found=true;
      chk=i;
    } else if(found){
      if(nxt==v[i]) break;
      circle += v[i];
    }
  }

  ans += circle * (n/(ct-chk));
  rep(i,n%(ct-chk)){
    ans += v[chk+i];
  }

  prt(ans);


}


Measured memory_bytes: 6640
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <math.h>
#include <map>
#include <stack>
using namespace std;
static const int INF = 1e9+7;
// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i =a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define PI 3.14159265359

int main(){
    int n; cin >> n;
    int d, x; cin >> d >> x;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    int result = 0;
    // 1, a+1, 2a+1, 
    rep(i,n){
        rep(j, d+1){
            if(1+j*a[i] <= d){
                result++;
            }else{
                break;
            }
        }
    }

    cout << result + x << endl;

    return 0;
}


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

const int INF = 1e9;
const int MAX = 101;

int d, n;
int a[MAX], e[MAX], r[MAX];


int bfs(){
	int dis[MAX][MAX];
	for (int i = 0; i < MAX; i++) {
		fill(dis[i], dis[i] + MAX, INF);
	}
	dis[d][0] = 0;

	queue<pair<int, int>> q;
	q.emplace(d,0);
	while(not q.empty()){
		int hp, exp;
		tie(hp, exp) = q.front(); q.pop();

		for (int i = 0; i < n; i++) {
			if(r[i] > exp) continue;
			
			int nhp = max(0, hp - a[i]);
			int nexp = min(100, exp + e[i]);
			if(dis[nhp][nexp] > dis[hp][exp] + 1){
				dis[nhp][nexp] = dis[hp][exp] + 1;
				q.emplace(nhp, nexp);
			}
		}
	}

	int res = INF;
	for (int i = 0; i <= 100; i++) {
		res = min(res, dis[0][i]);
	}
	return res;
}

int main(){
	while(cin >> d >> n, d||n){
		for (int i = 0; i < n; i++) {
			cin >> a[i] >> e[i] >> r[i];
		}

		int ans = bfs();
		if(ans == INF) cout << "NA" << endl;
		else cout << ans << endl;
	}
}



Measured memory_bytes: 3212
#include <iostream>

using namespace std;

int main(void) {
	int H,W;


	while (true)
	{
		cin >> H >> W;
		if (H == 0 && W == 0)
		{
			break;
		}

		for (int i = 0; i < H; i++)
		{			
			for (int j = 0; j < W; j++)
			{
				if (i == 0 || i == H - 1)
				{
					cout << "#";
				}
				else
				{
					if (j == 0 || j == W - 1)
					{
						cout << "#";
					}
					else
					{
						cout << ".";
					}
				}
			}
			cout << endl;
		}
		cout << endl;
	}



	return 0;
}


Measured memory_bytes: 3080
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

struct bit {
    vector<int> v; // 部分和をbitで管理 仮想配列はa[1...n]
    bit(int n){ // bit(int n) : v(n + 1) {}
        v.resize(n + 1);
    }
    
    int sum(int i){ // 仮想配列a[1]~a[i]の和を求める
        int ret = 0;
        for(; i > 0; i -= i & -i){ // i & -i: iの1が立っている最高位bitをの2^を返す
            ret += v[i];
        }
        return ret;
    }
    
    void add(int i, ll w) { // index:iにwを加える
        for (; i < v.size(); i += i & -i) {
            v[i] += w;
        }
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    
    int N, Q;
    cin >> N >> Q;
    vector<int> C(N);
    rep(i, N) {
        cin >> C[i];
        C[i]--;
    }
    vector<pair<pair<int, int>, int>> query(Q); // r, l, ind
    
    vector<int> last(N, -1);
    rep(i, Q) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        query[i] = mp(mp(r, l), i);
    }
    
    sort(all(query));
    int curq = 0;
    
    bit B(N);
    vector<int> ans(Q);
    rep(i, N) {
        if(last[C[i]] != -1) {
            B.add(last[C[i]] + 1, -1);
        }
        last[C[i]] = i;
        B.add(i + 1, 1);
        while(curq < Q) {
            if (query[curq].first.first <= i && curq < Q) {
//                cout << "==" << curq << "," << query[curq].second << endl;
                ans[query[curq].second] = B.sum(query[curq].first.first + 1) - B.sum(query[curq].first.second);
                curq++;
            }
            else break;
        }
        
    }
    rep(i, Q) output(ans[i]);
    
    
    return 0;
}


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

int main () {
    int n;
    cin >> n;
    double X[100], Y[100];
    for (int i=0; i<n; i++) cin >> X[i];
    for (int i=0; i<n; i++) cin >> Y[i];

    double manhattan = 0;
    for (int i=0; i<n; i++) manhattan += fabs(X[i] - Y[i]);
    printf("%lf\n", manhattan);

    double s = 0;
    for (int i=0; i<n; i++) s += pow(X[i] - Y[i], 2);
    double euclid = sqrt(s);
    printf("%lf\n", euclid);

    double c = 0;
    for (int i=0; i<n; i++) c += pow(fabs(X[i] - Y[i]), 3);
    double cublic = cbrt(c);
    printf("%lf\n", cublic);

    double max = -1;
    for (int i=0; i<n; i++) {
        double tmp = fabs(X[i] - Y[i]);
        if (max < tmp) max = tmp;
    }
    printf("%lf\n", max);
}

Measured memory_bytes: 1264
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {

  int A, B, C; std::cin >> A >> B >> C;
  std::cout << std::max(0, C-(A-B)) << std::endl; 

  return 0;
}


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

// Define
using ll = int64_t;
using ul = uint64_t;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ul MAX = ULONG_MAX;
const char nl = '\n';

#define elif else if
#define def inline auto
#define run __attribute__((constructor)) def _

// Debug
#define debug(x) cerr << (x) << " (L:" << __LINE__ << ")" << '\n'

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i < _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i > _##i; --i)
#define rep(i, n) inc(i, 0, n)
#define be(c) begin(c), end(c)

// Stream
#define fout(n) cout << fixed << setprecision(n)
#define fasten cin.tie(0), ios::sync_with_stdio(0)

// Speed
run() { fasten, fout(10); }
#pragma GCC optimize("-O3")
#pragma GCC target("avx")

signed main() {
    int n;
    cin >> n;
    double ans = 0;
    rep (i, n) {
        double x;
        string s;
        cin >> x >> s;
        if (s == "BTC")
            ans += 380000.0 * x;
        else
            ans += x;
    }
    cout << ans << endl;
}


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

using namespace std;
typedef long long ll;

#define INF (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

vector<ll> a;

int main(void)
{
  ll n, k;
  cin >> n >> k;
  REP(i, n) {
    ll a1;
    cin >> a1;
    a.push_back(a1);
  }
  ll m = k - 1;
  ll p = (n - 1 + m - 1) / m;
  cout << p << endl;
}


Measured memory_bytes: 1400
import sys
input = sys.stdin.readline

INF = 10 ** 18

N, W = map(int, input().split())
lst = [INF] * (10 **5 + 10)
lst[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(10 ** 5 + 9, v - 1, -1):
        lst[i] = min(lst[i], lst[i - v] + w)
    for i in range(v - 1, -1, -1):
        lst[i] = min(lst[i], lst[i + 1])

for i in range(10 ** 5 + 9, -1, -1):
    if lst[i] <= W:
        print (i)
        exit()


Measured memory_bytes: 42284
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <cmath>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
const ll MOD = 998244353;

int main() {
    ll N;
    cin >> N;
    vector<vector<ll>> H(N, vector<ll>(3,0));

    for (ll i = 0; i < N; ++i) {
        cin >> H[i][0] >> H[i][1] >> H[i][2];
    }
    vector<vector<ll>> dp(N, vector<ll>(3, 0));
    dp[0][0] = H[0][0];
    dp[0][1] = H[0][1];
    dp[0][2] = H[0][2];
    for (ll i = 1; i < N; ++i) {
        for (ll j = 0; j < 3; ++j) {
            dp[i][j] = H[i][j] + max(j==0?0:dp[i-1][0], max(j==1?0:dp[i-1][1], j==2?0:dp[i-1][2]));
        }
    }
    cout << max(dp[N-1][0], max(dp[N-1][1], dp[N-1][2])) << endl;
}


Measured memory_bytes: 11136