akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

string s;
int d;

void add(int& x, int v) {
  x = (x + v) % MOD;
}

void solve() {
  // dp[i][j][k]: 到第i位为止，和为k mod d的数有几个。j代表是否前面都和s中第i位相同
  vector<vector<int> > dp(2, vector<int>(d, 0));
  dp[1][0] = 1;
  for (int i=1; i<=s.size(); ++i) {
    vector<vector<int> > next(2, vector<int>(d, 0));
    for (int g=0; g<=9; ++g) {
      for (int p=0; p<d; ++p) {
        int digit = s[i-1] - '0';
        int q = (g + p) % d;
        if (g < digit) {
          add(next[0][q], dp[0][p]);
          add(next[0][q], dp[1][p]);
        } else if (g == digit) {
          add(next[0][q], dp[0][p]);
          add(next[1][q], dp[1][p]);
        } else {
          add(next[0][q], dp[0][p]);
        }
      }
    }
    dp = next;
  }
  cout << ((dp[0][0] + dp[1][0] - 1) % MOD + MOD) % MOD << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  cin >> d;
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX_N = 100001;
static const int INFTY = 1000000001;
int n;
int h[MAX_N];
int L[MAX_N], R[MAX_N], st[MAX_N];

void solve() {
    int t = 0;
    for (int i = 0; i < n; i++) {
        while (t > 0 && h[st[t-1]] >= h[i]) t--;
        L[i] = (t == 0) ? 0 : (st[t-1] +1);
        st[t++] = i;
    }

    t = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (t > 0 && h[st[t-1]] >= h[i]) t--;
        R[i] = (t == 0) ? n : st[t-1];
        st[t++] = i;
    }

    long long res = 0;
    for (int i = 0; i < n; i++) {
        res = max(res, (long long) h[i] * (R[i] - L[i]));
    }
    printf("%lld\n", res);
}


int main() {
    scanf("%d", &n);
    //fill(st, st+n+1, 0);
    for (int i = 0; i < n; i++) scanf("%d", &h[i]);
    solve();
    return 0;
}



Measured memory_bytes: 4748
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long LL;
using namespace std;

int main() {
	int n; cin >> n;
	vector<int> a(n);
	for (int &x : a)cin >> x;
	int cnt = 0;

	for (int i = 0; i < n ; i++) {
		int mipos = i;
		for (int j = i; j < n ; j++) {
			if (a[j] < a[mipos]) {
				mipos = j;
			}
		}
		if (i != mipos) {
			swap(a[i], a[mipos]);
			cnt++;
		}
	}
	rep(i, n) printf(i != n - 1 ? "%d " : "%d\n", a[i], a[i]);
	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 3236
#include <iostream>
#include <assert.h>
#include <vector>
#include <stdio.h>
#include <iomanip>
#define mod 1000000007
using namespace std;

int dp[2][100010];

void add(int & a, int b)
{
    a += b;
    if (a < 0)
        a += mod;
    if (a >= mod)
        a -= mod;
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);

    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        int * from = dp[(i & 1) ^ 1];
        int * act = dp[i & 1];

        int v;
        scanf("%d", &v);
        int s = 0;

        for (int j = 0; j <= k; j++) {
            /// vreau sa iau cel putin 0 cel mult v -> vin din (j - v, j)
            add(s, from[j]);
            if (j > v)
                add(s, -from[j - v - 1]);
            act[j] = s;
        }
    }

    printf("%d\n", dp[n & 1][k]);
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include <cassert>
#include<string>
#include<vector>
#include <utility>
#include <math.h>
#include<cmath>
#include<map>
#include <limits>
# include <iomanip>
#include <queue>
#define INF 1000000000000000009;
#define WARU 1000000007;

using namespace std;
int gcd(int a, int b) {
	while (a % b != 0) {
		int c = 0;
		c = a % b;
		a = b;
		b = c;
	}
	return  b;
}

