akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#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 pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
int n,m,x,y,a[100010],b[100010];

int li[100010]={}; //偶奇
int dp[100010][2]={};
int ans[100010]={};
bool used[100010]={};
bool usedd[100010]={};
set<int> st;
vector<int> g[100010];

int solve();

int main(){
	cin >> n;
	REP(i,0,n-1) cin >> x >> y,g[x-1].push_back(y-1),g[y-1].push_back(x-1);
	cin >> m; REP(i,0,n) dp[i][0]=-INF,dp[i][1]=INF;
	REP(i,0,m) cin >> a[i] >> b[i],a[i]--,dp[a[i]][0]=dp[a[i]][1]=b[i],used[a[i]]=true;
	
	solve();
	return 0;
}

int solve(){
	queue<int> qu;
	stack<int> st;
	qu.push(a[0]);
	REP(i,0,n) usedd[i]=false;
	while(!qu.empty()){
		auto p=qu.front(); qu.pop();
		if(usedd[p]) continue; usedd[p]=true;
		
		for(auto e:g[p]) qu.push(e);
		st.push(p);
	}
	
	while(!st.empty()){
		auto p=st.top(); st.pop();
		if(used[p]) continue;
		
		int mi=dp[p][0],ma=dp[p][1];
		for(auto e:g[p]){
			mi=max(mi,dp[e][0]);
			ma=min(ma,dp[e][1]);
		}
		
		mi=max(mi-1,-INF),ma=min(ma+1,INF);
		if(mi>ma){cout << "No" << endl; return 0;}
		dp[p][0]=mi,dp[p][1]=ma;
	}
	
	REP(i,0,n) used[i]=false;
	qu.push(a[0]); ans[a[0]]=b[0];
	while(!qu.empty()){
		auto p=qu.front(); qu.pop();
		used[p]=true;
		
		for(auto e:g[p]){
			if(used[e]) continue;
			if(dp[e][0]<=ans[p]-1&&ans[p]-1<=dp[e][1]) ans[e]=ans[p]-1;
			else if(dp[e][0]<=ans[p]+1&&ans[p]+1<=dp[e][1]) ans[e]=ans[p]+1;
			else{cout << "No" << endl; return 0;}
			qu.push(e);
		}
	}
	
	cout << "Yes" << endl;
	REP(i,0,n) cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 9720
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int m=1e9+7;
int f[1000001]={1,1},inv[1000001]={1,1},invf[1000001]={1,1},n;
signed main()
{
	cin>>n;
	for(int i=2;i<=n;i++)f[i]=f[i-1]*i%m,inv[i]=(m-m/i)*inv[m%i]%m,invf[i]=invf[i-1]*inv[i]%m;
	int ans=0;
	for(int i=(n+1)/2;i<n;i++)ans+=f[i]*f[i-1]%m*invf[2*i-n]%m;
	cout<<(m+f[n]-ans%m)%m<<endl;
	return 0;
}


Measured memory_bytes: 23680
#include <algorithm>
#include <cstdio>

const int N=200005,M=1<<19,mo=924844033;
int a[M],b[M],rev[M],g[20][2],fst[N],fac[N],inv[N],n,tot=0,invn;
struct Edge{
	int to,nxt;
}e[N*2];

void addedge(int x,int y){
	e[++tot].to=y;e[tot].nxt=fst[x];fst[x]=tot;
}

int dfs(int x,int father){
	int sz=1;
	for (int i=fst[x];i;i=e[i].nxt)
		if (e[i].to!=father) sz+=dfs(e[i].to,x);
	if (x!=1) a[sz]++,a[n-sz]++;
	return sz;
}

void FFT(int *a,int n,int f){
	for (int i=0;i<n;i++)
		if (i<rev[i]) std::swap(a[i],a[rev[i]]);
	for (int i=1,t=0;i<n;i<<=1,t++){
		int wn=g[t][f];
		for (int j=0;j<n;j+=i<<1){
			int w=1;
			for (int k=0;k<i;k++,w=1ll*w*wn%mo){
				int x=a[j+k],y=1ll*w*a[j+k+i]%mo;
				a[j+k]=(x+y)%mo;
				a[j+k+i]=(x-y)%mo;
			}
		}
	}
	if (f)
		for (int i=0;i<n;i++) a[i]=1ll*a[i]*invn%mo;
}

int ksm(int x,int y){
	int i=1;
	for (;y;y>>=1,x=1ll*x*x%mo)
		if (y&1) i=1ll*i*x%mo;
	return i;
}

void mul(int m){
	int L=0,n=1;
	for (;n<m;n<<=1) L++;
	invn=ksm(n,mo-2);
	for (int i=1;i<n;i++)
		rev[i]=rev[i>>1]>>1^((i&1)<<(L-1));
	int val0=ksm(5,(mo-1)/n),val1=ksm(val0,mo-2);
	for (int i=L-1;i>=0;i--){
		g[i][0]=val0;val0=1ll*val0*val0%mo;
		g[i][1]=val1;val1=1ll*val1*val1%mo;
	}
	FFT(a,n,0);FFT(b,n,0);
	for (int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mo;
	FFT(a,n,1);
}

int main(){
	scanf("%d\n",&n);
	for (int i=1;i<n;i++){
		int x,y;
		scanf("%d%d\n",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	dfs(1,0);
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mo;
	inv[n]=ksm(fac[n],mo-2);
	for (int i=n;i;i--) inv[i-1]=1ll*inv[i]*i%mo;
	for (int i=0;i<=n;i++){
		a[i]=1ll*a[i]*fac[n-i]%mo;
		b[i]=inv[i];
	}
	mul(n*2);
	for (int i=1;i<=n;i++){
		int ans=(1ll*fac[n]*inv[n-i]%mo*n-a[n-i])%mo*inv[i]%mo;
		printf("%d\n",(ans+mo)%mo);
	}
}

Measured memory_bytes: 21632
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long
#define lli long long int

using namespace std;
using P = pair<int,int>;

int main(){

  int N;
  cin >> N;

  if(N >= 30){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n; cin >> n;
    vector<string> ss(3);
    REP(i,3) cin >> ss[i];
    int ans = 0;
    REP(i,n) {
        set<char> st;
        REP(j,3) {
            st.insert(ss[j][i]);
        }
        ans += st.size()-1;

    }
    
    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define in insert
#define sort(v) sort(v.begin(),v.end())
int main()
{
    int n,k,x,y;
    cin>>n>>k>>x>>y;
    if(k<=n)
    cout<<x*k+(n-k)*y<<endl;
    else
        cout<<n*x<<endl;
}


Measured memory_bytes: 3616
#include <stdio.h>

int main(void){
    int n;
    scanf("%d", &n);

    char s[n];
    scanf("%s", s);

    int count=0;

    for(int i=0; i<n; i++){
        if(s[i]!=s[i+1]){
            count++;
        }
    }
    printf("%d", count);
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

string s,t;
int f[3030][3030];
pii from[3030][3030];
int lens,lent;

void dfs(int x,int y){
    if(x<= 0 || y<=0) return ;
    dfs(from[x][y].fs,from[x][y].sc);
    cout<<s[x];
}
void upd(int i,int j,int x,int y){
    if(s[x] == t[y]) from[i][j] = {x,y};
    else from[i][j] = from[x][y];
}
int main(){
    // debug;
    ios;
    cin>>s>>t;
    lens = s.length(),lent = t.length();
    s = "#" + s; t = "^"+t;
    for(int i = 1;i<=lens;i++){
        for(int j = 1;j<=lent;j++){
            if(s[i] == t[j]) {
                f[i][j] = f[i-1][j-1] + 1;
                upd(i,j,i-1,j-1);
            }else{
                f[i][j] = max(f[i-1][j],f[i][j-1]);
                if(f[i-1][j] > f[i][j-1]) upd(i,j,i-1,j);
                else upd(i,j,i,j-1);
            } 
        }
    }
    int x = from[lens][lent].fs,y = from[lens][lent].sc;
    dfs(x,y);
    if(s[lens] == t[lent]) cout<<s[lens];

    
    return 0;
}


Measured memory_bytes: 107648
#include <stdio.h>

int main() {

	char a, b;

	scanf("%c %c",&a,&b);

	if (a == 'H'&&b == 'H') {
		printf("H\n");
	}
	else if (a == 'H'&&b == 'D') {
		printf("D\n");
	}
	else if (a == 'D'&&b == 'H') {
		printf("D\n");
	}
	else {
		printf("H\n");
	}

	return 0;
}

Measured memory_bytes: 128
H, W = map(int, input().split())
S = [input() for _ in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            flag = False
            for i in [-1, 0, 1]:
                for j in [-1, 0, 1]:
                    if not i+j in [-1, 1]:
                        continue
                    if 0 <= h+i < H and 0 <= w+j < W:
                        if S[h+i][w+j] == '#':
                            flag = True
            if not flag:
                print('No')
                exit()
print('Yes')

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

using namespace std;

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

	for(int i=a;i<=b;i++){
		if(i%k == 0){
			cout << "OK" << endl;
			return 0;
		}
	}

	cout << "NG" << endl;

	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<fstream>
#include<algorithm>
#include<string>
using namespace std;
string st;
long long x;
int a[100];
int main()
{
     cin>>st;
     for(int i=0;i<st.size();i++)
     {
     	if(st[i]=='0')
     	{
     		x++;
			a[x]=0;
     	}
     	if(st[i]=='1')
     	{
     		x++;
			a[x]=1;
     	}
     	if(st[i]=='B'&&x>0)
     	{
     		x--;
     	}
     }
     for(int i=1;i<=x;i++)
     {
     	cout<<a[i];
     }
     
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr_inv(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define rep(i,n) repr(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define MOD 1000000007
#define PI 3.1415926535
using namespace std;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	int a, b, c[6], i=0, d, num=0, sq;

	cin>>a>>b;

	if(a>=100){
		c[i++]=1; c[i++]=0; c[i++]=0;
	}else if(a>=10){
		c[i++]=a/10; c[i++]=a%10;
	}else{
		c[i++]=a;
	}

	if(b>=100){
		c[i++]=1; c[i++]=0; c[i++]=0;
	} else if(b>=10){
		c[i++]=b/10; c[i++]=b%10;
	} else{
		c[i++]=b;
	}
	d=i-1;
	rep(j, i){
		num+=(int)pow(10, (double)d)*c[j];
		d--;
	}
	sq=(int)sqrt(num);
	cout<<yn(sq*sq==num)<<endl;
}

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define pb(i) push_back(i)
#define INF 100100100
#define EPS 1e-9
#define itn int
typedef long long ll;
typedef vector<int> vi;
typedef map<string, int> msi;
const int dx[] = {0, 1, 0, -1, -1, 1, 1, -1};  //座標移動用
const int dy[] = {1, 0, -1, 0, -1, 1, -1, -1};

template<typename T, typename U>
T gcd(T a, T b) {return (b ? gcd(b, a%b) : a);}

template<typename T, typename U>
T lcm(T a, T b) {return (a * b / gcd(a, b));}

int in() {int x; cin >> x; return x;}

int main()
{
    int a, b, c;

    cin >> a >> b;

    cout << (a-1) * (b-1) << endl;
    return (0);
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    int a,b,k;
    cin >> a >> b >> k;
    rep(i,k){
        if(i%2 == 0){
            if(a%2)a--;
            b += a/2;
            a /= 2;
        }else{
            if(b%2)b--;
            a += b/2;
            b /= 2;
        }
    }
    cout << a << " " << b << endl;
}


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

ll N;

void solve(ll num, ll bits, ll &count)
{
	if (num > N) return;
	if (num <= N && (bits & 0b111) == 0b111) ++count;
	
	solve(num*10+3, bits | 0b001, count);
	solve(num*10+5, bits | 0b010, count);
	solve(num*10+7, bits | 0b100, count);
}

int main(int argc, char **argv)
{
	cin >> N;
	ll count{0};
	solve(0, 0, count);
	std::cout << count << std::endl;
}


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

int main(void)
{
    char    str[512];
    char    str2[512];
    int i;
    int len;
    int len2;
    int on = 0;

    scanf("%s", str);
    scanf("%s", str2);

    len = strlen(str);
    len2 = strlen(str2);
    on = strncmp(str, str2, len);
    if (on == 0 && len + 1 == len2) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
    
    return  0;
}

Measured memory_bytes: 1712
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll N, D, X;
  cin >> N >> D >> X;
  vl A(N);
  rep(i, N) cin >> A[i];

  ll cnt = X;

  rep(i, N) cnt += (D - 1) / A[i] + 1;

  cout << cnt << endl;
  
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
using namespace std;
int main(){
	int f=0;
	string s,sma="";
	getline(cin,s);
	for(int i=0;i<s.size();i++){
		if(s[i]==' ' || s[i]==',' || s[i]=='.'){
			if(sma.size()>2 && 7>sma.size()){
				if(f)cout<<" ";
				f=1;
				cout<<sma;
			}
			sma="";
		}
		else{
			sma+=s[i];
		}
		
	}
	if(sma.size()>2 && 7>sma.size()){
		if(f)cout<<" ";
		f=1;
		cout<<sma;
	}
	cout<<endl;
	
	return 0;
}


Measured memory_bytes: 1176
#include<iostream>
#include<vector>
#include<string>
#define int double
using namespace std;

signed main() {
	int a[8];
	while (1) {
		for (signed b = 0; b < 8; b++)cin >> a[b];
		if (cin.fail())break;
		if (a[6]<a[0] || a[4]>a[2] || a[7] < a[1] || a[5] > a[3])cout << "NO" << endl;
		else cout << "YES" << endl;
	}
}

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

struct UnionFind{
	vector<int> par;
	vector<int> sizes;
	UnionFind(int n):par(n),sizes(n,1){
		for(int i=0;i<n;i++)par[i] = i;
	}
	int find(int x){
		if(x == par[x])return x;
		return par[x] = find(par[x]);
	}
	void unite(int x,int y){
		x = find(x);y = find(y);
		if(x == y)return;
		if(sizes[x] < sizes[y])swap(x,y);
		par[y] = x;
		sizes[x] += sizes[y];
	}
	bool same(int x,int y){
		return find(x) == find(y);
	}
	int size(int x){
		return sizes[find(x)];
	}
};

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

	UnionFind uf(N);
	long long ret = 0;
	for(int i=0;i<N-1;i++){
		long long cost = A*(x[i+1]-x[i]);
		if( B > cost ){
			uf.unite(i,i+1);
			ret += cost;
		}
	}

	set<int> st;
	for(int i=0;i<N;i++){
		st.insert(uf.find(i));
	}

	cout << ret + (B * (st.size()-1)) << endl;

	return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <string>
#include <bitset>

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

    unsigned long N = S.size();
    int M = 1 << (N-1);
    long long sum = 0;
    for(int i=0; i<M; i++){
        std::bitset<9> plus(i);
        // std::cout << plus << " ";
        long long times = 1;
        sum += S[N-1] - '0';
        for(int j=0; j<N-1; j++){
            if(plus[j] == true) times = 1;
            else times *= 10;
            sum += times * (S[N-2-j] - '0');
        }
        // std::cout << sum << std::endl;
    }
    std::cout << sum << std::endl;
}

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

bool isPalindrome(string s,int l,int r){
    while(l<r){
        if(s[l]!=s[r]) return false;
        else l++,r--;
    }
    return true;
}

int main(){
    string s;
    cin>>s;
    if(isPalindrome(s,0,s.length()-1) and isPalindrome(s,0,(s.length()-2)/2) and isPalindrome(s,(s.length()+2)/2,s.length()-1) ) printf("Yes\n");
    else printf("No\n");
    return 0;
}


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

string convert(string str){
  char pre = 0;
  int  cnt = 0;
  ostringstream sout;

  str += "+";
  for(int i=0; i<str.length(); i++){
    if(pre != str[i]){
      if(pre){
	sout << cnt << pre;
      }
      pre=str[i]; cnt=1;
    }
    else {
      cnt++;
    }
  }
  return sout.str();
}

int main()
{
  int n;
  while(cin >> n, n){
    string str;
    cin >> str;
    while(n--) {
      str = convert(str);
    }
    cout << str << endl;
  }
}

Measured memory_bytes: 1408
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  long long N;
  scanf("%lld", &N);
  std::vector<long long> A(N);
  ll sum = 0;
  for (int i = 0; i < N; i++)
  {
    scanf("%lld", &A[i]);
    sum += A[i];
  }
  int itr = -1;
  ll left = 0;
  for (int i = 0; i < N; ++i)
  {
    if (left + A[i] > sum / 2)
    {
      itr = i;
      break;
    }
    if (itr < 0)
      left += A[i];
  }
  cout << min(abs(sum - 2 * left), abs(sum - 2 * (left + A[itr]))) << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

vector<int> adj[1000];

int main() {
	fastio;
	int N, M;
	cin >> N >> M;

	for (int a, b, i = 0; i < M; ++i) {
		cin >> a >> b;
		adj[--a].push_back(--b);
	}

	vector<int> ans;
	for (int i = 0; i < N; ++i) {
		int wif[1000];
		ini(wif, -1);

		queue<int> Q;
		for (int nxt : adj[i]) {
			Q.push(nxt);
			wif[nxt] = i;
		}

		while (!Q.empty()) {
			int now = Q.front(); Q.pop();

			if (now == i) {
				vector<int> tmp = { i };
				for (int j = wif[i]; j != i; j = wif[j]) tmp.push_back(j);

				if (ans.empty() || sz(ans) > sz(tmp)) ans = tmp;
				break;
			}

			for (int nxt : adj[now]) if (wif[nxt] == -1) {
				wif[nxt] = now;
				Q.push(nxt);
			}
		}
	}

	if (ans.empty()) return cout << -1, 0;

	cout << sz(ans) << endl;
	for (int i : ans) cout << i + 1 << endl;

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define trav(a, x) for(auto& a : x)
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
ll md = 1e9+7;


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

    vi last(200009,-1);
    vi prev(200009,-1);
    int n;
    vi c;
    vi dp(200009);
    
    cin >> n;
    c = vi(n);
    rep(i,0,n){
        cin >> c[i];
        c[i]--;
        if(last[c[i]] != -1){
            prev[i] = last[c[i]];
        }else{

        }
        last[c[i]] = i;
    }
    dp[0] = 1;
    rep(i,1,n){
        if(c[i]==c[i-1]){
            dp[i] = dp[i-1];
        }else{
            if(prev[i] == -1){
                dp[i] = dp[i-1];
            }else{
                dp[i] = dp[i-1]+dp[prev[i]];
                dp[i] %= md;
            }
        }
    }

    cout << dp[n-1] << endl;

    return 0;
}


Measured memory_bytes: 3456
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;


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

int main() {
    int N,K;
    cin >> N >> K;
    ll h[111111] = {};
    ll dp[111111] = {};
    for(int i=0;i<N;i++){
        cin >> h[i];
        dp[i] = INF;
    }
    
    dp[0] = 0;

    for(int i=0;i<N;i++){
        for(int j=1;j<=K;j++){
            chmin(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
        }
    }
cout << dp[N-1]  << endl;
    return 0;
}



Measured memory_bytes: 1920
import java.util.Scanner;

public class Main {

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

		if (x.equals(y.subSequence(0, y.length() - 1))) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}


		sc.close();
	}

}


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

// int/long:		-2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)
// while (getline(cin, S)) {}

// #include <cstdio>
// int a;
// scanf("%d", &a);
// printf("%d\n", a);
//
// for (int i=0; i<n; ++i)
// 	scanf("%d", &a[i]);
//
// char c;
// scanf(" %c", &c);
//
// cout << "\n";

// cout <<fixed <<setprecision(10)

// priority_queue<int> q;
// priority_queue<int, vector<int>, less<int>> q; // Default: vector, less
// priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

//
// Notes
//
// When specified less than N, try full scan.
// RE: empty vector
// Check Qs
// long/int
// xor -> count each bit
// Check values
// 	1,000,000 -> Loop
// 	100,000	-> vector(int:400KB, long:800KB) 

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define	MOD 1000000007

#define	Rep0(i, n)	for (int i=0; i<n; i++)
#define	Rep1(i, n)	for (int i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	string S;
	cin >>S;
	bool F=true;
	if (1==S.size()%2) {
		cout <<"No" <<endl;
		return 0;
	}
	Rep0(i, S.size()) {
		if (0==i%2) {
			if ('h'!=S.at(i))
				F=false;
		} else {
			if ('i'!=S.at(i))
				F=false;
		}
	}
	if (F)
		cout <<"Yes" <<endl;
	else
		cout <<"No" <<endl;
	return 0;
}



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

int main() {
	int N,a=0;
	char S[100];
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
	}
	if (N % 2 == 1) {
		cout << "No" << endl;
	}
	else {
		for (int l = 0; l < N / 2; l++) {
			if (S[l] == S[N / 2 + l])a++;
		}
		if (a == N / 2)cout << "Yes" << endl;
		else {
			cout << "No" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 764
def gcd(a, b):
    tmp = a%b
    if tmp == 0:
        return b
    return gcd(b, tmp)

a, b, c, d = map(int, input().split())

cd = (c * d) // gcd(c, d)
a_c = (a-1) // c
b_c = b // c
a_d = (a-1) // d
b_d = b // d
a_cd = (a-1) // cd
b_cd = b // cd

print(b - a + 1 - (b_c - a_c) - (b_d - a_d) + (b_cd - a_cd))


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

const int N = 1e5 + 10;
int a[N], col[N];
vector<pair<int, int>> adj[N];

void dfs(int root, int par, int c) {
    int cc = 0;
    for (int i = 0; i < adj[root].size(); i++) {
        int u = adj[root][i].first;
        if (u ^ par) {
            if (cc == c)
                cc++;
            col[adj[root][i].second] = cc;
            dfs(u, root, cc);
            cc++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, u, v;
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        adj[--u].push_back(make_pair(--v, i));
        adj[v].push_back(make_pair(u, i));
    }
    dfs(0, -1, -1);
    int ans = adj[0].size();
    for (int i = 1; i < n; i++)
        ans = max(ans, (int)adj[i].size());
    cout << ans << "\n";
    for (int i = 1; i < n; i++)
        cout << col[i] + 1 << "\n";
    cout << '\n';
    return 0;
}

Measured memory_bytes: 9344
_ = input()
l = list(map(int,input().split()))
mn = 99999
for i in l:
  count = 0
  while True:
    if i %2 ==0:
      count +=1
      i = int(i/ 2)
    else:
      break
  if mn > count:
    mn = count
print(mn)



Measured memory_bytes: 2940
#include <cstdio>
#include <vector>
#include <cstring>
#include <functional>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <set>
#include <queue>
#include <assert.h>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <complex>
#include <numeric>
#include <map>
#include <time.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<int,ull> piu;
typedef pair<ull,ull> puu;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
typedef pair<pii,ll> ppl;
typedef pair<ll,pii> plp;
typedef pair<ll,pll> plP;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
typedef pair<double,int> pdi;
typedef pair<int,double> pid;
typedef pair<double,pii> pdp;
typedef pair<double,double> pdd;
typedef pair<pdd,double> pd3;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i,n) for (int (i) = 0; (i) < (n); (i)++)
#define repn(i,a,n) for (int (i) = (a); (i) < (n); (i)++)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define SORT(x) sort((x).begin(),(x).end())
#define SORTN(x,n) sort((x),(x)+(n))
#define ERASE(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define COUNT(x,c) count((x).begin(),(x).end(),(c))
#define REMOVE(x,c) (x).erase(remove((x).begin(),(x).end(),(c)),(x).end())
#define REVERSE(x) reverse((x).begin(),(x).end())
#define FORIT(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))-(x).begin()
#define lb(x,a) lower_bound((x).begin(),(x).end(),(a))
#define LBN(x,a,n) lower_bound((x),(x)+(n),(a))-(x)
#define lbN(x,a,n) lower_bound((x),(x)+(n),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))-(x).begin()
#define ub(x,a) upper_bound((x).begin(),(x).end(),(a))
#define BS(x,a) binary_search((x).begin(),(x).end(),(a))
#define BS2(x,n,a) binary_search((x),(x)+(n),(a))
#define NB(x) (((x)&~((x)+((x)&-(x))))/((x)&-(x))>>1)|((x)+((x)&-(x)))
#define NP(x) next_permutation((x).begin(),(x).end())
#define MM(x,p) memset((x),(p),sizeof(x))
#define SQ(x) (x)*(x)
#define SC(c1,c2) strcmp(c1,c2)==0
#define mp make_pair
#define INF (1<<29)
#define INFL (1LL<<61)
#define fi first
#define se second
#define EPS 1e-9
#define MOD 1000000007
#define MIN(x,a) x=min(x,a)
#define MAX(x,a) x=max(x,a)
#define madd(x,a) x=(x+a)%MOD
#define msub(x,a) x=(x+MOD-a)%MOD
#define OUTPUT(x) rep(__,x.size())printf("%d%c",x[__],__+1==x.size()?'\n':' ')

int N;
string S;

bool bf[30001][10];
bool pf[30001][10];
bool on[1000];

int main()
{
	scanf("%d",&N);
	cin>>S;
	rep(i,S.size())
	{
		if(i)rep(j,10)bf[i][j]=bf[i-1][j];
		if(i)bf[i][S[i-1]-'0']=true;
	}
	
	for(int i=N-1;i>=0;i--)
	{
		if(i!=N-1)rep(j,10)pf[i][j]=pf[i+1][j];
		if(i!=N-1)pf[i][S[i+1]-'0']=true;
	}
	rep(i,N)
	{
		int c=S[i]-'0';
		rep(j,10)rep(k,10)if(pf[i][k]&&bf[i][j])
		{
			int r=j*100+k+c*10;
			on[r]=true;
		}
	}
	int c=0;
	rep(i,1000)c+=on[i];
	printf("%d\n",c);
}

Measured memory_bytes: 896
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long ul;
typedef unsigned int ui;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
#define All(v) (v).begin(),(v).end()
#define Rep(i,n) for(int i = 0; i < (int)n; i++)
#define Reps(i,n) for(int i = 1; i <= (int)n; i++)
#define For(i,m,n) for(int i = m; i < n; i++)
#define Fors(i,m,n) for(int i = m; i <= n; i++)
#define Inf 2e9
#define F first
#define S second
#define pb push_back
#define mp make_pair
struct speed{speed(){cin.tie(); ios::sync_with_stdio(false); cout << fixed << setprecision(18);}}speed;

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

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

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



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

Measured memory_bytes: 256
gets; a = gets.split.map(&:to_i).sort + [Float::INFINITY]
gets; b = gets.split.map(&:to_i).sort + [Float::INFINITY]

d = []
until a.empty?
  if a[0] < b[0]
    d << a.shift
  elsif a[0] > b[0]
    d << b.shift
  else
    a.shift
    b.shift
  end
end
d[0..-1].each {|x| p x }



Measured memory_bytes: 72656
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repeq(i,a,b) for(int i=a;i<=(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void check(vi a) {
    ll sum=0;
    int n=sz(a);
    rep(i,0,n) sum+=a[i];
    set<int> seen;
    rep(i,0,n) {
        assert(!seen.count(a[i]));
        seen.insert(a[i]);
    }
    rep(i,0,n) {
        assert(a[i]<=30000);
        assert(__gcd((ll)a[i],sum-a[i])!=1);
    }
}
vi twos(int n) {
    vi ans;
    rep(i,0,n) {
        ans.push_back(2*(i+1));
    }
    if(n%3==1) {
        ans[n-1]+=4;
    }
    return ans;
}
vi threes(int n) {
    vi ans;
    rep(i,0,n) {
        ans.push_back(6*i+3);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vi ans;
    if(n==3) {
        ans = vi{2,5,63};
    }
    else {
        int m=n/4;
        if(m%2==1) ++m;
        ans = twos(n-m);
        vi th=threes(m);
        for(int x:th) ans.push_back(x);
    }
    //check(ans);
    for(int x:ans) cout<<x<<" ";
    cout<<endl;
}


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

#define MOD 1000000007

using namespace std;

int main() {
	int n, m; cin >> n >> m;
	vector<bool> broken(n + 1, false);
	vector<int> dp(n + 2, 0);
	for (int i = 0; i < m; ++i) {
		int a; cin >> a;
		broken[a] = true;
	}

	dp[0] = 1;
	for (int i = 0; i < n; ++i) {
		if (broken[i]) dp[i] = 0;
		dp[i + 1] += dp[i]; dp[i + 1] %= MOD;
		dp[i + 2] += dp[i]; dp[i + 2] %= MOD;
	}
	
	cout << dp[n] << endl;

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int huiwen(string s)
{
    string t;
    t = s;
    reverse(s.begin(),s.end());
    if(t == s)
        return 1;
    else
        return 0;
}

int main()
{
    int n,i;
    string s,n1,n2;
    cin >> s;
    if(huiwen(s))
    {
        n = s.size();
        for(i = 0;i < (n-1)/2 ;i++)
            n1 += s[i];
        for(i = (n+3)/2-1; i < n ;i++)
            n2 += s[i];
        if(huiwen(n1) && huiwen(n2))
            cout << "Yes" <<endl;
        else
            cout << "No" <<endl;
    }
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
n,m,l=gets.split.map(&:to_i)
a=Array.new(n){ gets.split.map(&:to_i) }
b=Array.new(m){ gets.split.map(&:to_i) }
c=Array.new(n){ Array.new(l) }
n.times do |i|
  l.times do |j|
    c[i][j]=a[i].zip(b.transpose[j]).reduce(0){|s,(x,y)|s+x*y}
  end
end
puts c.map{|l|l*' '}



Measured memory_bytes: 14484
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<string>
#include<algorithm>

using ll = long long;
using namespace std;

const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
	int n;cin >> n;
	vector<vector<int>> cost(n+1, vector<int>(3, 0));
	vector<vector<int>> dp(n+1, vector<int>(3, 0));
	for (int i = 1;i < n+1;i++){
		for (int j = 0;j < 3;j++){
			cin >> cost[i][j];
		}
	}

	for (int i = 0;i < n;i++){
		for (int j = 0;j < 3;j++){
			for (int k = 0;k < 3;k++){
				if (j == k) continue;
				dp[i+1][k] = max(dp[i+1][k], dp[i][j]+cost[i+1][k]);
			}
		}
	}
	cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
/*
	for (int i = 0;i < n+1;i++){
		for (int j = 0;j < 3;j++){
			cout << dp[i][j];
		}
		cout << endl;
	}
*/	
}

Measured memory_bytes: 11136
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
struct data{
    int a,b,c,d;
};
int main(){
  while(1){
      ll n,m;
      cin>>n>>m;
      if(n==0)return 0;
      int r;
      cin>>r;
      V<data> dat(r);
      for(int i=0;i<r;i++){
          cin>>dat[i].a>>dat[i].b>>dat[i].c>>dat[i].d;
      }
       int q;
      cin>>q;
      V<data> query(q);
      map<int,int> mp;
      V<bool> used(m,false);
      int cnt=0;
      for(int i=0;i<q;i++){
          cin>>query[i].a>>query[i].b>>query[i].c;
          if(!used[query[i].c-1]){
              mp[query[i].c-1]=cnt++;
              used[query[i].c-1]=true;
          }  
      }
      V<V<ll>> tim(cnt,V<ll>(1270,0)),sum(cnt,V<ll>(1270,0));
      for(int i=0;i<r;i++){
          if(!used[dat[i].c-1])continue;
          if(dat[i].d){
              tim[mp[dat[i].c-1]][dat[i].a]++;
          }else{
              tim[mp[dat[i].c-1]][dat[i].a]--;
          }
      }
      for(int i=0;i<cnt;i++){
          for(int j=0;j<1265;j++){
              tim[i][j+1]+=tim[i][j];
          }
      }
      for(int i=0;i<cnt;i++){
          for(int j=0;j<1265;j++){
              sum[i][j+1]+=(tim[i][j]>0)+sum[i][j];
          }
      }
      for(int i=0;i<q;i++){
          cout<<sum[mp[query[i].c-1]][query[i].b]-sum[mp[query[i].c-1]][query[i].a]<<"\n";
      }
  }
}


Measured memory_bytes: 3560
#include<iostream>
#include<map>
using namespace std;
int N,K;
map<int,int>M;
long pre[2<<17];
main()
{
	cin>>N>>K;
	long ans=0;
	M[0]=1;
	pre[0]=0;
	long now=0;
	for(int i=0;i<N;i++)
	{
		long A;cin>>A;
		now=(now+A-1)%K;
		pre[i+1]=now;
		if(K<=i+1)M[pre[i+1-K]]--;
		ans+=M[now]++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 11136
// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = int64_t;
using ull = uint64_t;
using PLL = pair<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
// #include "../debug/debug.cpp"
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

const ll inf = 5e15;

int main() {
    ll N;
    cin >> N;
    V<ll> B(N - 1);
    for(auto &&ele : B) cin >> ele;
    ll ans = 0;
    for(ll i = 0; i < N; i++) {
        ll a = (0 < i ? B[i - 1] : inf);
        ll b = (i < B.size() ? B[i] : inf);
        ans += min(a, b);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

typedef pair<int,int> P;

int main(void) {
    int N,K;

    cin>>N>>K;

    vector<P> s;
    for(int i = 1;i*i <= N;i++) {
        s.push_back({i,0});
        s.push_back({N/i,0});
    }
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());

    for(int i = 0;i < s.size()-1;i++) {
        int up = N/s[i].first;
        int bp = N/s[i+1].first;
        s[i].second = up-bp;
    }
    s.back().second = 1;
    int m = s.size();
    map<int,int> mp;
    for(int i = 0;i < m;i++) {
        mp[s[i].first] = i;
    }
    vector<vector<Int>> dp(K+1, vector<Int>(m));
    dp[0][mp[N]] = 1;

    for(int i = 0;i < K;i++) {
        for(int j = m-2;j >= 0;j--) {
            dp[i][j] += dp[i][j+1];
            dp[i][j] %= MOD;
        }
        for(int j = 0;j < m;j++) {
            int nj = mp[N/s[j].first];
            dp[i+1][j] += dp[i][nj]*s[j].second;
            dp[i+1][j] %= MOD;
        }
    }

    Int ans = 0;
    for(int i = 0;i < m;i++) {
        ans = (ans + dp[K][i])%MOD;
    }

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


Measured memory_bytes: 54512
# 

a=gets().chomp
b=gets().chomp
la=a.length
lb=b.length
k=0

if la>lb
    k=1

elsif la<lb
    k=-1

else
    for i in 0..la-1
        if a[i]>b[i]
            k=1
        elsif a[i]<b[i]
            k=-1
        end
        if k!=0
            break
        end
    end
end

if k==1
    puts("GREATER")
elsif k==-1
    puts("LESS")
else
    puts("EQUAL")
end



Measured memory_bytes: 1788
function length_plus(moji){
    moji = String(moji);
    while(moji.length < 6){
        moji = "0" + moji;
    }
    return(moji);
}
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
    input = input.split("\n");
    tmp1 = input[0].split(" ");
    N = parseInt(tmp1[0]);
    M = parseInt(tmp1[1]);
    var hairetu = [];
    for(i = 1; i < M +1; i++){
        i_nojyoho= input[i].split(" ")
        hairetu.push({kuni: parseInt(i_nojyoho[0]), shi: i, nen: parseInt(i_nojyoho[1])});
    }
    hairetu.sort(function(a,b){
        if(a.kuni < b.kuni) return -1;
        if(a.kuni > b.kuni) return 1;
        if(a.nen < b.nen) return -1;
        if(a.nen > b.nen) return 1;
        return 0;
    });
    for(i = 0; i < hairetu.length; i++){
        if(i === 0||hairetu[i].kuni !== hairetu[i-1].kuni){
            hairetu[i].jyun = 1;
        }else{
            hairetu[i].jyun = hairetu[i-1].jyun + 1;
        }
    }
    for(i = 0; i < hairetu.length; i++){
        bangou = length_plus(hairetu[i].kuni) + length_plus(hairetu[i].jyun);
        hairetu[i].bangou = bangou;
    }
    hairetu.sort(function(a,b){
        if(a.shi < b.shi) return -1;
        if(a.shi > b.shi) return 1;
        return 0;
    });
    for(i = 0; i < hairetu.length; i++){
        console.log(hairetu[i].bangou);
    }
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 78308
#include <iostream>
#include<queue>
#include<stack>
#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 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;
const long long MOD = 1e9 + 7;
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));
}

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

	ll n, t;
	cin >> n >> t;
	Array a(n, 0);
	REP(i, n) cin >> a[i];

	ll min = a[0];

	ll max = 0;
	ll max_n = 0;

	for (ll i = 1; i < n; i++) {
		if (min > a[i]) {
			min = a[i];
		}

		if (a[i] - min > max) {
			max = a[i] - min;
			max_n = 1;
		}
		else if(a[i] - min == max){
			max_n++;
		}
	}

	cout << max_n << endl;


	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int A,B;


int main(){
    cin>>A>>B;
    long long n,m;
    n=max(A,B);
    m=min(A,B);    
    while(true){
        if(n%m==0)break;
        n+=max(A,B);
    }
    
    cout<<n<<endl;

}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::str::*;
#[allow(unused_imports)]
use std::mem::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::HashMap;
#[allow(unused_imports)]
use std::collections::VecDeque;
#[allow(unused_imports)]
use std::usize;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();
    line.trim().to_string().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_cols<T: FromStr>() -> Vec<T> {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();

    line.trim()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn main() {
    let n = read::<i64>();
    println!("{}", n/3);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#ifdef LOCAL
#include "Template.cpp"
#else
#define t(...)
#endif
#define endl "\n"

class SegmentTree {
public:
    vector<int> arr;
    int n;
    vector<int> tree;
    SegmentTree(int size) {
        n = size;
        arr.assign(n + 1, 0);
        tree.resize(4 * n + 1);
    }
    void update(int curr, int l, int r, int pos, int val) {
        if(l == r) {
            tree[curr] = max(tree[curr], val);
            return ;
        }
        int mid = (l + r) / 2;
        if (pos <= mid)
        {
            update(curr * 2, l, mid, pos, val);
        }
        else
        {
            update(curr * 2 + 1, mid + 1, r, pos, val);
        }
        tree[curr] = max(tree[curr<<1], tree[curr<<1|1]);
    }
    int query(int curr, int l, int r, int i, int j) {
        if (j < l || i > r)
            return 0;
        if (i <= l && r <= j)
        {
            return tree[curr];
        }
        int mid = (l + r) / 2;
        int left = query(curr * 2, l, mid, i, j);
        int right = query(curr * 2 + 1, mid + 1, r, i, j);
        return max(left, right);
    }
};

void solve()
{
    int n, k; cin >> n >> k;
    vector<int> arr(n+1);
    for(int i = 1; i <= n; i ++) {
        cin >> arr[i];
    }
    SegmentTree tree(1e7);
    vector<int> dp(n+1);
    for(int i = 1; i <= n; i ++) {
        int left = max(0LL, arr[i] - k);
        int right = arr[i] + k;
        int maxx = tree.query(1, 1, (1e7)-1, left, right);
        t(i, left, right, maxx);
        dp[i] = 1 + maxx;
        tree.update(1, 1, (1e7)-1, arr[i], dp[i]);
    }
    t(dp);
    int ans = *max_element(dp.begin(), dp.end());
    cout << ans << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 398680
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
using itn = int;
using namespace std;
static const long double GRATIO=(long double)(1+sqrt(5))/2;
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 sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    //0:上 1:下 2:左 3:右
    char s[4] = {'U','D','L','R'};
    int x_to,y_to;
    if(tx-sx>0) x_to=3;
    else x_to=2;
    if(ty-sy>0) y_to=0;
    else y_to=1;
        rep(i,abs(tx-sx)) cout<<s[x_to];
        rep(i,abs(ty-sy)) cout<<s[y_to];
        rep(i,abs(tx-sx)) cout<<s[5-x_to];
        rep(i,abs(ty-sy)) cout<<s[1-y_to];
        cout<<s[1-y_to];
        rep(i,abs(tx-sx)+1) cout<<s[x_to];
        rep(i,abs(ty-sy)+1) cout<<s[y_to];
        cout<<s[5-x_to];
        cout<<s[y_to];
        rep(i,abs(tx-sx)+1) cout<<s[5-x_to];
        rep(i,abs(ty-sy)+1) cout<<s[1-y_to];
        cout<<s[x_to]; 
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean flag = false, imposible = false;		
		ArrayList<Integer> a = new ArrayList<Integer>();
		ArrayList<Integer> b = new ArrayList<Integer>();
		for(int i = 0; i < n; i++){
			b.add(sc.nextInt());
		}
		for(int i = 0; i < n; i++){
			for(int j = b.size() - 1; 0 <= j; j--){
				if(b.get(j) == j + 1){
					a.add(j + 1);
          b.remove(j);
					flag = true;
					break;
				}
			}
			if(flag == false){
				imposible = true;
				break;
			}else{
				flag = false;
			}
		}
		if(imposible == true){
			System.out.println(-1);
		}else {
			for(int i = a.size() -1 ; 0 <= i; i--){
				System.out.println(a.get(i));
			}
		}
	}
}


Measured memory_bytes: 23124
#!/usr/bin/env python3
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
seen = set()
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
    seen.add(a)
ab.sort()

decomp = list(seen)
decomp.sort()
node_num = len(decomp)
comp = dict()
for i, item in enumerate(decomp):
    comp[item] = i

# Take diff
d = [0] * (node_num + 1)
prev = 0
for a, b in ab:
    if b != prev:
        d[comp[a]] = 1
    prev = b
if prev != 0:
    d[node_num] = 1

switch_dict = dict()
lr = []
for i in range(m):
    l, r = map(int, input().split())
    lft = bisect.bisect_left(decomp, l)
    rgt = bisect.bisect_right(decomp, r)
    if lft != rgt:
        lr.append((lft, rgt))
        switch_dict[(lft, rgt)] = i + 1

edge = [[] for _ in range(node_num + 1)]
for l, r in lr:
    edge[l].append(r)
    edge[r].append(l)

visited = [0] * (node_num + 1)
ans = []
def dfs(p, v):
    ret = d[v]
    for nv in edge[v]:
        if nv == p:
            continue
        if not visited[nv]:
            visited[nv] = 1
            val = dfs(v, nv)
            if val == 1:
                if v < nv:
                    ans.append(switch_dict[(v, nv)])
                else:
                    ans.append(switch_dict[(nv, v)])
                ret += 1
    return ret % 2

for i in range(node_num + 1):
    if visited[i]:
        continue
    visited[i] = 1
    ret = dfs(-1, i)
    # Check last node is ok or not
    if ret == 1:
        print(-1)
        exit()

# Check trees cover all 1 or not
for c, is_visited in zip(d, visited):
    if not is_visited and c:
        print(-1)
        exit()

ans.sort()
print(len(ans))
print(*ans)

Measured memory_bytes: 162368