akhauriyash/Code-Regression huggingface dataset:
// Target Expert 

/*
 * Author    : raj1307 - Raj Singh
 * Institute : Jalpaiguri Government Engineering College
 * Date      : 28.07.19
 */

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <iomanip>
 #include <memory.h>
#include <assert.h>
using namespace std;

//#define DEBUG
#ifdef DEBUG
#define deb(...) cerr<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
#define debarr(a,n) cerr<<#a<<" : ";for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
#define debmat(mat,row,col) cerr<<#mat<<" :\n";for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
	cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
	const char *comma=strchr(names+1,',');
	cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}

#else
#define deb(...) {}
#define debarr(a,n) {}
#define debmat(mat,row,col) {}
#define endl "\n"
#endif

#define fio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define fr(i, a, b) for(int i = (a); i < (b); ++i)
#define fb(i, b, a) for(int i = (b); i > (a); --i)
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define int long long
#define pb push_back
#define sz(x) ((int)x.size())
int max(int a,int b){if(a>b) return a; else return b;}
int min(int a,int b){if(a>b) return b; else return a;}

const int mod = 1000*1000*1000+7;

int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}


const int N = 1e5 + 5;

int n,W;

int cache[N][105];
int v[N],w[N];

int dp(int weg,int pos){

	if(weg<=0 or pos==n)
		return 0;

	else if(cache[weg][pos]!=-1)
		return cache[weg][pos];

	else if(w[pos]>weg)
		return cache[weg][pos]=dp(weg,pos+1);
	

	else{

		
		cache[weg][pos]=max(v[pos]+dp(weg-w[pos],pos+1),dp(weg,pos+1));

		return cache[weg][pos];

	}

}









void solve(){


	cin>>n>>W;
	fr(i,0,n){ 
		cin>>w[i];
	 	cin>>v[i];
	}

	memset(cache,-1,sizeof(cache));

	cout<<dp(W,0);


}




signed main() {
	fio;
	 
	cout<<fixed<<setprecision(10);
	int t=1;
//	cin>>t;
	while(t--) {
		solve();
	}

	
	return 0;
}


Measured memory_bytes: 82304
#include <iostream>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define MOD 1000000007
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

class SumSegTree {
private:

