akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX = 1e7+10;
ll n, x, m, ans;
ll pre[MAX];
unordered_map<ll, int> mp;

int main(){
    scanf("%lld%lld%lld", &n, &x, &m);
    ll op1, op2, t = 0;
    bool flag = false;
    mp[x] = 1;
    pre[1] = x;
    ans = x;
    for (ll i = 2; i <= n; i++){
        x = x * x % m;
        ans += x;
        pre[i] = pre[i-1] + x;
        if (mp[x]){
            flag = true;
            op1 = mp[x];
            op2 = i - 1;
            break;
        }
        mp[x] = i;
    }
    //cout << op1 << " " << op2 << endl;
    //cout << pre[op2] - pre[op1-1] << endl;
    //cout << pre[op1-1] << endl;
    //cout << pre[op1+242]-pre[op1-1] << endl;
    if (flag && x!=0){
        ans = pre[op1-1];
        ll sy = n - (op1 - 1);
        ll sz = op2 - op1 + 1;
        ans += sy/sz*(pre[op2]-pre[op1-1]);
        ans += pre[op1+sy%sz-1] - pre[op1-1];
    }
    printf("%lld\n", ans);
    return 0;
}


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

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  
  long long int i = min(A, B);
  int count = 0;
  while (i > 0) {
    if (A%i==0 && B%i==0) {
      count++;
      if (count == K) {
        cout << i << endl;
        break;
      }
    }
    i--;
  }
  
  return 0;
}

Measured memory_bytes: 256
n, m = gets.chomp.split(' ').map(&:to_i)
a = gets.chomp.split(' ').map(&:to_i).sort.reverse
bc =[]

0.step(m - 1) do |i|
  k = gets.chomp.split.map(&:to_i)
  bc.push({b: k[0], c:k[1]})
end

bc = bc.sort_by {|h| -1 * h[:c]}

ite_bc = 0
ite_a = 0
ans = 0

0.step(n - 1, 1) do |_i|
  if a[ite_a].to_i < bc.dig(ite_bc, :c).to_i
    ans += bc[ite_bc][:c]
    if bc[ite_bc][:b] == 1
      ite_bc += 1
    else
      bc[ite_bc][:b] -= 1
    end
  else
    ans += a[ite_a]
    ite_a += 1
  end
end
p ans

Measured memory_bytes: 41160
#include<stdio.h>
#include<ctype.h>
int main(){
  int i,c;
  int cnt[128]={0};
  while((c=getchar())!=EOF){
    if(isupper(c)){
      c=tolower(c);
    }
    cnt[c]++;
    i++;
  }
  for(i=97;i<=122;i++){
    printf("%c : %d\n",i,cnt[i]);
  }
 return 0;
}

