akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N; cin >> N;
   vector<int> H(N);
   for (int i = 0; i < N; ++i) cin >> H[i];
   sort(H.begin(), H.end(), greater<int>());
   int cur = 0;
   while (cur+1 < N && H[cur+1] > cur+1) cur++;
   int up = H[cur] - cur - 1;
   int right = 0;
   while (cur + right + 1 < N && H[cur+right+1] == cur+1) right++;
   if ((up & 1) || (right & 1)) cout << "First\n";
   else cout << "Second\n";
   return 0;
}


Measured memory_bytes: 3736
#include <algorithm>
#include <iostream>

using namespace std;

long long solve(long long n,
        long long ga, long long sa, long long ba,
        long long gb, long long sb, long long bb) {
    long long res = n;
    for (int i = 0; gb > ga ? i * ga <= n : i <= 0; i++) {
        for (int j = 0; sb > sa ? i * ga + j * sa <= n : j <= 0; j++) {
            res = max(res, n + i * (gb - ga) + j * (sb - sa));
            res = max(res, n + i * (gb - ga) + j * (sb - sa) + ((n - i * ga - j * sa) / ba) * (bb - ba));
        }
    }
    return res;
}

int main() {
    long long n, ga, sa, ba, gb, sb, bb;
    cin >> n >> ga >> sa >> ba >> gb >> sb >> bb;

    if ((ga < gb && sa < sb) || (ga > gb && sa > sb)) {
        swap(ga, ba);
        swap(gb, bb);
    }

    cout << solve(solve(n, ga, sa, ba, gb, sb, bb), gb, sb, bb, ga, sa, ba) << endl;
}


Measured memory_bytes: 256
/*-----lusar98-----*/
#include<bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define mod 1000000007
#define eps 1e-9
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
using namespace std;
int main()
{
    //fast();
    ll n;
    cin>>n;
    ll arr[n];
    for(ll i=0;i<n;i++)
    	cin>>arr[i];
    ll dp[n+2];
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(ll i=2;i<n;i++)
    {
    	dp[i] = min(dp[i-1] + abs(arr[i]-arr[i-1]), dp[i-2] + abs(arr[i]- arr[i-2]));
    }
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1792
N = int(input())

A = list(map(int,input().split()))
import heapq
L = A[:N]
heapq.heapify(L)
sum_L = sum(A[:N])
L_list = []
L_list.append(sum_L)
for i in range(N):
    sum_L += A[N+i]
    heapq.heappush(L,A[N+i])
    sum_L -= heapq.heappop(L)
    L_list.append(sum_L)

A = list(map(lambda x:-x, A[::-1]))
R = A[:N]
heapq.heapify(R)
sum_R = sum(A[:N])
R_list = []
R_list.append(sum_R)


for i in range(N):
    sum_R += A[N+i]
    heapq.heappush(R,A[N+i])
    sum_R -= heapq.heappop(R)
    R_list.append(sum_R)
maxi = -10000000000000000000000000000
R_list = R_list[::-1]
for i in range(N+1):
    maxi = max(maxi,L_list[i] + R_list[i])

print(maxi)


Measured memory_bytes: 132596
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/

void build(){

}
#define N 101010
LL n , a[ N ];
void init(){
  n = getint();
  for( int i = 0 ; i < n ; i ++ )
    a[ i ] = getint();
}
LL cal( LL sgn ){
  LL pre = 0 , ans = 0;
  for( int i = 0 ; i < n ; i ++ ){
    pre += a[ i ];
    if( sgn == +1 and pre <= 0 ){
      ans += 1 - pre;
      pre = 1;
    }
    if( sgn == -1 and pre >= 0 ){
      ans += pre + 1;
      pre = -1;
    }
    sgn = -sgn;
  }
  return ans;
}
void solve(){
  printf( "%lld\n" , min( cal( 1 ) , cal( -1 ) ) );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long int
#define FASTIO std::ios::sync_with_stdio(false);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define inf 1e18
#define g(x) cout<<x<<" "<<endl;
#define gg(x,y) cout<<x<<" & "<<y<<" "<<endl
#define jam(t) cout<<"Case #"<<t<<": "
#define ggg(x,y,z) cout<<x<<" & "<<y<<" & "<<z<<" "<<endl
#define all(x) x.begin(),x.end()
#define input_from_file  freopen("input.txt", "r", stdin);
#define mod 98764321234ll
#define sz 400005
#define bitcnt(x) __builtin_popcountll(x)
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
using namespace std;
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...);
}

ll C(ll a, ll b){
    return (a*(a-1))/2;
}

ll a[sz];
ll cnt[sz];
void solve(){
    ll n;
    cin >> n;
    for(ll i=1;i<=n;i++){
        cin >> a[i];
        cnt[a[i]]++;
    }
    ll re = 0;
    for(ll i=1;i<=n;i++){
        ll tot = cnt[i];

        re += C(tot,2);
    }
   // trace(C.fac[5]);
    for(ll i=1;i<=n;i++){
        ll an = re;
        an -= C(cnt[a[i]],2);
        an += C(cnt[a[i]]-1,2);

        g(an);
    }
}
int main()
{

 
    FASTIO
    cin.tie(NULL);
    fflush(stdout);
    ll t = 1;
   // cin >> t;
    for(ll tcase = 1;tcase <= t;tcase++){
        solve();
        
    }
return 0;
}

