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

#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define rep(i, x, y) for(decltype(y) i = (x) - ((x) > (y)); i != (y) - ((x) > (y)); i += 1 - 2 * ((x) > (y)))
#define trav(i,a) for(auto& (i) : (a))
#define all(a) (a).begin(),(a).end()
#define sz(a) int((a).size())
#define clr(a,x) memset((a),(x),sizeof(a)) // array (0,-1)
#define dbg(x) cerr << "STDERR => " << __LINE__ << ": " << #x << " = " << (x) << "  :(\n";
#define pb push_back
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline void cpuTime() { cerr << "cpu time : " << double(clock())/CLOCKS_PER_SEC << "\n"; return; }
using ll = long long;
using ull = unsigned long long;
using F = float;
using D = double;
using vi = vector<int>;
using pii = pair<int,int>;

// calculate cycle length
vi cycle(int n, vi &p){

    vector<bool> isVisited(n,false);
    vi clen(n,0); // store cycle length

    rep(i,0,n){
        if(!isVisited[i]){
            int in = i, cnt = 0;
            stack<int> q;
            while(!isVisited[in]){
                ++cnt;
                q.push(in);
                isVisited[in] = true;
                in = p[in];
            }

            while(!q.empty()){
                clen[q.top()] = cnt;
                q.pop();
            }
        }
    }

    return clen;
}

void solve(){

    int n = 0, k = 0;
    cin >> n >> k;

    vi p(n,0), c(n,0);
    rep(i,0,n){
        int tmp = 0;
        cin >> tmp;
        p[i] = tmp-1;
    }
    rep(i,0,n) cin >> c[i];

    vi clen = cycle(n,p);
    ll ans = LLONG_MIN;
    rep(i,0,n){
        int l = clen[i], in = i;
        ll cost = 0;
        int m = min(l,k);
        rep(j,0,m){
            cost += c[in];
            ans = max(ans, cost);
            in = p[in];
        }

        if(k > l){
            cost = (k/l-1)*cost;
            ans = max(ans, cost);

            rep(j,0,l){
                cost += c[in];
                ans = max(ans, cost);
                in = p[in];
            }

            rep(j,0,k%l){
                cost += c[in];
                ans = max(ans, cost);
                in = p[in];
            }
        }
    }

    cout << ans << "\n";
    return;
}

/*
 read the question carefully ( what're the exact constraints? )
 look out for SPECIAL CASES (n=1?) and OVERFLOW (ll vs int?) ARRAY OUT OF BOUNDS
 Check datatypes
*/
int main(){

    fast_io;
    int t=1;
    // cin >> t;

    while(t--){
        solve();
    }

    cpuTime();
return 0;
}


Measured memory_bytes: 3948
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        int N;
        Long[] A;
        long ans = 0;

        void solve(InputReader in, PrintWriter out) {
            N = in.nextInt();
            A = new Long[3*N];
            for (int i = 0; i < 3*N; ++i) {
                A[i] = in.nextLong();
            }
            Arrays.sort(A, Comparator.reverseOrder());

            for (int i = 0; i < N; ++i) {
                ans += A[2*i + 1];
            }

            out.println(ans);
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        int[] nextIntArray(int n) {
        	int[] arr = new int[n];
        	for (int i = 0; i < n; ++i) {
        		arr[i] = nextInt();
        	}
        	return arr;
        }

        long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = nextLong();
            }
            return arr;
        }
    }
}


Measured memory_bytes: 58212
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#include <climits>
#include <memory>
#include <numeric>
#include <utility>


#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
#define PI 3.14159265358979323846264338327950L;
const int INF2 = 1001001001;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
const ll LINF = 1e18 + 100;
using namespace std;
using Graph = vector<vector<int>>;



int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
// 最小公倍数の計算

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


	void init(int n)
	{
		for (int i = 0; i < n; i++) par[i] = i;
		for (int i = 0; i < n; i++) r[i] = 0;
	}

	int find(int x)
	{
		if (par[x] == x)return x;
		else return find(par[x]);
	}

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (r[x] < r[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (r[x] == r[y])
			{
				r[x]++;
			}
		}
	}
};

const int MAX_N = 110000;

int memo[MAX_N];

int rec(int n) {
	if (n == 0)return 0;
	if (memo[n] != -1)return memo[n];

	int res = n;

	for (int pow6 = 1; pow6 <= n; pow6 *= 6)res = min(res, rec(n - pow6) + 1);

	for (int pow9 = 1; pow9 <= n; pow9 *= 9)res = min(res, rec(n - pow9) + 1);

	return memo[n] = res;
}

int calc(int x) {
	int ret = 0;
	while (x % 2 == 0) {
		x /= 2;
		ret++;
	}

	return ret;
}