Measured memory_bytes: 2684
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define rep(i,l,r) for(rint i=l;i<=r;i++)
#define per(i,l,r) for(rint i=l;i>=r;i--)
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define fir first
#define sec second
#define mset(s,t) memset(s,t,sizeof(s))
template<typename T1,typename T2>void ckmin(T1 &a,T2 b){if(a>b)a=b;}
template<typename T1,typename T2>void ckmax(T1 &a,T2 b){if(a<b)a=b;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
int read(){
  int x=0,f=0;
  char ch=getchar();
  while(!isdigit(ch))f|=ch=='-',ch=getchar();
  while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
  return f?-x:x;
}
#define int long long
const int N=3000005;
int n,q;
struct Seg{
  #define ls (u<<1)
  #define rs (u<<1|1)
  int minn[N],tag[N];
  void pushup(int u){
    minn[u]=min(minn[ls],minn[rs]);
  } 
  void pushdown(int u){
    if(tag[u]!=1e9){
      tag[ls]=min(tag[ls],tag[u]);
      tag[rs]=min(tag[rs],tag[u]);
      minn[ls]=min(minn[ls],tag[u]);
      minn[rs]=min(minn[rs],tag[u]);
      tag[u]=1e9;
    }
  }
  void build(int u,int l,int r){
    tag[u]=1e9,minn[u]=n;
    if(l==r)return;
    int mid=l+r>>1;
    build(ls,l,mid),build(rs,mid+1,r);
  }
  void update(int u,int l,int r,int ql,int qr,int dlt){
    pushdown(u);
    if(ql<=l&&r<=qr){
      minn[u]=min(minn[u],dlt);
      tag[u]=min(tag[u],dlt);
      return;
    }
    pushdown(u);
    int mid=l+r>>1;
    if(ql<=mid)update(ls,l,mid,ql,qr,dlt);
    if(qr>mid)update(rs,mid+1,r,ql,qr,dlt);
    pushup(u);
  }
  int query(int u,int l,int r,int pos){
    pushdown(u);
    if(l==r)return minn[u];
    int mid=l+r>>1;
    if(pos<=mid)return query(ls,l,mid,pos);
    else return query(rs,mid+1,r,pos);
  }
}row,col;
// row:行，col:列 
signed main(){
  n=read(),q=read();
  ll ans=1ll*(n-2)*(n-2);
  row.build(1,1,n);
  col.build(1,1,n);
  while(q--){
    int opt=read(),x=read();
    if(opt==1){
      int t=col.query(1,1,n,x);
      //printf("opt = 1, t=%d\n",t);
      ans-=max(0ll,t-2);
      if(t-1>=2)row.update(1,1,n,2,t-1,x);
    }else{
      int t=row.query(1,1,n,x);
      ans-=max(0ll,t-2);
      if(t-1>=2)col.update(1,1,n,2,t-1,x);
    }
    //printf("%lld\n",ans);
  }
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 34844
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int, int>
#define pll pair<long long,long long>
#define vl vector<long long>
#define vll vector<pll>
#define vi vector<int>
#define vii vector<pii>
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define tcase int tt; cin>>tt; while(tt--)
#define tcase2 int tt; cin>>tt; for(int qq=1;qq<=tt;qq++)
using namespace std;
typedef long long int ll;
typedef  unsigned long long int ull;
typedef long double ld;
const int MAXN = 1000002;
const int MOD2 = 998244353;
const int MOD = 1000000007; 
const int INF = 1e8;
const ld EPS = 1e-7;
// Extra
#define forn(i, n) for(int i = 0; i < (int)n; i++)
#define forne(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define trav(a, x) for(auto& a : x)
#define fill(x,y) memset(x,y,sizeof(x))
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
ll mul(ll x, ll y)
{
    return (x * 1ll * y) % MOD2;
}

ll fastpow(ll x, ll y)
{
    ll z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}
vector<ll>adj[100001] ;
ll m=0 ;
ll ans[100001]={0} ;
ll income[100001]={0} ;
bool visited[100001] ;
void dfs(ll x)
{   if(visited[x])
   return ;
	visited[x]=true ;
	
	for(auto u:adj[x])
	{   
		dfs(u) ;
		ans[x]=max(ans[x],1+ans[u]) ;
	
	}
}
int main(int argc, char** argv)
{   sws ;
   // tcase
    {
    ll n,m ,u,v;
    cin>>n>>m ;
    forn(i,m)
    {
    	cin>>u>>v ;
    	u--;v-- ;
    	adj[u].pb(v) ;
    	//income[v]++ ;
	}
	forn(i,n)
	visited[i]=false ;
	forn(i,n)
	{
		if(!visited[i])
		{
			dfs(i) ;
		}
	//	cout<<ans[i]<<" ";
	}
	m=0;
	forn(i,n)
	{  //cout<<ans[i]<<" ";
	    if(ans[i]>m)
	    m=ans[i] ;
	}
	cout<<m<<"\n" ;
    }
return 0 ;
}

Measured memory_bytes: 12064
#include <bits/stdc++.h>
#define ms(x, n) memset(x,n,sizeof(x));
#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define rep1(i, n) for(int i = 1; i <= (int)n; ++i)
#define pb push_back
#define PI acos(-1.0)
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;



int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    ll ans;
    cin >> n;
    ans = n * (n-1) / 2;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入力

		int n = sc.nextInt();
		
		List<Long> list = new ArrayList<>();


		for (int i = 0; i < n; i++) {
			long v = sc.nextLong();
			list.add(v);
		}
		Collections.sort(list);

		double result = 0;
		result += list.get(0) / Math.pow(2,n-1);
		result += list.get(1) / Math.pow(2,n-1);

		for (int i = 2; i < n; i++) {
			long v = list.get(i);
			result += v / Math.pow(2,n-i);
		}

		System.out.println(result);

	}
}


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

#define EQ(a,b) (abs((a)-(b)) < EPS)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define sz size()
#define all(a) (a).begin(),(a).end()

using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
typedef pair<D,int> pdi;

const D EPS = 1e-8;
const D PI = acos(-1);

inline D dot(P x, P y){return real(conj(x)*y);}
inline D cross(P x, P y){return imag(conj(x)*y);}

inline D seg_p_dis(L a,P x){
  if(dot(a.sc-a.fs,x-a.fs)<EPS)return abs(x-a.fs);
  if(dot(a.fs-a.sc,x-a.sc)<EPS)return abs(x-a.sc);
  return abs(cross(a.sc-a.fs,x-a.fs))/abs(a.sc-a.fs);
}

inline D seg_seg_dis(L a,L b){
  D res = 1e10;
  res = min(res,seg_p_dis(a,b.fs));
  res = min(res,seg_p_dis(a,b.sc));
  res = min(res,seg_p_dis(b,a.fs));
  res = min(res,seg_p_dis(b,a.sc));
  return res;
}

int main(){
  int w,n;
  while(cin >> w >> n){
    if(w==0)return 0;

    vector< vector<L> > l(n);
    rep(i,n){
      int m;
      cin >> m;
      vector<P> p(m);
      rep(j,m){
	int x,y;
	cin >> x >> y;
	p[j] = P(x,y);
      }
      rep(j,m){
	l[i].push_back(L(p[j],p[(j+1)%m]));
      }
    }

    int v = n+2;
    vector< vector<pdi> > g(v);
    g[v-2].pb(pdi(w,v-1));
    L ls = L(P(0,0),P(0,1e4)), lt = L(P(w,0),P(w,1e4));
    rep(i,n){
      D dis = w;
      for(L a : l[i])dis = min(dis, seg_seg_dis(ls,a));
      g[v-2].pb(pdi(dis, i));
      dis = w;
      for(L a : l[i])dis = min(dis, seg_seg_dis(lt,a));
      g[i].pb(pdi(dis,v-1));
      rep(j,i){
	dis = w;
	for(L a : l[i])for(L b : l[j]){
	    dis = min(dis, seg_seg_dis(a,b));
	  }
	g[i].pb(pdi(dis,j)); g[j].pb(pdi(dis,i));
      }
    }

    vector<D> d(v,1e9);
    d[v-2] = 0;
    priority_queue<pdi, vector<pdi>, greater<pdi> > q;
    q.push(pdi(0,v-2));
    while(q.size()){
      pdi p = q.top(); q.pop();
      D cost = p.fs;
      int cur = p.sc;

      if(cur == v-1)break;
      if(d[cur]+EPS < cost)continue;

      for(pdi nxt : g[cur]){
	D ncost = cost + nxt.fs;
	int u = nxt.sc;
	if(d[u] > ncost + EPS){
	  d[u] = ncost;
	  q.push(pdi(ncost,u));
	}
      }
    }
    cout << fixed << setprecision(9) << d[v-1] << endl;
  }
}

