akhauriyash/Code-Regression huggingface dataset:
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let N: usize = read();
    let M: usize = read();
    let mut graph: Vec<Vec<usize>> = vec![vec![]; N];
    for _ in 0..M {
        let a: usize = read::<usize>() - 1;
        let b: usize = read::<usize>() - 1;
        graph[a].push(b);
        graph[b].push(a);
    }
    use std::collections::VecDeque;
    let mut queue: VecDeque<(usize, Vec<usize>)> = VecDeque::new();
    queue.push_front((0, vec![0]));
    let mut ans = 0;
    while let Some((num, path)) = queue.pop_back() {
        if path.len() == N {
            ans += 1;
        }
        for &next in &graph[num] {
            if !path.contains(&next) {
                let mut path = path.clone();
                path.push(next);
                queue.push_back((next, path));
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string.h>
#define max(a, b) ((a)>(b) ? (a) : (b))

short dp[3001][3001] = {0};

int main(){
  char s[3001], t[3001];
  scanf("%s %s", s, t);

  int i, j;
  for(i=strlen(s)-1; i>=0; i--){
    for(j=strlen(t)-1; j>=0; j--){
      dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
      if(s[i] == t[j])  dp[i][j] = max(dp[i][j], dp[i+1][j+1]+1);
    }
  }

  i = j = 0;
  int k = dp[0][0];
  while(k){
    if(dp[i+1][j] == k){ i++; }
    else if(dp[i][j+1] == k){ j++; }
    else{ putchar(s[i]); i++; j++; k--;}
  } puts("");

  return 0;
}


Measured memory_bytes: 17792
#include <bits/stdc++.h>
#define ll  long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define vi vector<int>
#define br cout <<"\n";
#define all(x)  (x).begin(),(x).end()
#define tr(c,i) for(auto i : c)
#define pii pair< int,int >
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define pq priority_queue< pair<ll,pii> ,vector<pair<ll,pii>>,greater <pair<ll,pii>> >p;//container adapter makes ascending q
#define er(x) cout << x << " "
#define err(x,y) cout << x << " "<<y
const int M = 200005;
using namespace std;
clock_t time_p=clock();
void dem()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
using namespace std ;
const int N =  50  ;
const int dx[] = { 1, -1 , 0 , 0  };
const int dy [] = { 0 ,0 , 1 , -1  };
int main (){
   int n ;
   cin >> n ;
   vi a(n),  b(n) , c(n);
   ll s = 0 ;
   for ( int &x : a ) cin >> x ;
   for ( int &x : b ){cin >> x ; s += x ; }
   for ( int i = 0 ; i < n - 1 ; ++ i )
    cin >> c[i] ;
   for ( int i = 1 ; i < n ; ++ i ){
    if( a[i - 1 ] + 1 == a[i])
     s += c[a[i-1] - 1 ] ;

   }

cout << s ;
return 0 ;

}


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

#define mx 100005
#define ll long long 

int ar[mx];
char ch[mx];

int m,n,k,ii;


void solve()
{
	cin>>n;
	if(n>=30)cout<<"Yes\n";
	else cout<<"No\n";
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif

	int t=1;
	while(t--)
	{
		solve();
	}
	return 0;
}

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

int main() {
	
	int n, m;
	cin >> n >> m;
	vector<int> a(m);
	vector<unsigned long long int> f(n+1);
	vector<int> b(n+1);

	for (int i = 0; i < m; i++) {
		cin >> a.at(i);
		b.at(a.at(i)) = 1;
	}

	f.at(0) = 1;
	f.at(1) = 1;

	for (int i = 2; i < n+1; i++) {
		if (b.at(i - 1) == 0)f.at(i) += f.at(i - 1);
		if (b.at(i - 2) == 0)f.at(i) += f.at(i - 2);
		f.at(i) %= 1000000007;
	}
	
	cout << f.at(n) << endl;





}

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

typedef long long ll;

int const N = 200 * 1000 + 16;
int const M = 1000 * 1000 * 1000 + 7;
int const inf = 1000 * 1000 * 1000;

typedef pair<int,int> type;

int X;


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

  cin >> X;
  ll l = 1;
  ll r = 1e9;
  ll ans = 0;
  while(l <= r) {
    ll m = l + r >> 1;
    if(X <= m*(m+1)/2)
      r = m - 1, ans = m;
    else
      l = m + 1;
  }

  cout << ans;
}

Measured memory_bytes: 256
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

using Weight = ll;

// 辺
struct Edge {
	size_t from;
	size_t to;
	Weight cost;
	Edge(size_t t, Weight c) : to(t), cost(c) {}
	Edge(size_t f, size_t t, Weight c) : from(f), to(t), cost(c) {}
	bool operator<(const Edge& rhs) const { return this->cost > rhs.cost; }
};

// グラフ G=(V,E)
struct Graph {
	size_t node;
	std::vector<std::vector<Edge>> edges;

	Graph(size_t n) : node(n), edges(n) {}
};

void solve(Graph& g, VI& result, int node, int parent) {
	for(auto& e : g.edges[node]) {
		if(e.to == parent) {
			continue;
		}

		if(e.cost % 2 == 0) {
			result[e.to] = result[e.from];
			solve(g, result, e.to, e.from);
		} else {
			result[e.to] = (result[e.from] + 1) % 2;
			solve(g, result, e.to, e.from);
		}
	}
}

int main() {
	int n;
	cin >> n;
	Graph g(n);
	REP(i, n - 1) {
		ll u, v, w;
		cin >> u >> v >> w;
		g.edges[u - 1].push_back(Edge(u - 1, v - 1, w));
		g.edges[v - 1].push_back(Edge(v - 1, u - 1, w));
	}
	VI result(n, -1);
	result[0] = 0;
	solve(g, result, 0, 0);
	REP(i, n) { cout << result[i] << endl; }
	return 0;
}


Measured memory_bytes: 13748
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        
        // 
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        
        int i = s.length();
        int j = t.length();
        String answer = "";
        while (i > 0 && j > 0) {
            if (dp[i][j] == dp[i - 1][j]) {
                i--;
            } else if (dp[i][j] == dp[i][j - 1]) {
                j--;
            } else {
                answer = String.valueOf(s.charAt(i - 1)) + answer;
                i--;
                j--;
            }
        }
        
        System.out.println(answer);
    }
}