int a[12][12];
int D;
ll G;
vector<ll> P, C;

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

	int k;

	cin >> k;
	int gu = 0;
	int ki = 0;
	rep(i, 1, k + 1) {
		if (i % 2 == 0)gu++;
		else ki++;
	}
	 
	cout << gu * ki << endl;
	
}
	

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;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 dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define arrdump(n,a) for(int i=0;i<n;i++) {cout<<((i>0)? " ":"")<<a[i];}cout<<"\n";


typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp

#define MAX 505
int N;
int A[MAX];

static void insertion() {
    for (int i = 1; i < N; i++) {
        int j = i - 1;
        int v = A[i];

        while(j >= 0 && A[j] > v) {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        arrdump(N, A);
    }
}

int main() {
    cin >> N;
    REP(i, N) cin >> A[i];
    arrdump(N, A);
    insertion();
    return 0;
}


Measured memory_bytes: 3120
#include <iostream>

using namespace std;

int main(){
	int N, A[20], B[20], C[20];
	cin >> N;
	for (int i = 0; i < N; i++){
		cin >> A[i];
		A[i]--;
	}
	for (int i = 0; i < N; i++){
		cin >> B[i];
	}
	for (int i = 0; i < N-1; i++){
		cin >> C[i];
	}

	int ans = B[A[0]];
	for (int i = 1; i < N; i++){
		ans += B[A[i]];
		if (A[i] == A[i-1] + 1){
			ans += C[A[i-1]];
		}
	}

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

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

int main(){
  int N, D;
  cin >> N >> D;
  if (N % (2*D +1) == 0){
    cout << N / (2*D +1) << endl;
  } else {
    cout << N / (2*D +1) + 1 << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
 
using namespace std;
 
typedef long long int ll;
typedef vector<long long int> VL;
typedef vector<VL> VVL;

string sanitize(string s) {
    for(int i=0; i<s.length(); i++) {
        char c = s[i];
        if('A' <= c && c <= 'Z') {
            s[i] = c + ('a' - 'A');
        }
    }
    return s;
}
 
int main() {
    string w, t_w;
    
    cin >> w;
    int res = 0;
    while(1) {
        cin >> t_w;
        if(t_w.compare("END_OF_TEXT") == 0) break;
        
        t_w = sanitize(t_w);
        if(t_w.compare(w) == 0) {
            res++;
        }
    }
    
    cout << res << endl;
    
    return 0;
}



Measured memory_bytes: 3176
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.io.PrintWriter;

@SuppressWarnings("unchecked")
public class Main {
    public static void main(String[] args) throws IOException {
        final String s;

        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            s = reader.readLine();
        }

        PrintWriter out = new PrintWriter(System.out);

        final String[] sl = s.split(" ");
        int N = Integer.parseInt(sl[0]);
        int Y = Integer.parseInt(sl[1]);

        boolean flg = false;
        for (int i = 0; i <= N; i++)  {
            for (int j = 0; i + j <= N; j++) {
                int k = N - i - j;
                if (Y == 10000 * i + 5000 * j + 1000 * k) {
                    out.println(i + " " + j + " " + k);
                    flg = true;
                    break;
                }
            }
            if (flg) break;
        }

        if (!flg) out.println("-1 -1 -1");

        out.flush();
    }
}


Measured memory_bytes: 25172
#!/usr/bin/env python
# -*- coding:utf-8 -*-

from __future__ import division, print_function, absolute_import, unicode_literals

N, T = map(int, input().split())
A = list(map(int, input().split()))

maxA = [0] * N
minA = [0] * N

maxA[N-1] = A[-1]
for i in range(1, N):
    maxA[N-i-1] = max(maxA[N-i], A[N-i])
# print(maxA)

max_diff = -10000000000
for i in range(N-1):
    max_diff = max(maxA[i] - A[i], max_diff)
# print(max_diff)
cnt = 0
for i in range(N-1):
    if maxA[i] - A[i] == max_diff:
        cnt += 1
print(cnt)


Measured memory_bytes: 15148
MAX = 10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def Com(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

N, A, B, C, D = map(int, input().split())
dp = [[0]*(N+1) for _ in range(B-A+2)]
dp[0][0] = 1

for i in range(B-A+1):
    for j in range(N+1):
        m = 1
        
        for k in range(min(D, (N-j)//(i+A))+1):
            if k==0 or C<=k:
                dp[i+1][j+(i+A)*k] += m*finv[k]*dp[i][j]
                dp[i+1][j+(i+A)*k] %= MOD
            
            m *= Com(N-j-(i+A)*k, i+A)
            m %= MOD
            
print(dp[B-A+1][N])


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

signed main(){
  int N; cin >> N;
  vector<int> a(N);
  for(int i = 0; i < N; i++) cin >> a[i];
  deque<int> deq;
  for(int i = 0; i < N; i++){
    int id = lower_bound(deq.begin(), deq.end(), a[i]) - deq.begin();
    if(id == 0) deq.push_front(a[i]);
    else deq[id - 1] = a[i];
  }
  cout << deq.size() << endl;
}

Measured memory_bytes: 1792
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N;
    cin >> N;

    vector<int> A(N - 1);
    REP(i, N - 1) cin >> A[i];

    map<int, int> m;
    REP(i, N - 1) {
        m[A[i] - 1]++;
    }

    REP(i, N) {
        print(m[i]);
    }
}


Measured memory_bytes: 13544
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//#define int long long
using bll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
#define p(var) std::cout<<var<<std::endl
#define PI (acos(-1))
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(v) (v).begin(), (v).end()
#define uniq(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
template<typename T> inline void pv(vector<T> v) { for(ll i=0, N=v.size(); i<N; i++) cout<< v[i] << (i==N-1 ? '\n' : ' '); }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T1, typename T2> inline T1 power(T1 x, T2 n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T> class dvector : public std::vector<T> {
public:
	dvector() : std::vector<T>() {}
	explicit dvector(size_t n, const T& value = T()) : std::vector<T>(n,value) {}
	dvector(const std::vector<T>& v) : std::vector<T>(v) {}
	T& operator[](size_t n){ return this->at(n); }
};
template<typename T1, typename T2> ostream& operator<<(ostream& s, pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, dvector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){ s << v[i]; if (i < len - 1) s << "\t"; } return s; }
template<typename T> ostream& operator<<(ostream& s, dvector< dvector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){ s << vv[i] << endl; } return s; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, map<T1, T2>& m) {
	s << "{" << endl; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << endl; } s << "}" << endl; return s; }
template<typename T> ostream& operator<<(ostream& s, set<T>& se) {
	s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}" << endl; return s; }
template<typename T> ostream& operator<<(ostream& s, multiset<T>& se) {
	s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}" << endl; return s; }
#ifdef LOCAL_DEV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#ifdef LOCAL_TEST
	#define vector dvector
#endif

/*-----8<-----8<-----*/



ll N;


void input() {
	scanf("%lld", &N);
	vector<pair<ll,ll>> a;
	rep(i, N){
		ll t;
		cin>>t;
		pair<ll,ll> tt=make_pair(t,i+1);
		a.push_back(tt);
	}
	sort(all(a));
	rep(i,N){
		cout<< a[i].second << (i==N-1 ? '\n' : ' ');
	}
}

signed main() {
	input();

	return 0;
}


Measured memory_bytes: 2544
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int INT_INF = 1e9;
const ll MOD = 1e9 + 7;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 0; i <= n; i++)
#define rrep(i,n) for(int i=n;i>0;i--)
#define RREP(i,n) for(int i=n;i>=0;i--)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
using fint64 = int_fast64_t;
int dp[3005][3005];

int main() { 
	string s, t;
	cin >> s >> t;
	dp[0][0]=0;
		rep(i,s.size()){
			rep(j,t.size()){
				if(s[i]==t[j]){
					dp[i+1][j+1]=dp[i][j]+1;
				}else{
					dp[i+1][j+1]=max({dp[i][j],dp[i+1][j],dp[i][j+1]});
				}
			}
		}
		//int len=dp[s.size()][t.size()];
		//cerr<<len<<endl;
                int i = s.size(), j = t.size();
                int p = dp[i][j];
                set<int> a;
                while (p) {
                  if (dp[i - 1][j] == p)
                    i--;
                  else if (dp[i][j - 1] == p)
                    j--;
                  else {
                    a.insert(i);
                    i--;
                    j--;
                    p--;
                  }
                }
                auto itr = a.begin();
                while (itr != a.end()) {
                  cout << s.at(*itr - 1);
                  itr++;
                }
                cout << endl;
                return 0;
}


Measured memory_bytes: 35584
#include <iostream>
using namespace std;
int n,a[100010];
int b[100010]={0},ans;
int main()
{
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>a[i];
		a[i]++;
		b[a[i]-1]++;
		b[a[i]]++;
		b[a[i]+1]++;
	}
	for (int i=0;i<100005;i++)
	{
		ans=max(ans,b[i]);
	}
	cout<<ans<<endl;
	system("pause");
    return 0;
}

Measured memory_bytes: 1268
#include <cstdio>
#define rg register

const int N=200101,p=1e9+7;
int fac[N],inv[N],n,a,W,H,A,B;

inline int c(int x,int y) {return 1ll*fac[x]*inv[y]%p*inv[x-y]%p;}

inline int qpow(int A,int B){int r=1;for(;B;B>>=1,A=1ll*A*A%p)if(B&1)r=1ll*r*A%p;return r;}
template <typename _tp> inline void pls(int&A,_tp B){A=A+B<p?A+B:A+B-p;}
template <typename _tp> inline _tp max(_tp A,_tp B){return A>B?A:B;}

int main(){
	scanf("%d%d%d%d",&H,&W,&A,&B);
	int lim=max(H-A+B-2,W-B+H);
	fac[0]=inv[0]=1;
	for(rg int i=1;i<=lim;++i)fac[i]=1ll*fac[i-1]*i%p;
	inv[lim]=qpow(fac[lim],p-2);
	for(rg int i=lim-1;i;--i)inv[i]=1ll*inv[i+1]*(i+1)%p;
	for(rg int i=0;i<H-A;++i)
		pls(a,1ll*c(i+B-1,i)*c(W-B+H-i-2,W-B-1)%p);
	printf("%d\n",a);return 0;
}

Measured memory_bytes: 1792
N = int( input())
A = list( map( int, input().split()))
B = [ ( abs(A[i]), i) for i in range(N)]
B.sort( key=None, reverse = True)
_,s = B[0]
ans = 0
ANS = []
if A[s] == 0:
    pass
else:
    for i in range(N):
        if i == s:
            continue
        ANS.append( str(s+1) + " " + str(i+1))
        ans += 1
    if A[s] > 0:
        for i in range(N-1):
            ANS.append( str(i+1) + " " + str(i+2))
            ans += 1
    else:
        for i in range(N-1, 0, -1):
            ANS.append( str(i+1) + " " + str(i))
            ans += 1
print(ans)
for i in range(ans):
    print( ANS[i])


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

using ll = long long;

const ll MOD = 1e9+7;

int main() {
   // 入力
   int H, W, K;
   cin >> H >> W >> K;

   // DPテーブルを初期化する
   ll dp[H+1][W];
   fill(dp[0], dp[H+1], 0);
   dp[0][0] = 1;

   for (int h = 0; h < H; h++) { // それぞれの高さについてループを回す
      for (int mask = 0; mask < (1<<(W-1)); ++mask) { // bit全探索のループ

         // 横線が隣り合っていないかチェック
         bool ok = true;
         for (int i = 0; i < W-2; ++i) {
            // これで末尾が11のときにはじくことが出来る
           if (((mask >> i) & 3) == 3) ok = false;
         }
         // 隣り合っていたらこの先の処理を飛ばす
         if (!ok) continue;

         int perm[W];
         for (int i = 0; i < W; i++) perm[i] = i;

         for (int i = 0; i < W-1; i++) {
            if ((mask >> i) & 1) {
               swap(perm[i], perm[i+1]);
            }
         }

         for (int i = 0; i < W; i++) {
            dp[h+1][perm[i]] += dp[h][i];
            dp[h+1][perm[i]] %= MOD;
         }
      }
   }

   cout << dp[H][K-1] << endl;

   return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


N, M = read_ints()
A = read_ints()
ans = N - sum(A)
print(ans if ans >= 0 else -1)


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

using namespace std;

int main() {
  // K: right off the bat, it feels like it would require
  // some sort of bitmask DP, but with 2^100 states, that's clearly
  // wrong...
  //
  // oh wow I really misread that, it's not that you can't
  // reuse an element of A
  //
  // so this should be just a DP with good and bad states
  // 10^5 states, 100 transitions: 10^7, which is totally fast
  // enough


  cin.tie(0);
  cin.sync_with_stdio(0);

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

  bool dp[k+1];
  // 0 is a bad state; in other words, player 2 would win
  // if you started the game with 0 stone
  dp[0] = false;
  for(int i = 1; i<=k; ++i) {
    // i is good if you can go to any bad state; bad otherwise
    bool can_go_bad = false;
    for(int j = 0; j<n; ++j) {
      if(a[j] <= i && !dp[i-a[j]]) can_go_bad = true;
    }
    dp[i] = can_go_bad;
  }
  cout << (dp[k] ? "First" : "Second") << endl;
}


Measured memory_bytes: 384
import heapq

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key = lambda x:x[0])
ab.append([10 ** 10, 0])
ans = 0
cand = []
day = 1
pos = 0
while day <= m:
    while ab[pos][0] <= day:
        heapq.heappush(cand, ab[pos][1] * -1)
        pos += 1
    day += 1
    if cand:
        ans += heapq.heappop(cand) * -1
print(ans)
        

Measured memory_bytes: 97608
if __name__ == "__main__":
    n = input()

    if len(n) > 1:
        tmp = n[0] + '9' * (len(n) - 1)
    else:
        print(int(n))
        exit()

    if int(tmp) > int(n):
        tmp = str(int(n[0]) - 1) + '9' * (len(n) - 1)

    ans = 0
    for s in tmp:
        ans += int(s)

    print(ans)


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef tuple<int,int,int> iii;
typedef vector<iii> viii;

#define umap unordered_map
#define uset unordered_set
#define pb push_back
#define LSOne(x) (x & (-x))
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

const int iinf = 1e9+7;
const ll inf = 1e18+7;

const int N = 1e5+7;
int in_degree[N], dis[N];
vi al[N];
bool vis[N];

void dfs(int a) {
    vis[a] = true;
    for (auto& b : al[a]) {
        dis[b] = max(dis[b],dis[a]+1);
        --in_degree[b];
        if (in_degree[b] == 0) dfs(b);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,m; cin >> n >> m;
    while (m--) {
        int a,b; cin >> a >> b;
        al[a].pb(b);
        ++in_degree[b];
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i] && in_degree[i] == 0)
            dfs(i);
    int ret = 0;
    for (int i = 1; i <= n; ++i) ret = max(ret, dis[i]);
    cout << ret << endl;
}


Measured memory_bytes: 9728
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        int C = scan.nextInt();
        if((A!=B && A!=C && B!=C) || (A==B && B==C)){
            System.out.println("No");
        }else{
            System.out.println("Yes");
        }
    }
}