Measured memory_bytes: 2512
#include <iostream>
#include <vector>
int main() {
    int A,B,C,X,Y;
    std::cin >> A >> B >> C >> X >> Y;
    
    int max_num = X>Y ? X : Y;
    std::vector<int> mon_ary(max_num+1);
    for (int i=0; i <= max_num; i++) {
        int temp_A_num = X-i > 0 ? X-i : 0;
        int temp_B_num = Y-i > 0 ? Y-i : 0;
        mon_ary[i] = temp_A_num*A + temp_B_num*B + 2*i*C;
    }
    std::cout << *std::min_element(mon_ary.begin(),mon_ary.end()) << std::endl;
    return 0;
}

Measured memory_bytes: 888
N = input()
N = int(N)
A = input()
array = A.split()
ind = 0
for n in array:
    array[ind] = int(n)
    ind = ind+1

mx = max(array)
array.remove(mx)
haf = mx/2
x = [abs(e-haf) for e in array]
min_idx = x.index(min(x))
r = array[min_idx]

print(mx, r)


Measured memory_bytes: 13144
def main():
    n, k = [int(x) for x in input().split()]
    scores = [int(x) for x in input().split()]
    # zip にすると2つのリストを作るのか，これよりも少し時間とメモリ増。
    {
        print('Yes' if scores[index] < new else 'No')
        for index, new in enumerate(scores[k:])}


if __name__ == '__main__':
    main()


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

#Z algorithm

def Z_algorithm(s):
    n = len(s)
    Z = [0]*n
    Z[0] = n
    i,j = 1,0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1

        #再利用部分
        while i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

n = int(input())
s = input()

ans = 0
for i in range(n):
    z = Z_algorithm(s[i:])
    for j,k in enumerate(z):
        if j >= k:
            ans = max(ans,k)
print(ans)

Measured memory_bytes: 49628
# -*- coding: utf-8 -*-

n = int(input())

adj = [[0 for _ in range(n)] for _ in range(n)]

for _ in range(n):
    ls = list(map(int, input().split(" ")))
    f = ls[0]
    for i in range(ls[1]):
        adj[f - 1][ls[2 + i] - 1] = 1

for i in range(n):
    for j in range(n):
        print(adj[i][j], end="")
        if j < n - 1:
            print(" ", end="")
    print()


Measured memory_bytes: 7096
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}


char a[55][55];

int main(){FIN

    ll n;cin>>n;
    vll x(n), y(n);
    REP(i,n) {cin>>x[i]; y[i]=x[i];}
    VSORT(y);
    ll left = y[(n-1)/2];
    ll right = y[(n+1)/2];
    REP(i,n){
        if (x[i]<=left) cout<<right<<' ';
        else cout<<left<<' ';
    }
    cout<<endl;
    return 0;
}

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

#define fir first
#define sec second
using namespace std;
typedef long long LL;