int main() {
	int N = 0;
	//bool ok = false;
	long long a[100005],K = 0, ans = 1, amari = 0, memo = 0;
	cin >> K;
	if (K % 2 == 0) {
		cout << "-1" << endl;
		return 0;
	}
	amari = 7 % K;
	while (amari != 0&&ans<K+10) {
		amari = 7+(amari * 10) % K;
		amari = amari % K;
		//cout << amari << endl;
		ans++;
	}
	if (ans == K + 10) {
		cout << "-1" << endl;
		return 0;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,N) for(ll i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

string s;

int main(){
    cin >> s;
    if(s[0] == s[1] && s[1] == s[2])cout << "Yes" << endl;
    else if(s[2] == s[3] && s[1] == s[2])cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

vector<int> v[10];
bool used[10];
int ans;
int N,M;

void dfs (int x, int cnt) {
    if( used[x] ) return;
    used[x] = true;
    int l = v[x].size();
    for(int i=0; i<l; i++) {
        dfs(v[x][i], cnt+1);
    }
    used[x] = false;
    if( N-1 == cnt ) ans++;
    return ;
}

int main (){
    cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<map>
#include<time.h>
#include<cstring>
#include<iomanip>
#include<numeric>
#include<list>
#include<stack>
#define lli long long int
#define h 10000
#define pf push_front
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
using namespace std;
int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL) ;
  lli t, flag, i, l, j, k, x, y, n, m, a, b;
  	cin>>x;
  	cout<<!x<<endl;
  return 0;
} 


Measured memory_bytes: 3564
L = [list(map(int,input().split())) for _ in range(3)]

a1 = 0
b1 = L[0][0]
b2 = L[0][1]
b3 = L[0][2]
a2 = L[1][1] - b2
a3 = L[2][2] - b3

assumption = []
l = [a1+b1,a1+b2,a1+b3]
assumption.append(l)
l = [a2+b1,a2+b2,a2+b3]
assumption.append(l)
l = [a3+b1,a3+b2,a3+b3]
assumption.append(l)
if assumption == L:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <stack>
#include <cassert>
using namespace std;
typedef long long LL;
const int M = 1e6 + 5;
const int N = 200000 + 5;
const LL mod = 19260817;
const int MAX = 5e5 + 5;
const int MAXV = 100000 + 5;
const LL INF = (1LL << 62);
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.);
char s[105],now[105];
int len;
int c(char x){
    strcpy(now,s);
    for(int i = 0; i <= len; i++){
        bool flag = 1;
        for(int j = 0; j < len - i; j++)if(now[j] != x)flag = 0;
        if(flag)return i;
        for(int j = 0; j < len - i - 1; j++){
            if(now[j] == x || now[j + 1] == x){
                now[j] = x;
            }
        }
    }
}
int main() {
#ifdef local
    freopen("input", "r", stdin);
//    freopen("w", "w", stdout);
//    freopen("input", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans = inf;
    cin>>s;
    len = strlen(s);
    for(int i = 0; i < 26; i++){
        ans = min(ans,c(i + 'a'));
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 256
import collections
n = int(input())
a = list(map(int,input().split()))
ac = collections.Counter(a)
q = int(input())
b = [0] * q
c = [0] * q
for i in range(q):
    b[i],c[i] = map(int,input().split())
sum = sum(a)
for j in range(q):
    div = 0
    if ac[b[j]] != 0:
        div = c[j] * ac[b[j]] - b[j] * ac[b[j]]
        ac[c[j]] += ac[b[j]]
        ac[b[j]] = 0
    sum += div
    print(sum)

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

int main(){
	vector<int> v(3);
    int a;
    scanf("%d%d%d",&v[0],&v[1],&v[2]);
    scanf("%d",&a);
    sort(v.begin(),v.end());
    printf("%lld\n",(long long int)(v[0]+v[1]+v[2]*pow(2,a)));
	
	return 0;
}

Measured memory_bytes: 256
import sys, math
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    a, b, x = LI()

    if 2*x<(a**2)*b:
        ans = 90 - math.degrees(math.atan(2*x / (a*(b**2))))
    elif (a**2)*b == x:
        ans = 0
    else:
        ans = 90 - math.degrees(math.atan(a**3 / (2*((a**2)*b-x))))
    print(ans)

if __name__ == '__main__':
    resolve()

Measured memory_bytes: 3188
import java.util.*;

class Main {
	Scanner sc = new Scanner(System.in);

	public void run() {
		while(true){
			int n=sc.nextInt();
			if(n==0)break;
			char[][] map=new char[n][n];
			for(int i=0;i<n;i++){
				map[i]=sc.next().toCharArray();
			}
			int max=0;
			for(int y=0;y<n;y++)
				for(int x=0;x<n;x++){
					int w=0,h=0;
					while(x+w<n && map[y][x+w]!='*')w++;
					while(y+h<n && map[y+h][x]!='*')h++;
					for(int dy=0;dy<h;dy++)for(int dx=0;dx<w;dx++){
						if(y+dy<n && x+dy<n && map[y+dy][x+dx]=='*'){
							if(dx<dy){
								h=dy;
							}else if(dx>dy){
								w=dx;
							}else{
								h=w=dx;
							}
						}
					}
					max=Math.max(max,Math.min(w,h));
				}

			ln(max);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public static void pr(Object o) {
		System.out.print(o);
	}

	public static void ln(Object o) {
		System.out.println(o);
	}

	public static void ln() {
		System.out.println();
	}
}

Measured memory_bytes: 15000
#include <bits/stdc++.h>
#include<string>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
char s[maxn];
int dp[maxn][2];
int main(){
    cin>>s+1;
    int len=strlen(s+1);
    reverse(s+1,s+1+len);
    dp[0][1]=1;
    for(int i=1;i<=len;i++){
        dp[i][1]=min(dp[i-1][1]-1,dp[i-1][0])+10-s[i]+'0';
        dp[i][0]=min(dp[i-1][1]-1,dp[i-1][0])+2+s[i]-'0';
        dp[i][0]=min(dp[i-1][0]+s[i]-'0',dp[i][0]);
        dp[i][1]=min(dp[i-1][1]+s[i]-'0'+9,dp[i][1]);
    }
    cout<<min(dp[len][1]+1,dp[len][0])<<endl;
	return 0;
}

Measured memory_bytes: 9088
//Author:xht37
#include <bits/stdc++.h>

#define ui unsigned int
#define ll long long
#define ul unsigned ll
#define ld long double

#define pi pair <int, int>
#define fi first
#define se second
#define mp make_pair

#define ls (p << 1)
#define rs (ls | 1)
#define md ((t[p].l + t[p].r) >> 1)

#define vi vector <int>
#define pb push_back
#define pq priority_queue

#define dbg(x) cerr << #x" = " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)

#define fl(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

namespace io {
	const int SI = 1 << 21 | 1;
	char IB[SI], *IS, *IT, OB[SI], *OS = OB, *OT = OS + SI - 1, c, ch[100];
	int f, t;
	#define gc() (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin), IS == IT ? EOF : *IS++) : *IS++)
	inline void flush() {
		fwrite(OB, 1, OS - OB, stdout), OS = OB;
	}
	inline void pc(char x) {
		*OS++ = x;
		if (OS == OT) flush();
	}

	template <class I>
	inline void rd(I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c & 15), c = gc());
		x *= f;
	}
	template <class I>
	inline void rd(I &x, I &y) {
		rd(x), rd(y);
	}
	template <class I>
	inline void rd(I &x, I &y, I &z) {
		rd(x), rd(y), rd(z);
	}
	template <class I>
	inline void rda(I *a, int n) {
		for (int i = 1; i <= n; i++) rd(a[i]);
	}
	inline void rdc(char &c) {
		for (c = gc(); c < 33 || c > 126; c = gc());
	}
	inline void rds(char *s, int &n) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (n = 0; c >= 33 && c <= 126; s[++n] = c, c = gc());
		s[n+1] = '\0';
	}
	inline void rds(string &s) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (s.clear(); c >= 33 && c <= 126; s.pb(c), c = gc());
	}

	template <class I>
	inline void print(I x, char k = '\n') {
		if (!x) pc('0');
		if (x < 0) pc('-'), x = -x;
		while (x) ch[++t] = x % 10 + '0', x /= 10;
		while (t) pc(ch[t--]);
		pc(k);
	}
	template <class I>
	inline void print(I x, I y) {
		print(x, ' '), print(y);
	}
	template <class I>
	inline void print(I x, I y, I z) {
		print(x, ' '), print(y, ' '), print(z);
	}
	template <class I>
	inline void printa(I *a, int n) {
		for (int i = 1; i <= n; i++) print(a[i], " \n"[i==n]);
	}
	inline void printc(char c) {
		pc(c);
	}
	inline void prints(char *s, int n) {
		for (int i = 1; i <= n; i++) pc(s[i]);
		pc('\n');
	}
	inline void prints(string s) {
		int n = s.length();
		while (t < n) pc(s[t++]);
		pc('\n'), t = 0;
	}
	struct Flush {
		~Flush() {
			flush();
		}
	} flusher;
}
using io::rd;
using io::rda;
using io::rdc;
using io::rds;
using io::print;
using io::printa;
using io::printc;
using io::prints;

const int N = 2e5 + 7;
int n, a[N];
ll s, ans;

int main() {
	rd(n), rda(a, n);
	map<ll, int> c;
	for (int i = 1; i <= n; i++)
		c[s]++, s += a[i], ans += c[s];
	print(ans);
	return 0;
}

Measured memory_bytes: 18776
// ABHISHEK JAISWAL
#include<bits/stdc++.h>
#include<string>
#include<math.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<ll> vi;
typedef pair<ll,ll> pi;

#define f first 
#define s second 
#define pb push_back 
#define mp make_pair
#define rep(i,a,b) for (ll i = a; i <= b; i++)
#define repl(i,a,b) for (ll i = a; i < b; i++)
#define repz(i,a,b) for (ll i = a; i >=b; i--)
#define repr(i,a,b) for (ll i = a-1; i >=b; i--)

long long gcd(long long a, long long b){
	return a? gcd(b % a, a) : b;
}

ll find_(vector<ll> &cn, ll i){
    if(cn[i]==i)return i;
    
    return find_(cn,cn[i]);
}

void union_(vector<ll> &cn, ll i, ll j, vector<ll> &cur){
    ll pi = find_(cn,i);
    ll pj = find_(cn,j);
    
    if(pi!=pj){
        // siz[cur[i]]--;
        // siz[cur[j]]--;
        // siz[cur[pi]+cur[pj]]++;
        cur[pi] += cur[pj];
        cur[pj] = cur[pi];
    }
    
    if(pi<pj){
        cn[pi]=pj;
    }
    else if(pi>pj){
        cn[pj] = pi;
    }
    
    return;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

    ll t = 1;
    // cin>>t;
    while(t--){
    ll n;  cin>>n;
    ll m;  cin>>m;
    
    vector<ll> cn(n+1);
    vector<ll> cur(n+1,1);
    // cur[1]=n;
    rep(i,1,n)cn[i]=i;
    
    repl(i,0,m){
        ll a,b;
        cin>>a>>b;
        
        union_(cn,a,b,cur);
    }
    
    ll mx = 0;
    // repl(i,1,n)
    rep(i,1,n)mx = max(mx,cur[i]);
    
    cout<<mx<<"\n";
    
    
    }
    return 0;
}



Measured memory_bytes: 6364
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>

#define llong long long int

using namespace std;

int main(int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    double sum = 0;
    int a[105];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    double av = sum / n;
    int ans = n - 1;
    double dif = abs(a[n - 1] - av);
    for (int i = n - 2; i >= 0; --i) {
        if (abs(a[i] - av) <= dif) {
            ans = i;
            dif = abs(a[i] - av);
        }
    }

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

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* Dijkstra O(NlogM)*/

template <typename Type = int>
struct Dijkstra{
  int V;
  vector<vector<pair<int,Type>>> G;
  vector<Type> cost;

  Dijkstra(int n):
    V(n), G(n, vector<pair<int,Type>>()) {}

  void add_edge(int u, int v, Type c){
    G[u].push_back({v, c});
  }

  Type solve(int s, int g = -1){
    cost.assign(V, -1);
    priority_queue<pair<Type,int>> pq;
    Type max_cost = 0;

    pq.push({0, s});

    while(pq.size()){
      Type now_cost = pq.top().first;
      int now = pq.top().second;
      pq.pop();

      if(cost[now] >= 0) continue;

      cost[now] = -now_cost;
      max_cost = max(max_cost, -now_cost);

      if(now == g) return -now_cost;

      for(int i=0; i<(int)G[now].size(); i++)
        pq.push({now_cost - G[now][i].second, G[now][i].first});
    }

    return max_cost;
  }
};

vector<int> rev[SIZE];

int main(){
  int N, M;


  cin >> N >> M;

  Dijkstra<> dijk(N);

  for (int i=0; i<M; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;

    dijk.add_edge(a, b, 1);
    rev[b].push_back(a);
  }


  int minDist = INF, minStart = 0;

  for (int i=0; i<N; i++) {
    dijk.solve(i);

    int minC = INF;

    for (int p : rev[i])
      if (dijk.cost[p] != -1) minC = min(minC, dijk.cost[p]);

    if (minDist > minC) {
      minStart = i;
      minDist = minC;
    }
  }

  if (minDist == INF) {
    puts("-1");
    return 0;
  }

  dijk.solve(minStart);

  vector<int> ans;
  int now = minStart;
  int dist = minDist;

  do{
    ans.push_back(now + 1);

    for (int p : rev[now]) {
      if (dijk.cost[p] == dist) {
        now = p;
        dist = dist-1;
        break;
      }
    }

  }while(now != minStart);

  cout << ans.size() << endl;

  for (int p : ans) {
    cout << p << endl;
  }

  return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t,n,m,i,j,k,x,y,u=0,h;
    cin>>x;
    for (int i = 0; i < 1000; i++) {
        for (int j = -1000; j < 1000; j++) {
            if (x == (pow(i, 5) - pow(j, 5))) {
                cout << i << " " << j;
                return 0;
            }
        }
    }
}

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

int main () {
  string a="abc";
  string b="abc";
  for (int i=0;i<3;++i) cin >> a[i];
  for (int i=0;i<3;++i) cin >> b[i];

  bool ans=true;
  for (int i=0;i<3;++i) {
    if (a[i]!=b[2-i]) ans=false;
  }

  if (ans) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

int countPrimes(long long x) {
  map<long long, int> m;
  for(long long i=2; i*i <= x; i++) {
    while(x % i == 0) {
      m[i]++;
      x /= i;
    }
  }
  if (x != 1) m[x]++;
  return m.size();
}

int main() {
  long long a, b; cin >> a >> b;
  long long x = __gcd(a, b);
  cout << countPrimes(x) + 1 << endl;
}

// EOF

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

using namespace std;

int main()
{
    string s;
    cin >> s;
    char fst = s[0];
    if (fst != s[1] || fst != s[2])
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, x;
    cin >> N >> x;
    if (x == 1 || x == 2 * N - 1) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    int order[200010];
    rep(i, N * 2 - 1) order[i] = (N + i + 1) % (N * 2 - 1) + 1;
    x -= 2;
    rep(i, N * 2 - 1) {
        cout << order[(x + i) % (N * 2 - 1)] << endl;
    }

    return 0;
}
//     2
//   3 2 2
// 5 3 1 2 4

//       2
//     3 2 2    
//   5 3 2 2 4
// 7 5 3 1 2 4 6


//        3
//      5 3 1
//    6 5 3 1 2
//  6 7 5 3 1 2 4  

//        5
//      6 5 3
//    6 6 5 3 2
//  4 6 7 5 3 1 2 

//       4
//     3 4 5
//   2 3 4 5 6
// 1 2 3 4 5 6 7

//       2
//     6 2 2
//   6 6 2 2 3
// 5 6 7 1 2 3 4


//

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

typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;


//===

const ll mod = static_cast<ll>(1e9 + 7);



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

	ll ans = 0;
	int idx = 0;
	ll a_cnt_prev = 0;
	while (idx < s.size()) {
		while (idx < s.size() && s[idx] != 'A') {
			a_cnt_prev = 0;
			++idx;
		}

		ll a_cnt = 0, bc_cnt = 0;
		while (idx < s.size() && s[idx] == 'A') {
			++a_cnt;
			++idx;
		}
		while (idx < s.size() - 1 && s[idx] == 'B' && s[idx + 1] == 'C') {
			++bc_cnt;
			idx += 2;
		}

		ans += (a_cnt + a_cnt_prev) * bc_cnt;
		a_cnt_prev += a_cnt;
	}

	cout << ans << endl;
}

Measured memory_bytes: 640
#include <algorithm>
#include <iomanip>
#include <iostream>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define MAX_N 50
using namespace std;

int main(void) {
  int N;
  cin >> N;
  int V[MAX_N];
  rep(i, N) { cin >> V[i]; }
  sort(V, V + N);

  double ANS = V[0];
  for (int i = 1; i < N; i++) {
    ANS = (ANS + V[i]) / 2.0;
  }
  cout << setprecision(10) << ANS << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <array>
#include <iomanip>
#include <unordered_set>
#define ll long long
#define ar array
#define AC ios_base::sync_with_stdio(0);
using namespace std;
const int N = 1e5;
const int M = 1e9+7;
int n;
ll dp[405][405];
ll arr[405];


int main(){
    AC
    cin>>n;
    arr[0] = 0;
    for(int i=1; i<=n; i++){
        ll x;
        cin>>x;
        arr[i] = x+arr[i-1];
    }

    for(int l=2; l<=n; l++){
        for(int i=0; i<n-l+1; i++){
            int end = i+l-1;
            dp[i][end] = dp[i][i]+dp[i+1][end]+(arr[i+1]-arr[i])+(arr[end+1]-arr[i+1]);
            for(int k=i+1; k<=end; k++){
                dp[i][end] = min(dp[i][end], dp[i][k]+dp[k+1][end]+(arr[k+1]-arr[i])+(arr[end+1]-arr[k+1]));
            }
        }
    }

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

Measured memory_bytes: 4384
import sys
from collections import Counter


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    V = nl()
    V_e = V[0::2]
    V_o = V[1::2]
    V_e_c = Counter(V_e)
    V_o_c = Counter(V_o)

    if V_e_c.most_common()[0][0] != V_o_c.most_common()[0][0]:
        ans = len(V) - \
            V_e_c.most_common()[0][1] - V_o_c.most_common()[0][1]

    else:
        if len(V_e_c.most_common()) == 1 or len(V_o_c.most_common()) == 1:
            if len(V_e_c.most_common()) == 1 and len(V_o_c.most_common()) == 1:
                ans = len(V) // 2
            else:
                if len(V_e_c.most_common()) != 1:
                    ans = len(V) // 2 - V_e_c.most_common()[1][1]
                else:
                    ans = len(V) // 2 - V_o_c.most_common()[1][1]

        else:
            ans = len(V) - max(
                V_e_c.most_common()[0][1] + V_o_c.most_common()[1][1],
                V_e_c.most_common()[1][1] + V_o_c.most_common()[0][1],
            )

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 24740
#include<bits/stdc++.h>
using namespace std;
int a[2001];
int main()
{
	int n,x,y;
	cin>>n>>x>>y;
	for (int i = 1; i < n; ++i)
	{
		for(int j = i;j <= n ; j++)
		{
			a[min((j-i),(abs(x-i)+1+abs(y-j)))]++;
		}
	}
	for (int i = 1; i < n; ++i)
	{
		cout<<a[i]<<endl;
	}

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  char a[2][3];
  for(int i = 0;i<2;i++){
    for(int j = 0;j<3;j++){
  cin >> a[i][j];
    }
  }
  if(a[0][0]==a[1][2]&&a[1][0]==a[0][2]&&a[0][1]==a[1][1])
  cout << "YES"  <<endl;
  else cout<< "NO"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int a;
map<int,int> m;
vector<int> vi;
int main(){
    int n,k;
    cin>>n>>k;
    rep(i,n){
        cin>>a;
        m[a]++;
    }
    int mx=0,mx2=0;
    for(map<int,int>::iterator it=m.begin();it!=m.end();++it){
        vi.pb(it->second);
    }
    sort(vi.begin(),vi.end(),greater<int>());
    int ans=0;
    for(int i=0;i<min(k,(int)vi.size());++i) ans+=vi[i];
    cout<<n-ans<<endl;
    return 0;
}

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

import numpy as np

n = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int64)
B = np.array(list(map(int, input().split())), dtype=np.int64)

ans = 0
for i in range(30):
    t = 1 << i
    C = B.copy() % (2*t)
    E = A.copy() % (2*t)
    C.sort()
    E.sort()
    D = np.searchsorted(C, 2*t-E, side="left")
    D -= np.searchsorted(C, t-E, side="left")
    D += np.searchsorted(C, 4*t-E, side="left")
    D -= np.searchsorted(C, 3*t-E, side="left")
    cnt = D.sum() % 2
    ans += cnt << i
print(ans)


Measured memory_bytes: 52796
N = int(input())
def change(x):
    if x==0: x=26
    return chr(ord('a')+int(x)-1)
def helper(N,x):
    if N<=26: return change(N)
    if (int(N/x)):
        if N%x !=0:
            return helper(int(N/x),x)+change(N%x)
        else:
            return helper(int(N/x)-1,x)+change(N%x)
print(helper(N,26))

Measured memory_bytes: 61748
import math
a,b,x = map(int,input().split(" "))
v = a*a*b
if v >= 2*x:
    print(180*math.atan(a*b*b/(2*x))/math.pi)
else:
    print(180*math.atan((2*b/a)-(2*x/a/a/a))/math.pi)

Measured memory_bytes: 3060
//Dragon_warrior7(IITK)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define nl cout << '\n'
#define sor(x) sort(x.begin(), x.end())
#define rev(v) reverse(v.begin(), v.end())
#define lb(v, temp) lower_bound(v.begin(), v.end(), temp)
#define ub(v, temp) upper_bound(v.begin(), v.end(), temp)
#define fi first
#define se second
#define llmax 1000000000000000000
#define deb(x) cout << #x << " " << x << "\n"
#define pll pair<ll, ll> 
#define vll vector<ll> 
#define rub cout << "\n------------------------------------\n"
void read(vector<ll> &v)
{
	for (int i = 0; i < v.size(); i++)
		cin >> v[i];
}

void print(vector<ll> v)
{
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
}
ll n,m,a,b,temp,x,y;
string str;
set<ll> s;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	ll sum[n];
	map<string,int> index;
	for(int i=0;i<n;i++)
	{
	    cin>>str;
	    index[str]=i;
	    cin>>a;
	    if(i==0)
	    sum[i]=a;
	    else
	    sum[i]=sum[i-1]+a;
	}
	string s;
	cin>>s;
	cout<<sum[n-1]-sum[index[s]];
	
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int,int> P;

int main(){
  int n,k;
  cin >> n >> k;
  int a[n];
  rep(i,n)cin >> a[i];
  int sum = 0;
  rep(i,n)sum+=a[i];
  set<int> cand;
  for(int i=1;i*i<=sum;i++){
    if(sum%i!=0)continue;
    cand.insert(i);
    cand.insert(sum/i);
  }
  int ans=1;
  for(int t:cand){
    //cout << t << endl;
    int d[n];
    rep(i,n){
      d[i]=a[i]%t;
    }
    sort(d,d+n);
    ll need=0;
    {
      ll sum_mod = 0;
      rep(i,n)sum_mod+=d[i];
      int w = sum_mod/t;
      rep(i,n-w)need+=d[i];
    }
    if(need<=k)ans = t;
  }
  cout << ans << endl;
}

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

using namespace std;

int main()
{
	long long int i, j, temp, n, total, w, v;
	cin >> n >> total;

	vector<long long int> val[n];
	long long int dp[n+1][total+1];
	for(i=0;i<n;i++)
	{
		cin >> w >> v;
		val[i].push_back(v);
		val[i].push_back(w);

	}

	for(i=0;i<=n;i++)
	{

		for(j=0;j<=total;j++)
		{
			if(i==0 || j==0)
			{
				dp[i][j] = 0;
			}

			else if(val[i-1][1] <= j)
			{
				dp[i][j] = max(val[i-1][0] + dp[i-1][j-val[i-1][1]], dp[i-1][j]);
				//cout << "i: " << i << " j: " << j << " " << dp[i][j] << endl;
			}

			else
			{
				dp[i][j] = dp[i-1][j];
			}
		}
	}

	cout << dp[n][total] << endl;

	return 0;
}

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

int main() {
    int n;
    cin >> n;
    map<string, int> ss;
    int maxi = 0;
    rep(i, n) {
        string s;
        cin >> s;
        ss[s]++;
        maxi = max(maxi, ss[s]);
    }
    for (auto s : ss) {
        if (s.second == maxi) {
            cout << s.first << endl;
        }
    }
}

Measured memory_bytes: 25216
#include<iostream>
#include<string>
#include<cmath>

using namespace std;

int main(){
  int n;
  int a[2][100];
  cin>>n;
  for(int i=0;i<2;i++){
    for(int j=0;j<n;j++){
      cin>>a[i][j];
    }
  }
  int ans = 0;
  for(int i=1;i<n;i++){
    a[0][i] += a[0][i-1];
  }
  for(int i=n-2;i>=0;i--){
    a[1][i] += a[1][i+1];
  }
  for(int i=0;i<n;i++){
    ans = max(ans,a[0][i]+a[1][i]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"os"
	"strconv"
	"fmt"
)

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r:rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf) + 1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf) + 1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}

func main() {
	sc := NewScanner()
	N, A, B := sc.NextInt(), sc.NextInt(), sc.NextInt()
	S := sc.NextLine()

	b := 0
	a := 0
	total := 0
	for i := 0; i < N; i++ {
		if S[i] == 'a' {
			a++
			if total < A + B {
				fmt.Println("Yes")
				total++
			} else {
				fmt.Println("No")
			}
		} else if S[i] == 'b' {
			if total < A + B && b < B {
				fmt.Println("Yes")
				total++
				b++
			} else {
				fmt.Println("No")
			}
		} else {
			fmt.Println("No")
		}
	}
}



Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl


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

    cout << n*(n-1)/2 << endl;
    return 0;

}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;
    ll k;
    ll x1,x2,y1,y2;
    cin >> x1 >> y1 >> x2 >> y2 ;
    ll difx = x2 - x1;
    ll dify = y2 - y1;
    ll x3 = x2 - dify;
    ll y3 = y2 +difx;
    ll x4 = x3 -difx;
    ll y4 = y3 - dify;
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;

int main(){
  int H, W, D;
  cin >> H >> W >> D;
  vector<vector<int>> A(H, vector<int>(W));
  rep(i,H)rep(j,W) cin >> A[i][j];
  int Q;
  cin >> Q;
  vector<int> l(Q), r(Q);
  rep(i,Q){
    cin >> l[i] >> r[i];
    l[i]--; r[i]--;
  }
  vector<pair<int, int>> num(H*W);
  rep(i,H)rep(j,W) num[A[i][j]-1] = {i, j};
  vector<int> sum(H*W+1);
  for(int i=1; i<=H*W; i++){
    if(i-D>=0)
      sum[i] = sum[i-D]+abs(num[i].first-num[i-D].first)+abs(num[i].second-num[i-D].second);
  }
  rep(i,Q)
    cout << sum[r[i]]-sum[l[i]] << endl;
  return 0;
}

Measured memory_bytes: 3328
#include<stdio.h>
int main() {
	int H, W;
	int i, j;

    scanf("%d%d", &H, &W);
	while (H != 0 || W != 0) {
		for (i = 0; i < H; i++) {
			for (j = 0; j < W; j++) {
				if ((i + j) % 2 == 0)printf("#");
				else printf(".");
			} printf("\n");
		}
		printf("\n");
		scanf("%d%d", &H, &W);
	}return 0;
}

Measured memory_bytes: 572
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N int
	fmt.Scan(&N)

	inputs := scanInputs(N)
	sort.Stable(ByName(inputs))
	city := make([]Result, 0)
	city = append(city, inputs[0])
	for i := 1; i < N; i++ {
		// fmt.Println(inputs[i].City, city[len(city)-1].City)
		if city[len(city)-1].City != inputs[i].City {
			// fmt.Println(city)
			sort.Sort(sort.Reverse(ByPoint(city)))
			for _, v := range city {
				fmt.Println(v.Num)
			}
			city = make([]Result, 0)
		}
		city = append(city, inputs[i])
	}
	// fmt.Println(city)
	sort.Sort(sort.Reverse(ByPoint(city)))
	for _, v := range city {
		fmt.Println(v.Num)
	}
	city = make([]Result, 0)

}

type ByPoint []Result

func (a ByPoint) Len() int           { return len(a) }
func (a ByPoint) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByPoint) Less(i, j int) bool { return a[i].Point < a[j].Point }