Measured memory_bytes: 21332
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

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

	ll a, b, c, d;
	CIN2(a, b);
	CIN2(c, d);
	ll ans = max({ b * d, a * d, a * c, b * c });
	COUT(ans);

	return 0;
}

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

int main() {
  int N,M;
  int max=0;
  
  cin >> N;
  vector<string> Ns(N);
  for (int i=0; i<N; i++)
    cin >> Ns.at(i);
  
  cin >> M;
  vector<string> Ms(M);
  for (int i=0; i<M; i++)
    cin >> Ms.at(i);
  
  for (int i=0; i<N; i++){
    int num=0;
    for (int j=0; j<N; j++){
      if (Ns.at(i)==Ns.at(j)) num++;
    }
    for (int k=0; k<M; k++){
      if (Ns.at(i)==Ms.at(k)) num--;
    }
    if (num>max) max=num;
  }
  
  for (int i=0; i<M; i++){
    int num=0;
    for (int j=0; j<M; j++){
      if (Ms.at(i)==Ms.at(j)) num--;
    }
    for (int k=0; k<N; k++){
      if (Ms.at(i)==Ns.at(k)) num++;
    }
    if (num>max) max=num;
  }
  
  cout << max << endl;
}


Measured memory_bytes: 3568
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
#define MOD 1'000'000'007
using namespace std;
typedef long long ll;
typedef long double ld;

