akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int seat[17] = {0};
	int X = 0;
	int stop[100] = {0};
	int time = 0;
	queue<int> Q;
	while(X < 100){
		int x;
		if(time%5 == 0 && time < 500){
			Q.push(time/5);
		}
		while(1){
			if(Q.size())x = Q.front();
			else x = -1;
			bool f = false;
			
			if(~x){
				int people = (x%5==1?5:2);
				int use = 19 + 3 * (x%3) + 17 * (x%2);
				rep(i,17-people+1){
					bool flag = true;
					rep(j,people){
						flag &= seat[i+j] == 0;
					}
					if(flag){
						rep(j,people){
							seat[i+j] = use;
						}
						f = true;
						break;
					}
				}
			}
			if(f){	
				stop[x] = time - x * 5;
				Q.pop();
				X++;
			}
			if(!f)break;
		}
		rep(i,17){
			seat[i] = max(0,seat[i]-1);
		}
		time++;
	}
	int n,c=0;
	
	while(cin >> n){
		if(n <= 5)c++;
		cout << stop[n] << endl;
	}
	int a = 0;
	while(c>=2){cout << a/a << endl;};
	
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
#define mmm 1000000007
#define pb push_back
									//nestedcode


 int main(){
	ios::sync_with_stdio(false);
  	cin.tie(0); cout.tie(0);
  	ll a,b,d,i,t,ans = 0;
  	cin>>a>>b;
  	d = __gcd(a,b);
  	for(i=2;i*i<=d;i++){
  		t = 0;
  		while(d%i == 0){
  			d = d/i;
  			t  = 1;
		  }
		  if(t)	ans++;
	  }
	  if(d!=1)  ans++;
	  cout<<ans+1;
}

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

int main(){
	int n;
	while(cin >> n){
		int num[100];
		int ans = 0;
		for(int i = 0; i < n; i++) cin >> num[i];
		sort(num, num+n);


		for(int i = 1; i <= n; i++){
			for(int j = 0; j < i; j++){
				ans += num[j];
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1176
import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] X =  new int[N];

        for(int i=0;i<N;i++){
            X[i] = sc.nextInt();
        }
        int ans = 1000000000;

        for(int j=1;j<101;j++){
            int total = 0;
            for(int i=0;i<N;i++){
                total += Math.pow(j-X[i],2);
            }
            ans = Math.min(ans,total);
        }

        System.out.println(ans);
    }

}








Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), i##_max = (b); i < i##_max; ++i)
#define RFOR(i, a, b) for (int i = (b)-1, i##_min = (a); i >= i##_min; --i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()

using namespace std;
using vi = vector<int>;
using vd = vector<double>;
using pi = pair<int, int>;
using pd = pair<double, double>;
using i64 = int64_t;
using u64 = uint64_t;

constexpr int INF = 1 << 30;
constexpr int MOD = 1000000007;

template <typename T>
void print(vector<T> &v) {
  REP(i, v.size()) {
    if (i) cout << " ";
    cout << v[i];
  }
  cout << endl;
}

class DisjointSet {
 public:
  vi rank, p;

  DisjointSet() {}
  DisjointSet(int size) : rank(size, 0), p(size, 0) {
    REP(i, size) make_set(i);
  }

  void make_set(int x) {
    p[x] = x;
    rank[x] = 0;
  }

  bool same(int x, int y) { return find_set(x) == find_set(y); }

  void unite(int x, int y) { link(find_set(x), find_set(y)); }

  void link(int x, int y) {
    if (rank[x] > rank[y]) {
      p[y] = x;
    } else {
      p[x] = y;
      if (rank[x] == rank[y]) rank[y]++;
    }
  }

  int find_set(int x) {
    if (x != p[x]) {
      p[x] = find_set(p[x]);
    }
    return p[x];
  }
};

class Edge {
 public:
  int source, target, cost;
  Edge(int source = 0, int target = 0, int cost = 0)
      : source(source), target(target), cost(cost) {}
  bool operator<(const Edge &e) const { return cost < e.cost; }
};

int kruskal(int n, vector<Edge> &edges) {
  int total_cost = 0;
  sort(ALL(edges));
  auto dset = DisjointSet(n + 1);
  REP(i, n) { dset.make_set(i); }
  for (auto &&e : edges) {
    if (!dset.same(e.source, e.target)) {
      total_cost += e.cost;
      dset.unite(e.source, e.target);
    }
  }
  return total_cost;
}

int main() {
  int n, m, s, t, w;
  cin >> n >> m;
  vector<Edge> edges;
  REP(i, m) {
    cin >> s >> t >> w;
    edges.emplace_back(s, t, w);
  }
  cout << kruskal(n, edges) << endl;
}


Measured memory_bytes: 4540
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <climits>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;
template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

const double PI=3.14159265358979323846;

int main()
{
	int a, b, h, m;
	cin >> a >> b >> h >> m;

	double ans, anglea, angleb, cosab;
	anglea = (double)(h*60+m) / (double)( 12 * 60);
	angleb = (double)m / 60.0;

	cosab = cos( (anglea - angleb) * 2.0 * PI );
	ans = (double)(a*a + b*b) - (double)(2*a*b)*cosab;
	ans = sqrt(ans);
	printf("%.10lf\n", ans);
}


Measured memory_bytes: 4164
s = input()
k = int(input())