type ByName []Result

func (b ByName) Len() int           { return len(b) }
func (b ByName) Swap(i, j int)      { b[i], b[j] = b[j], b[i] }
func (b ByName) Less(i, j int) bool { return b[i].City < b[j].City }

type Result struct {
	City  string
	Point int
	Num   int
}

func scanInputs(len int) (results []Result) {
	var city string
	var point int
	for i := 0; i < len; i++ {
		fmt.Scan(&city, &point)
		results = append(results, Result{city, point, i + 1})
	}
	return
}


Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>
#include<math.h>

typedef int32_t i32;
typedef int64_t i64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))
#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))
#define SORT(a,num,cmp) qsort((a),(num),sizeof(*(a)),cmp)

#define F 4

const i32 mod[F] = {1000001011,1000001021,1000001053,1000001087};
const i32 rad = 100000;

i32 mod_pow (i32 r, i32 n, i32 mod) {
  i64 t = 1;
  i64 s = r;
  while (n > 0) {
    if (n & 1) t = t * s % mod;
    s = s * s % mod;
    n >>= 1;
  }
  return t;
}

void query (i32 **dp, i32 l, i32 r, i32 *res) {
  for (i32 i = 0; i < F; ++i) {
    res[i] = (dp[l][i] - (i64) dp[r][i] * mod_pow (rad, r - l, mod[i]) % mod[i] + mod[i]) % mod[i];
  }
}