int N,K;
int D[10];

int main(){
    cin>>N>>K;
    rep(i,K){
        int d;
        cin>>d;
        D[d]++;
    }

    int ans=N;
    while(true){
        int x=ans;
        bool flag=true;
        while(x>0){
            flag&=(D[x%10]+1)%2;
            x/=10;
        }
        if(flag) break;
        ans++;
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 3576
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = sum(b)
for i in range(n-1):
  if a[i] + 1 == a[i+1]:
    ans += c[a[i]-1]
print(ans)

Measured memory_bytes: 3064
// minpro2019_C
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <tuple>  // std::tuple std::get
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>  // std::setprecision()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
typedef long long ll;

const int MOD = 1000000007;  // 1 000 000 007


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    // input
    ll K, A, B;
    cin >> K >> A >> B;
    
    // calculation
    if (K == 1) {
        // ビスケットを叩いて＋１で２枚
        cout << 2 << "\n";
    } else if (K == 2) {
        // たたくのみ or 1回交換する
        // B = 1 でも良い．どうせ増やせないから
        cout << std::max(ll(1+2), B) << "\n";
    } else if (K >= 3){
        ll bis = 1;
        if (K < A - bis + 2) {
            // 1回も交換できないとき
            cout << 1 + K << "\n";
        } else if (K == A - bis + 2) {
            // ぴったり1回だけ交換できるとき
            cout << max(1+K, B) << "\n";
        } else {
            // 1回以上交換できるとき
            // 1回目
            bis = max(1 + (A-1) + 2, B);
            K -= (A - 1) + 2;
            
            // 2回目以降
            if (A + 2 >= B) {
                // 交換が得じゃないとき
                cout << bis + K << "\n";
            } else {
                // 交換が得なとき: (A + 2) < B
                while (K >= 2) {
                    if (bis >= A) {
                        // 2回分使って交換
                        bis += B - A;
                        K -= 2;
                    } else if (bis < A) {
                        // ビスケットがA枚未満
                        bis++;
                        K--;
                    }
                }
                
                // K = 1 or 0
                cout << bis + K << "\n";
                
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scanln(&n, &k)
	height := 0
	weight := 0
	block := 1
	for n >= block {
		if weight <= k*block {
			height++
			n -= block
			weight += block
		} else {
			block++
		}
	}
	fmt.Println(height)
}


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

int main(void)
{
    int N;
    cin >> N;

    vector<int> A(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    sort(A.begin(), A.end());
    int min = A[0];
    int max = A[A.size() - 1];

    cout << max - min << endl;

    return (0);
}

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

int main() {
  string S,T;
  cin>>S>>T;
  int A=0;
  if(S.at(0)==T.at(0)){
    A=A+1;
  }
  if(S.at(1)==T.at(1)){
    A=A+1;
  }
  if(S.at(2)==T.at(2)){
    A=A+1;
  }
  cout<<A<< endl;
}
  


Measured memory_bytes: 256
<?php
// Your code here!
fscanf(STDIN,"%d %d %d %d",$s[1],$s[2],$s[3],$s[4]);

 if (in_array (1,$s) && in_array (9,$s) && in_array (7,$s) && in_array (4,$s))
  echo "YES";
  else 
  echo "NO";

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

long long M = 1e9 + 7;

long long fpow(long long a, long long b) {
    long long ans = 1;
    while (b > 0) {
        if (b % 2 == 1) ans = (ans * a) % M;
        a = (a * a) % M;
        b /= 2;
    }
    return ans;
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    long long ans = (fpow(10, n) - 2LL * fpow(9, n) + fpow(8, n)) % M;
    if (ans < 0) ans += M;
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3644
S = input()

count = 1
i = 1
word = S[0]
while i < len(S):
    if word != S[i]:
        word = S[i]
        i += 1
    else:
        word = S[i: i+2]
        i += 2
    count += 1

if i != len(S):
    count -= 1
print(count)

Measured memory_bytes: 9216
#include<cstdio>
using namespace std;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1,j=m+1; i<j; i++,j--)
        printf("%d %d\n",i,j);
    for(int i=m+2,j=2*m+1; i<j; i++,j--)
        printf("%d %d\n",i,j);
    return 0;
}

Measured memory_bytes: 1700
import java.util.Scanner;

public class Main {
    static int sx;
    static int sy;
    static int tx;
    static int ty;
    static long mod = 1000000007L;
    static long[] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sx = sc.nextInt();
        sy = sc.nextInt();
        tx = sc.nextInt();
        ty = sc.nextInt();

        int distanceX = tx - sx;
        int distanceY = ty - sy;

        //1週目
        proc("R", distanceX);
        proc("U", distanceY);
        proc("L", distanceX);
        proc("D", distanceY);

        //2週目
        proc("D", 1);
        proc("R", distanceX+1);
        proc("U", distanceY+1);
        proc("L", 1);

        proc("U", 1);
        proc("L", distanceX+1);
        proc("D", distanceY+1);
        proc("R", 1);

        System.out.println();
    }
    static void proc(String direction, int distance) {
        for (int i = 0; i < distance; i++) {
            System.out.print(direction);
        }
    }
}


Measured memory_bytes: 23488
// Iterative Deepening
#include <cstdio>
#include <cmath>
#include <string>
#include <cassert>
using namespace std;

#define N (4)
#define N2 (N * N)
#define LIMIT (100)

static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};
static const char dir[4] = {'r', 'u', 'l', 'd'};
int MDT[N2][N2];		// ???????????????????????¢???????????????

struct Puzzle {
    int f[N2];
    int space;
    int MD;
};

Puzzle state;
int limit;			// ??±????????¶???
int path[LIMIT];

// ???????????????????????¢??????????????????
int getAllMD( Puzzle pz ) {
    int sum = 0;
    for ( int i = 0; i < N2; i++ ) {
	if ( pz.f[i] == N2 ) continue;
	sum += MDT[i][pz.f[i] - 1];
    }

    return sum;
}

bool isSolved() {
    for ( int i = 0; i < N2; i++ ) {
	if ( state.f[i] != i + 1 ) return false;
    }
    
    return true;
}


bool dfs( int depth, int prev ) {
    if ( state.MD == 0 ) return true;
    // ?????¨?????±???????????\??????????????£??????????¶?????????¶???????¶??????????????????????
    if ( depth + state.MD > limit ) return false;
    
    int sx = state.space / N;
    int sy = state.space % N;
    Puzzle tmp;

    for ( int r = 0; r < 4; r++ ) {
	int tx = sx + dx[r];
	int ty = sy + dy[r];
	if ( tx < 0 || ty < 0 || tx >= N || ty >= N ) continue;
	if ( max( prev, r ) - min( prev, r ) == 2 ) continue;
	tmp = state;
	state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1];
	state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1];
	swap( state.f[tx * N + ty], state.f[sx * N + sy] );
	state.space = tx * N + ty;
	if ( dfs( depth + 1, r ) ) { 
	    path[depth] = r;
	    return true;
	}
	state = tmp;
    }
    
    return false;
}