template <typename T> inline bool cmin(T & a, const T & b) { return a > b ? a = b, 1 : 0;}
template <typename T> inline bool cmax(T & a, const T & b) { return a < b ? a = b, 1 : 0;}
int inp() {
	int x = 0, f = 1;char ch;
	for(ch = getchar(); !isdigit(ch); ch = getchar())
		if(ch == '-') f = -1;
	for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	return x * f;
}
const int MaxN = 55;
int n; LL a[MaxN], ans;
int main() {
	int i;
	n = inp();
	for(i = 1; i <= n; i++) scanf("%lld", a+i);
	for(;;) {
		LL s = 0, b = 0;
		for(i = 1; i <= n; i++) b = a[i]/n, a[i] %= n, a[i] -= b, s += b;
		if(!s) break;
		for(i = 1; i <= n; i++) a[i] += s;
		ans += s;
	}
	cout << ans;
	return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (int i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

template<typename T>
void say(vector<T> s, char r) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << r << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("yes");
	else say("no");
}

void Yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

void YN(bool b) {
	if (b)say("YES");
	else say("NO");
}

template<typename T>
void maxi(T& a, T b) {
	a = max(a, b);
}

template<typename T>
void mini(T& a, T b) {
	a = min(a, b);
}

void exact_say(double x) {
	cout << setprecision(numeric_limits<double>::max_digits10) << x << endl;
}

template<class T> void getVector(vector<T>& v) {
	for (int i = 0; i < v.size(); ++i)
		cin >> v[i];
}

std::string revString(std::string s) {
	string ret;
	auto it = s.rend();
	while (it != s.rbegin()) {
		ret.push_back(*it);
		++it;
	}
	return ret;
}

vector<vvi> init() {
	vi v;
	rep(10)v.push_back(0);
	vvi vv;
	rep(3)vv.push_back(v);
	vector<vvi> vvv;
	rep(4)vvv.push_back(vv);
	return vvv;
}

char eval(int m, int f, int r) {
	if (m == -1 || f == -1)return 'F';
	else if (m + f >= 80)return 'A';
	else if (m + f >= 65)return 'B';
	else if (m + f >= 50)return 'C';
	else if (m + f >= 30) {
		if (r >= 50)return 'C';
		else return 'D';
	}
	else return 'F';
}

signed main() {
	while (true) {
		int m, f, r;
		cin >> m >> f >> r;
		if (m == -1 && f == -1 && r == -1)return 0;
		say(eval(m, f, r));
	}
}


Measured memory_bytes: 3020
def read_input():
    s = input()
    return s

def submit():
    s = read_input()
    char_occurs = {}

    for c in s:
        if c in char_occurs.keys():
            print('no')
            return
        else:
            char_occurs[c] = 1

    print('yes')

if __name__ == '__main__':
    submit()

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

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

  if(n <= 10 || n == 12 || n == 14 || n == 15 || n == 16 || n == 18 || n == 20 || n == 21 || n == 24 || n == 25 || n == 27|| n == 28 || n == 30 || n == 32 || n == 35 || n == 36 || n == 40 || n == 42 || n == 45 || n == 48 || n == 49 || n == 54 || n == 56 || n == 63 || n == 64 || n == 72 || n == 81){
    cout << "Yes";
  }else{
    cout << "No";
  }
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;

	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), m = sc.nextInt();
		int max = m;
		boolean f = true;
		for(int i=0;i<n;i++) {
			m += sc.nextInt() - sc.nextInt();
			if(m < 0) f = false;
			max = max(max, m);
		}
		System.out.println((f? max: 0));
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

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

Measured memory_bytes: 41944
n,a,b  =map(int,input().split())
se = a+b
br = 0
cnt = 0
if a == 0:
    print(0)
elif b == 0:
    print(n)
else:
    cnt = n//se
    if cnt == 0:
        if n < a:
            print(n)
        else:
            print(a)
    else:
        res = a*cnt
        n -= se*cnt
        if n <= a:
            res += n
        else:
            res += a
        print(res)


Measured memory_bytes: 3060
#include<algorithm>
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

vector<ll> getDivisorsList(ll n)
{
    vector<ll> ret;

    for (ll i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }

    sort(begin(ret), end(ret));
    return ret;
}

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

    int N, M;
    cin >> N >> M;

    auto lst = getDivisorsList(M);

    auto itr = lower_bound(all(lst), N);

    if (itr != lst.end())
    {
        cout << M / *itr << endl;
    }
    else
    {
        cout << 1 << endl;
    }

    return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout << fixed;
	string s;
	cin >> s;
	if (s[s.length() - 1] == 's')
		s += "es";
	else
		s += "s";
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 3612
N, K = map(int, input().split())
H = list(map(int, input().split()))

inf =10**13

dp = [inf] * N
dp[0] = 0

for i in range(N):
    d = dp[i]
    h = H[i]
    for j in range(i+1, min(N, i+K+1)):
        dp[j] = min(dp[j], d + abs(h - H[j]))

print(dp[-1])

Measured memory_bytes: 52448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const double PI = acos(-1);  



int main(){
  ll n; cin >> n;
  vector<ll> a(n);
  map<ll, ll> mp;

  for(int i=0; i<n; i++)  cin >> a.at(i);
  ll ans=0;
  for(ll i=0; i<n; i++){
    ans += mp[i-a[i]];
    mp[i+a[i]] += 1;
  }

  cout << ans << endl;
  
    
}