Measured memory_bytes: 87288
#include<iostream>
#include<math.h>
#include<bits/stdc++.h>
#define ll long long int
#define hell 1000000007LL
using namespace std;
ll power(ll x, ll y){ 
    if(y==0)
     return 1;
    else
    {
        ll p=power(x,y/2);
        if(y%2==0)
         return (p*p)%hell;
        else
        return (x*((p*p)%hell))%hell;
    }}
ll gcd(ll x,ll y)
{
    if(y==0)
     return x;
    else
    return gcd(y,x%y);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(20);
    ll k,a,b;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            cout<<"OK";
            exit(0);
        }
    }
    cout<<"NG";}

Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    int N;
    cin >> N;
    
    vector<int> A(N), B(N);
    for ( int i = 0; i < N; i++ ) {
        int a;
        cin >> a;
        if ( i ) { A[i]  = A[i-1]+a; }
        else  { A[i] = a; }
    }
    for ( int i = 0; i < N; i++ ) {        
        int a;
        cin >> a;
        if ( i ) { B[i]  = B[i-1]+a; }
        else  { B[i] = a; }
    }
    
    int ans = 0;
    for ( int i = 0; i < N; i++ ) {        
        ans =  max( ans, A[i] + B[N-1] - ( i ? B[i-1] : 0 ) );
    }
    
    cout << ans << endl;
    
    return 0;
}

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

typedef long long LL;
typedef unsigned long long ULL;

#define debug printf("fuck %d\n", __LINE__);

inline LL read() {
	LL res = 0, bo = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if (ch == '-') bo = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { res = (res << 1) + (res << 3) + ch - '0'; ch = getchar(); }
	return bo * res;
}

template<typename T> void read(T &x) { x = read(); }
template<typename T, typename ...Argv> void read(T &a, Argv &...argv) { read(a); read(argv...); }

const int N = 1e5 + 10, p = 1e9 + 7;

typedef std::pair<int, int> pii;

int f[N], tr[N], tot, a[N], b[N], t[N], cnt;
pii o[N];

void Modify(int x, int y) { for (; x < N; x += x & -x) (tr[x] += y) %= p; }
int ask(int x) { int res = 0; for (; x; x -= x & -x) (res += tr[x]) %= p; return res; } 