// ????????±???
string iterative_deepening( Puzzle in ) {
    in.MD = getAllMD( in );	// ????????¶?????????????????????????????¢
    
    for ( limit = in.MD; limit <= LIMIT; limit++ ) {
	state = in;
	if ( dfs( 0, -100 ) ) {
	    string ans = "";
	    for ( int i = 0; i < limit; i++ ) ans += dir[path[i]];
	    return ans;
	}
    }

    return "unsolvable";
}

int main()
{
    for ( int i = 0; i < N2; i++ ) {
	for ( int j = 0; j < N2; j++ ) {
	    MDT[i][j] = abs( ( i / N ) - ( j / N ) ) + abs( ( i % N ) - ( j % N ) );
	}
    }

    Puzzle in;

    for ( int i = 0; i < N2; i++ ) {
	scanf("%d", &in.f[i]);
	if ( in.f[i] == 0 ) {
	    in.f[i] = N2;
	    in.space = i;
	}
    }

    string ans = iterative_deepening( in );

    printf("%d\n", (int)ans.size());

    return 0;
}

Measured memory_bytes: 1076
/*
*                                 Name : chaitanya
*
*                         Institute : ANITS,Visakhapatnam
*   "Don't regret anything you do, because in the end it makes you who you are."
*
*/
#include<cstdio>
#include<iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#include<sstream>
#define infy  1000000000
#define all(x) begin(x),end(x)
#define ll long long int
#define ff first
#define ss second
#define pb push_back
const ll m = 1000000007;
using namespace std;