i32 equal (i32 *a, i32 *b) {
  for (i32 i = 0; i < F; ++i) {
    if (a[i] != b[i]) {
      return 0;
    }
  }
  return 1;
}

void run (void) {
  const i32 LEN = 500000;
  char *s = ALLOC (3 * LEN + 1, char);
  char *t = ALLOC (LEN + 1, char);
  scanf ("%s%s", s, t);
  i32 n = strlen (s);
  i32 m = strlen (t);
  const i32 d = n;
  while (n < 2 * m || n < 2 * d) {
    memcpy (s + n, s, sizeof (char) * d);
    n += d;
  }
  i32 **hash = ALLOC (n + 1, i32 *);
  {
    i32 *buf = ALLOC (F * (n + 1), i32);
    for (i32 i = 0; i <= n; ++i) {
      hash[i] = buf;
      buf += F;
    }
  }
  for (i32 i = n - 1; i >= 0; --i) {
    for (i32 j = 0; j < F; ++j) {
      hash[i][j] = ((i64) rad * hash[i + 1][j] + s[i] - 'a' + 1) % mod[j];
    }
  }
  i32 hash_t[F] = {0, 0, 0, 0};
  for (i32 i = m - 1; i >= 0; --i) {
    for (i32 j = 0; j < F; ++j) {
      hash_t[j] = ((i64) rad * hash_t[j] + t[i] - 'a' + 1) % mod[j];
    }
  }
  i32 *dp = ALLOC (n, i32);
  for (i32 i = 0; i < n; ++i) {
    dp[i] = -1;
  }
  i32 ans = 0;
  for (i32 i = 0; i < d; ++i) {
    if (dp[i] >= 0) continue;
    dp[i] = -2;
    i32 now = i;
    i32 k = 0;
    i32 hash_s[F];
    query (hash, i, i + m, hash_s);
    while (equal (hash_s, hash_t)) {
      ++k;
      now = (now + m) % d;
      if (dp[now] >= 0) {
        k += dp[now];
        break;
      }
      if (dp[now] == -2) {
        puts ("-1");
        return;
      }
      dp[now] = -2;
      query (hash, now, now + m, hash_s);
    }
    ans = MAX (ans, k);
    dp[i] = k;
    query (hash, i, i + m, hash_s);
    now = i;
    while (equal (hash_s, hash_t)) {
      --k;
      now = (now + m) % d;
      if (dp[now] >= 0) break;
      dp[now] = k;
      query (hash, now, now + m, hash_s);
    }
    if (dp[now] < 0) dp[now] = 0;
  }
  printf ("%" PRIi32 "\n", ans);
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 43136
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n,h;
    cin>>n>>h;
    vector<ll> a(n),b(n);
    rep(i,n) cin>>a[i]>>b[i];
    sort(all(a),greater<ll>());
    sort(all(b),greater<ll>());
    ll sum=0,cnt=0,now=0;
    while(1){
        if(b[now]>a[0]){
            sum+=b[now];
            now++;
            cnt++;
            if(sum>=h) break;
        }else{
            cnt+=(h-sum+a[0]-1)/a[0];
            break;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

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

using namespace std;

const int N=3e5+5;

int coh[N],cow[N];
int n,m,k;
map< pair<int,int> , int> got;

int main()
{
	scanf("%d %d %d",&n,&m,&k);
	int mxh=0,mxc=0;
	for(int i=0;i<k;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		coh[x]++; cow[y]++;
		mxh=max(mxh,coh[x]); mxc=max(mxc,cow[y]);
		got[{x,y}]++;
	}
	vector<int> a,b;
	for(int i=1;i<=n;i++)
		if(coh[i]==mxh) a.push_back(i);
	for(int i=1;i<=m;i++)
		if(cow[i]==mxc) b.push_back(i);
	if(1LL*a.size()*b.size()>k) printf("%d\n",mxh+mxc);
	else
	{
		int add=1;
		for(int i:a)
			for(int j:b)
				add=min(add,got[{i,j}]);
		printf("%d\n",mxh+mxc-add);
	}
}

Measured memory_bytes: 28528
S = list(input())
lst=[]
for i in range(len(S)):
    if S[i]!="A" and S[i]!="C" and S[i]!="T" and S[i]!="G":
        lst.append(i)
lst.insert(0,-1)
lst.append(len(S))
dif=[]
for j in range(len(lst) - 1):
    dif.append(lst[j+1] - lst[j])

ans = max(dif) - 1
print(ans)




Measured memory_bytes: 3064
#include <stdio.h>
#include <iostream>
using namespace std;

#define H_MAX 1400
#define W_MAX 1400
#define NIL -1

int H, W;
int DP[H_MAX + 1][W_MAX + 1];
int TILE[H_MAX + 1][W_MAX + 1];

int main(){
    scanf("%d", &H);
    scanf("%d", &W);

    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            scanf("%d", &TILE[i][j]);
        }
    }

    for(int i = 0; i <= H; i++){
        TILE[i][0] = 0;
    }
    for(int j = 0; j <= W; j++){
        TILE[0][j] = 0;
    }

    int m = 0;
    for(int k = 2; k <= H + W; k++){
        for(int i = 1; i <= H && 1 <= k - i; i++){
            if(W < k - i) continue;
            if(TILE[i][k - i] == 1){
                DP[i][k - i] = 0;
            }else{
                DP[i][k - i] = min(DP[i - 1][k - i], min(DP[i - 1][k - i - 1], DP[i][k - i - 1])) + 1;
            }
            m = max(m, DP[i][k - i]);
        }
    }

    /*
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            printf("%d ", DP[i][j]);
        }
        printf("\n");
    }
    */

    printf("%d\n", m * m);
}



Measured memory_bytes: 18524
/* ex3_3
   tamayama */

#include<stdio.h>
 int main (void){
 
    int N,K;
    int input_K;
    int digit=1;
    scanf("%d %d",&N,&K);
    input_K = K;

    while(K <= N){  /*Nを超えないように何回KをK倍したかを求める*/
    K = input_K*K;  /*もとのKの値をinput_KとおいてKと区別*/
    digit++;
    }
    printf("%d\n",digit);

   return 0;
}


Measured memory_bytes: 128
while True:
    result = set()
    n, x = map(int, raw_input().split())
    if n == 0 and x == 0:
        break
    else:
        for i in range(1, n + 1):
            for j in range(i, n + 1):
                for k in range(j, n + 1):
                    if i + j + k == x and i != j and j != k and k != i:
                        temp = [i, j, k]
                        sorted(temp)
                        temp = tuple(temp)
                        result.add(temp)
        print(len(result))

Measured memory_bytes: 6496
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

ll n, m, l, dp[310][310], s[310][310], t[310][310];
int main() {
	REP(i, 310) {
		REP(j, 310) {
			if (i != j) {
				s[i][j] = INF;
				t[i][j] = INF;
			}
		}
	}
	cin >> n >> m >> l;
	REP(i, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		s[a][b] = c;
		s[b][a] = c;
	}
	REP(k, n) {
		REP(i, n) {
			REP(j, n) {
				if (s[i][k] + s[k][j] < s[i][j]) s[i][j] = s[i][k] + s[k][j];
			}
		}
	}
	REP(i, n) {
		REP(j, n){
			if (s[i][j] <= l) t[i][j] = 1;
		}
	}
	REP(k, n) {
		REP(i, n) {
			REP(j, n) {
				if (t[i][k] + t[k][j] < t[i][j]) t[i][j] = t[i][k] + t[k][j];
			}
		}
	}

	ll q;
	cin >> q;
	REP(i, q) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		if (t[a][b] == INF)cout << -1 << endl;
		else cout << t[a][b] - 1 << endl;
	}
}