int main() {
	int n = read(), m = read();
	for (int i = 1; i <= n; ++ i) read(a[i]);
	for (int i = 1; i <= m; ++ i) read(b[i]);
	std::sort(b + 1, b + m + 1);
	for (int i = 1; i <= n; ++ i) {
		int x = std::lower_bound(b + 1, b + m + 1, a[i]) - b;
		if (b[x] == a[i] || a[i] > b[m] || a[i] < b[1]) continue;
		o[++ tot] = pii(a[i] - b[x - 1], b[x] - a[i]);
		t[++ cnt] = b[x] - a[i];
	}
	std::sort(t + 1, t + cnt + 1); cnt = std::unique(t + 1, t + cnt + 1) - t - 1;
	for (int i = 1; i <= tot; ++ i) o[i].second = std::lower_bound(t + 1, t + cnt + 1, o[i].second) - t;
	std::sort(o + 1, o + tot + 1, [](pii a, pii b) { return a.first == b.first ? a.second > b.second : a.first < b.first; });
	tot = std::unique(o + 1, o + tot + 1) - o - 1;
	f[0] = 1;
	for (int i = 1; i <= tot; ++ i) {
		f[i] = ask(o[i].second - 1) + 1;
		Modify(o[i].second, f[i]);
	}
	int ans = 0;
	for (int i = 0; i <= tot; ++ i) (ans += f[i]) %= p;
	std::cout << ans << std::endl;
	return 0;
}

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

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N,M,K; cin >> N >> M >> K;
	vector<ll> A(N),B(M);
	int res = 0;
	forn(i,0,N){
		cin >> A[i];
		if(i)A[i] += A[i-1];
		if(A[i] <= K){
			res = max(res,i+1);
		}
	}
	forn(i,0,M){
		cin >> B[i];
		if(i)B[i] += B[i-1];
		if(B[i] <= K){
			res = max(res,i+1);
		}
	}
	forn(i,0,N){
		if(A[i] >= K)break;
		ll queda = K-A[i];
		//cout << i << ' ' << A[i] << ' ' << queda << '\n';
		int ini = 0,fin = M-1;
		int tmp = i+1;
		while(ini < fin){
			int mit = (ini+fin)>>1;
			if(B[mit] <= queda)ini = mit+1;
			else fin = mit;
		}
		if(B[ini] > queda)ini--;
		//cout << ini << '\n';
		tmp += (ini+1);
		res = max(res,tmp);
	}
	cout << res << '\n';
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/


Measured memory_bytes: 6368
using System;
class Program {
    static void Main (string[] args) {
        var inp = Console.ReadLine().Split(' ');
        var inp2 = Console.ReadLine().Split(' ');

        int hp = int.Parse(inp[0]);
        int number = int.Parse(inp[1]);

        for(int i = 0;i < number;i++) {
            hp -= int.Parse(inp2[i]);
            if(hp <= 0) {
                Console.WriteLine("Yes");
                return;
            }
        }

        Console.WriteLine("No");
    }
}

Measured memory_bytes: 18016
def main(s):
    price_total = 700
    if s[0] == 'o':
        price_total += 100
    if s[1] == 'o':
        price_total += 100
    if s[2] == 'o':
        price_total += 100
    print(price_total)


s = input()
main(s)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;



void trace(int A[],int N){
    REP(i,N){
        if(i>0)printf(" ");
        printf("%d",A[i]);
    }
    printf("\n");
}


int main(){
    int N;
    cin >> N;
    int r[N];
    REP(i,N)cin >> r[i];
    int count = 0;
    REP(i,N){
        int minj = i;
        for(int j=i;j<N;j++){
            if(r[j] < r[minj])minj = j;
        }
        int v = r[i];
        r[i] = r[minj];
        r[minj] = v;
        if(i!= minj)count++;
    }


    trace(r,N);
    cout << count << endl;
}



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


int main(){
  int sum=0;
  string s;
  char num;

  while(cin >> s){
    if(s == "0") break;
    
    for(int i=0; i<(int)s.size() ; ++i){
      num = s[i] - '0';

      sum += num;
    }

    cout << sum << endl;

    sum = 0;
  }

  
  return 0;
}



Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define line printf("-----------------------------\n")
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define filein freopen("input.txt","r",stdin)
#define fileout freopen("output.txt","w",stdout)
using namespace std;
int  main()
{
    string str;
    cin>>str;
    int num=0;
    num=num*10+str[2]-'0';
    num=num*10+str[3]-'0';
    int num1=0;
    num1=num1*10+str[0]-'0';
    num1=num1*10+str[1]-'0';
    if(num>=1 and num<=12)
    {
        if(num1>=1 and num1<=12) cout<<"AMBIGUOUS"<<endl;
        else cout<<"YYMM"<<endl;
    }
    else if(num1>=1 and num1<=12)
    {
        if(num>=1 and num<=12) cout<<"AMBIGUOUS"<<endl;
        else cout<<"MMYY"<<endl;
    }
    else cout<<"NA"<<endl;


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define nn 3000009
char s[nn],t[nn];int n;
int from[nn];
#define err {puts("-1");exit(0);}
int main()
{
	scanf("%d",&n);
	scanf("%s%s",s+1,t+1);
	if(s==t) 
	{
		puts("0");
		exit(0);
	}
	
	int p=n;
	for(int i=n;i>=1;i--)
	{
		if(p>i) p=i;
		while(p) if(t[i]==s[p]) break;else p--;
		if(!p) err;
		from[i]=p;
	}
	
	int ans=0;
	deque<int> dq;int rig=0;
	from[n+1]=1324564;
	for(int i=n;i>=1;i--)
	{
		if(t[i]!=t[i+1])
		{
			if(i>=from[i+1])
            {
                rig--;
				dq.push_front(from[i+1]-rig-1);
                while(dq.back()+rig>=i) dq.pop_back();
                dq.push_back(i-rig);
            }
            else
			{
				dq.clear();
				if(from[i]!=i) dq.push_back(i-rig);
			}
            ans=max(ans,(int)dq.size());
		}
	}
	cout<<ans;
	return 0;
}

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

using namespace std;

char S[60] = {};

int main() {
	cin >> S;
	for (int i = 49; i >= 0; i--) {
		if (S[i] == 'F') {
			for (int j = 0; j < i; j++) {
				cout << S[j];
			}
			cout << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>   
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
     
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}
using Graph = vector<vector<int>>;
Graph G;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c, d; cin >> a >> b >> c >> d;
    if(d == 1) cout << 1 << endl;
    else cout << 0 << endl;
}

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

const int64_t MOD = 1000000007;
typedef int64_t ll;
typedef uint64_t ull;

#define INF LLONG_MAX

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  
  int n;
  cin >> n;
  
  // まずはエラトステネスのふるい
  int max = 55555;
  int flag[max+1] = {};
  flag[0] = flag[1] = 1;
  for(int i=2;i<=sqrt(max);i++){
    if(flag[i]==1) continue;
    for(int j=2; i*j<=max;j++){
    	flag[i*j] = 1;
    }
  }
  
  list<int> candidate;
  for(int i=0; i<=max;i++){
    if(flag[i]==0){
      if(i%5==1) candidate.push_back(i);
    }
  }
  int count = 0;
  for(auto c: candidate){
    cout << c << " ";
    count++;
    if(count==n)break;
  }
  cout << endl;
  
  return 0;
}



Measured memory_bytes: 3944
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] array = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
		System.out.println(array[sc.nextInt() - 1]);
	}
}