int main()
{
    int n;
    cin >> n;
    if (n >= 30)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
typedef long long lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()

using namespace std;

void execute()
{
	int N;
	string input;
	bool tmp;
	int ans_num = -1;
	cin >> N;
	cin >> input;
	input = input[N - 1] + input;
	vector<vector<bool>> ans(4, vector<bool>(N + 2));
	ans[0][0] = ans[0][1] = ans[1][0] = ans[2][1] = true;
	ans[1][1] = ans[2][0] = ans[3][0] = ans[3][1] = false;

	for (int i = 2; i < N + 2; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			ans[j][i] = ans[j][i - 1] ^ ans[j][i - 2] ^ (input[i - 2] == 'o');
		}
	}

	for (int i = 0; i < 4; i++)
	{
		if (ans[i][0] == ans[i][N] && ans[i][1] == ans[i][N + 1])
			ans_num = i;
	}

	if (ans_num == -1)
	{
		cout << ans_num << endl;
		return;
	}
	for (int i = 2; i < N + 2; i++)
	{
		cout << (ans[ans_num][i] ? "S" : "W");
	}
	cout << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

int h,w;
string s[11];

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

int main(){
	cin.sync_with_stdio(false);
	while(1){
		cin>>h>>w;
		if(h==0)break;
		rep(i,h)cin>>s[i];
		string res="";
		map<string,int> smap;
		rep(i,h)rep(j,w){
			rep(d,8){
				string ss;
				ss+=s[i][j];
				int ny=i+dy[d],nx=j+dx[d];
				if(ny>=h)ny=0;
				if(ny<0)ny=h-1;
				if(nx>=w)nx=0;
				if(nx<0)nx=w-1;
				while(ny!=i||nx!=j){
					ss+=s[ny][nx];
					smap[ss]++;
					if(smap[ss]==2){
						if(ss.length()>res.length()||(ss.length()==res.length()&&ss<res)){
							res=ss;
						}
					}
					ny+=dy[d],nx+=dx[d];
					if(ny>=h)ny=0;
					if(ny<0)ny=h-1;
					if(nx>=w)nx=0;
					if(nx<0)nx=w-1;
				}
			}
		}
		if(res=="")cout<<0<<endl;
		else cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 37956
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;

struct uf {
private:
	vector<int> par, ran;
public:
	void init(int n) {
		par.resize(n, 0);
		ran.resize(n, 0);
		rep(i, n) {
			par[i] = i;
		}
	}
	int find(int x) {
		if (par[x] == x)return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (ran[x] < ran[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (ran[x] == ran[y])ran[x]++;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

ll mod_pow(ll x, ll n) {
	ll ret = 1;
	while (n) {
		if (n % 2)ret = ret * x%mod;
		x = x * x%mod; n >>= 1;
	}
	return ret;
}
int n, m;
void solve() {
	if (m == 0) {
		cout << mod_pow(2, n) << endl; return;
		
	}
	uf u; u.init(n + 1);
	rep(i, m) {
		int a, b; cin >> a >> b;
		u.unite(a, b);
	}
	int tmp = 0;
	rep1(i, n) {
		if (!u.same(0, i)) {
			tmp++; u.unite(0, i);
		}
	}
	ll ans = mod_pow(2, tmp) + 1;
	cout << ans % mod << endl;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (cin >> n >> m, n) {
		solve();
	}
	//stop
	return 0;
}



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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

int main() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }
    sort(all(a));

    ll ub = 1e18, lb = -1e18;
    while (ub - lb > 1) {
        ll mid = (ub + lb) / 2;
        auto is_smaller = [&](ll x) {
            ll cnt = 0;
            rep(i, n) {
                if (a[i] >= 0) {
                    ll l = -1, r = n;
                    while (r - l > 1) {
                        ll o = (l + r) / 2;
                        if (a[i] * a[o] < x) {
                            l = o;
                        } else {
                            r = o;
                        }
                        // debug(l);
                        // debug(r);
                        // debug(o);
                    }
                    cnt += r;
                } else {
                    ll l = -1, r = n;
                    while (r - l > 1) {
                        ll o = (l + r) / 2;
                        if (a[i] * a[o] < x) {
                            r = o;
                        } else {
                            l = o;
                        }
                        // debug(l);
                        // debug(r);
                        // debug(o);
                    }
                    cnt += n - r;
                }

                if (a[i] * a[i] < x) cnt--;
            }
            cnt /= 2;
            return cnt < k;
        };

        // debug(mid);
        if (is_smaller(mid)) {
            lb = mid;
        } else {
            ub = mid;
        }
    }
    cout << lb << endl;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		ArrayList<Integer> arrPost = new ArrayList<Integer>();
		BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			int n = Integer.parseInt(buffReader.readLine());

			if(n == 0) 	break;
			else 		arrPost.add(n);
		}

		for(int i = 0; i < arrPost.size(); i++) System.out.println("Case " + (i + 1) + ": " + arrPost.get(i));
	}
}

Measured memory_bytes: 33132
a, b ,k =map(int, input().split())
#print(a,b,k)

l = []
for i in range(1,max(a,b)+1):
    if max(a,b)%i == 0:
        l.append(i)
m = []
for j in range(1,min(a,b)+1):
    if min(a,b)%j == 0:
        m.append(j)
z = []
for n in l:
    for o in m:
        if n == o:
            z.append(o)
#print(l)
#print(m)
#print(z)
print(z[-k])



Measured memory_bytes: 3064
#include <iostream>
#include <sstream>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#define N 9
#define n 3
#define Blank 0
#define up -N/n
#define down N/n
#define left -1
#define right 1
#define limit 34
using namespace std;
struct p{
  int v[N];
  int blankPlace;
  int g=0;
  int h=0;
  bool operator < (const p& pazzle) const {
    for(int i=0;i<N;i++){
      if(v[i] == pazzle.v[i]) continue;
      return v[i]<pazzle.v[i];
    }
    return false;
  }
};
priority_queue <p, vector<p>, greater<p> > pazzle;
map <p,bool> existPazzle;
bool operator > (const p a,const p b){return a.h+a.g>b.h+b.g;};

int calculate_h(p this_pazzle,int i){
  if(i == this_pazzle.blankPlace ) return abs(i/n-(N-1)/n)+abs(i%n-(N-1)/n);
  else return abs(i/n-(this_pazzle.v[i]-1)/n)+abs(i%n-(this_pazzle.v[i]-1)%n);
}

p checkPazzle(p thisPazzle){
  thisPazzle.h = 0;
    for(int i=0;i<N;i++)
      thisPazzle.h += calculate_h(thisPazzle,i);
  return thisPazzle;
}

void moveBlank(p thisPazzle,int move){
  int moved = thisPazzle.blankPlace + move;
  thisPazzle.g++;
  //cout<<"g: "<<thisPazzle.g<<" moved: "<<moved<<endl;
  swap(thisPazzle.v[thisPazzle.blankPlace],thisPazzle.v[moved]);
  if(existPazzle[thisPazzle])return;
  thisPazzle.blankPlace = moved;
  thisPazzle = checkPazzle(thisPazzle);
  if(thisPazzle.g+thisPazzle.h>limit)return;
  pazzle.push(thisPazzle);
}

void movePazzle(p thisPazzle){
  if(thisPazzle.blankPlace+up>=0)
    moveBlank(thisPazzle,up);
  if(thisPazzle.blankPlace+down<9)
    moveBlank(thisPazzle,down);
  if(thisPazzle.blankPlace + left >= 0&&thisPazzle.blankPlace/3 == (thisPazzle.blankPlace+left)/3)
    moveBlank(thisPazzle,left);
  if(thisPazzle.blankPlace/3 == (thisPazzle.blankPlace+right)/3)
    moveBlank(thisPazzle,right);
}

p dfs(){
  p tmp,thisPazzle;
  tmp.g = -1;
  while(!pazzle.empty()){
    thisPazzle = pazzle.top();
    pazzle.pop();
    existPazzle[thisPazzle]=true;
    if(!thisPazzle.h)return thisPazzle;
    movePazzle(thisPazzle);
  }
  return tmp;
}

int main(){
  p thisPazzle;
  for(int i=0;i<N;i++){
    cin>>thisPazzle.v[i];
    if(thisPazzle.v[i]==Blank)thisPazzle.blankPlace=i;
  }
  thisPazzle = checkPazzle(thisPazzle);
  pazzle.push(thisPazzle);
  thisPazzle = dfs();
  cout<<thisPazzle.g<<endl;
  return 0;

}




Measured memory_bytes: 5540