array = []
max_length = 6
if(len(s) < 5):
    max_length = len(s) + 1
for l in range(1, max_length):
    for i in range(len(s)):
        if i + l > len(s):
            continue
        array.append(s[i:i+l])
        
array = list(set(array))
array.sort()
print(array[k-1])

Measured memory_bytes: 5068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define OUT(x) cout << #x << " = " << x << endl; 
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main(void){
	int N, M; cin >> N >> M;
	vector<int> v[1000];
	rep(i, M){
		int a, b; cin >> a >> b;
		v[a].pb(b), v[b].pb(a);
	}
	reps(i, 1, N + 1){
		printf("%d\n", v[i].size());
	}
	return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 3e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	cout << n * n * n << endl;
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"errors"
	"fmt"
)

func oddPercent(num int) float64 {
	var odds = make([]int, 0, num)
	if num >= 1 && num <= 100 {
		for i := num; i >= 0; i-- {
			if i%2 == 1 {
				odds = append(odds, i)
			}
		}
		p := float64(len(odds)) / float64(num)
		return p
	}
	panic(errors.New("No solution"))
}

func main() {
	var n int
	fmt.Scan(&n)
	fmt.Print(oddPercent(n))
}


Measured memory_bytes: 512
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <utility>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    int k;
    cin >> k;
    cout << (k / 2) * ((k + 1) / 2) << endl;
}


Measured memory_bytes: 256
a = list(input())
ans = "f"
while ans != "t":
    del a[len(a)-1]
    if len(a) % 2 == 0:
        if a[0:len(a) // 2] == a[len(a) // 2:len(a)]:
            print(len(a))
            ans = "t"


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    int ans = 0;
    rep(i, n) rep(j, i) rep(k, j) {
        if (a[i] != a[j] && a[j] != a[k] && a[k] != a[i] &&
            abs(a[j] - a[k]) < a[i] && a[i] < a[j] + a[k])
            ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
import sys

S = str(input())

for i in range(len(S)):
    if (i+1) % 2 == 1:
        if S[i] == "L":
            print("No")
            sys.exit()
    else:
        if S[i] == "R":
            print("No")
            sys.exit()
            
print("Yes")

Measured memory_bytes: 38384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    	Scanner input = new Scanner(System.in);
      	int N = input.nextInt();
      	double ans = 0;
      
     	for (int i = 0; i < N; i++) {
        	double X = input.nextDouble();
          	String U = input.next();
          	if (U.equals("JPY")) {
            	ans += X;
            } else {
            	ans += X * 380000.0;
            }
          	
        }
      	
      
      System.out.print(ans);

    }
}


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

constexpr int mod = 1e9 + 7;

int dp[301][301][301];

void add(int& x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}

struct segment {
    int l, x;
    segment(int l_, int x_) : l(l_), x(x_) {}
};