Measured memory_bytes: 7424
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
 
int main(){
  ll N,M;
  cin >> N >> M;
  vector<ll> A(N);
  for(ll i=0;i<N;i++) cin >> A[i];

  sort(A.begin(),A.end(),greater<ll>());

  ll l=0,r=200010;
  ll m=0,n=0;
  ll v;
  ll tot=0;

  while(l+1<r){
    tot=0;
    n=N-1;
    v=(l+r)/2;
    for(ll i=0;i<N;i++){
      while(A[n]+A[i]<v && 0<=n) n--;
      tot+=n+1;
    }
    if(tot<M) r=v; else l=v;
  }
  
  vector<ll> s(N,0);
  tot=0;
  for(ll i=0;i<N;i++){
    tot+=A[i]; s[i]=tot;
  }

  tot=0;
  ll ans=0;
  n=N-1;
  for(ll i=0;i<N;i++){
    while(A[n]+A[i]<r && 0<=n) n--;
    if(n>=0) ans+=s[n]+A[i]*(n+1);
    tot+=n+1;
  }
  ans+=l*(M-tot);

  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll H, W; cin >> H >> W;
    vector<string> board(H);
    vvll horiz(H, vll(W));
    vvll vert(H, vll(W));
    rep(i, H) cin >> board[i];

    rep(i, H) {
        ll stopper = -1;
        board[i].push_back('#');
        rep(j, W + 1) {
            if (board[i][j] == '#') {
                ll sum = (j - 1) - stopper;
                if (sum > 0) {
                    for (ll k = stopper + 1; k < j; k++) {
                        horiz[i][k] = sum;
                    }
                }
                stopper = j;
            }
        }
        board[i].erase(board[i].begin() + board[i].size() - 1);
    }
    // for (auto elem1 : horiz) {
    //     for (auto elem : elem1) cout << elem << " "; cout << endl;
    // }

    board.push_back(string(W, '#'));
    rep(j, W) {
        ll stopper = -1;
        rep(i, H + 1) {
            if (board[i][j] == '#') {
                ll sum = (i - 1) - stopper;
                if (sum > 0) {
                    for (ll k = stopper + 1; k < i; k++) {
                        vert[k][j] = sum;
                    }
                }
                stopper = i;
            }
        }
    }
    // for (auto elem1 : vert) {
    //     for (auto elem : elem1) cout << elem << " "; cout << endl;
    // }

    ll max_num = 0;
    rep(i, H) rep(j, W) max_num = max(max_num, horiz[i][j] + vert[i][j] - 1);
    cout << max_num << endl;
    return 0;
}

Measured memory_bytes: 67072
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>
#define N 200020
using namespace std;

int a[N];
map<int, int> f;

int main(void)
{
    int n, k;
    int i, j;
    long long o;

    scanf("%d %d", &n, &k);
    f[0] = 1;
    for(i = 1, j = o = 0; i <= n; i ++)
    {
        for(; i - j >= k; j ++)
            f[((a[j] - j) % k + k) % k] --;
        scanf("%d", &a[i]);
        a[i] = (a[i] + a[i - 1]) % k;
        // printf("pos %d : %d (%d) - %d\n",i,a[i],((a[i]-i)%k+k)%k,f[((a[i]-i)%k+k)%k]);
        o += f[((a[i] - i) % k + k) % k];
        f[((a[i] - i) % k + k) % k] ++;
    }
    printf("%lld\n", o);

    return 0;
}


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

int main(){
    while(1){
        int n;
        cin >> n;
        if(n==0) break;

        vector<pair<double, string> > data(n);
        for(int i=0; i<n; i++){
            string name;
            int p,a,b,c,d,e,f,s,m;
            cin >>name>>p>>a>>b>>c>>d>>e>>f>>s>>m;
            double rate = (double)(f*m*s-p)/((a+b+c)+(d+e)*m);
            data[i] = make_pair(-rate,name);
        }
        sort(data.begin(), data.end());
        for(int i=0; i<n; i++){
            cout << data[i].second << endl;
        }
        cout << "#" << endl;
    }
    return 0;
}

Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int d;
  cin>>d;
  cout<<"Christmas";
  FOR(i,d,25){
    cout<<" Eve";
  }
  cout<<endl;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
inline bool read(ll &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&c^-1;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int mod=1e9+7;
map<ll,ll> dp;
ll n;

ll dfs(ll n){
if (n<2) return n+1;
if (dp[n]) return dp[n];
return dp[n]=n&1?(dfs((n>>1)-1)%mod+2*dfs(n>>1))%mod
                :(dfs((n>>1)-1)*2%mod+dfs(n>>1))%mod;
}

int main(){
read(n);
write(dfs(n));
}

Measured memory_bytes: 256
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int i,a[52],suu,n,e,j;
	char b[5]="SHCD",c;
	for(i=0;i<52;i++)	a[i]=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)	{
		scanf(" %c %d",&c,&suu);
		for(j=0;j<4;j++)	if(b[j]==c)	e=j;
		a[e*13+suu-1]=1;
	}
	for(i=0;i<52;i++)	{
		if(a[i]==0)	{
			e=i/13;
			suu=i%13;
			printf("%c %d\n",b[e],suu+1);
		}
	}
	return 0;
}