	int _sum(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return 0;    // 交差しない
		if (a <= l && r <= b)return dat[k];   // a,l,r,bの順で完全に含まれる
		else {
			int s1 = _sum(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
			int s2 = _sum(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
			return s1 + s2;
		}
	}
public:
	int n, height;
	vector<int> dat;

	// 初期化（_nは最大要素数）
	SumSegTree(int _n) {
		n = 1;
		height = 1;
		while (n < _n) {
			n *= 2;
			height++;
		}
		dat = vector<int>(2 * n - 1, 0);
	}

	// 場所i(0-indexed)にxを足す
	void add(int i, int x) {
		i += n - 1; // i番目の葉ノードへ
		dat[i] += x;
		while (i > 0) { // 下から上がっていく
			i = (i - 1) / 2;
			dat[i] += x;
		}
	}

	// 区間[a,b)の総和。ノードk=[l,r)に着目している。
	int sum(int a, int b) {
		return _sum(a, b, 0, 0, n);
	}
};


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

	ll n, k;
	cin >> n >> k;
	Array a(n, 0), f(n, 0);

	REP(i, n) cin >> a[i];
	REP(i, n)cin >> f[i];
	sort(all(a));
	sort(all(f), greater<ll>());

	auto check=[&](ll x)->ll {
		ll con = 0;
		REP(i, n) {
			if (a[i] * f[i] <= x)continue;
			//xを超えないよう調整
			con += (a[i]-x/f[i]);//修行すると消化コストaを減らせる
			if (con > k) return 0;
		}
		return 1;
	};


	ll l = -1;
	ll r = 1e12 + 1;
	while (l + 1 < r) {
		ll mid = l + r >> 1;
		if (check(mid)) {
			r = mid;
		}
		else {
			l = mid;
		}
	}

	cout << r << endl;
	return 0;
}

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

using namespace std;

int main(){

    int e, s; 
    cin >> e >> s;

    if(e <= 8 && s <= 8){
        cout << "Yay!" << endl;
    }else{
        cout << ":(" << endl;
    }

    return 0;
}

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

int main()
{
	stack<int>a;
	string b;
	int kotae = 0;
	while (cin >> b) {
		if (isdigit(b[0]) == true) {
			a.push(stoi(b));
		}
		else {
				int aa=0, bb=0 ;
				aa = a.top();
				a.pop();
				bb = a.top();
				a.pop();
			if (b == "+") {
				a.push(aa + bb);
			}
			else if (b == "*") {
				a.push(aa*bb);
			}
			else if (b == "-") {
				a.push(bb-aa);
			}
		}
	}
cout<<a.top()<<endl;
	return 0;
}

Measured memory_bytes: 3224
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority queue
#include<deque>//double_ended queue
using namespace std;
int main()
{ 
    int n;
    long long a,b;
    cin>>n>>a>>b;
    long long x[n];
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    long long d[n-1];
    long long c;
    c=b/a;//距離c以下なら歩いた方がお得
    long long ans=0;
    for(int i=0;i<n-1;i++){
        if(x[i+1]-x[i]<=c){ans=ans+a*(x[i+1]-x[i]);}
        else{ans=ans+b;}
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<sstream>


#define reps(i,f,n) for(int i = f; i < int(n); i++)
#define rep(i,n) reps(i,0,n)

#define PII pair<int,int>
#define PP pair< int,PII >


using namespace std;

int main(){
	
	int n;
	int m;
	int in,out;
	scanf("%d%d", &n, &m);
	
	int ans = m;
	
	rep(i,n){
		scanf("%d%d", &in, &out);
		m += in-out;
		ans = max(m,ans);
		if(m < 0){
			m = -1000000000;
		}
	}
	if(m < 0){
		puts("0");
	}else{
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1188
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;
using ll = long long;
int main() {
    int n; cin >> n;
    vector<int> p(n);
    for (int i=0;i<n;i++){
        cin >> p[i];
    }
    int ans = 0;
    for (int i=1;i<n-1;i++){
        if (p[i-1]<p[i]&&p[i]<=p[i+1]) ans++;
        else if (p[i+1]<p[i]&&p[i]<=p[i-1]) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int sumMat(vector<vector<int> > &table, int x, int y, int w, int h){
	int lt = x == 0 || y == 0 ? 0 : table[x-1][y-1];
	int lb = x == 0 ? 0 : table[x-1][y-1+h];
	int rt = y == 0 ? 0 : table[x-1+w][y-1];
	int rb = table[x-1+w][y-1+h];
	return rb - rt - lb + lt;
}

int main(void){
	int n;
	vector<vector<int> > mat;
	vector<vector<int> > table;

	cin >> n;
	for(int i=0;i<n;i++){
		vector<int> row;
		for(int j=0;j<n;j++){
			int inp;
			cin >> inp;
			row.push_back(inp);
		}
		mat.push_back(row);
	}

	table = mat;
	for(int i=0;i<n;i++){
		for(int j=0;j<n-1;j++){
			table[i][j+1] += table[i][j];
		}
	}
	for(int i=0;i<n-1;i++){
		for(int j=0;j<n;j++){
			table[i+1][j] += table[i][j];
		}
	}

	int maxSum = INT_MIN;
	for(int x=0;x<n;x++){
		for(int y=0;y<n;y++){
			for(int w=1;w+x<=n;w++){
				for(int h=1;h+y<=n;h++){
					maxSum = max(maxSum, sumMat(table, x, y, w, h));
				}
			}
		}
	}

	cout << maxSum << endl;

	return 0;
}

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

using Float = double;
using Point = complex<Float>;
struct Line{ Point a,b; };
struct Circle{ Point center; Float r; };

const Float INF = 200;
const Float EPS = 1e-8;
const Float width = 100;

inline bool eq(Float a,Float b) { return abs(a - b) < EPS; }
inline Float dot(const Point &p1,const Point &p2){ return real(conj(p1) * p2); }

Point projection(const Line &l,const Point &p){
	Float t = dot(l.b - l.a,p - l.a) / norm(l.b - l.a);
	return l.a + (l.b - l.a) * t;
}

vector<Point> crosspoint(const Circle &c,const Line &l){
	vector<Point> ret;
	Point p = projection(l,c.center),vect = (l.b - l.a) / abs(l.b - l.a);
	if(abs(p - c.center) > c.r) return ret;
	Float d = sqrt(c.r * c.r - norm(p - c.center));
	ret.push_back(p + vect * d);
	if(!eq(abs(p - c.center),c.r)) ret.push_back(p - vect * d);
	return ret;
}

vector<Point> crosspoint(const Circle &c1,const Circle &c2){
	vector<Point> ret;
	Point d = c2.center - c1.center;
	Float rcosa = (c1.r * c1.r + norm(d) - c2.r * c2.r) / (abs(d) * 2);
	if(eq(0,abs(d)) || abs(rcosa) > c1.r) return ret;
	Float rsina = sqrt(c1.r * c1.r - rcosa * rcosa);
	ret.push_back(c1.center + d / abs(d) * Point(rcosa,rsina));
	if(!eq(rcosa,c1.r)) ret.push_back(c1.center + d / abs(d) * Point(rcosa,-rsina));
	return ret;
}

int n;
Float w,x[15],y[15],h[15];

bool bisearch(Float r){
	Float margin = (w > r ? r : sqrt(r * r - (r - w) * (r - w)));
	Circle cs[10];
	for(int i = 0;i < n;i++){
		Float cr = (h[i] > r ? r : sqrt(r * r - (r - h[i]) * (r - h[i])));
		cs[i] = {Point(x[i],y[i]),cr};
	}
	vector<Point> corner = {
		Point(margin,margin),
		Point(margin,width - margin),
		Point(width - margin,width - margin),
		Point(width - margin,margin)
	};
	Line ls[4];
	for(int i = 0;i < 4;i++) ls[i] = {corner[i],corner[(i + 1) % 4]};
	vector<Point> candidate = corner;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < 4;j++){
			vector<Point> inters = crosspoint(cs[i],ls[j]);
			for(const auto &p : inters) candidate.push_back(p);
		}
		for(int j = i + 1;j < n;j++){
			vector<Point> inters = crosspoint(cs[i],cs[j]);
			for(const auto &p : inters) candidate.push_back(p);
		}
	}
	for(const auto &p : candidate){
		if(!(margin - EPS <= imag(p) && imag(p) <= width - margin + EPS
		&& margin - EPS <= real(p) && real(p) <= width - margin + EPS)) continue;
		bool isOK = true;
		for(int i = 0;i < n;i++){
			if(abs(p - cs[i].center) <= cs[i].r - EPS) isOK = false;
		}
		if(isOK) return true;
	}
	return false;
}

signed main(){
	while(cin >> n >> w,n){
		for(int i = 0;i < n;i++) cin >> x[i] >> y[i] >> h[i];
		Float ng = INF,ok = 0;
		for(int i = 0;i < 100;i++){
			Float mid = (ng + ok) / 2;
			if(bisearch(mid)) ok = mid;
			else ng = mid;
		}
		printf("%.9lf\n",ok);
	}
}


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

int main() {
  int H, W;
  string S1, S2, S3;

  cin >> H >> W;
  S1 = "";
  cin >> S2;
  for (int i = 0; i < H; i++) {
    S3 = "";
    if ((i+1) < H) {
      cin >> S3;
    }
    for (int j = 0; j < W; j++) {
      int n = 0;
      if (S2.at(j) == '#') {
        cout << S2.at(j);
        continue;
      }
      if (S1 != "") {
        if ((j-1) >= 0) {
          if (S1.at(j-1) == '#') n++;
        }
        if (S1.at(j) == '#') n++;
        if ((j+1) < W) {
          if (S1.at(j+1) == '#') n++;
        }
      }
      if ((j-1) >= 0) {
        if (S2.at(j-1) == '#') n++;
      }
      if ((j+1) < W) {
        if (S2.at(j+1) == '#') n++;
      }
      if (S3 != "") {
        if ((j-1) >= 0) {
          if (S3.at(j-1) == '#') n++;
        }
        if (S3.at(j) == '#') n++;
        if ((j+1) < W) {
          if (S3.at(j+1) == '#') n++;
        }
      }
      cout << n;
    }
    cout << endl;
    S1 = S2;
    S2 = S3;
  }
}


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

typedef long long int ll;
int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        int now=i;
        int s=0;
        while(now!=0)
        {
            int r=now%10;
            now=now/10;
            s+=r;
        }
        if(s>=a&&s<=b)
        {
            sum+=i;
        }
    }
    cout<<sum<<endl;
    //main();

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

typedef struct {
	int f,p,r;
}t;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
int cmp1(const void *a,const void *b){
	return ((t *)b)->p-((t *)a)->p;
}
int cmp2(const void *a,const void *b){
	return ((t *)a)->f-((t *)b)->f;
}

int main(void){
	int a,b,c,d,i,n=in(),r;
	t v[100];
	memset(v,0,sizeof(v));
	for(i=0;i<n;i++){
		v[i].f=i;
	}
	for(i=0;i<n*(n-1)/2;i++){
		a=in();
		b=in();
		c=in();
		d=in();
		if(c>d){
			v[a-1].p+=3;
		}
		else if(c<d){
			v[b-1].p+=3;
		}
		else{
			v[a-1].p+=1;
			v[b-1].p+=1;
		}
	}
	qsort(v,n,sizeof(t),cmp1);
	for(i=0,r=0;i<n;i++){
		if(i>0&&v[i-1].p==v[i].p){
			v[i].r=r;
		}
		else{
			r=i+1;
			v[i].r=r;
		}
	}
	qsort(v,n,sizeof(t),cmp2);
	for(i=0;i<n;i++){
		print(v[i].r);
	}
	return 0;
}

Measured memory_bytes: 652
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
using namespace std;

using Graph=vector<vector<pair<int,int>>>;
Graph G;
vector<int> color;

void func(int i,int p){
    for(auto next_i:G[i]){
        if(next_i.first==p)continue;
        
        if(next_i.second%2==0)color[next_i.first]=color[i];
        else                  color[next_i.first]=1-color[i];

        func(next_i.first,i);
    }
    
}

int main(){
    G.resize(100010);
    color.resize(100010);
    pair<int,int> p,q;
    int N,u[100010],v[100010],w[100010];
    cin>>N;
    for(int i=1;i<=N;++i){
        cin>>u[i]>>v[i]>>w[i];
        p.first=v[i],p.second=w[i];
        G[u[i]].push_back(p);
        q.first=u[i],q.second=w[i];
        G[v[i]].push_back(q);
    }

    color[1]=0;
    func(1,0);

    for(int i=1;i<=N;++i)
        cout<<color[i]<<endl;

    return 0;
}

Measured memory_bytes: 10240
#include "bits/stdc++.h"
#define _CRT_SECURE_NO_WARNINGS
#define rep(i,n) for(int i = 0;i < n;i++)
#define REP(i,n,k) for(int i = n;i < k;i++)
#define P(p) cout << (p) << endl;
#define sP(p) cout << setprecision(15) << fixed << p << endl;
#define Pi pair<int,int>
#define IINF 1e9
#define LINF 1e18
#define vi vector<int>
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 0, 1,0,-1 };
int dy[] = { 1, 0,-1,0 };
int dx8[] = { -1,-1,-1,0,0,1,1,1 };
int dy8[] = { -1,0,1,-1,1,-1,0,1 };

unsigned long long sttoi(std::string str) {
	unsigned long long ret;
	std::stringstream ss; ss << str;
	ss >> ret;
	return ret;
}

ull gcd(ull a, ull b) {
	if (b > a)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a%b);
}

int comb(int n, int k) {
	int ans = 1;
	for (int i = 0; i < min(k, n - k); i++) {
		ans *= n - i;
		ans /= i + 1;
	}
	return ans;
}

ll mod_pow(ll n, ll p, ll mod) {
	if (p == 0) return 1 % mod;
	if (p < 2) {
		return n % mod;
	}
	else {
		ll d = 2, value = (n%mod)*(n%mod) % mod;
		while (d * 2 < p) { d *= 2;	value *= value;	value %= mod; }
		value %= mod;
		return ((value%mod) * (mod_pow(n, p - d, mod) % mod)) % mod;
	}
}

bool isPrime(int n) {
	if (n <= 1)return false;
	if (n == 2)return true;
	if (n % 2 == 0)return false;
	for (int i = 3; i*i <= n; i += 2) {
		if (n%i == 0)return false;
	}
	return true;
}

void solve() {
	string s;
	cin >> s;
	vector<string> st;
	st.push_back(s);
	int size = s.length();
	int count = 1;
	while (count < size) {
		vector<string> tmp;
		rep(i, st.size()) {
			int cnt = 0;
			rep(j, st[i].length()) {
				if (count == cnt) {
					tmp.push_back(st[i].substr(0, j) + "+" + st[i].substr(j, st[i].length() - j));
				}
				if (st[i][j] >= '0' && st[i][j] <= '9') cnt++;
			}
		}
		rep(i, tmp.size()) {
			st.push_back(tmp[i]);
		}
		count++;
	}
	ll ans = 0;
	rep(i, st.size()) {
		vi pos;
		ll sum = 0;
		rep(j, st[i].length()) {
			if (st[i][j] == '+') {
				pos.push_back(j);
			}
		}
		int p = 0;
		vector<ll> num;
		rep(j, pos.size()) {
			num.push_back(sttoi(st[i].substr(p, pos[j] - p)));
			p = pos[j] + 1;
		}
		num.push_back(sttoi(st[i].substr(p, st[i].length() - p)));
		rep(j, num.size()) {
			sum += num[j];
		}
		ans += sum;
	}
	P(ans);
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
h,w = LI()
y,x = LI()
print(h*w-h*x-w*y+y*x)
"""

#B
"""
n,m,c = LI()
b = LI()
a = LIR(n)
ans = 0
for i in range(n):
    d = c
    for k in range(m):
        d += b[k]*a[i][k]
    if d > 0:
        ans += 1
print(ans)
"""


#C

"""
n,m = LI()
v = LIR(n)
v.sort(key = lambda x:x[0])
ans = 0
k = 0
for a,b in v:
    if k+b >= m:
        ans += (m-k)*a
        print(ans)
        quit()
    ans += b*a
    k += b
"""
#D
a,b = LI()
k = list(bin(b)[2::])
l = len(k)
ans = [0 for i in range(l)]
po = [2]
for i in range(l):
    po.append(po[-1]*2)
for i in range(l):
    o = a//po[i]
    r = b//po[i]
    c = a%po[i]
    d = b%po[i]
    if o == r:
        key = max(0,d+1-max(c,po[i]//2))
    else:
        key = (r-o)*po[i]//2
        if c > po[i]//2:
            key -= c-po[i]//2
        if d >= po[i]//2:
            key += d-po[i]//2-1
    ans[i] = key%2
po.insert(0,1)
d = 0
for i in range(l):
    d += ans[i]*po[i]
print(d)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 38640
N = int(input())

al = [chr(ord('a') + i) for i in range(26)]
out = dict(zip(al,[100]*26))
# print(out)

for i in range(N):
    S = list(input())
    dam = dict(zip(al,[0]*26))
    for T in S:
        dam[T] += 1   #辞書Tに+1
    for key in out.keys():
        out[key] = min(out[key], dam[key])
    # print(dam)
outS = ""
for key in out.keys():
    # print(key)
    outS += key*out[key]
print(outS)


Measured memory_bytes: 66068
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static Scanner cin = new Scanner();

    static void Main(string[] args) {
        int N = cin.Int();

        var dp = new int[100010, 3];
        var happiness = new int[100010, 3];

        for (int i = 0; i < N; i++) {
            happiness[i, 0] = cin.Int();
            happiness[i, 1] = cin.Int();
            happiness[i, 2] = cin.Int();
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (j != k) dp[i, j] = Math.Max(dp[i, j], dp[i - 1, k] + happiness[i - 1, k]);
                }
            }
        }
        var ans = new int[] { dp[N, 0], dp[N, 1], dp[N, 2] };
        Array.Sort(ans);
        Console.WriteLine(ans[2]);
        Console.ReadLine();
    }
}

class Scanner //標準入力
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int Int()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = Int() + add;
        }
        return Array;
    }

    public long Long()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = Long() + add;
        }
        return Array;
    }

    public double Double()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = Double() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 17348
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vi t(n);
    rep(i, n) cin >> t[i];
    int m;
    cin >> m;
    vi p(m), x(m);
    rep(i, m) cin >> p[i] >> x[i];

    int sum = accumulate(t.begin(), t.end(), 0);
    rep(i, m) {
        p[i]--;
        cout << sum - (t[p[i]] - x[i]) << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5,mod=1e9+7;
ll inv(ll x){return x==1?x:(mod-mod/x)*inv(mod%x)%mod;}
ll n,a,b;
ll solve(ll x)
{
    ll ans=1;
    for(ll i=1;i<=x;i++)
        ans=ans*(n-i+1)%mod*inv(i)%mod;
    return ans;
}
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    cin>>n>>a>>b;
    ll ans=qpow(2,n);
    ans--;
    ans=(ans-solve(a))%mod;
    ans=(ans-solve(b))%mod;
    ans=(ans+mod)%mod;
    printf("%lld\n",ans);
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var x, y int
	v := make([]int, 2)
	for {
		fmt.Scan(&x, &y)
		if x == 0 && y == 0 {
			break
		}
		v[0] = x
		v[1] = y

		sort.Ints(v)
		fmt.Println(v[0], v[1])
	}
}



Measured memory_bytes: 1332
using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace debug
{
    class ProgramD
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            List<Task> task = new List<Task>();



            for (int i = 0; i < n; i++)
            {
                string[] s = Console.ReadLine().Split(' ');

                task.Add(new Task(s[0],int.Parse(s[1]) ,i + 1));
            }

            //まず町の名前を小さい順、そして得点の高い順に並べる
            var sorted = task.OrderBy(t => t.town).ThenByDescending(t => t.point);

            foreach (var s in sorted)
            {
                Console.WriteLine(s.num);
                
            } 
        }
    }


    public class Task
    {
        public string town;
        public int point;
        public int num;
        public Task(string town, int point,int num)
        {
            this.town = town;
            this.point = point;
            this.num = num;
        }
    }
}



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

using namespace std;

long long int n,k,w,sum;
long long int dizi[105][5];
long long int dp[103][100003];
long long  dpf(int crr,int kalan){
	// printf("%d %d\n",crr,kalan );
	if(kalan<=0){
		return 0;
	}
	if(crr>=n){
		return 1000000009;
	}
	if(dp[crr][kalan]!=-1){
		return dp[crr][kalan];
	}
	dp[crr][kalan]=min(  dpf( crr+1,kalan-dizi[crr][1] )+dizi[crr][0],  dpf(crr+1,kalan)   );
	return dp[crr][kalan];

}


int main(){
	//freopen("a.gir","r",stdin);
    //freopen("a.cik","w",stdout);
    for(int i=0;i<102;i++){
   		for(int j=0;j<100002;j++){
   			dp[i][j]=-1;
   		}
  	}
  	// printf("a\n");
	scanf("%lld %lld",&n,&w);

	for(int i=0;i<n;i++){
		scanf("%lld %lld",&dizi[i][0],&dizi[i][1]);
		sum+=dizi[i][1];
	}
	//printf("%lld\n",dpf(0,17));
	for(int i=sum;i>0;i--){
		// printf("%lld\n",sum );
		if(dpf(0,i)<=w){
			printf("%d\n",i );
			return 0;
		}
	}		
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
#define gap ' '
#define L(i) ((i) - (&i))

const int MAXN = 1e7 + 5;
	
int main(){	
	int n, m; cin >> n >> m;
	ll ans = 0;
	for(int i = 1; i <= n; ++i){
		ans+=(n-i);
	}
	for(int i = 1; i <= m; ++i){
		ans+=(m-i);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3664
l = input()
n = len(l)
mod = 10 ** 9 + 7
memo = [1]
memo2 = [1]

for i in range(n):
    memo.append(memo[-1] * 3 % mod)
    memo2.append(memo2[-1] * 2 % mod)

i = 1
j = -1
ans = 0

for c in l:
    if c == '1':
        j += 1
        ans += (memo[n-i] ) * memo2[j]
        ans %= mod
    i+=1
ans += memo2[j+1]
ans %= mod
print(ans)


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

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j,n,k;
    cin>>n>>k;
    vector<long long int> a(n);
    for(i=0;i<n;i++)
        cin>>a[i];
    long long int mod=1000000007;
    vector<vector<long long int>> poss(n+1);
    poss[1]=vector<long long int> (k+1,0);
    for(i=0;i<=k;i++)
    {
        if(i<=a[0])
            poss[1][i]=1;
    }
    for(i=2;i<=n;i++)
    {
        poss[i]=vector<long long int> (k+1,0);
        long long int sum=0;
        for(j=0;j<=k;j++)
        {
            if(j<=a[i-1])
                sum = (sum + poss[i-1][j]);
            else
            {
                sum = (sum + poss[i-1][j] - poss[i-1][j-a[i-1]-1]);
            }
            poss[i][j]=sum%mod;
        }
    }

    cout<<poss[n][k]%mod<<endl;


}

Measured memory_bytes: 78720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll ans1=a*c;
	ll ans2=a*d;
	ll ans3=b*c;
	ll ans4=b*d;
	ll fa=max({ans1,ans2,ans3,ans4});
	if(a<=0&&b>=0||c<=0&&d>=0){
		cout<<max(ll(0),fa);
	}
	else{
		cout <<fa;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long 
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;
#define FORR(x,arr) for(auto& x:arr)

/*
bool isprime(int x){
	for(int i = 2;i*i<=x;i++){
		if(x%i == 0)return false;
	}
	return x!=1;
}
int gcd(int a, int b) 
{ 
    if (a == 0) 
       return b; 
    if (b == 0) 
       return a; 
   
    if (a == b) 
        return a; 
   
    if (a > b) 
        return gcd(a-b, b); 
    return gcd(a, b-a); 
} 
void dfs(int x,int y){
		if(x == n+1){
			int tmp = 0;
			FOR(i,0,k){
				if(tmp1[mortyy[i]]-tmp1[morty[i]] == mortyyy[i])tmp+=mortyyyy[i];
			}
			rick = max(rick,tmp);
			return ;
		}
		int i;
		for(i = y;i<=n1;i++){
			tmp1[x] = i;
			dfs(x+1,i);
		}
	}
*/


//3111111111111111111111111111111

	int morty[310000];
	vi adj[310000];

	void solve(){

		ini(n);
		ini(n1);
		FOR(i,0,n){
			in(morty[i]);
		}
		FOR(i,0,n1){
			ini(x);
			ini(x1);
			x--;
			x1--;
			adj[x].push_back(x1);
			adj[x1].push_back(x);
		}
		int rick = 0;
		FOR(i,0,n){
			int one = 0;
			if(adj[i].size() == 0)rick++;
			else{
				FOR(i1,0,adj[i].size()){
					if(morty[i]<=morty[adj[i][i1]]){
						one =1 ;
						break;
					}
				}
				if(one == 0)rick++;
			}

		}
		out(rick);





	}









































int32_t main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall 
	oneforall

	solve();
	


	return 0;
}

Measured memory_bytes: 15172
#include <iostream>
#include <iomanip>
#include <map>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    int a[n];
    map<int, long long> m;
    long long totalCount = 0;
    for(int i=0; i<n; i++){
        cin >> a[i];
        m[a[i]] += 1;
    }
    for(auto x : m){
        long long y = x.second;
        totalCount += (y*(y-1))/2LL;
    }
    for(int i=0; i<n; i++){
        long long ans = 0;
        long long y = m[a[i]] - 1;
        ans = totalCount - (m[a[i]] * (m[a[i]]-1))/2 + (y*(y-1))/2;
        cout << ans << '\n';
    }
    return 0;
}

Measured memory_bytes: 11520
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int maxs = 0,sum = 0;
int tot(int a,int b,int c){
    int s = a*10 + b + c;
    return s;
}
int main(){
    int a,b,c;
    
    cin>>a>>b>>c;
    
    sum = tot(a,b,c);
    if(sum>maxs) maxs = sum;
    sum = tot(a,c,b);
    if(sum>maxs) maxs = sum;
    sum = tot(b,a,c);
    if(sum>maxs) maxs = sum;
    sum = tot(c,b,a);
    if(sum>maxs) maxs = sum;
    sum = tot(c,a,b);
    if(sum>maxs) maxs = sum;
    sum = tot(b,c,a);
    if(sum>maxs) maxs = sum;
    
    cout<<maxs<<endl;
    return 0;
}

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

using ll = long long;
ll modinv(ll a, ll m) {
	assert(m > 0);
	if (m == 1) return 0;
	a %= m;
	if (a < 0) a += m;
	assert(a != 0);
	if (a == 1) return 1;
	return m - modinv(m, a) * m / a;
}

template <int MOD_> struct modnum {
private:
	int v;
public:
	static const int MOD = MOD_;

	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

	modnum operator ~ () const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}

	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}

	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

using num = modnum<int(1e9)+7>;


int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	vector<num> dp(13, 0);
	dp[0] = 1;
	for(char c : s){
		vector<num> newdp(13, 0);
		for(int x = 0; x < 13; x++){
			for(int f = 0; f < 10; f++){
				if(('0' + f) == c || '?' == c){
					newdp[(x * 10 + f) % 13] += dp[x];
				}
			}
		}
		dp = newdp;
	}
	cout << (int)dp[5] << '\n';
}

Measured memory_bytes: 512
import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] initial = sc.nextLine().split("");
    long K = sc.nextLong();
    long index = 1;
    String answer = "1";
    for (String num: initial) {
      if (num.equals("1") && index < K) {
        index++; 
      } else {
        answer = num;
        break;
      }
    }  
    System.out.println(answer);
  }
}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _GLIBCXX_DEBUG
#define rep(i, c) for (int i = 0; i < (int)c; i++)
#define debug(x) cout << #x << " = " << x << endl
#define print(x) cout << x << endl;
const ll MOD = 1000000007;

int main()
{
    int S, W;
    cin >> S >> W;
    if (W >= S)
    {
        cout << "unsafe" << endl;
    }
    else
    {
        cout << "safe" << endl;
    }
}


Measured memory_bytes: 3632
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpT, *szpFpA;
#endif

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	char lc1Buf[1024], lc1Out[1024];

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// 金額・必要枚数取得
	int liAVal, liBVal, liCVal, liACnt, liBCnt;
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d%d%d%d%d", &liAVal, &liBVal, &liCVal, &liACnt, &liBCnt);
	liCVal *= 2;

	// 全てABの場合
	int liCCnt;
	if (liACnt < liBCnt) {
		liCCnt = liBCnt;
	}
	else {
		liCCnt = liACnt;
	}
	int liMin = liCVal * liCCnt;

	// １枚ずつ減算
	while (liCCnt > 0) {
		liCCnt--;
		int liSum = liCVal * liCCnt;

		// A
		if (liCCnt < liACnt) {
			liSum += (liACnt - liCCnt) * liAVal;
		}

		// B
		if (liCCnt < liBCnt) {
			liSum += (liBCnt - liCCnt) * liBVal;
		}

		// 最小値更新
		if (liMin > liSum) {
			liMin = liSum;
		}
	}

	// 結果セット
	sprintf(lc1Out, "%d\n", liMin);

	// 結果表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpT);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
//Optimisations
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("O2")
//shortcuts for functions
#define pb push_back
#define mp make_pair
#define ff first 
#define ss second
#define all(v) v.begin(),v.end()
#define prec(n) fixed<<setprecision(n)
#define n_l '\n'
// make it python 
#define gcd __gcd
#define append push_back
#define str to_string
// utility functions shortcuts
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sswap(a,b) {a=a^b;b=a^b;a=a^b;}
#define swap(a,b) {auto temp=a; a=b; b=temp;}
#define init(dp) memset(dp,-1,sizeof(dp));
#define set0(dp) memset(dp,0,sizeof(dp));
#define bits(x) __builtin_popcount(x)
#define SORT(v) sort(all(v))
#define endl "\n"
#define forr(i,n) for(ll i=0;i<n;i++)
// declaration shortcuts
#define ll long long
// Constants
constexpr int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};
constexpr ll INF = 1999999999999999997; 
constexpr int inf= INT_MAX;
constexpr int MAXSIZE = int(1e6)+5;
constexpr auto PI  = 3.14159265358979323846L;
constexpr auto oo  = numeric_limits<int>::max() / 2 - 2;
constexpr auto eps = 1e-6;
constexpr auto mod = 1000000007;
constexpr auto MOD = 1000000007;
constexpr auto MOD9 = 1000000009;
constexpr auto maxn = 100006;
//void IOfile(){
//freopen(file_name, reade_mode, stdin);
//freopen(file_name, write_mode, stdout);
//}
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int main(){
	fastio();
	int k,x;
	cin>>k>>x;
	if(500*k>=x){
		cout<<"Yes";
	}else{
		cout<<"No";	
	}
}

Measured memory_bytes: 256
#https://atcoder.jp/contests/abc156/tasks/abc156_b
N,K = map(int,input().split())
q, mod = divmod(N,K)
mod_list = [mod]
while True:
    q , mod =divmod(q,K)
    mod_list.append(mod)
    if q <=0 :
        break

n_ary = int("".join(map(str,mod_list[::-1])))
print(len(str(n_ary)))

Measured memory_bytes: 9120
n,m = gets.chomp.split.map(&:to_i)
l_ary = []
r_ary = []

for i in 0..(m-1)
    a,b = gets.chomp.split.map(&:to_i)
    l_ary << a
    r_ary << b
end
l_ary.sort!
r_ary.sort!
if (r_ary[0] - l_ary[-1] + 1) >= 0
    puts  r_ary[0] - l_ary[-1] + 1
else
    puts 0
end

Measured memory_bytes: 4604
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
 
for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

#print(graph)

check = [-1]*(N)
check[0] = 0

q = deque([0])

while q:
	#print(q)
	p = q.popleft()
	#print(p, check)
	for x in graph[p]:
		#print(x)
		if check[x] == -1:
			check[x] = p+1
			q.append(x)


if -1 in check:
	print("No")
	exit()
else:
	print("Yes")

for i in range(1, N):
	print(check[i])



Measured memory_bytes: 45148
import sys

input = sys.stdin.readline

def main():
    ans = 'NO'
    S = input().rstrip('\n')
    if S.count('KIH') == 1 and S.count('A') <= 4 and S.replace('A', '') == 'KIHBR' and S.count('AA') == 0:
        ans = 'YES'
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int N = 0;
	int x = 0;
	int y = 0;
	cin >> N >> x >> y;
	vector<int> A(N);
	int min = N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			min = abs(i - j);
			if (min > abs(i - x) + 1 + abs(j - y)) {
				min = abs(i - x) + 1 + abs(j - y);
			}
			if (min > abs(i - y) + 1 + abs(j - x)) {
				min = abs(i - y) + 1 + abs(j - x);
			}
			A.at(min)++;
		}
	}
	for (int i = 2; i <= N; i++) {
		cout << A.at(i-1) << endl;
	}
	return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
    int a, b, k;
    cin >> a >> b >> k;

    if ((b - a) / 2 < k)
        rep2(i, a, b + 1) cout << i << '\n';
    else
    {
        int idx = 0;
        rep2(i, a, b + 1)
        {
            if (idx < k || (b - a) - idx < k)
                cout << i << '\n';
            idx++;
        }
    }
    return 0;
}


Measured memory_bytes: 3644
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

XplusY = [x + y for x, y in XY]
XminusY = [x - y for x, y in XY]

print(max([max(XplusY) - min(XplusY), max(XminusY) - min(XminusY)]))


Measured memory_bytes: 61424
#include<bits/stdc++.h>
using namespace std;
int n,a,f[100001],ans;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        f[a-1]++;
        f[a+1]++;
        f[a]++;
    }
    for(int i=1;i<=100000;i++)
        if(f[i]>ans)
            ans=f[i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int main()
{
	int y,m;char c;
	cin>>y>>c>>m;
	//cout<<y<<' '<<m<<endl;
	if(y<2019 || (y==2019 && m<5)){
		cout<<"Heisei"<<endl;
	}
	else cout<<"TBD"<<endl;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;

void mainmain(){
	int n,m,s,g1,g2;
	while(cin>>n>>m>>s>>g1>>g2,n){
		s--;
		g1--;
		g2--;
		VV(int) vv;
		initvv(vv,n,n);
		rep(i,n) rep(j,n) vv[i][j]=INF;
		vvint vvr=vv;
		rep(i,m){
			int a,b,c;
			cin>>a>>b>>c;
			a--;
			b--;
			vv[a][b]=c;
			vvr[b][a]=c;
		}
		// cout<<0<<endl;
		rep(k,n){
			rep(i,n){
				rep(j,n){
					vv[i][j]=min(vv[i][j],vv[i][k]+vv[k][j]);
					vvr[i][j]=min(vvr[i][j],vvr[i][k]+vvr[k][j]);
				}
			}
		}
		rep(i,n){
			vv[i][i]=0;
			vvr[i][i]=0;
		}
		int ans=INF;
		rep(i,n){
			ans=min(ans,vvr[i][s]+vv[i][g1]+vv[i][g2]);
		}
		cout<<ans<<endl;
		/*
		priority_queue<pii> pq;
		vint v(n,-1);
		pq.push(mkp(0,s));
		while(!pq.empty()){
			pii t=pq.top();
			pq.pop();
			if(v[t.S]!=-1) continue;
			cout<<-t.F<<" "<<t.S<<endl;
			v[t.S]=-t.F;
			rep(i,vv[t.S].size()){
				// cout<<vv[t.S][i].F<<endl;
				if(v[vv[t.S][i].F]==-1){
					pq.push(mkp(t.F-vv[t.S][i].S,vv[t.S][i].F));
				}
			}
		}
		*/
		// cout<<v[g1]+v[g2]<<endl;
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

Measured memory_bytes: 1304
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using LL = unsigned long long;
const int INF = 1e9;

int k;
vector<vector<LL>> a(100, (vector<LL>(10, 0)));
vector<int> totals(100, 0);

int search(int digit, int num, int zan)
{
  if (digit <= 0) return 0;
  for (int i = -1; i < 2; ++i)
  {
    if (num + i >= 0 && num + i <= 9) {
      zan -= a[digit][num + i];
      if (zan <= 0) {
        LL n = search(digit - 1, num + i, zan + a[digit][num + i]);
        if (digit > 1) n += (num + i) * pow(10, digit - 1);
        else n += num + i;
        return n;
      }
    }
  }
  return 0;
}

vector<int> dp() {
  for(int i = 0; i < 10; ++i) a[1][i] = 1;
  totals[1] = 9;
  int total, digit = 1;
  while (true) {
    ++digit;
    total = totals[digit - 1];
    for (int i = 0; i < 10; ++i) {
      for (int j = -1; j < 2; ++j) {
        if (i + j >= 0 && i + j <= 9) a[digit][i] += a[digit - 1][i + j];
      }
      if(i > 0) total += a[digit][i];
      if (total >= k) return {digit, i};
    }
    totals[digit] =  total;
  }
}

int main() {
  cin >> k;
  if (k < 13) {
    cout << k << endl;
    return 0;
  }
  vector<int> res = dp();
  k -= totals[res[0] - 1];
  for(int i = 1; i < res[1]; ++i) k -= a[res[0]][i];
  LL num = search(res[0] - 1, res[1], k);
  num += res[1] * pow(10, res[0] - 1);
  cout << num << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a,b,c,len;
int main()
{
    scanf("%d%d",&a,&b);
    c=b;
    while(c>0)
    {
        c/=10;
        len++;
    }
    a=a*pow(10,len)+b;
    if(sqrt(a)==floor(sqrt(a)))printf("Yes\n");
    else printf("No\n");
    return 0;
}


Measured memory_bytes: 256
n,k = map(int, input().split())
ans = 0
for b in range(1, n+1):
    ans += (n // b) * max(0, b-k)
    if n % b > 0:
        if k == 0:
            ans += max(0, (n % b) - k)
        else:
            ans += max(0, (n%b) - k + 1)
print(ans)

Measured memory_bytes: 3060
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

#define FOR1(n) for(int i=0;i<n;i++)
#define FOR2(j, n) for(int j=0;j<n;j++)
#define FOR3(i, m, n) for(int i=m;i<=n;i++)
#define ALL(c) c.begin(), c.end()
#define SCANF(x) scanf("%lld", &x)
#define MOD 1000000007
#define MAX 1000000001
#define INF 1410065408
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
struct edge{int from, to; ll cost;};

/*
逆順ソート sort(ALL(vec), greater<ll>());
ペア定義 P pair = make_pair(100, 200);
集合find set.find(item);
小さい順に取り出したい優先度付きキュー
priority_queue<int, vector<int>, greater<int> > que;
配列の最大要素 *std::max_element(ALL(vec))
*/

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int w, h, n;
	cin >> w >> h >> n;
	
	int xmin = 0, xmax = w, ymin = 0, ymax = h;
	
	FOR1(n){
	    int x, y, a;
	    cin >> x >> y >> a;
	    
	    if(a == 1 && xmin < x){
	        xmin = max(0, x);
	    }else if(a == 2 && xmax > x){
	        xmax = min(w, x);
	    }else if(a == 3 && ymin < y){
	        ymin = max(0, y);
	    }else if(a == 4 && ymax > y){
	        ymax = min(h, y);
	    }
	}
	
	cout << max(0, xmax - xmin) * max(0, ymax - ymin) << endl;
	return 0;
}


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

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
    int n;
    int p;
    cin >> n;
    int m = n + 2;
    int ans = 0;

    rep(i, n) {
        cin >> p;
        if (p < m)
            m = p;
        if (p <= m)
            ans++;
        if (m == 1)
            break;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256