Measured memory_bytes: 27456
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int num;
	cin>>num;
	int coli[110]={0};
	int i;
	int ans=0;	
	for(i=0;i<num;i++)
	{
		cin>>coli[i];
	}
	for(i=1;i<num;i++)
	{
		if(coli[i-1]==coli[i])
		{
			coli[i]=10000+i;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}

import Data.Bool (bool)

main :: IO ()
main = do
    n  <- read <$> getLine
    xs <- fmap read . words <$> getLine
    answer $ solve n xs

type Answer = Int
answer :: Answer -> IO ()
answer = print

solve :: Int -> [Int] -> Int
solve n = bin 2 (2 * n - 2)
  where
    bin l g
      | l == g    = const g
      | r == 1    = bool l g . gte g
      | otherwise = bool . bin l (m - 1) <*> bin m g <*> gte m
      where
        r = g - l
        m = l + r `div` 2
    gte x = go . foldr ((:) . (x <=)) []
    go (x : y : xs)
      | x == y    = left   2 x y $ zip [3 ..] xs
      | otherwise = left   0 x y $ zip [3 ..] xs
    left !l !w z xs@((i, x) : xs')
      | i >= n    = middle l w z xs
      | z /= x    = left   l w x xs'
      | otherwise = left   i x x xs'
    middle l w z xs@((i, x) : xs')
      | i >  n    = right  m w z xs
      | z /= x    = right  m w x xs'
      | otherwise = x
      where
        m = 2 * n - l
    right m w z [(i, x)]
      | z /= x    = w
      | otherwise = x
    right m w z ((i, x) : xs)
      | i >  m    = w
      | z /= x    = right m w x xs
      | otherwise = x


Measured memory_bytes: 84348
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VV(T, a, b, c) vector<vector<T>>(a, vector<T>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define VVV(T, a, b, c, d)                                                     \
  vector<vector<vector<T>>>(a, vector<vector<T>>(b, vector<T>(c, d)))
#define SP(a) fixed << setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N, X, T;
  cin >> N >> X >> T;
  cout << ((N + X - 1) / X) * T << endl;

  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define all(c) (c).begin(), (c).end()

bool solve(string& s){
    s.erase(remove_if(all(s), [](char c){return string("()[]").find(c) == string::npos;}), s.end());
    vector<char> st;
    for(auto c: s){
        if(c == '(' || c == '[')st.push_back(c);
        else if(st.empty() || st.back() != (c == ')'? '(': '['))return false;
        else st.pop_back();
    }
    return st.empty();
}

vector<string> split(const string& in, char delim){
    istringstream stream(in);
    string field;
    vector<string> res;
    while(getline(stream, field, delim) && !field.empty())res.push_back(field);
    return res;
}

int main(){
    string buf = "";
    for(string line; getline(cin, line); line.erase(remove(all(line), '\n'), line.end()), buf += line);
    for(auto s: split(buf, '.'))cout << (solve(s)? "yes\n": "no\n");
    return 0;
}

Measured memory_bytes: 2072
#include<stdio.h>
#define MAX 100005
#define NIL -1

struct Node{ int p, l, r, dg,d, s, h;};
struct Node T[MAX]; // Tree

int count1 = 0, n;
int getdepth(int);
void  prinr(int);
int getheight(int, int);

int getdepth(int d){

  if(d == NIL){
    return count1;
  }

  else{
    count1++;
    return getdepth(T[d].p);
  }

}

int getheight(int h, int c){

  int a=0, b=0;
  
  if(T[h].r != NIL){
    a = getheight(T[h].r, c+1);
  }
  
  if(T[h].l != NIL){
    b = getheight(T[h].l, c+1);
  } 
  
  if(T[h].l == NIL && T[h].r == NIL){
    return c;
  }
  
  if(a>=b){
    return a;
  }
  return b;
  
}
  

void print(int u){
 
  printf("node %d:", u);
  
  printf(" parent = %d,", T[u].p);
  
  printf(" sibling = %d,", T[u].s);

  printf(" degree = %d,", T[u].dg);

  printf(" depth = %d,", T[u].d);

  printf(" height = %d,", T[u].h);

  prinr(u);

    printf("\n");


}


void prinr(int u){

  if(T[u].p == NIL){
    printf(" root");
  }
  
  else if(T[u].dg == 0){
    printf(" leaf");
  }

  else{
    printf(" internal node");
  }

}

main(){
  int i, j, d, v, c, l, r;

  scanf("%d", &n);

  for ( i = 0; i < n; i++ ) {
    T[i].p = T[i].l = T[i].r = T[i].dg = T[i].s = NIL;
  }

  for ( i = 0; i < n; i++ ){
    c=0;
    scanf("%d %d %d", &v, &l, &r);

    T[v].l = l;
    T[v].r = r;

    T[l].p = v;
    T[l].s = r;

    T[r].p = v;
    T[r].s = l;

    if(l == NIL){
      c++;
    } 
    if(r == NIL){
      c++;
    }

    if(c == 0){
      T[v].dg = 2;
    }
    else if(c == 1){
      T[v].dg = 1;
    }
    else{
      T[v].dg = 0;
    }

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

    T[i].d  = getdepth(T[i].p);
    T[i].h = getheight(i, 0);

  }

  for ( i = 0; i < n; i++ ) print(i);
  return 0;
}

Measured memory_bytes: 608
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e18
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

const int MAX = 2000010;
const int MOD = 1000000007;

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

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll add(ll x, ll y)
{
    x += y;
    if (x >= MOD)
        return x - MOD;
    return x;
}
ll sub(ll x, ll y)
{
    x -= y;
    if (x < 0)
        return x + MOD;
    return x;
}
ll mult(ll x, ll y)
{
    return (x * y) % MOD;
}
ll bin_pow(ll x, ll p)
{
    if (p == 0)
        return 1;
    if (p & 1)
        return mult(x, bin_pow(x, p - 1));
    return bin_pow(mult(x, x), p / 2);
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin>>k;
    string s;
    cin>>s;
    int N=(int)s.size()+k;
    int n=(int)s.size();
    COMinit();
    int ans=0;
    for (int i = n; i <= N; i++)
    {
        int x=bin_pow(25,i-n);
        int y=bin_pow(26, N - i);
        int z=COM(i-1, n-1);
       // cerr<<i-n<<" "<<N-i<<" "<<z<<" "<<ans<<endl;
        ans+= mult(z,mult(x,y));
        ans%=MOD;

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

Measured memory_bytes: 51220
h,w = map(int,input().split())
from collections import Counter
s = [[] for i in range(h)]
for i in range(h):
    s[i] = input()

ss = []
for i in range(h):
    for j in range(w):
        ss.append(s[i][j])
            
b = Counter(ss)
odd = 0
    
if h % 2 == 0 and w % 2 == 0:
    fl = 1
    for i in b:
        if b[i] % 4 != 0:
            fl = 0
            
    if fl == 1:
        print("Yes")
    else:
        print("No")
        
elif h % 2 == 1 and w % 2 == 0:
    flsum = 0
    for i in b:
        flsum += b[i] % 4
        if b[i] % 2 == 1:
            odd += 1
        
    if odd != 0:
        print("No")
    elif flsum >= 0 and flsum <= w:
        print("Yes")
    else:
        print("No")
        
elif h % 2 == 0 and w % 2 == 1:
    flsum = 0
    for i in b:
        flsum += b[i] % 4
        if b[i] % 2 == 1:
            odd += 1
        
    if odd != 0:
        print("No")
    elif flsum >= 0 and flsum <= h:
        print("Yes")
    else:
        print("No")
        
else:
    flsum = 0
    for i in b:
        flsum += b[i] % 4
        if b[i] % 2 == 1:
            odd += 1
        
    if odd != 1:
        print("No")
    elif flsum >= 0 and flsum <= h+w-1:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 39280
#include <stdio.h>
int main() {
	
	int num, fnt, mdl, bck;
	scanf("%d", &num);
	
	fnt = num / 100;
	mdl = num / 10 % 10;
	bck = num % 100 % 10;
	
	if (fnt != 7){
		if (mdl != 7){
			if (bck != 7){
				printf("No");
			}
			else printf("Yes");
		}
		else printf("Yes");
	}
	else printf("Yes");

	
	return 0;
}

Measured memory_bytes: 1736
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n;
	int m;
	string s;
	int i;
	int cnt;
	vector<int>v;
	int flg;
	int sum;
	int x;
	while(1){
		cin>>n;
		if(n==0)	break;
		cin>>m;
		cin>>s;
		v.clear();
		i=0;
		cnt=0;
		while(s.size()-1>i){
			flg=0;
			if(s[i]=='I'){
				if(s[i+1]=='O'){
					if(s[i+2]=='I'){
						cnt++;
						flg=1;
						i+=2;
					}
				} 
			}
			if(flg==0){
				if(cnt!=0){
					v.push_back(cnt);
				}
				cnt=0;
				i++;
			}
		}
		/* for(i=0;i<v.size();i++){
			cout<<v[i]<<endl;
		} */
		sum=0;
		for(i=0;i<v.size();i++){
			if(v[i]+1-n>=0){
				sum+=v[i]+1-n;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}


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

long long llabs(long long int n);

int main(){
    long long N,K;
    long long tmp;
    cin>>N>>K;
    long long t=N%K;
    tmp=min(t,K-t);
    cout<<tmp<<endl;
}

Measured memory_bytes: 3620
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  const int N = 100000;
  vector<int> is_prime(N + 1, 1);
  is_prime[0] = 0;
  is_prime[1] = 0;
  for (int i = 2; i <= N; i++) {
    if (!is_prime[i]) continue;
    for (int j = i * 2; j <= N; j += i) {
      is_prime[j] = 0;
    }
  }

  vector<int64_t> s(N + 1);
  for (int i = 0; i < N; i++) {
    int x = is_prime[i] && is_prime[(i + 1) / 2];
    s[i + 1] = s[i] + x;
  }
  int q;
  cin >> q;
  int l, r;
  for (int i = 0; i < q; i++) {
    cin >> l >> r;
    cout << s[r + 1] - s[l] << endl;
  }
  return 0;
}


Measured memory_bytes: 1792
import scala.io.StdIn.{readLine, readInt}
import scala.util.control.Breaks
import scala.collection.mutable.BitSet

object Main {
  val b = new Breaks

  def check(board:Array[Array[String]], i:Int, j:Int) = {
    var k = i
    var l = j
    var flg = board(i)(j) == "."

    while(flg && k>=0 && l>=0) {
      if(board(k)(l)!=".") flg = false
      k-=1;l-=1
    }

    k = i;l = j
    while(flg && k<8 && l<8) {
      if(board(k)(l)!=".") flg = false
      k+=1;l+=1
    }

    k = i;l = j
    while(flg && k<8 && l>=0) {
      if(board(k)(l)!=".") flg = false
      k+=1;l-=1
    }

    k = i;l = j
    while(flg && k>=0 && l<8) {
      if(board(k)(l)!=".") flg = false
      k-=1;l+=1
    }
    flg
  }

  def scan(board:Array[Array[String]],x:BitSet,y:BitSet):Boolean = {
    if(!x.isEmpty || !y.isEmpty) {
      var flg = false
      b.breakable {
        for(i<-x) {
          for(j<-y) {
            if(check(board,i,j)) {
              board(i)(j)="Q"
              if(scan(board,x-i,y-j)) {
                flg = true
                b.break
              } else {
                board(i)(j)="."
              }
            }
          }
        }
      }
      flg
    } else {
      true
    }
  }

  def main(args:Array[String]) = {
    val n = readInt
    val board = Array.ofDim[String](8,8)
    val x = BitSet(0,1,2,3,4,5,6,7)
    val y = BitSet(0,1,2,3,4,5,6,7)
    for(i<-0 to 7;j<-0 to 7) board(i)(j) = "."

    for(i<-0 until n) {
      val s = readLine.split(" ").map(_.toInt)
      board(s(0))(s(1)) = "Q"
      x -= s(0)
      y -= s(1)
    }
    scan(board,x,y)
    board.foreach( e=> println(e.mkString("")) )
  }
}

Measured memory_bytes: 47788
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  rep(i, n){
    double x[3], y[3];
    rep(j, 3){
      cin >> x[j] >> y[j];
    }
    int tmp = 0;
    while(x[tmp] == x[(tmp + 1) % 3] || x[tmp] == x[(tmp + 2) % 3]){
      swap(x[0], x[tmp]);
      swap(y[0], y[tmp]);
      tmp++;
    }
    double yc = (((x[0] - x[2]) * (x[0] * x[0] + y[0] * y[0] - x[1] * x[1] - y[1] * y[1])) \
                - ((x[0] - x[1]) * (x[0] * x[0] + y[0] * y[0] - x[2] * x[2] - y[2] * y[2]))) \
                / ((x[0] - x[2]) * (y[0] - y[1]) - (x[0] - x[1]) * (y[0] - y[2])) / 2.;
    double xc = (((y[0] - y[2]) * (x[0] * x[0] + y[0] * y[0] - x[1] * x[1] - y[1] * y[1])) \
                - ((y[0] - y[1]) * (x[0] * x[0] + y[0] * y[0] - x[2] * x[2] - y[2] * y[2]))) \
                / ((y[0] - y[2]) * (x[0] - x[1]) - (y[0] - y[1]) * (x[0] - x[2])) / 2.;
    cout << setprecision(3) << fixed;
    cout << xc << " " << yc << " ";
    cout << sqrt((x[0] - xc) * (x[0] - xc) + (y[0] - yc) * (y[0] - yc)) << endl;
  }
	return 0;
}



Measured memory_bytes: 3124
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using P	  = pair<ll, ll>;
using mat = vector<vector<ll>>;
typedef string::const_iterator State;
class ParseError {};

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

constexpr ll INF = 1e16;
constexpr ll INM = 114514;
constexpr ll MOD = 1e9 + 7;
constexpr ld EPS = 1e-12;

template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, int t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll b) {
	if (a > 0) return a % b;
	if (a % b == 0) return 0;
	ll x = -a / b + 1;
	a += x * b;
	return a % b;
}
ll powm(ll a, ll b, ll c) {
	if (b == 0)
		return 1;
	else if (b % 2 == 0) {
		ll d = powm(a, b / 2, c);
		return (d * d) % c;
	} else
		return (a * powm(a, b - 1, c)) % c;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};

int n;
vector<P> g[114514];
map<int, int> color;
map<int, bool> used;

int ans = 0;

void dfs(int v, int c) {
	int cnt = 1;
	used[v] = true;
	for (int i = 0; i < g[v].size(); i++) {
		if (cnt == c) cnt++;
		if (!used[g[v][i].first]) {
			color[g[v][i].second] = cnt;
			dfs(g[v][i].first, cnt);
			ans = max(ans, cnt);
			cnt++;
		}
		//cout << g[v][i].first << " " << cnt << endl;
	}
}

int main() {
	IOS();
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		g[a].emplace_back(b, i);
		g[b].emplace_back(a, i);
	}
	dfs(1, 0);
	dump(ans);
	for (int i = 0; i < n - 1; i++) {
		dump(color[i]);
	}
	return 0;
}

Measured memory_bytes: 17664
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define pll pair<ll,ll>
#define pint pll
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int n,k;
  cin >> n >> k;
  ll s;
  cin >> s;
  ll a[n]={};
  if(s<(mod-7)){
    rep(i,k)cout << s << ' ';
    rep(i,n-k)cout << s+1 << ' ';
    cout << endl;
  }else{
    rep(i,k)cout << s << ' ';
    rep(i,n-k)cout << s-1 << ' ';
    cout << endl;
  }
return 0;}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
typedef long long ll;
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using namespace std;

//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvll = vector<vll>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------


int main() {
    int n;
    cin>>n;
    rep(i,n){
        string s1,s2;
        cin>>s1>>s2;
        
        
        vvll dp(s1.size()+1,vll(s2.size()+1));
        
        rep(i,s1.size()){
            dp.at(i).at(0)=0;
            rep(j,s2.size()){
                dp.at(0).at(j)=0;
                if(s1.at(i)==s2.at(j)){
                    dp.at(i+1).at(j+1)=(dp.at(i).at(j)+1);//,dp.at(i).at(j+1)+1);
                }else{
                    dp.at(i+1).at(j+1)=max(dp.at(i+1).at(j),dp.at(i).at(j+1));
                }
            }
        }
        cout<<dp.at(s1.size()).at(s2.size())<<endl;
    }
    
}



Measured memory_bytes: 10872
#include <iostream>
#include <vector>
#include <map>

using namespace std;


int main(int argc, char** argv) {
    long long N, M, a, b;
    cin >> N >> M;
    std::multimap<long long, long long> mp;
    for (int n = 0; n < N; ++n) {
        cin >> a >> b;
        mp.insert(make_pair(a, b));
    }
    long long sum{0};
    long long bought{0};
    for (auto m : mp) {
        if (bought + m.second > M) {
            sum += (M - bought) * m.first;
            bought = M;
            break;
        }
        sum += m.second * m.first;
        bought += m.second;
    }
    cout << sum << endl;

    return 0;
}


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

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (__typeof(a.begin()) x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define endl '\n'

int root = 0;
int n;
vector<int> c[100005];
const int K = 20;
int parent[K][100005];
int depth[100005];

void bfs(int v, int p, int d) {
  queue<tuple<int, int, int>> que;
  que.push(make_tuple(v, p, d));
  while (!que.empty()) {
    auto ele = que.front(); que.pop();
    int vv = get<0>(ele), pp = get<1>(ele), dd = get<2>(ele);
    parent[0][vv] = pp;
    depth[vv] = dd;
    for (auto i: c[vv]) {
      que.push(make_tuple(i, vv, dd + 1));
    }
  }
}

void init() {
  bfs(root, -1, 0);
  for (int k = 0; k + 1 < K; k++) {
    for (int v = 0; v < n; v++) {
      if (parent[k][v] < 0) parent[k + 1][v] = -1;
      else parent[k + 1][v] = parent[k][parent[k][v]];
    }
  }
}

int lca(int u, int v) {
  if (depth[u] > depth[v]) swap(u, v);
  for (int k; k < K; k++) {
    if ((depth[v] - depth[u] >> k & 1)) {
      v = parent[k][v];
    } 
    if (u == v) return u;
  }
  for (int k = K - 1; k >= 0; k--) {
    if (parent[k][u] != parent[k][v]) {
      u = parent[k][u];
      v = parent[k][v];
    }
  }
  return parent[0][u];
}

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

  cin >> n;
  rep(i, n) {
    int k;
    cin >> k;
    rep(j, k) {
      int cj;
      cin >> cj;
      c[i].push_back(cj);
    }
  }

  init();

  int q;
  cin >> q;
  rep(i, q) {
    int u, v;
    cin >> u >> v;
    cout << lca(u, v) << endl;
  }

  return 0;
}

Measured memory_bytes: 16808
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll a,b;
    cin >>  a >> b;
    if(a > 9 || b > 9 || a < 1 || b < 1) {
        cout << -1 << endl;
    }
    else {
        cout << a* b << endl;
    }
}

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

int main() {
	vector<int> a(4), b(4);
	while (cin >> a[0] >> a[1] >> a[2] >> a[3]) {
		for (int i = 0; i < 4; i++) {
			cin >> b[i];
		}
		int hit = 0, brow = 0;
		for (int i = 0; i < a.size(); i++) {
			if(a[i]==b[i])hit++;
			for (int j = 0; j < b.size(); j++) {
				if (i != j && a[i] == b[j])brow++;
			}
		}
		cout << hit << " " << brow << endl;
	}
	return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <bits/stdc++.h>
#define ll long long

using namespace std;
int a[22],v[22],c[22];

int main()
{
    int n;  cin >> n;
    for(int i = 0;i<n;i++)  cin >> v[i];
    for(int i = 0;i<n;i++)  cin >> c[i];
    int Ans = 0;
    for(int i = 0;i<(1 << n);i++){
        int s = 0 , s2 = 0;
        for(int j = 0;j<n;j++){
            if(i & (1 << j))  s+=v[j],s2+=c[j];
        }
        Ans = max(Ans , s - s2);
    }
    cout << Ans;
    return 0;
}


Measured memory_bytes: 256
#include <math.h>
#include <iostream>
#include<string>
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
#include <stdlib.h>
using namespace std;

int main()
{
int N,Alice=0,Bob=0;cin >> N;
vector<int> a(N);
for(int i=0;i<N;i++){cin >> a.at(i);}
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
for(int i=0;i<N;i++)
{
  if(i%2==0)Alice+=a.at(i);
  else Bob+=a.at(i);
}
cout << Alice-Bob;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

selection_sort = A[:]

counter = 0
for i in range(len(selection_sort)):
    v = selection_sort[i]
    min_v = v
    min_i = i
    for j in range(i, len(selection_sort)):
        if min_v > selection_sort[j]:
            min_v = selection_sort[j]
            min_i = j
    if v != min_v:
        counter += 1
        selection_sort[i], selection_sort[min_i] = selection_sort[min_i], selection_sort[i]
        
print(' '.join(map(str, selection_sort)))
print(counter)
        
    


Measured memory_bytes: 5600
use std::collections::BTreeMap;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };

    let n: usize = sc.read();
    let a: Vec<u64> = sc.vec(n);

    if solve(a) {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn solve(a: Vec<u64>) -> bool {
    let n = a.len();
    let mut count = BTreeMap::new();
    for &a in a.iter() {
        *count.entry(a).or_insert(0) += 1;
    }
    let mut count = count.into_iter().collect::<Vec<(u64, usize)>>();
    count.sort();
    if n % 3 != 0 {
        return count.len() == 1 && count[0].0 == 0;
    }
    if count.len() == 3 {
        let ((a, ac), (b, bc), (c, cc)) = (count[0], count[1], count[2]);
        ac == bc && ac == cc && a ^ b ^ c == 0
    } else if count.len() == 2 {
        let ((a, ac), (_, bc)) = (count[0], count[1]);
        a == 0 && ac * 2 == bc
    } else if count.len() == 1 {
        count[0].0 == 0
    } else {
        false
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 8444