Measured memory_bytes: 21716
using System;
using System.Linq;
class Program{
  static void Main(string[] args){
    var vals = Console.ReadLine().Split().Select(x => int.Parse(x)).ToList();
    var N=vals[0];
    var A=vals[1];
    var B=vals[2];
    int ans=0;
    for(int i=0;i<=N;i++){
      int sum=sumDigits(i);
      if(A<=sum &&sum<=B){
      ans+=i;
      }
    }
	Console.WriteLine(ans);
  }
  static int sumDigits(int n) {
    int sum = 0;
    while (n > 0) {
      sum += n % 10;
      n = n / 10;
    }
    return sum;
  }
}

Measured memory_bytes: 13268
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

    private void run() {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        long[] a = new long[N];
        Map<Long, Integer> map = new HashMap<>();
        Long val;
        Long firstVal = scanner.nextLong();
        for (int i = 0; i < N - 1; i++) {
            val = scanner.nextLong();
            Integer fuga = map.get(val);
            if (fuga == null) {
                map.put(val, 1);
            } else {
                map.put(val, 1 + fuga);
            }
        }
        Map<Long, Integer> orig = (HashMap<Long, Integer>) ((HashMap<Long, Integer>) map).clone();
        Long prevVal = 0L;
        Long currVal = 0L;
        for (Long key : map.keySet()) {
            if (map.containsKey(firstVal ^ key)) {
                map = (HashMap<Long, Integer>) ((HashMap<Long, Integer>) orig).clone();
                decMap(map, key);
                prevVal = firstVal;
                currVal = key;

                while (map.containsKey(prevVal ^ currVal)) {
                    decMap(map, prevVal ^ currVal);
                    Long tmp = currVal;
                    currVal = currVal ^ prevVal;
                    prevVal = tmp;
                }
                if (map.size() == 0) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");
    }

    private void decMap(Map<Long, Integer> map, Long key) {
        Integer val = map.get(key);
        if (val == 1) {
            map.remove(key);
        } else {
            map.put(key, val - 1);
        }
    }
}


Measured memory_bytes: 62292
import numpy as np
from collections import defaultdict
from itertools import chain, combinations


def ext_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = ext_gcd(b % a, a)
        return g, x - (b // a) * y, y


def calc_div(n):
    sq = int(n**.5 + 10)
    x = np.arange(1, sq)
    x = x[n % x == 0]
    x = np.concatenate((x, n // x))
    return np.unique(x)


def solve(n):
    if n == 1:
        return 1
    factors = calc_div(2 * n)
    # print(factors)
    # trivial answer
    res = 2 * n - 1

    # power set
    for p in factors:
        q = (2 * n) // p
        if p == 1 or q == 1:
            continue
        a, x, y = ext_gcd(p, q)
        if a > 1:
            continue
        if x < 0:
            res = min(res, abs(p * x))
        else:
            res = min(res, abs(q * y))
        # print(p, q, p * x, q * y)
    # print(res)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(11) == 10
    assert solve(20200920) == 1100144


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


Measured memory_bytes: 766940
a, b, c = map(int, input().split())
if a == b == c:
    if a % 2 == 0:
        print(-1)
    else:
        print(0)
else:
    cnt = 0
    while a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
        a, b, c = (b+c)//2, (a+c)//2, (a+b)//2
        cnt += 1
    print(cnt)

Measured memory_bytes: 9152
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 303;
int a[N][N],n,m;
int c[N],cnt[N],vis[N];

int main(){
    scanf("%d%d",&n,&m);
    rep(i,0,n) rep(j,0,m) scanf("%d",a[i] + j) , --a[i][j];
    int ans=n+1;
    rep(i,0,m) {
        rep(i,0,n) while(vis[a[i][c[i]]]) ++c[i];
        rep(i,0,m) cnt[i]=0;
        rep(i,0,n) cnt[a[i][c[i]]]++;
        int Mx=0,id=0;
        rep(i,0,m) if(cnt[i]>Mx) Mx=cnt[i],id=i;
        ans=min(ans,Mx);
        vis[id]=true;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#define ALL(x) (x).begin(), (x).end()     //昇順
#define RALL(x) (x).rbegin(), (x).rend()  // 降順
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
const long long mod = 1e9 + 7;
typedef long long ll;
typedef priority_queue<int> PQ;
typedef vector<long long> VL; // VL a(n);
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<VS> VSS;
typedef vector<VC> VCC;
typedef vector<VL> VLL; // VII a(n,VI(m)) n * m
typedef pair<ll, ll> PL;
typedef map<ll, ll> MP; // MP a;
typedef vector<pair<ll, ll>> PS;

template <class T, class U>
bool chmax(T &a, U b) {
  if (a <= b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T, class U>
bool chmin(T &a, U b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
  os << "}";
  return os;
}

// g++ -std=c++11 prac.cpp
// operator << (cout,a);
// chmin(min,a)

int main() {
  ll n,k,m,x=0,y=0,z = 0,h=0,w=0,ans=0,sum = 0, Max = -1, Min = 3e9+1;
  string s,t;
  bool ok=true;
  cin >> s;
  for(int bit = 0; bit < (1 << s.size()); bit++){
    sum = s[0]-'0';
    for(int i=1; i<s.size(); i++){
      if(bit & (1<<i))
        sum -= (s[i]-'0');
      else
        sum += (s[i]-'0');
    }
    if(sum == 7){
      cout << s[0];
      for(int i=1; i<s.size(); i++){
        if(bit & (1<<i)){
          cout << '-'; cout << s[i];
        }
        else{
          cout << '+'; cout << s[i];
        }
      }
       cout << "=7"; return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#define MOD 924844033
using namespace std;
const int MAXN = 2005;
int f[2][MAXN*2][MAXN],n,k,tot,g[MAXN],fac[MAXN];
bool ed[MAXN*2];
inline void add(int &x,int a)
{
	x+=a;
	if(x>=MOD)x-=MOD;
	if(x<0)x+=MOD;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;++i){
		int len=0;
		int p=i,sta=1;
		while((sta==1 || p<=2*n) && (sta==-1 || p<=n)){
			++len;
			p+=k+sta*n;
			sta=-sta;
		}
		ed[tot+=len]=1;
	}
	for(int i=n+1;i<=n+k;++i){
		int len=0;
		int p=i,sta=-1;
		while((sta==1 || p<=2*n) && (sta==-1 || p<=n)){
			++len;
			p+=k+sta*n;
			sta=-sta;
		}
		ed[tot+=len]=1;
	}
	f[0][0][0]=1;
	ed[0]=1;
	for(int i=1;i<=n*2;++i)
		for(int j=0;j<=n;++j){
			f[0][i][j]=f[0][i-1][j]+f[1][i-1][j];
			if(f[0][i][j]>=MOD)f[0][i][j]-=MOD;
			if(!ed[i-1])f[1][i][j]=f[0][i-1][j-1];
		}
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=(long long)fac[i-1]*i%MOD;
	for(int i=0;i<=n;++i)
		g[i]=(long long)(f[0][n*2][i]+f[1][n*2][i])%MOD*fac[n-i]%MOD;
	int ans=0;
	for(int i=0,sta=1;i<=n;++i,sta=-sta)
		add(ans,g[i]*sta);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 62976
'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf8');
// Your code here!
 
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	let s = input;
	//出力
	console.log(s[2]==s[3]&&s[4]==s[5]?"Yes":"No");
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7500
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1e9 + 7;

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

    vector<vector<long long int>> a(n, vector<long long int>(n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> a[i][j];
        }
    }

    vector<vector<long long int>> dp(n, vector<long long int>(n));// id.
    for(int i=0; i<n; i++) dp[i][i] = 1;

    for(int i=0; i<60; i++){// 2^60 < 10^18
        vector<vector<long long int>> c(n, vector<long long int>(n));
        if(((k>>i) & 1) == 1){
            for(int j=0; j<n; j++){
                for(int l=0; l<n; l++){
                    for(int m=0; m<n; m++){
                        c[j][l] += a[j][m] * dp[m][l];
                        c[j][l] %= MOD;
                    }
                }
            }
            dp = c;
        }

        vector<vector<long long int>> b(n, vector<long long int>(n));
        for(int j=0; j<n; j++){
            for(int l=0; l<n; l++){
                for(int m=0; m<n; m++){
                    b[j][l] += a[j][m] * a[m][l];
                    b[j][l] %= MOD;
                }
            }
        }
        a = b;
    }

    long long int ans = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            ans += dp[i][j];
            ans %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
N, W = map(int, input().split())
d = []
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))

d = sorted(d)
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        w1, v1 = d[i]
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        if w + w1 <= W:
            dp[i + 1][w + w1] = max(dp[i + 1][w + w1], dp[i][w] + v1)


num = 0
for i in range(W + 1):
    num = max(num, dp[N][i])

print(num)

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

int main(){
	string s;
	cin>>s;
	int q;
	cin>>q;
	deque<char>deq;
	for(int i=0; s[i]; i++) deq.push_back(s[i]);
	bool reversed = false;
	while(q--){
		int op;
		cin>>op;
		if(op==1) reversed = !reversed;
		if(op==2){
			int a;
			char b;
			cin>>a>>b;
			if(a==1){
				if(reversed) deq.push_back(b);
				else deq.push_front(b);
			}
			else{
				if(reversed) deq.push_front(b);
				else deq.push_back(b);
			}
		}
	}
	if(reversed){
		while(!deq.empty()){
			cout<<deq.back();
			deq.pop_back();
		}
	}
	else{
		while(!deq.empty()){
			cout<<deq.front();
			deq.pop_front();
		}
	}
}

Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
bool v[N];
int cnt[N];
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	v[1] = 1;
	for (int i = 1; i <= n; ++ i) cnt[i] = 1;
	for (int i = 0; i < m; ++ i) {
		int a, b;
		scanf("%d%d", &a, &b);
		cnt[a] --;
		cnt[b] ++;
		if (v[a]) v[b] = 1;
		if (cnt[a] == 0) v[a] = 0;
	}
	int ans = 0;
	for (int i = 1; i <= n; ++ i) if (v[i]) ans ++;
	printf("%d\n", ans);
}



Measured memory_bytes: 768
import std.stdio;
import std.array;
import std.algorithm;
import std.string;
import std.conv;

void main(){
    int[] pasta; int[] juice;
    for(int i = 0; i < 3; i++){
        pasta ~= readln().chomp().to!int();
    }
    for(int i = 0; i < 2; i++){
        juice ~= readln().chomp().to!int();
    }
    writeln(pasta.minPos()[0] + juice.minPos()[0] - 50);
}

Measured memory_bytes: 964
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

 
int dp[1000][1000];
int x,y;

const int MAX = 1000006;
int fac[MAX], inv[MAX], finv[MAX];

void pre(){
	inv[1]=1;
	for (int i = 2; i <MAX ; i++)
	{
		inv[i]=inv[mod%i]*(mod-mod/i)%mod;
	}
	fac[0]=finv[0]=1;
	for (int i = 1; i < MAX; ++i)
	{
		fac[i]=fac[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
int ncr(int n, int r){
	if(r<0||r>n)return 0;
	return fac[n]*finv[r]%mod*finv[n-r]%mod;
}

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
	
	cin >> x >> y;
	dp[0][0] = 1;
	pre();
	// for(int i=0;i<=x;i++){
	// 	for(int j=0;j<=y;j++){
	// 		dp[i+2][j+1] = ( dp[i+2][j+1] + dp[i][j] )%mod;
	// 		dp[i+1][j+2]  = ( dp[i+1][j+2] + dp[i][j] )%mod;
	// 		if(dp[i][j]);
	// 		//cout << i << " " << j << " " << dp[i][j] << endl;
	// 	}
	// }
	// cout << dp[x][y] << endl;

	int ans = 0;
  
  for(int i=0;i<=x;i++){
  	int steps = x-i*2;
  	if(steps<0)continue;
  	int xw = ncr( i+steps, i );
  	int yd = i + steps*2;
  	if(yd!=y)continue;
  	int xy = ncr( i+steps, i );
  	ans = ( ans + xy%mod)%mod;
  }  
  cout << ans << endl;

return 0;
}
///....


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

def main():

	W,H,x,y,r = map(int,raw_input().split())
	if 0 <= (x-r) and (x+r) <= W and 0 <= (y-r) and (y+r) <= H:
		print('Yes')
	else:
		print('No')

if __name__ == "__main__":

	main()


Measured memory_bytes: 6444
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
typedef long long ll;
typedef vector<int> vi;
typedef unsigned long ul;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef set<int> si;
typedef multiset<int> mi;
 
const ll INF = 1e18;
const int MOD = 1e9+7;

int main() {
	
	int a;
	cin>>a;
	cout<<a+pow(a,2)+pow(a,3)<<"\n";
	
	return 0;
}


Measured memory_bytes: 4068
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<int, int> P;


int main(){
    int N;
    cin >> N;
    ll x[202000];
    ll y[202000];
    for(int i = 0; i < N; i++){
        cin >> x[i];
        y[i] = x[i];
    }

    sort(y, y+N);

    ll m1 = y[N/2-1];
    ll m2 = y[N/2];
    for(int i = 0; i < N; i++){
        if(x[i] > m1){
            cout << m1 << endl;
        }
        else if(x[i] <= m1){
            cout << m2 << endl;
        }
    }

    return 0;

}


Measured memory_bytes: 6016
A, B, H, M = gets.split.map(&:to_i)

def get_x_y_by_degree d, len
  r = d / 180 * Math::PI
  x = Math.cos(r) * len
  y = Math.sin(r) * len
  [x, y]
end

hour_d = H / 12.0 * 360 + M / 60.0 * 30
min_d = M / 60.0 * 360

hour = get_x_y_by_degree hour_d, A
minute = get_x_y_by_degree min_d, B

dis = Math.sqrt (hour[0] - minute[0]) ** 2 + (hour[1] - minute[1]) ** 2
puts dis

Measured memory_bytes: 14644
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
    int N,K;
    cin >> N >> K;
    int ans = 0;
    while(N) {
        N /= K;
        ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

#define N 10000
#define Q 500

int main(){
  int n,q;
  int s[N],t[Q];
  int i,j,count=0;

  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&s[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++)scanf("%d",&t[i]);

  for(i=0;i<q;i++){/*t*/
    for(j=0;j<n;j++){/*s*/
      if(t[i]==s[j]){
	count++;
	break;
      }
    }
  }
  printf("%d\n",count);
  return 0;
}



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

using namespace std;

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


#define PP pair<ll, P>
struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

vector<PP> g;
ll kr() {
	ll cost = 0;
	sort(ALL(g));
	UnionFind uni(110000);
	REP(i, g.size()) {
		ll a = g[i].second.first, b = g[i].second.second;
		if (!uni.findSet(a, b)) {
			uni.unionSet(a, b);
			cost += g[i].first;
		}
	}
	return cost;
}

int main() {
	ll n, m;
	cin >> n >> m;
	REP(i, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		g.push_back(PP(c, P(a, b)));
	}
	cout << kr() << endl;
}



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

#define MOD 1000000007 // 10^9 + 7
#define MAX 20000
using namespace std;


long long int 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 int 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;
}


int main() {
  // 前処理
  COMinit();

  int n, k;

  scanf("%d%d", &n, &k);

  for (int i = 1; i <= k; i++) {
    long long int ans = ( COM(k-1, i-1) * COM(n-k+1, i) ) % MOD;
    printf("%lld\n", ans);
  }

  return 0;
}



Measured memory_bytes: 768
let rec lower_bound l r p =
  if r <= 1 + l
  then r
  else let m = (l + r) / 2 in
       if p m
       then lower_bound l m p
       else lower_bound m r p

let () = Scanf.scanf "%d %d\n" @@ fun n k ->
  let as_ = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ Fun.id in
  Printf.printf "%d\n" @@
  lower_bound 0 10000000000 @@ fun l ->
    ( >= ) k @@
    Array.fold_right (fun a -> ( + ) @@ (a - 1) / l) as_ 0

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

int cnt[505][505];

int main(){
  int n,m;
  cin>>n>>m;
  tuple<ll,ll,ll> xyz[1005];
  rep(i,n){
    ll x,y,z;
    cin>>x>>y>>z;
    xyz[i]=make_tuple(x,y,z);
  }
  ll ans=0;
  int pm[2]={1,-1};
  rep(i,8){		      
    ll sum[1005];
    rep(j,n){
      sum[j]=pm[i/4]*(get<0>(xyz[j]))+pm[(i/2)%2]*(get<1>(xyz[j]))+pm[i%2]*(get<2>(xyz[j]));
    }
    sort(sum,sum+n);
    reverse(sum,sum+n);
    ans=max(ans,accumulate(sum,sum+m,0ll));
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
int main ()
{
    ll a,b,c,d;
   cin>>a>>b>>c>>d;
   vector<ll> v;
   v.pb(a*c);
   v.pb(a*d);
   v.pb(b*c);
   v.pb(b*d);
   cout<<*max_element(all(v));
   return 0;

}

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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

int N;

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

  cin >> N;
  deque< int > ans;
  REP(i, N) {
    CIN(a);
    if (i & 1) ans.push_back(a);
    else ans.push_front(a);
  }

  if (N & 1) {
    REP(i, N) {
      cout << ans.front();
      ans.pop_front();
      if (i < N - 1) cout << " ";
    }
  } else {
    RREP(i, N) {
      cout << ans.back();
      ans.pop_back();
      if (i > 0) cout << " ";
    }
  }
  cout << endl;

  return 0;
}




Measured memory_bytes: 3072
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod = 1e9 + 7;
void solve(){
    int n;
    cin >> n;
    int cnt0 = 0, cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x % 4 == 0) cnt2++;
        else if (x % 2 == 0) cnt1++;
        else cnt0++;
    }
    if (cnt2 >= cnt0) cout << "Yes";
    else if (cnt0 - cnt2 == 1 && cnt1 == 0) cout << "Yes";
    else cout << "No";
}
int main(){
    speed;
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve();
    }
}

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

using namespace std;

class Dice
{
  public:
    vector<int> diceNum;
    Dice(vector<int>& inputs);
    void toW();
    void toS();
    void ParallelRotation();
};

Dice::Dice(vector<int>& inputs)
{
  diceNum=inputs;
}

void Dice::toW()
{
  swap(diceNum[0],diceNum[3]);
  swap(diceNum[0],diceNum[5]);
  swap(diceNum[0],diceNum[2]);
}

void Dice::toS()
{
  swap(diceNum[0],diceNum[1]);
  swap(diceNum[0],diceNum[5]);
  swap(diceNum[0],diceNum[4]);
}

void Dice::ParallelRotation()
{
  swap(diceNum[1],diceNum[2]);
  swap(diceNum[2],diceNum[4]);
  swap(diceNum[4],diceNum[3]);
}

bool Judge(Dice& dice1,Dice& dice2)
{
  int count=0;
  for(int i=0;i<6;i++)
  {
    if(dice1.diceNum[i]==dice2.diceNum[i]) count++;
  }
  if(count==6)return true;
  else return false;
    
}

bool preJudge(Dice& dice1,Dice& dice2)
{
  int count=0;
  bool flag=false;
  while(1)
  {
    dice2.toS();
    for(int j=0;j<4;j++)
    {
      dice2.ParallelRotation();
      flag=Judge(dice1,dice2);
      if(flag==true) break;
    }
    if(flag==true) break;
    dice2.toW();
    for(int j=0;j<4;j++)
    {
      dice2.ParallelRotation();
      flag=Judge(dice1,dice2);
      if(flag==true) break;
    }
    count++;
    if(flag==true) break;
    if(count==3)break;
  } 
  return flag;
}

int main(int argc,char* argv[])
{
  vector<int> inputs(6);
  int number;
  int count =0;
  cin >> number;
  bool flag=false;
  
  vector<Dice> Dices;
  for(int i=0;i<number;i++)
  {
    for(int j=0;j<6;j++)
    {
      cin >> inputs[j];
    }
    Dices.push_back(Dice(inputs));
  }
  for(int i=0;i<number-1;i++)
  {
    for(int j=i+1;j<number;j++)
    {
      flag = preJudge(Dices[i],Dices[j]);
      if(flag==true) break;
    }
    if(flag==true) break;
  }
  if(flag==true) cout << "No" << endl;
  else if(flag==false) cout << "Yes" << endl;
}

Measured memory_bytes: 3164
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();

    let ans = n * (n - 1) / 2;

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


Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
typedef long long LL;
typedef long double Lf;
#define Rep(i,a,n)for(int i=(int)(a);i<(int)(n);i++)
#define rep(i,n)Rep(i,0,n)
#define Ma(x,y) ((x)>(y)?(x):(y))
#define mi(x,y) ((x)<(y)?(x):(y))
#define N 1001
#define MOD 1000000007
int acs(const void* a, const void* b) { return *(int*)a - *(int*)b; }//1,2,3,4
int des(const void* a, const void* b) { return *(int*)b - *(int*)a; }//8,7,6,5
int cmp_char(const void* a, const void* b) { return *(char*)a - *(char*)b; }//a,b,c,d
int cmp_str(const void* a, const void* b) { return strcmp(*(const char**)a, *(const char**)b); }//aaa,aab
//temmie_のsnippet

int main() {
	int n,a,c[9]={0};
	scanf("%d",&n);
	rep(i,n){
		scanf("%d",&a);
		rep(j,8)if(400*j<=a&&a<=400*j+399)c[j]++;
	}
	rep(j,8){n-=c[j];if(c[j])c[8]++;}
	printf("%d %d",c[8]?c[8]:1,n+c[8]);
}

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

prev = A[0]
dist = K - A[N-1] + A[0]
for i in range(1,N):
#  print('dist=', dist)
#  print('A[i]=', A[i])
#  print('prev=', prev)
#  print('A[i]-prev=', A[i] - prev)
  if A[i] - prev > dist:
    dist = A[i] - prev
  prev = A[i]

ans = K - dist
print(ans)


Measured memory_bytes: 26420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int main() {
  int N; cin >> N;
  vector<int> A(N),B(N);
  rep(i,N) {
    cin >> A[i];
    B[i] = A[i];
  }

  sort(all(B));

  int maxA = B[N-1];
  int nextA = B[N-2];
 
  rep(i,N) {
    if(A[i] == B[N-1]) A[i] = B[N-2];
    else A[i] = B[N-1];
  }
  
  rep(i,N) cout << A[i] << endl;
}

Measured memory_bytes: 3200