Measured memory_bytes: 2744
#include "bits/stdc++.h"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;
	
#define WHATS(var)cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
	
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
	os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
	int i=0;
	for(auto it:v){
		if(i > 0){os << ' ';}
		os << it;
		i++;
	} 
	return os;
}
using ll=long long ;

int main() {
	ios::sync_with_stdio(false);
	// int a,b,c,d;cin>>a>>b>>c>>d;
	// cout<<(int(b>d))<<endl;

	// int N;cin>>N;
	// int answer=-1;
	// for(int i=1;i<50000;++i){
	// 	int j=i*108;
	// 	j/=100;
	// 	if(j==N){
	// 		answer=i;
	// 		break;
	// 	}
	// }
	// if(answer==-1)cout<<":("<<endl;
	// else cout<<answer<<endl;

	// int N;cin>>N;
	// string st;cin>>st;
	// //vector<vector<int>>dp(4,vector<int>(30001));
	// int answer=0;
	// for(int i=0;i<1000;++i){
	// 	vector<int>v;
	// 	int k=i;
	// 	for(int j=0;j<3;++j){
	// 		v.push_back(k%10);
	// 		k/=10;
	// 	}
		
	// 	int now=0;
	// 	for(auto c:st){
	// 		if(now<3&&v[now]==c-'0'){
	// 			now++;
	// 		}
	// 	}
	// 	if(now==3)answer++;
	// }

	// cout<<answer<<endl;
	// return 0;

	ll answer=1;
	int N;cin>>N;
	vector<int>v(3);
	while(N--){
		int a;cin>>a;
		ll val=0;
		int place=-1;
		for(int i=0;i<3;++i){
			if(a==v[i]){
				val++;
				place=i;
			}
		}
		if(place!=-1){
			answer*=val;
			v[place]++;
		}else{
			answer=0;
			break;
		}
		//WHATS(v)
		answer%=ll(1e9+7);
	}
	cout<<answer<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
using namespace std;
int main() {
	int a, b, c;
	while (cin >> a >> b >> c) {
		long long i = 0;
		while (true) {
			int sum = (a + b)*i;
			if (c >= sum % 60 && c <= sum % 60 + a) {
				sum = ceil(sum / 60) * 60 + c;
				if (sum > (a + b)*i+a) {
					sum -= 60;
				}
				cout << sum << endl;
				break;
			}
			if (i >= 1000000) {
				cout << -1 << endl;
				break;
			}
			i++;
		}
	}
}

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

    int main() {
      int N; cin >> N;  // 作業回数
      int K; cin >> K;  // 加算指定数
      int R = 1;        // 表示数

      rep(i,N){
        if (R*2 < R+K) {
          R *= 2;
        } else {
          R += K;
        }
      }
      cout << R << endl;
    }

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>

using namespace std;

#define ll long long

int main(void){
    double a, b, x;

    cin >> a >> b >> x;

    double ans;

    if(x <= a*b*a/2.0){
        ans = atan(a*pow(b, 2.0)/2.00000/x);
    }else{
        ans = atan(2.0*(pow(a, 2.0)*b-x) / pow(a, 3.0));
    }

    ans = 180.000000 * ans / M_PI;
    printf("%.7f\n", ans);

    return 0;
}

Measured memory_bytes: 256
N, L = map(int, input().split())
L_list = [n+L for n in range(N)]
if 0 in L_list:
    L_list.remove(0)
    print(sum(L_list))
elif L_list[0] > 0:
    print(sum(L_list[1:]))
else:
    print(sum(L_list[:-1]))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
 
int main() {
  int N,sum=0;
  cin >> N;
  vector<int>A(N),B(N),C(N);
  for(int i=0;i<N;i++){
      cin >>A[i];
  }
  for(int i=0;i<N;i++){
      cin >> B[i];
  }
  for(int i=0;i<N-1;i++){
      cin >> C[i];
  }
  for(int i=0;i<N;i++){
      sum += B[A[i]-1];
      if(A[i]+1==A[i+1] && i!=N){
          sum += C[A[i]-1];
      }
  }
  cout << sum;

}

Measured memory_bytes: 256
def hit_blow(str1, str2)
  n, m = 0, 0
  
  4.times do |i|
    n += 1 if str1[i] == str2[i]
    m += 1 if str1.include?(str2[i])
  end
  
  return [n ,m - n]
end

loop do
  str = gets.split
  
  break if str == ["0", "0"]
  
  h, b = hit_blow(str[0], str[1])
  
  puts "#{h} #{b}"
end

Measured memory_bytes: 6108
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    d = dict()
    for a in A:
        if a in d and d[a]:
            d[a] = False
        else:
            d[a] = True

    ans = sum(1 for flag in d.values() if flag)

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 22140
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)


int main() {
    int x;
	cin >> x;
    string ans;
    if(x<1200)ans="ABC";
    else ans = "ARC";
      cout << ans << endl;
}

Measured memory_bytes: 256
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

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

vector<string> vec_splitter(string s) {
    for(char& c: s) c = c == ','?  ' ': c;
    stringstream ss; ss << s;
    vector<string> res;
    for(string z; ss >> z; res.push_back(z));
    return res;
}