Measured memory_bytes: 2048
/*
⣿⣿⣿⣿⣿⣿⡷⣯⢿⣿⣷⣻⢯⣿⡽⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠸⣿⣿⣆⠹⣿⣿⢾⣟⣯⣿⣿⣿⣿⣿⣿⣽⣻⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣻⣽⡿⣿⣎⠙⣿⣞⣷⡌⢻⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⡄⠹⣿⣿⡆⠻⣿⣟⣯⡿⣽⡿⣿⣿⣿⣿⣽⡷⣯⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣟⣷⣿⣿⣿⡀⠹⣟⣾⣟⣆⠹⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢠⡘⣿⣿⡄⠉⢿⣿⣽⡷⣿⣻⣿⣿⣿⣿⡝⣷⣯⢿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣯⢿⣾⢿⣿⡄⢄⠘⢿⣞⡿⣧⡈⢷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣧⠘⣿⣷⠈⣦⠙⢿⣽⣷⣻⣽⣿⣿⣿⣿⣌⢿⣯⢿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣟⣯⣿⢿⣿⡆⢸⡷⡈⢻⡽⣷⡷⡄⠻⣽⣿⣿⡿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣏⢰⣯⢷⠈⣿⡆⢹⢷⡌⠻⡾⢋⣱⣯⣿⣿⣿⣿⡆⢻⡿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡎⣿⢾⡿⣿⡆⢸⣽⢻⣄⠹⣷⣟⣿⣄⠹⣟⣿⣿⣟⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⢸⣯⣟⣧⠘⣷⠈⡯⠛⢀⡐⢾⣟⣷⣻⣿⣿⣿⡿⡌⢿⣻⣿⣿
⣿⣿⣿⣿⣿⣿⣧⢸⡿⣟⣿⡇⢸⣯⣟⣮⢧⡈⢿⣞⡿⣦⠘⠏⣹⣿⣽⢿⣿⣿⣿⣿⣯⣿⣿⣿⡇⢸⣿⣿⣾⡆⠹⢀⣠⣾⣟⣷⡈⢿⣞⣯⢿⣿⣿⣿⢷⠘⣯⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡈⣿⢿⣽⡇⠘⠛⠛⠛⠓⠓⠈⠛⠛⠟⠇⢀⢿⣻⣿⣯⢿⣿⣿⣿⣷⢿⣿⣿⠁⣾⣿⣿⣿⣧⡄⠇⣹⣿⣾⣯⣿⡄⠻⣽⣯⢿⣻⣿⣿⡇⢹⣾⣿
⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⡽⡇⢸⣿⣿⣿⣿⣿⣞⣆⠰⣶⣶⡄⢀⢻⡿⣯⣿⡽⣿⣿⣿⢯⣟⡿⢀⣿⣿⣿⣿⣿⣧⠐⣸⣿⣿⣷⣿⣿⣆⠹⣯⣿⣻⣿⣿⣿⢀⣿⢿
⣿⣿⣿⣿⣿⣿⣿⣿⠘⣯⡿⡇⢸⣿⣿⣿⣿⣿⣿⣿⣧⡈⢿⣳⠘⡄⠻⣿⢾⣽⣟⡿⣿⢯⣿⡇⢸⣿⣿⣿⣿⣿⣿⡀⢾⣿⣿⣿⣿⣿⣿⣆⠹⣾⣷⣻⣿⡿⡇⢸⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⠇⢸⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠻⡇⢹⣆⠹⣟⣾⣽⣻⣟⣿⣽⠁⣾⣿⣿⣿⣿⣿⣿⣇⣿⣿⠿⠛⠛⠉⠙⠋⢀⠁⢘⣯⣿⣿⣧⠘⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡈⣿⡃⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡙⠌⣿⣆⠘⣿⣞⡿⣞⡿⡞⢠⣿⣿⣿⣿⣿⡿⠛⠉⠁⢀⣀⣠⣤⣤⣶⣶⣶⡆⢻⣽⣞⡿⣷⠈⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠘⠁⠉⠉⠉⠉⠉⠉⠉⠉⠉⠙⠛⠛⢿⣄⢻⣿⣧⠘⢯⣟⡿⣽⠁⣾⣿⣿⣿⣿⣿⡃⢀⢀⠘⠛⠿⢿⣻⣟⣯⣽⣻⣵⡀⢿⣯⣟⣿⢀⣿
⣿⣿⣿⣟⣿⣿⣿⣿⣶⣶⡆⢀⣿⣾⣿⣾⣷⣿⣶⠿⠚⠉⢀⢀⣤⣿⣷⣿⣿⣷⡈⢿⣻⢃⣼⣿⣿⣿⣿⣻⣿⣿⣿⡶⣦⣤⣄⣀⡀⠉⠛⠛⠷⣯⣳⠈⣾⡽⣾⢀⣿
⣿⢿⣿⣿⣻⣿⣿⣿⣿⣿⡿⠐⣿⣿⣿⣿⠿⠋⠁⢀⢀⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣌⣥⣾⡿⣿⣿⣷⣿⣿⢿⣷⣿⣿⣟⣾⣽⣳⢯⣟⣶⣦⣤⡾⣟⣦⠘⣿⢾⡁⢺
⣿⣻⣿⣿⡷⣿⣿⣿⣿⣿⡗⣦⠸⡿⠋⠁⢀⢀⣠⣴⢿⣿⣽⣻⢽⣾⣟⣷⣿⣟⣿⣿⣿⣳⠿⣵⣧⣼⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣽⣳⣯⣿⣿⣿⣽⢀⢷⣻⠄⠘
⣿⢷⣻⣿⣿⣷⣻⣿⣿⣿⡷⠛⣁⢀⣀⣤⣶⣿⣛⡿⣿⣮⣽⡻⣿⣮⣽⣻⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢀⢸⣿⢀⡆
⠸⣟⣯⣿⣿⣷⢿⣽⣿⣿⣷⣿⣷⣆⠹⣿⣶⣯⠿⣿⣶⣟⣻⢿⣷⣽⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢀⣯⣟⢀⡇
⣇⠹⣟⣾⣻⣿⣿⢾⡽⣿⣿⣿⣿⣿⣆⢹⣶⣿⣻⣷⣯⣟⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⡿⡇⢸⡇
⣿⣆⠹⣷⡻⣽⣿⣯⢿⣽⣻⣿⣿⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⢸⣿⠇⣼⡇
⡙⠾⣆⠹⣿⣦⠛⣿⢯⣷⢿⡽⣿⣿⣿⣿⣆⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠎⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⢀⣿⣾⣣⡿⡇
⣿⣷⡌⢦⠙⣿⣿⣌⠻⣽⢯⣿⣽⣻⣿⣿⣿⣧⠩⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⢰⢣⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⢀⢀⢿⣞⣷⢿⡇
⣿⣽⣆⠹⣧⠘⣿⣿⡷⣌⠙⢷⣯⡷⣟⣿⣿⣿⣷⡀⡹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣈⠃⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣴⡧⢀⠸⣿⡽⣿⢀
⢻⣽⣿⡄⢻⣷⡈⢿⣿⣿⢧⢀⠙⢿⣻⡾⣽⣻⣿⣿⣄⠌⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⢁⣰⣾⣟⡿⢀⡄⢿⣟⣿⢀
⡄⢿⣿⣷⢀⠹⣟⣆⠻⣿⣿⣆⢀⣀⠉⠻⣿⡽⣯⣿⣿⣷⣈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⢀⣠⠘⣯⣷⣿⡟⢀⢆⠸⣿⡟⢸
⣷⡈⢿⣿⣇⢱⡘⢿⣷⣬⣙⠿⣧⠘⣆⢀⠈⠻⣷⣟⣾⢿⣿⣆⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⣠⡞⢡⣿⢀⣿⣿⣿⠇⡄⢸⡄⢻⡇⣼
⣿⣷⡈⢿⣿⡆⢣⡀⠙⢾⣟⣿⣿⣷⡈⠂⠘⣦⡈⠿⣯⣿⢾⣿⣆⠙⠻⠿⠿⠿⠿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢋⣠⣾⡟⢠⣿⣿⢀⣿⣿⡟⢠⣿⢈⣧⠘⢠⣿
⣿⣿⣿⣄⠻⣿⡄⢳⡄⢆⡙⠾⣽⣿⣿⣆⡀⢹⡷⣄⠙⢿⣿⡾⣿⣆⢀⡀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⣀⣠⣴⡿⣯⠏⣠⣿⣿⡏⢸⣿⡿⢁⣿⣿⢀⣿⠆⢸⣿
⣿⣿⣿⣿⣦⡙⣿⣆⢻⡌⢿⣶⢤⣉⣙⣿⣷⡀⠙⠽⠷⠄⠹⣿⣟⣿⣆⢙⣋⣤⣤⣤⣄⣀⢀⢀⢀⢀⣾⣿⣟⡷⣯⡿⢃⣼⣿⣿⣿⠇⣼⡟⣡⣿⣿⣿⢀⡿⢠⠈⣿
⣿⣿⣿⣿⣿⣷⣮⣿⣿⣿⡌⠁⢤⣤⣤⣤⣬⣭⣴⣶⣶⣶⣆⠈⢻⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣷⣶⣤⣌⣉⡘⠛⠻⠶⣿⣿⣿⣿⡟⣰⣫⣴⣿⣿⣿⣿⠄⣷⣿⣿⣿
*/


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


int main()
{
    string s;
    cin >> s;
    if (s.length() == 6 and s[2] == s[3] and s[4] == s[5])
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}


Measured memory_bytes: 256
fn main() {
    proconio::input! {
        n: usize,
        a: [u64; n],
    }

    let mut r = 1000u64;
    for i in 0..n - 1{
        if a[i] < a[i + 1] {
            let s = r / a[i];
            r += s * (a[i + 1] - a[i]);
        }
    }
    println!("{}", r);
}


Measured memory_bytes: 2188
n, m, l = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
B = [list(map(int, input().split())) for _ in range(m)]
C = [[0]*l for j in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k]*B[k][j]
for i in range(n):
    print(*C[i])


Measured memory_bytes: 7044