int main() {
    int n, m; cin >> n >> m;
    vector<vector<segment>> seg(n + 1);
    for(int i = 0; i < m; ++i) {
        int l, r, x; cin >> l >> r >> x;
        seg[r].emplace_back(l, x);
    }

    //vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
    dp[0][0][0] = 1;
    for(int rp = 0; rp < n; ++rp) {
        for(int i = 0; i <= rp; ++i) {
            for(int j = i; j <= rp; ++j) {
                array<int, 3> cur = {{i, j, rp}};
                do {
                    add(dp[rp + 1][cur[1]][cur[2]], dp[cur[0]][cur[1]][cur[2]]);
                    add(dp[cur[0]][rp + 1][cur[2]], dp[cur[0]][cur[1]][cur[2]]);
                    add(dp[cur[0]][cur[1]][rp + 1], dp[cur[0]][cur[1]][cur[2]]);
                } while(next_permutation(cur.begin(), cur.end()));
            }
        }

        const int r = rp + 1;
        for(auto const& s : seg[r]) {
            const int l = s.l;
            if(s.x == 1) {
                for(int i = 0; i < r; ++i) {
                    for(int j = l; j < r; ++j) {
                        dp[i][j][r] = dp[i][r][j] = dp[r][i][j] = 0;
                        dp[j][i][r] = dp[j][r][i] = dp[r][j][i] = 0;
                    }
                }
            } else if(s.x == 2) {
                for(int i = 0; i < l; ++i) {
                    for(int j = 0; j < l; ++j) {
                        dp[i][j][r] = dp[i][r][j] = dp[r][i][j] = 0;
                    }
                }
                for(int i = l; i < r; ++i) {
                    for(int j = l; j < r; ++j) {
                        dp[i][j][r] = dp[i][r][j] = dp[r][i][j] = 0;
                    }
                }
            } else if(s.x == 3) {
                for(int i = 0; i < l; ++i) {
                    for(int j = 0; j < r; ++j) {
                        dp[i][j][r] = dp[i][r][j] = dp[r][i][j] = 0;
                        dp[j][i][r] = dp[j][r][i] = dp[r][j][i] = 0;
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = i; j < n; ++j) {
            vector<int> idx = {i, j, n};
            do {
                add(ans, dp[idx[0]][idx[1]][idx[2]]);
            } while(next_permutation(idx.begin(), idx.end()));
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 106752
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
#define SPEED ios::sync_with_stdio(false);cin.tie(0);cout<<fixed<<setprecision(12)
#define erase(i) erase(i, 1)
signed gcd(int a, int b){return b?gcd(b,a%b):a;}
signed lcm(int a, int b){return a*b/gcd(a,b);}
template<typename T> void remove(std::vector<T>& vector, unsigned int index){vector.erase(vector.begin() + index);}
//priority_queue<int, vi, greater<int> > que;//昇順

using namespace std;

const int mod=1e9+7;

signed main(){
    SPEED;
    int a;
    string s;
    cin >> a >> s;
    if(a>=3200)cout << s << endl;
    else cout << "red" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define REP(i,n) for(int i=0; i<n; i++)
#define REP_R(i,n,m) for(int i=m; i<n; i++)
#define MAX 100
#define TIME 10

int N;
bool F[MAX+1][10];
int P[MAX+1][11];
int daymax[10];
ll ans = -(1 << 30);


void dfs(int pos);
void func();

int a[10];

int main() {

  /* IO */
  scanf("%d", &N);
  REP(i,N){
    REP(j,10){
      scanf("%d", &F[i][j]);
    }
  }
  REP(i,N){
    REP(j,11){
       scanf("%d", &P[i][j]);
     }
   }
  /* ... */


  dfs(0);

  cout << ans << endl;
}

void dfs(int pos) {
  if (pos == 10) {
    func();
    return;
  }

  a[pos] = 0; dfs(pos+1);
  a[pos] = 1; dfs(pos+1);
}

void func() {
  int score = 0;
  bool all = true;

  REP(i,10) {
    if (a[i]) all = false;
  }

  if (all) return;

  REP(i,N) {
    int cc = 0;
    REP(j,10) {
      if (a[j]==1 && F[i][j]==1) ++cc;
    }
    // printf("P[%d][%d]: %d\n", i,cc,P[i][cc]);
    score += P[i][cc];
  }

  REP(i,10) {
    // printf("%d", a[i]);
  }

  // printf(" ans: %d\n", score);


  ans = (score > ans) ? score : ans;
}


Measured memory_bytes: 256
n,x,y=gets.split.map &:to_i
as=[0]*(n-1)
1.upto(x-1){|d|
  as[d-1]=x-d
}
1.upto(n-y){|d|
  as[d-1]+=n-y+1-d
}
1.upto(x){|s|
  y.upto(n){|e|
    d=x-s+e-y+1
    as[d-1]+=1
  }
  (x+1).upto(y-1){|e|
    d=[e,x+y+1-e].min-s
    as[d-1]+=1
  }
}
(x+1).upto(y-1){|s|
  y.upto(n){|e|
    d=e-[s,x+y-1-s].max
    as[d-1]+=1
  }
}
(x+1).upto(y-2){|s|
  (s+1).upto(y-1){|e|
    d=[e-s,s-x+y-e+1].min
    as[d-1]+=1
  }
}
puts as

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

using namespace std;

typedef long long ll;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

int main() {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    string s, t;
    cin >> s >> t;
    bool ok = true;
    if (s.size () + 1 != t.size ())
        ok = false;
    else {for (int i = 0; i < s.size (); i++)
        if (s[i] != t[i])
            ok = false;
    }
    if (ok){
        cout << "Yes\n";
    }
    else
        cout << "No\n";
    return 0;
}


Measured memory_bytes: 3608
import sys
#import copy
#import math
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#import functools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    # input
    N, M = map(int, readline().split())
    A = list(map(int, readline().split()))

    sumA = sum(A)
    if sumA <= N:
        ans = N - sumA
    else:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 10188
#include<iostream>
#include<ios>
#include<algorithm>
using namespace std;
int n;
main()
{
	cin>>n;
	for(;n--;)
	{
		int h,m;
		scanf("%d:%d",&h,&m);
		int dm=m*12;
		int dh=h*60+m;
		int a=abs(dm-dh);
		if(a>360)a=720-a;
		cout<<(a<60?"alert":a>=180?"safe":"warning")<<endl;
	}
}


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

void sol()
{
	int n;
	std::cin >> n;

	int x=n%10;

	if(x==2 || x==4 || x==5 || x==7 || x==9)
	{
		std::cout << "hon" << std::endl;
	}

	else if(x==0 || x==1 || x==6 || x==8)
	{
		std::cout << "pon" << std::endl;
	}

	else if(x==3)
	{
		std::cout << "bon" << std::endl;
	}
}

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

	sol();

	return 0;
}

Measured memory_bytes: 3620
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
#include <iomanip>
#include<queue>
#include<algorithm>
#include <functional>
#include<vector>
#include <math.h>
#include <numeric>
#include <stack>
#include <map>
using namespace std;

const int N_MAX = 201;
int N;
int L;
int V[N_MAX];
int all_v = 0;
int dif = 1000000;
int ans;

int main() {
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		V[i] = L + i;
		all_v += V[i];
	}
	for (int i = 0; i < N; i++) {
		int tmp = abs(all_v - (all_v - V[i]));
		if (tmp < dif) {
			dif = tmp;
			ans = all_v - V[i];
		}
	}
	cout << ans << endl;
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
//#define int ll
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;
typedef vector<string> vst;
typedef vector<vst> vvst;
typedef pair<ld, ld> pld;
typedef complex<double> base;

#define inmin(a, b) a = min(a, (b))
#define inmax(a, b) a = max(a, (b))
#define mp(a,b) make_pair(a,b)
#define modsum(a, b) ((a) + (b) >= M ? (a) + (b) - M : (a) + (b))
#define modsubtract(a, b) ((a) - (b) < 0 ? (a) - (b) + M : (a) - (b))
#define modmultiply(a, b) (((a) * (b)) % M)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define sqr(x) ((x) * (x))
#define fori(i, n) for(int i = 0; i < int(n); ++i)
#define cint const int &
#define SZ(a) ((int)((a).size()))
#define watch(x) cout << (#x) << " = " << (x) << endl;

const double PI = 2 * acos(0.0);

const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";


inline void transpose(vector<string> &a) {

    int n = a.size();
    if (n == 0) return;
    int m = a[0].size();
    vector<string> b(m, string(n, ' '));
    fori (i, n) fori (j, m) b[j][i] = a[i][j];
    a = b;
}


template<class T>
inline ostream & operator << (ostream &out, vector<T> &a) {
    out << "{";
    fori (i, SZ(a))
        out << a[i] << vector<string>{", ", "}"}[i + 1 == SZ(a)];
    return out;
}

void smain();

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


#ifdef MAX_HOME
    freopen("input.txt", "r", stdin);
    clock_t start = clock();
#define cerr cout
#endif
    cout << setprecision(12) << fixed;
    smain();
#ifdef MAX_HOME
    cout << "\n\n\n\n";
    cout << "TOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
#endif
}


const int N = 409;
const ll oo = 1e18;
ll dp[N][N];
char did[N][N];
ll a[N];

ll get_dp(int l, int r) {
    if (l >= r) return 0;
    if (did[l][r]) return dp[l][r];
    did[l][r] = 1;
    ll &ret = dp[l][r];
    ret = oo;
    ll all = accumulate(a + l, a + r + 1, 0LL);
    for (int i = l; i < r; ++i) {
        inmin(ret, get_dp(l, i) + get_dp(i + 1, r) + all);
    }
    return ret;
}

void smain() {

    int n;
    cin >> n;
    fori (i, n) cin >> a[i];
    cout << get_dp(0, n - 1);
}

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

 int main()
 {
 	int n;
 	int ans=0;
 	cin >> n;
 	string a,b,c;
 	cin >> a>>b>>c;
 	for (int i = 0; i < n; i++){
 		if(a.at(i)==b.at(i)&&a.at(i)==c.at(i)){
 			
 		}else if(a.at(i)==b.at(i)||b.at(i)==c.at(i)||a.at(i)==c.at(i)){
 			ans++;
 		}else{
 			ans=ans+2;
 		}
 	}
 	cout << ans << endl;
 }

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

void include3(int x) {
    int xdec = x;
    while(x){
        if(x % 10 == 3){
            cout << " " << xdec ;
            return;
        }
        x /= 10;
    }
}

void checkNum(int x) {
    if(x % 3 == 0){
        cout << " " << x ;
        return;
    }else{
        include3(x);
        return;
    }
}

int main() {

    int n = 0;

    cin >> n ;

    for(int i = 1 ; i <= n ; i ++){
        checkNum(i);
    }
    cout << "\n";
}


Measured memory_bytes: 3092
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
#include <complex>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 

static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};
 
static const double EPS = 1e-10;

double dp[1<<12][12];

double compute_distance(int prev,int next,
                        const vector<int>& boxes){
  double h = abs(boxes[prev] - boxes[next]);
  double r = abs(boxes[prev] + boxes[next]);
  double w = sqrt(r * r - h * h);
  return w - (double)boxes[prev] + (double)boxes[next];
}

int main(){
  string str;
  while(getline(cin,str)){
    stringstream ss;
    ss << str;
    int box_width;
    ss >> box_width;

    int box;
    vector<int> boxes;
    while(ss >> box){
      boxes.push_back(box);
    }

    for(int S=0;S<=(1<<12)-1;S++){
      for(int i=0;i<12;i++){
        dp[S][i] = (double)box_width + 10.0;
      }
    }

    for(int i=0;i<boxes.size();i++){
      dp[(1<<i)][i] = 2 * boxes[i];
    }

    for(int S = 0; S <= (1<<boxes.size()) - 1;S++){
      for(int prev = 0; prev < boxes.size(); prev++){
        if(!(S & (1<<prev))) continue;
        for(int next = 0; next<boxes.size();next++){
          if(S & (1<<next)) continue;
          dp[S | (1<<next)][next] = min(dp[S | (1<<next)][next],
                                        dp[S][prev] + compute_distance(prev,next,boxes));
        }
      }
    }

    //OK,NA

    bool isok = false;
    for(int i = 0; i < boxes.size(); i++){
      if(dp[(1<<boxes.size())-1][i] <= (double)box_width + EPS){
        isok = true;
      }
    }
    printf("%s\n",isok ? "OK" : "NA");
  }
}

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

#define loop(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) loop(i, 0, a)

using namespace std;

template <class T>
using vec = std::vector<T>;
typedef long long ll;
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

const double PI = acos(-1.0);

// long long積のオーバーフロー検出
bool detect_mul_overflow(ll a, ll b)
{
    return a >= LONG_MAX / b;
}

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

struct edge
{
    int from, to, cost;
};

// int型の2次元配列(3×4要素の)の宣言
// vector<vector<int>> data(3, vector<int>(4));

int x,y;

int main()
{
    cin>> x;
    int ans=x+x*x+x*x*x;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3632
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <iomanip>
#include <math.h>
#include <list>
#include <numeric>
using namespace std;

long long combi(long long n, long long k) {
  if (n == k || k == 0)
    return 1;
  else {
    return combi(n - 1, k - 1) + combi(n - 1, k);
  }
}

long long gcd(int a, int b){
  if (a%b == 0){
    return(b);
  }
  else{
    return(gcd(b, a%b));
  }
}

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

  if(S == "ABC"){
    cout << "ARC" << endl;
  }
  else{
  cout << "ABC" << endl;
  }
}
 


Measured memory_bytes: 3632
#include <stdio.h>
#include <math.h>

int main(void)
{
  int h1, m1, h2, m2, k;
  
  scanf("%d %d %d %d %d", &h1, &m1, &h2, &m2, &k);
  
  printf("%d", (60*h2+m2) - (60*h1+m1) - k);

  return 0;
}

Measured memory_bytes: 1732
using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main()
    {
        string s = Console.ReadLine();

        long ans = long.Parse(s);

        for (int i = 1; i < 1 << (s.Length - 1); i++)
        {
            int tmp = 0;
            for (int j = 0; j < s.Length; j++)
            {
                if ((i >> j & 1) == 1)
                {
                    ans += long.Parse(s.Substring(tmp, j - tmp + 1));
                    tmp = j + 1;
                }

                if (j == s.Length - 1)
                {
                    ans += long.Parse(s.Substring(tmp, s.Length - tmp));
                }
            }
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
(defun splitat (c line)
  (labels ((rec (line acc)
				(let ((pos (position-if (lambda(cc) (char= c cc)) line)))
				  (if pos
					  (rec (subseq line (1+ pos)) (cons (subseq line 0 pos) acc))
					(nreverse (cons line acc))))))
	(rec line nil)))

(defun f(card lst)
  (labels ((rec(lst card)
             (if (null lst)
               (check card)
               (let ((a (car lst)))
                 (rec (cdr lst) (mapcar (lambda(row) (mapcar (lambda(cell) (if (= cell a) 0 cell)) row)) card)))))
           (check (card)
                  ;(format t "~{~A~%~}" card)
                  (or (some (lambda(row) (every #'zerop row)) card)
                      (some (lambda(i) (every #'zerop (mapcar (lambda(row) (nth i row)) card))) '(0 1 2))
                      (every #'zerop (list (nth 0 (nth 0 card)) (nth 1 (nth 1 card)) (nth 2 (nth 2 card))))
                      (every #'zerop (list (nth 0 (nth 2 card)) (nth 1( nth 1 card)) (nth 2 (nth 0 card)))))))
    (rec lst card)))

(let* ((line0 nil)
       (n 0)
       (lst nil))
  (dotimes (i 3)
    (setq line0 (cons (mapcar #'parse-integer (splitat #\space (read-line nil nil))) line0)))
  (setq n (parse-integer (read-line nil nil)))
  (dotimes (i n)
    (setq lst (cons (parse-integer (read-line nil nil)) lst)))
  (format t "~A~%" (if (f line0 lst) "Yes" "No")))


Measured memory_bytes: 17888
n=gets.to_i
c=gets.split.map(&:to_i).sort.reverse
s=0
mod=1000000007
w=2**(n-2)%mod
n.times do |i|
  s+=c[i]*(i+2)*w
  s%=mod
end
puts (s*w*4%mod).to_i


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

using namespace std;

int main(){

	int n,m;
	while(cin>>n>>m&&!(n==0&&m==0)){
		int scores[1001];
		vector<int> comb;
		for(int i = 0; i < n; i++){
			cin>>scores[i];
		}
		scores[n]=0;
		for(int i = 0; i < n+1; i++){
			for(int j = 0; j < n+1; j++){
				int sum=scores[i]+scores[j];
				if(sum<=m)
					comb.push_back(sum);
			}
		}
		sort(comb.begin(),comb.end());
		comb.erase(unique(comb.begin(),comb.end()));

		int maxNum=0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				int left = (scores[i]+scores[j]);
				if(left<=m&&comb[0]+left<=m){
					vector<int>::iterator it = lower_bound(comb.begin(),comb.end(),m-left);
					if(it==comb.end()){
						maxNum=max(maxNum,comb[comb.size()-1]+left);
					}
					else{
						if(*it==(m-left)){
							maxNum=m;
						}
						else{
							it--;
							maxNum=max(maxNum,*it+left);
						}
					}
				}
			}
		}
		cout<<maxNum<<endl;
	}

	return 0;
}

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

int main(){
    ll n,k;
    cin >> n >> k;
    if(n>k) n = n%k;
    while (abs(n-k)<n)
    {
        n = abs(n-k);
    }
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
int main()
{
    she_told_me_dont_worry
    int n, m;
    cin>>n>>m;
    int i;
    int digits[n+5];
    FOR0(i, n)
    {
        digits[i] = -1;
    }
    bool is = true;
    FOR0(i, m)
    {
        int s, c;
        cin>>s>>c;
        s--;
        if(digits[s] != -1 && digits[s] != c)
            is = false;
        digits[s] = c;
    }
    if(!is) cout<<-1<<endl;
    else 
    {
        if(n != 1 && digits[0] == 0) 
        {
            cout<<-1<<endl;
            return 0;
        }
        if(n == 1 && digits[0] == -1)
        {
            cout<<0<<endl;
            return 0;
        }
        FOR0(i, n) 
        {
            if(digits[i] == -1) 
            {
                if(i == 0)
                    digits[i] = 1;
                else digits[i] = 0;
            }
        }
        FOR0(i, n) cout<<digits[i];
        cout<<endl;
    }
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 256
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
#ifdef DAIJOBU
#include "/home/v-o_o-v/deb.h"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif 

using namespace std;

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#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)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef long long lint;
typedef double ld;

void a(); void b(); void c(); void d(); void e(); void f();

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

	a();
	// b();
	// c();
	// d();
	// e();
	// f();
	return 0;
}


void a(){
	string s, t;
	cin >> s >> t;
	t.erase(t.begin() + s.size());
	if(s == t)puts("Yes");
	else puts("No");
}

void b(){

}

void c(){

}

void d(){

}

void e(){

}

void f(){

}

Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>

using namespace std;
typedef long long ll;

int main() {
	int N; cin >> N;
	string s; cin >> s;
	int ans = 1;
	for (int i = 0; i < N-1; i++) {
		if (s[i] != s[i + 1]) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3736
def Suit2Num(s)
  return 0 if s == "S"
  return 1 if s == "H"
  return 2 if s == "C"
  return 3 if s == "D"
  nil
end
def Num2Suit(n)
  return "S" if n == 0
  return "H" if n == 1
  return "C" if n == 2
  return "D" if n == 3
  nil
end

s = Array.new(4)
4.times { |i| s[i] = Array.new(13) }

n = gets.to_i
n.times {
  cs,cn = gets.chomp.split(" ")
  s[Suit2Num(cs)][cn.to_i-1] = "Exist"
}

4.times { |i|
  13.times { |j|
    puts "#{Num2Suit(i)} #{j+1}" if s[i][j] != "Exist"
  }
}

Measured memory_bytes: 8652
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
s = input()
a = [0]*26

for x in s:
    a[ord(x)-ord('a')] += 1

ans = 1
for x in a:
    ans *= x + 1

ans = ( ans - 1 ) % ( 10**9 + 7 )
print(ans)

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

#define F                   first
#define S                   second
#define int                 long long int
#define pb                  push_back
#define mp                  make_pair
#define pii                 pair<int,int>
#define vi                  vector<int>
#define mii                 map<int,int>
#define pqb                 priority_queue<int>
#define pqs                 priority_queue<int,vi,greater<int> >
#define mod                 1000000007
#define endl                '\n'
#define rep(i,a,b)            for(int i=a;i<b;i++)
void solve() {
    int n;
    double d;
    cin >> n >> d;
    int x[n];
    int y[n];
    int ans = 0;
    rep(i, 0, n) {
        cin >> x[i];
        cin >> y[i];
        double dis = x[i] * x[i] + y[i] * y[i];
        dis = pow(dis, 0.5);
        if (dis <= d) {
            ans++;
        }
    }
    cout << ans << endl;


}
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
    c_p_c();
    solve();

    return 0;
}

Measured memory_bytes: 7488
#include<iostream>
#include<stdio.h>
using namespace std;
int n,w,t=0,a[101],b[101],f[101][100001];//khoi luong nho nhat khi den i va dat duoc j tien
void xuli()
{
	for(int i=0;i<=n;i++)
		for(int j=1;j<=t;j++)
			f[i][j]=1000000001;
	for(int i=0;i<=n;i++)
		f[i][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=t;j++)
		{
			f[i][j]=f[i-1][j];
			if(j-b[i]>=0)
				f[i][j]=min(f[i][j],f[i-1][j-b[i]]+a[i]);
		}
	for(int i=t;i>=1;i--)
		if(f[n][i]<=w)
		{
			cout<<i;
			break;
		}
}
int main()
{
	//freopen("knapsack.inp","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		t+=b[i];
	}
	xuli();
	return 0;
}

Measured memory_bytes: 43068
N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
num_in = [0] * (N+1)
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    num_in[y] += 1

st = []
for i in range(1, N+1):
    if num_in[i] == 0:
        st.append(i)

seq = []
while st:
    v = st.pop()
    seq.append(v)
    for u in adj[v]:
        num_in[u] -= 1
        if num_in[u] == 0:
            st.append(u)

v2i = {}
i2v = {}
for i, v in enumerate(seq):
    v2i[v] = i
    i2v[i] = v

dp = [0] * N
for i in range(N):
    v = i2v[i]
    for u in adj[v]:
        dp[v2i[u]] = max(dp[v2i[u]], dp[i] + 1)

print(max(dp))


Measured memory_bytes: 82336
#include <iostream>
#include <iomanip>
// std::cout << std::setprecision(2) << 3.141; // "3.1"
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>
// #include <bits/stdc++.h> all

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;

static const int giga = pow(10,9);
// double pi = 3.141592653589793238463;

int main(void){
  int n; cin >> n;
  vector<pii> a(n);
  
  for(int i = 0; i < n; i++){
    int temp; cin >> temp;
    a[i] = make_pair(temp,i+1);
  }

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

  for(int i = 0; i < n; i++){
    if(i != n-1){
      cout << a[i].second << " ";
    } else {
      cout << a[i].second << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;

int main(){
	ll ans=0;
	ll x;
	cin>>x;
	if(x>=500){
		ll tmp=x/500;
		ans+=1000*tmp;
		x-=500*tmp;
	}
	if(x>=5){
		ll res=x/5;
		ans+=5*res;
		res-=5*res;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void)
{
    long long A,V,B,W,T,x,i,D,D2;
    cin >> A >> V;
    cin >> B >> W;
    cin >> T;
    D=abs(A-B);
    D2=(V-W)*T;
    puts(D<=D2?"YES":"NO");
    
}


Measured memory_bytes: 3624
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
#import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s, n, node):
    # 頂点が探索済みかどうかのチェック配列
    check = [False for _ in range(n)]
    check[s] = True
    # 次見る頂点を格納するキュー
    queue = deque([s])
    visited_num = 1

    # 問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color = [-1 for _ in range(n)]
    color[s] = 0

    while visited_num < n:
        # グラフが全連結ではない場合
        if len(queue) == 0:
            # 空配列を返す
            # 現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex = queue.popleft()
        # インデックスがない場合は
        for next_vertex in node[now_vertex]:

            if check[next_vertex] == True:
                continue

            queue.append(next_vertex)
            check[next_vertex] = True

            # 問題固有の計算
            color[next_vertex] = color[now_vertex]+1
            visited_num += 1

    return color


mod = 10**9+7
# n=int(input())
# n,m=list(map(int,input().split()))
# a=list(map(int,input().split()))
def ceil(x, y): return (x+y-1)//y
def input_list(): return list(map(int, input().split()))


n = int(input())
num = 10**6
cal = [(7*pow(10, i, n)) % n for i in range(num)]
# print(cal[:10])
# n, m = list(map(int, input().split()))
c = 0
for i in range(num):
    c += cal[i]
    c %= n
    if c == 0:
        print(i+1)
        exit()

print(-1)


Measured memory_bytes: 143100
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
#define INF 10000000

int gcd(int a, int b){ return a%b ? gcd(b, a%b) : b; }//Ååöñ

struct edge{
	int to,cap,rev;
	edge(int t,int c,int r){
		to=t;cap=c,rev=r;
	}
};

vector<vector<edge> > G;
int level[100000];
int iter[100000];

void add_edge(int from,int to,int cap){
	G[from].push_back(edge(to,cap,G[to].size()));
	G[to].push_back(edge(from,0,G[from].size()-1));
}

void bfs(int s){
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s]=0;
	que.push(s);
	while(!que.empty()){
		int v=que.front();que.pop();
		for(int i=0;i<G[v].size();i++){
			edge &e=G[v][i];
			if(e.cap>0 && level[e.to]<0){
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}

int dfs(int v,int t,int f){
	if(v==t)return f;
	for(int &i=iter[v];i<G[v].size();i++){
		edge &e=G[v][i];
		if(e.cap>0 && level[v]<level[e.to]){
			int d=dfs(e.to,t,min(f,e.cap));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int s,int t){
	int flow=0;
	while(true){
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter,0,sizeof(iter));
		int f;
		while((f=dfs(s,t,INF))>0){
			flow+=f;
		}
	}
}


int main()
{
	int n,m;
	while(cin>>n>>m && n>0){
		G.clear();
		G.resize(n+m+2);
		vector<int> red,blue;
		for(int i=0;i<n;i++){
			int t;
			cin>>t;
			red.push_back(t);
			add_edge(0,1+i,1);
		}
		for(int i=0;i<m;i++){
			int t;
			cin>>t;
			blue.push_back(t);
			add_edge(n+i+1,n+m+1,1);
		}
		for(int r=0;r<n;r++){
			for(int b=0;b<m;b++){
				if(gcd(red[r],blue[b])>1){
					add_edge(r+1,n+b+1,1);
				}
			}
		}
		cout<<max_flow(0,n+m+1)<<endl;
	}
	return 0;
}

Measured memory_bytes: 6036
#include <bits/stdc++.h>
using namespace std;
#define int long long int

int power(int x, int y, int p)
{
    int res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

int sz[105], par[105];
int adj[105][105];
int n, m;
void init(){
	for(int i=1; i<=n; i++){
		sz[i] = 1;
		par[i] = i;
	}
}

int find(int u){
	while(u!=par[u]) u = par[u];
	return u;
}

void merge(int a, int b){
	a = find(a);
	b = find(b);
	if(a==b) return;
	if(sz[a]<sz[b]) swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
}

struct edge{
	int u, v, c;
};

int32_t main(){
	int n, m;
	cin>>n>>m;
	init();
	memset(adj, 0, sizeof adj);
	vector<edge> chk;
	for(int i=1; i<=m; i++){
		int u, v, c;
		cin>>u>>v>>c;
		adj[u][v] = c;
		adj[v][u] = c;
		chk.push_back({u, v, c});
	}
	for (int k = 1; k <=n; ++k) {
		    for (int i = 1; i <=n; ++i) {
		    	if(adj[k][i]==0) adj[k][i] = INT_MAX;
		    }
	}
	for (int k = 1; k <=n; ++k) {
	    for (int i = 1; i <=n; ++i) {
	        for (int j = 1; j <=n; ++j) {
	            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
	        }
	    }
	}
	int ans = 0;
	for(int i=0; i<chk.size(); i++){
		int u = chk[i].u;
		int v = chk[i].v;
		int c = chk[i].c;
		if(adj[u][v]!=c ) ++ans;
	}
	cout<<ans<<endl;
}

// UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU
// UURRURRDDDLLDLLULUUURRURRDDDLLDL


Measured memory_bytes: 384
#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 <cstdio>
#include <cmath>
using namespace std;

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> a(M), b(M);
  rep(i, M) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }
  vector<vector<int>> to(N);
  rep(i, M) {
    to[a[i]].push_back(b[i]);
    to[b[i]].push_back(a[i]);
  }
  int ans = 0;
  rep(i, M) {
    vector<bool> p(N, false);
    p[0] = true;
    queue<int> que;
    rep(j, to[0].size()) {
      if(!a[i] && to[0][j] == b[i])
        continue;
      p[to[0][j]] = true;
      que.push(to[0][j]);
    }
    while(!que.empty()) {
      int tmp = que.front();
      que.pop();
      rep(j, to[tmp].size()) {
        if(tmp == a[i] && to[tmp][j] == b[i])
          continue;
        if(tmp == b[i] && to[tmp][j] == a[i])
          continue;
        if(!p[to[tmp][j]]) {
          p[to[tmp][j]] = true;
          que.push(to[tmp][j]);
        }
      }
    }
    bool flag = false;
    rep(j, N) {
      if(!p[j]) {
        flag = true;
        break;
      }
    }
    if(flag)
      ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=200005;
const LL MAX=1e18;
LL n,a[N];
LL suf[N],pre[N];
LL calc (LL x,LL y,LL op)
{
	LL cnt=0;
	while (y<x)	{y*=4;cnt+=2;}
	if (x==y&&op==1) cnt+=2;
	return cnt;
}
LL calc1 (LL x,LL y,LL op)
{
	LL cnt=0;
	while (y>x)	{y*=4;cnt+=2;}
	if (x==y&&op==1) cnt+=2;
	return cnt;
}
LL sta[N],top,sta1[N];
int main()
{
	scanf("%lld",&n);
	for (LL u=1;u<=n;u++) scanf("%lld",&a[u]);
	suf[n]=0;top=0;sta[top]=MAX;sta1[top]=n+1;
	for (LL u=n-1;u>=1;u--) 
	{
		suf[u]=suf[u+1];
		if (a[u+1]>a[u])
		{
			sta[++top]=calc(a[u+1],a[u],1)-2;
			sta1[top]=u+1;
		}
		else
		{
			LL t=calc(a[u],a[u+1],0);
			LL now=u;
			suf[u]=suf[u]+t*(sta1[top]-now-1);
			//printf("%lld %lld %lld %lld\n",u,t,sta1[top],now);
			now=sta1[top]-1;
			while (top>0&&sta[top]<t)	
			{
				t=t-sta[top];
				top--;
				//printf("%lld %lld %lld %lld\n",u,t,sta1[top],now);
				suf[u]=suf[u]+t*(sta1[top]-now-1);
				now=sta1[top]-1;
			}
			sta[top]-=t;
		}
	}
/*	for (int u=1;u<=n;u++)  printf("%lld ",suf[u]);
	printf("\n");*/
	for (LL u=1;u<=n;u++) a[u]=-2*a[u];
	top=0;sta[top]=MAX;sta1[top]=0;
	pre[1]=0;
	for (LL u=2;u<=n;u++) 
	{
		pre[u]=pre[u-1];
		if (a[u]>a[u-1])
		{
			sta[++top]=calc1(a[u-1],a[u],1)-2;
			sta1[top]=u-1;
		}
		else
		{
			LL t=calc1(a[u],a[u-1],0);
			LL now=u;
			//printf("%lld %lld %lld %lld\n",u,t,a[u],a[u-1]);
			pre[u]=pre[u]+t*(now-sta1[top]-1);
			now=sta1[top]+1;
			while (top>0&&sta[top]<t)	
			{
				t=t-sta[top];
				top--;
				pre[u]=pre[u]+t*(now-sta1[top]-1);
				now=sta1[top]+1;
			}
			sta[top]-=t;
		}
	}
/*	for (int u=1;u<=n;u++)  printf("%lld ",pre[u]);
	printf("\n");*/
	LL ans=suf[1];
	for (LL u=2;u<=n+1;u++) ans=min(ans,pre[u-1]+u-1+suf[u]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
int main(){
  long int N;
  long int ans[2];
  cin >> N;
  long int A[N];
  ans[0] = 1;
  ans[1] = 1000000000;
  for(long int i=0;i<N;i++){
	cin >> A[i];
    ans[0] = max(ans[0],A[i]);
    ans[1] = min(ans[1],A[i]);
  }
  cout << ans[0] - ans[1] << endl;
  
return 0;
}

Measured memory_bytes: 256
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++i)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define all(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define VECV(a,n,m) vector<vector<int>> a(n, vector<int>(m));
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
bool f(string s){
  bool ans=true;
  rep(i,s.size()/2){
    if(s[i]!=s[s.size()/2+i]){
      ans=false;
      break;
    }
  }
  return ans;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin>>N;
  ll ans=0;
  rep(i,N+1){
    if(i%3!=0&&i%5!=0)
      ans+=i;
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 3624