void debug_out(vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, Head H, Tail... T) {
    if(idx > 0) cerr << ", ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, T...);
}

#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
#else
#define debug(...) 42
#endif

const double PI = acos(-1);
typedef long long ll;
#define int ll
#define fori(n) for(int i=0; i<int(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a, n) vd a(n); fori(n) { cin>>a[i]; }

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;

void solve() {
    cini(n);
    cini(m);
    cinai(h,n);
    vvi adj(n);
    for(int i=0; i<m; i++) {
        cini(a);
        cini(b);
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vb ans(n, true);

    for(int i=0; i<n; i++) {
        for(int j : adj[i])
            if(h[i]<=h[j])
                ans[i]=false;
    }

    int cnt=0;
    for(int i=0; i<n; i++)
        if(ans[i])
            cnt++;
    cout<<cnt<<endl;
    
}

signed main() {
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    solve();
}



Measured memory_bytes: 9788
#include<bits/stdc++.h>
using namespace std;
int main(){
	int k;
	string s;
	cin>>k>>s;
	if(k>=s.size()) cout<<s;
	else{
		for(int i=0;i<k;i++) cout<<s[i];
		cout<<"...";
	}
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
#define ll long long 
using Graph = vector<vector<int>>;
int main()
{
    int N;
    cin >> N;
    vector<int> P(N), a(N);
    for(int i = 0; i < N; ++i) {
        cin >> P[i];
        --P[i];
        a[P[i]] = i;
    }
 
    ll ans = 0;
    set<int> st;
    for(int i = N - 1; i >= 0; --i) {
        st.insert(a[i]);
        vector<int> l(2, -1), r(2, N);
        auto litr = st.find(a[i]);
        auto ritr = litr;
        for(int j = 0; j < 2; ++j) {
            if(litr == st.begin())
                break;
            --litr;
            l[j] = *litr;
        }
        for(int j = 0; j < 2; ++j) {
            ++ritr;
            if(ritr == st.end())
                break;
            r[j] = *ritr;
        }
        ll sec = (l[0] - l[1]) * (r[0] - a[i]) + (r[1] - r[0]) * (a[i] - l[0]);
        ans += sec * (i + 1);
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define MP make_pair
#define PB push_back
#define PII pair<int,int>
typedef long long LL;
const LL P = 1e9+7;
const int N = 10005;
const double pi = acos(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

char s[N];
int n, k, cont[N];

int main(){
	cin>>n>>k;
	cin>>(s+1);
	char a = 'z';
	rep(i,1,n) a = min(a, s[i]);
	rep(i,1,n) s[n*2+1-i] = s[i];
	
	int l = 0;
	cont[0] = 0;
	rep(i,1,2*n){
		cont[i] = s[i]==a ? cont[i-1] + 1 : 0;
		l = max(l, cont[i]);
	}
	
	string ans="";
	if(l>(n>>k-1)){
		rep(i,1,n)ans+=a;
		cout<<ans<<endl;
		return 0;
	}
	ans += (a+1);
	rep(i,n,2*n)if(cont[i]==l){
		string tmp="";
		int l1 = min(l<<k-1, n), beg, end;
		end = i - l, beg = end - (n - l1) + 1;
		rep(j,1,l1) tmp += a;
		if(end) rrep(j,end,beg) tmp += s[j];
		ans = min(ans, tmp);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
#define ll long long
#define inf int(1e9+7)
#define pb push_back
#define mp make_pair
string s;
bool used[26];
int main()
{
	cin>>s;
	for(int i=0;i<s.length();i++)
		used[s[i]-'a']=1;
	if(s.length()<26)
		for(int i=0;i<26;i++)
			if(!used[i])
			{
				cout<<s<<char(i+'a');
				return 0;
			}
	int id=-1;
	for(int i=s.length()-2;i>=0;i--)
		if(s[i]<s[i+1])
		{
			id=i;
			break;
		}
	if(id==-1)
	{
		puts("-1");
		return 0;
	}
	string t=s.substr(0,id);
	int idx2=id+1;
	for(int i=id+1;i<s.length();i++)
		if(s[i]<s[idx2]&&s[i]>s[id])
			idx2=i;
	t+=s[idx2];
	cout<<t;
	return 0;
}

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

ll inf=1ll<<60;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	int a,b,c;
	cin>>a>>b>>c;
	if ((a*100+b*10+c)%4==0){
		cout<<"YES";
	}
	else {
		cout<<"NO";
	}
	return 0;
}

Measured memory_bytes: 256
<?php
$alphabets = str_split('abcdefghijklmnopqrstuvwxyz');
$S         = str_split(trim(fgets(STDIN)));
sort($S);
$S = array_values(array_unique($S));

$k = 0;
foreach ($alphabets as $i => $alphabet) {
    if ($alphabet === $S[$i]) {
        $k++;
    } else {
        break;
    }
}

echo $k === 26 ? 'None' : $alphabets[$k];

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

using namespace std;

int main(){

	int X, A, B;
	cin >> X >>A >>B;

	if( B <= A ){
		cout << "delicious" <<endl;
	}

	else if( B <= A+X ){
		cout << "safe" <<endl;
	}
	else
		cout << "dangerous" <<endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define MAX 300001

int op(int a, int b)
{
    return max(a, b);
}
int e()
{
    return 0;
}
int main()
{
    int N, K;

    cin >> N >> K;

    segtree<int, op, e> seg(MAX);

    for (int i = 0; i < N; i++)
    {
        int A;

        cin >> A;

        int l = A - K;
        int r = A + K + 1;

        if (l < 0)
        {
            l = 0;
        }
        if (r > MAX)
        {
            r = MAX;
        }
        int v = seg.prod(l, r);

        seg.set(A, v + 1);
    }
    cout << seg.all_prod() << endl;
}

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

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	string S;
	cin >> N >> S;
	vector<ll> jc(N), ic(N);
	for (int i = 0; i < N; i++) {
		jc[i] = S[i] == 'J';
		ic[i] = S[i] == 'I';
	}
	for (int i = 1; i < N; i++) {
		jc[i] += jc[i - 1];
	}
	for (int i = N - 2; i >= 0; i--) {
		ic[i] += ic[i + 1];
	}
	ll cnt = 0;
	for (int i = 1; i < N - 1; i++) {
		if (S[i] == 'O') {
			cnt += jc[i - 1] * ic[i + 1];
		}
	}
	ll ma = 0, sum = 0;
	for (int i = 0; i + 1 < N; i++) {
		if (S[i] == 'O') {
			sum += ic[i + 1];
		}
	}
	ma = max(ma, sum);
	for (int i = 1; i < N; i++) {
		ma = max(ma, jc[i - 1] * ic[i]);
	}
	sum = 0;
	for (int i = 1; i < N; i++) {
		if (S[i] == 'O') {
			sum += jc[i - 1];
		}
	}
	ma = max(ma, sum);
	cout << cnt + ma << endl;
	return 0;
}



Measured memory_bytes: 4780
//============================================================================
// Name        : AOJ.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>
#include<algorithm>

using namespace std;
typedef long long ll;
int main(){

	char s1,s2,s3;
	int x=0,y=0,z=0;

	cin>>s1>>s2>>s3;

	if(s1=='a'){
		x+=1;
	}
	if(s2=='a'){
		x+=1;
	}
	if(s3=='a'){
		x+=1;
	}
	if(s1=='b'){
		y+=1;
	}
	if(s2=='b'){
		y+=1;
	}
	if(s3=='b'){
		y+=1;
	}
	if(s1=='c'){
		z+=1;
	}
	if(s2=='c'){
		z+=1;
	}
	if(s3=='c'){
		z+=1;
	}

	if(y==1&&x==1&&z==1){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}








	return 0;
}


Measured memory_bytes: 256
local n,k=io.read("*n","*n")
local ans=0
if (k==0) then
  ans=n*n
else
  for i=k,n do
    ans=ans+(i-k)*(n//i)
    if (n%i>=k) then
      ans=ans+(n%i)-k+1
    end
  end
end
print(ans)

Measured memory_bytes: 760
#-*-coding:utf-8-*-
from collections import Counter

def main():
    n = int(input())
    s_list = [input() for _ in range(n)]
    abc_list = [float('inf') for i in range(26)]
    abc = [chr(i) for i in range(ord('a'), ord('a')+26)]

    for i in s_list:
        counter = Counter(i)
        for j in range(26):
            abc_list[j] = min(abc_list[j], counter[abc[j]])
    
    for i in range(26):
        print(abc[i] * abc_list[i], end='')
    print('')



if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
s = input()
n = len(s) - 1

for bit in range(1 << n):
  buf = s[0]
  result = 0
  for i in range(n):
    if bit & (1 << i):
      buf += "+{}".format(s[i+1])
    else:
      buf += "-{}".format(s[i+1])
  if eval(buf) == 7:
    print("{}=7".format(buf))
    break

Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <typeinfo>
#include <math.h>
#include <iomanip>
#include <limits>

using namespace std;
using ll = long long;
const ll res = 1000000007;

int main() {
	long double L;
	cin >> L;
	long double s = L / 3.0;
	cout << setprecision(20) << s * s * s << endl;
}


Measured memory_bytes: 256
/* ABC168_A
    Stuartyg */

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>


int main(void){
        int num; /*nのこと*/
        scanf("%d",&num);
        num%=10; /*10で割った余りがnの1の位*/
        switch(num){
                case 3: /*1の位が3ならbonと出力*/
                printf("bon\n");
                break;
        case 0: /*1の位が0，1，6，8ならponと出力*/
                printf("pon\n");
                break;
        case 1:
                printf("pon\n");
                break;
        case 6:
                printf("pon\n");
                break;
        case 8:
                printf("pon\n");
                break;
        default: /*1の位がそれ以外ならhonと出力*/
                printf("hon\n");
                break;
        }
        return 0;
}


Measured memory_bytes: 1660
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

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(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let n = read::<usize>();
    let mut a = vec![0usize; n];
    let big_int = 998244353u64;
    for i in 0..n {
        a[i] = read::<usize>();
    }
    let sum_length = a.iter().sum::<usize>();

    let mut dp = vec![vec![0u64; sum_length + 1]; n + 1];
    dp[0][0] = 1;
    for i in 0..n {
        for j in (0..sum_length + 1).rev() {
            // not select
            dp[i + 1][j] += 2 * dp[i][j];
            dp[i + 1][j] %= big_int;
            // select
            if j + a[i] <= sum_length {
                dp[i + 1][j + a[i]] += dp[i][j];
                dp[i + 1][j + a[i]] %= big_int;
            }
        }
    }
    let mut sum = 0;
    for j in (sum_length + 1) / 2..sum_length + 1 {
        sum += dp[n][j];
        sum %= big_int;
    }

    sum *= 3;
    sum %= big_int;
    let mut ans = 1;
    for i in 0..n {
        ans *= 3;
        ans %= big_int;
    }
    ans += big_int - sum;
    ans %= big_int;

    if sum_length % 2 == 0 {
        let mut dp = vec![vec![0u64; sum_length + 1]; n + 1];
        dp[0][0] = 1;
        for i in 0..n {
            for j in (0..sum_length + 1).rev() {
                // not select
                dp[i + 1][j] += dp[i][j];
                dp[i + 1][j] %= big_int;
                // select
                if j + a[i] <= sum_length / 2 {
                    dp[i + 1][j + a[i]] += dp[i][j];
                    dp[i + 1][j + a[i]] %= big_int;
                }
            }
        }
        // println!("{:?}", dp);
        ans += 3 * dp[n][sum_length / 2];
        ans %= big_int;
    }

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


Measured memory_bytes: 618748
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<algorithm> // sort
#include<map> // pair
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
typedef long long ll;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
const ll mod = 1e9+7;
const int INF = 1e9;
const ll INFLONG = 1e18;
void swap(ll *a,ll *b){
  ll tmp = *a;
  *a = *b;
  *b = tmp;
}
ll bubbleSort(vector<ll> vec,ll n){
  ll sum = 0;
  for(ll i = 0;i < n-1;i++){
    for(ll j = 0;j < n-1-i;j++){
      if(vec[j] > vec[j+1]){
        sum ++;
        swap(&vec[j],&vec[j+1]);
      }
    }
  }
  rep(i,n){
    if(i != n-1){
      cout << vec[i] << " ";
    }else{
      cout << vec[i];
    }
  }
  cout << endl;
  return sum;
}
int main(){
  ll n;
  cin >> n;
  vector<ll> vec(n);
  rep(i,n){
    cin >> vec[i];
  }
  ll ans = bubbleSort(vec,n);
  cout << ans << endl;
}



Measured memory_bytes: 3164
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(int)(b); i++)
#define FORD(i, a, b) for (int i=a; i>(int)(b); i--)
#define PPC(x) __builtin_popcount(x)
#define MSB(x) (31 - __builtin_clz(x))
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define ithBit(m, i) ((m) >> (i) & 1)
#define ft first
#define sd second
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;

const int maxN = 1 << 18;
int mod;

bool good[1000];
int n;
char T[maxN];
int ile[maxN];

template <class T1, class T2> inline void addMod(T1& a, T2 b)	{   a = (a + b) % mod;  }
template <class T1, class T2> inline void multMod(T1& a, T2 b)	{   a = a * b % mod;    }

long long qpow(long long a, long long b)
{
    long long res0 = 1;
    for (; b!=0; b>>=1)
    {
        if (b & 1)  multMod(res0, a);
        multMod(a, a);
    }
    return res0;
}

void brut()
{
	long long res = 0;
	FOR(i, 0, n)
		if (good[T[i]])
			res += i+1;
	printf("%lld\n", res);
	exit(0);
}

void solve()
{
	int p;
	scanf ("%d%d", &n, &p);
	mod = p;
	scanf ("%s", T);
	
	if (p == 2)
	{
		good['0'] = good['2'] = good['4'] = good['6'] = good['8'] = true;
		brut();
	}
	if (p == 5)
	{
		good['0'] = good['5'] = true;
		brut();
	}
	
	ile[0] = 1ll;
	long long oneT = 1ll, ten = 1ll, pref = 0, res = 0;
	FOR(i, 0, n)
	{
		multMod(pref, 10);
		addMod(pref, T[i] - '0');
		long long dx = pref * oneT % mod;
		res += ile[dx];
		ile[dx]++;
		multMod(ten, 10);
		multMod(oneT, qpow(10, mod-2));		
	}		
	
	printf("%lld\n", res);
} 

 
int main()
{
	//ios_base::sync_with_stdio(false);
    int t;
    t=1;//scanf ("%d", &t);
    while (t--)
    	solve();
    return 0;    
}


Measured memory_bytes: 512
import math
import sys

X, K, D = map(int, input().split())

a = X - K * D
if a > 0:
    print(a)
    sys.exit()
if a + 2 * K * D < 0:
    print(abs(a + 2 * K * D))
    sys.exit()
else:
    b = a / (-2 * D)
    p = math.floor(b)
    q = math.ceil(b)
    r = -(a + 2 * D * p)
    s = a + 2 * D * q
    print(min(r,s))
    sys.exit()

Measured memory_bytes: 9180
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=(b)-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define uint unsigned int
#define MOD 100000007
#define MAXN 200005
#define MAXH 4
#define MAXM 100
#define INF 1LL << 61
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define mat vector<vector<T>>
#define T long long
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define cld complex<long double>
using namespace std;

int main(){
	fast_io();
	int n;cin >> n;
	vector<ll> a(n), b(n);
	ll t = 0;
	cu(i,0,n){cin >> a[i]; t += 2*(i&1?-a[i]:a[i]);}
	b[0] = t/2;
	cu(i,1,n)b[i] = 2*a[i-1] - b[i-1];
	cu(i,0,n)cout << b[i] << ' ';cout << '\n';
}


Measured memory_bytes: 2944
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int64_t  a,b,c,d;
    cin >>a >>b >>c >>d;

    int64_t t1,t2,t3,t4;
    t1 = a * c;
    t2 = a*d ;
    t3 = b*c;
    t4 = b*d;

    int64_t max =t1;

    if(max < t2){
        max =t2;
    }
    if(max < t3){
        max =t3;
    }
    if(max < t4){
        max =t4;
    }

    cout<< max <<endl;
}



Measured memory_bytes: 3580
/* ---------- STL Libraries ---------- */

// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */

using namespace std;

/* ---------- Type Abbreviation ---------- */

template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;

#define fst first
#define snd second
#define mp make_pair
#define mt make_tuple

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)


/* ---------- conversion ---------- */

#define INT(c) static_cast<int>(c)
#define CHAR(n) static_cast<char>(n)
#define LL(n) static_cast<ll>(n)
#define DOUBLE(n) static_cast<double>(n)

/* ---------- container ---------- */

#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) (LL((v).size()))
#define each(itr,v) for(auto (itr):(v))

#define FIND(v, k) (v).find(k) != (v).end()
#define VFIND(v, k) find(ALL(v), k) != (v).end()

#define gsort(b, e) sort(b, e, greater<decltype(*b)>())

/* ----------- debug ---------- */

template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	for (auto vv : v)
		os << vv << ",";
	return os << "]";
}

template <class T>
ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	for (auto vv : v)
		os << vv << ",";
	return os << "]";
}

template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) {
	return os << "(" << p.fst << "," << p.snd << ")";
}

/* ---------- Constants ---------- */

// const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* ---------- Short Functions ---------- */

template <typename T>
T sq(T a) {
	return a * a;
}

template <typename T>
T gcd(T a, T b) {
	if (a > b) return gcd(b, a);
	return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
	if (n == 0) return 1;
	if (n == 1) return b /* % MOD */;
	if (n % 2 == 0) {
		return mypow(b * b /* % MOD */, n / 2);
	}
	else {
		return mypow(b, n - 1) * b /* % MOD */;
	}
}

ll pcnt(ll b) {
	return __builtin_popcountll(b);
}



// const ll dx[4] = {0, -1, 1, 0};
// const ll dy[4] = {-1, 0, 0, 1};
// const ll dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const ll dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

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

	int a, b;
	cin >> a >> b;
	int K; cin >> K;
	int cnt = 0;
	int ans;
	int G = gcd(a, b);
	for (int i = G; i>0; i--) {
		if (a%i == 0 && b%i == 0) {
			cnt++;
			ans = i;
		}
		if (cnt == K) break;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#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 pbds tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>

#define F_OR(i, a, b, s) for (ll i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
 
// debug templates 
#define debug(x)       cerr<< #x <<" : "<< x << endl;
#define debuga(A,N)    cerr<< #A <<" : [";for(int i = 0; i<N;i++) cerr<<A[i]<<" "; cerr<<"]\n";
#define debuga2(A,N,M) cerr<< #A << " : \n"; for(int i=0;i<N;i++){cerr<<"[";for(int j=0;j<M;++j) cerr<<A[i][j]<<" ";cerr<<"]\n";}
#define debugp(p)      cerr<< #p <<" : "<<"("<<(p).first<<","<<(p).second<<")\n";
#define debugv(v)      cerr<< #v <<" : "<<"[";for(int i = 0; i< (v).size(); i++) cerr<<v[i]<<" "; cerr<<"]\n";
#define debugv2(v)     cerr<< #v << " : \n"; for(int i=0;i<v.size();i++){cerr<<"[";for(int j=0;j<(v[0].size());++j) cerr<<v[i][j]<<" ";cerr<<"]\n";}
#define debugs(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin(); itr!=m.end();itr++) cerr<<*itr<<" "; cerr<<"]\n";
#define debugm(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin();itr!=m.end(); itr++) cerr<<"("<<itr->first<<","<<itr->second<<") ";cerr<<"]\n";
 
const ll mod = 1e9+7;

ll power(ll a, ll b){
	ll result = 1;
	while(b>0){
		if(b&1) result = (result*a)%mod;
		(a*=a)%=mod;
		b/=2;
	}
	return result;
}

void solve(){
    string s; cin >> s;
    ll ans = 1, n = s.size(), cnt = 0;
    FOR(n){
        if(s[i] == '1') ++cnt, ans = (3*ans)%mod;
        else ans = (3*ans - power(2,cnt+1))%mod;
    }
    cout << (ans + mod)%mod;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	solve();
	return 0;
}
 


Measured memory_bytes: 3780
n, m = map(int, input().split())
sc_lst = [list(map(int, input().split())) for _ in range(m)]
lst = [0] * n
switch_lst = [0] * n

flag = False

if n == 1:
    lst = [0]
    switch_lst = [0]

    for i in range(m):
        s = 0
        c = sc_lst[i][1]

        if switch_lst[0] == 1:
            if c != lst[0]:
                flag = True
                break
        else:
            lst[0] = c
            switch_lst[0] = 1


else:
    flag = False
    for i in range(m):
        s = sc_lst[i][0] - 1
        c = sc_lst[i][1]

        if switch_lst[s] == 1:
            if lst[s] != c:
                flag = True
                break
            else:
                pass

        else:
            switch_lst[s] = 1
            lst[s] = c

            if s == 0 and c == 0:
                flag = True
                break


if flag:
    answer = -1
else:
    answer = ''
    for i in range(n):
        if switch_lst[i] == 1:
            answer += str(lst[i])
        else:
            if n == 1:
                answer = 0
            else:
                if i == 0:
                    answer += str(1)
                else:
                    answer += str(0)


print(answer)

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

class P
{
  static void Main()
  {
    var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
    Console.WriteLine("{0} {1} {2:f5}", a[0]/a[1], a[0]%a[1], Convert.ToDouble(a[0]) / a[1]);
  }
}

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

typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;

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

    int ans = s[0] - '0';
    bool c(true);
    for(int i=1;i<s.size();i++){
        if(s[i]!='9')   c = false;
    }
    if(!c){
        if (s.size() != 1)
        {
            ans += 9 * (s.size() - 1) - 1;
        }
    }else{
        ans += (s.size()-1)*9;
    }
    

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3568
def gcd(a, b):
    if(a < b):
        a, b = b, a
    if(b == 0):
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return a // gcd(a, b) * b

N = int(input())
A = list(map(int, input().split()))
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
mod = 10**9+7
l %= mod
for a in A:
    ans += (l * pow(a, mod-2, mod))%mod
    ans %= mod
print(ans)


Measured memory_bytes: 71512
#include<bits/stdc++.h>
#define lli long long int
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    lli n,x,t;
    cin>>n>>x>>t;
    if(n%x==0)
    cout<<(n/x)*t<<"\n";
    else
     cout<<((n/x)+1)*t<<"\n";
}

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

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
constexpr int MOD = 1e9 + 7;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}
// -------------------------------------------------------------------

using P = pair<int, int>;

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

    int a, b, q;
    cin >> a >> b >> q;
    vector<int> s(a), t(b), x(q);
    rep (i, a)
        cin >> s[i];
    rep (i, b)
        cin >> t[i];
    rep (i, q)
        cin >> x[i];
    s.insert(s.begin(), -pow(10, 11));
    t.insert(t.begin(), -pow(10, 11));
    s.push_back(pow(10, 12));
    t.push_back(pow(10, 12));

    repall (st, x) {
        auto ns = lower_bound(all(s), st);
        int sb = *ns;
        int ss = *--ns;
        auto nt = lower_bound(all(t), st);
        int tb = *nt;
        int ts = *--nt;

        int mi = pow(10, 12);
        for (int i : {sb, ss})
            for (int j : {tb, ts})
                mi = min(mi, abs(i - j) + min(abs(st - i), abs(st - j)));

        print(mi);
    }

    return 0;
}


Measured memory_bytes: 3680
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
	int a, b; cin >> a >> b;
	if(abs(a-b)>= 1) cout << max(a, b) + max(a, b)-1 << endl;
	else cout << a+b << endl;

	return 0;
}

Measured memory_bytes: 256
c1 = list(map(int,input().split()))
c2 = list(map(int,input().split()))
c3 = list(map(int,input().split()))

sw = 1
b1 = min(c1)
a = [c1[0]-b1, c1[1]-b1, c1[2]-b1]

if not(c2[0]-a[0] == c2[1]-a[1] == c2[2]-a[2]):
    sw = 0
if not(c3[0]-a[0] == c3[1]-a[1] == c3[2]-a[2]):
    sw = 0
    
print(["No","Yes"][sw])


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

int main(){
  string S;
  cin >> S;
  
  int chk = 0;
  
  
  for(int i=1; i<S.length() ; ++i){
    if(S[i]<='z' && 'a'<=S[i]) chk +=0;
    else if(S[i]=='C' && 2<=i && i<S.length()-1) chk++;
    else chk-=100;
  }  
  if(S[0]=='A' && chk==1) cout << "AC" << endl;
  else cout << "WA" << endl;

}

Measured memory_bytes: 256
N = int(input())
A = [input() for _ in range(N)]
B = list()
num_M=0
num_A=0
num_R=0
num_C=0
num_H=0
for i in A:
  if i[0]=='M':
    num_M+=1
    continue
  if i[0]=='A':
    num_A+=1
    continue
  if i[0]=='R':
    num_R+=1
    continue
  if i[0]=='C':
    num_C+=1
    continue
  if i[0]=='H':
    num_H+=1
    continue
print(num_M*num_A*num_R+num_M*num_A*num_C+num_M*num_A*num_H+num_M*num_R*num_C+num_M*num_R*num_H+num_M*num_C*num_H+num_A*num_R*num_C+num_A*num_C*num_H+num_A*num_R*num_H+num_R*num_C*num_H)


Measured memory_bytes: 9776