akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
int H,W;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
string mp[50];
int vis[50][50][4][1000];
string s;
int pr[1000];
main()
{
	cin>>H>>W;
	queue<pair<pair<int,int>,pair<int,int> > >P;
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)for(int k=0;k<4;k++)for(int l=0;l<1000;l++)
	{
		vis[i][j][k][l]=1e9;
	}
	for(int i=0;i<H;i++)
	{
		cin>>mp[i];
		for(int j=0;j<W;j++)
		{
			if(mp[i][j]=='s')
			{
				P.push(make_pair(make_pair(i,j),make_pair(0,0)));
				vis[i][j][0][0]=0;
			}
		}
	}
	cin>>s;
	stack<int>parse;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='['||s[i]=='{')parse.push(i);
		else if(s[i]==']')
		{
			pr[parse.top()]=i;
			parse.pop();
		}
		else if(s[i]=='}')
		{
			pr[i]=parse.top();
			pr[pr[i]]=i;
			parse.pop();
		}
	}
	while(!P.empty())
	{
		int x=P.front().first.first,y=P.front().first.second;
		int r=P.front().second.first,id=P.front().second.second;
		int now=vis[x][y][r][id];
		P.pop();
		if(mp[x][y]=='g')
		{
			cout<<now<<endl;
			return 0;
		}
		vector<pair<pair<pair<int,int>,pair<int,int> >,int> >ns;
		if(s[id]=='['||s[id]=='{')
		{
			bool cond;
			char op=s[id+1];
			bool neg=false;
			if(op=='~')
			{
				neg=true;
				op=s[id+2];
			}
			if(op=='N')cond=r==0;
			else if(op=='E')cond=r==1;
			else if(op=='S')cond=r==2;
			else if(op=='W')cond=r==3;
			else if(op=='C')
			{
				int tx=x+dx[r],ty=y+dy[r];
				cond=mp[tx][ty]=='#';
			}
			else if(op=='T')cond=true;
			if(neg)cond=!cond;
			if(cond)
			{
				ns.push_back(make_pair(make_pair(make_pair(x,y),make_pair(r,neg?id+3:id+2)),now));
			}
			else
			{
				ns.push_back(make_pair(make_pair(make_pair(x,y),make_pair(r,pr[id]+1)),now));
			}
		}
		else if(s[id]==']')
		{
			ns.push_back(make_pair(make_pair(make_pair(x,y),make_pair(r,id+1)),now));
		}
		else if(s[id]=='}')
		{
			ns.push_back(make_pair(make_pair(make_pair(x,y),make_pair(r,pr[id])),now));
		}
		else if(s[id]=='^'||s[id]=='v')
		{
			int dir=s[id]=='^'?r:(r+2)%4;
			int tx=x+dx[dir],ty=y+dy[dir];
			if(mp[tx][ty]!='#')
			{
				ns.push_back(make_pair(make_pair(make_pair(tx,ty),make_pair(r,id+1)),now+1));
			}
			else
			{
				ns.push_back(make_pair(make_pair(make_pair(x,y),make_pair(r,id+1)),now+1));
			}
		}
		else if(s[id]=='<'||s[id]=='>')
		{
			int nr=s[id]=='<'?(r+3)%4:(r+1)%4;
			ns.push_back(make_pair(make_pair(make_pair(x,y),make_pair(nr,id+1)),now+1));
		}
		for(pair<pair<pair<int,int>,pair<int,int> >,int>p:ns)
		{
			int nx=p.first.first.first,ny=p.first.first.second;
			int nr=p.first.second.first,nid=p.first.second.second;
			int cost=p.second;
			if(vis[nx][ny][nr][nid]>cost)
			{
				vis[nx][ny][nr][nid]=cost;
				P.push(p.first);
			}
		}
	}
	cout<<-1<<endl;
}



Measured memory_bytes: 42292
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

string adj;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	while(n>0)
	{
		ll c;
		if(n%26)
			c = n%26-1;
		else
		{
			n = n-1;
			c = 25;
		}
		adj.pb((char)('a'+c));
		n = n/26;
	}

	reverse(all(adj));
	cout << adj << "\n";
}

Measured memory_bytes: 3656
n = int(input())
members = input()
m_e = members.count("E")
cost = m_e
costs = []
for i in range(n):
    if members[i]=="E":
        cost-=1
    if (i!=0 and members[i-1]=="W"):
        cost+=1
    costs.append(cost)
print(min(costs))

Measured memory_bytes: 15516
#include <bits/stdc++.h>
using namespace std;
#define mod (int) (1e9+7)
int main() {
	// your code goes here
	int n;
	int i,j,k;
	
	cin>>n;
	int a[n][n];
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	cin>>a[i][j];
	
	int dp[1<<n];
	memset(dp,0,sizeof dp);
	dp[0]=1;
	
	
	for(i=0;i<1<<n;i++)
	{
	    k=__builtin_popcount(i);
	    for(j=0;j<n;j++)
	    {
	       // cout<<i<<" : "<<dp[i]<<" , ";
	        
	        if(!(i&(1<<j)) && a[j][k])
	        {
	            dp[i^(1<<j)]+=dp[i];
	            dp[i^(1<<j)]%=mod;
	        }
	        
	    }
	   // cout<<endl;
	}
	
	
	cout<<dp[(1<<n) -1];
	return 0;
}


Measured memory_bytes: 11736
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

S = list(ins())


def solve():
    n = len(S)
    k = n
    i = 0
    while i < n:
        if i + 1 < n and S[i] == S[i + 1]:
            k -= 1
            i += 3
        else:
            i += 1
    return k


print(solve())


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

int main() {
  vector<int> n(3);
  for(int i =0 ; i<3 ; i++){
    cin >> n.at(i);
  }
  sort(n.begin(), n.end());
  reverse(n.begin(), n.end());
  
  cout << n.at(0)*10 + n.at(1) + n.at(2) << endl;
}


Measured memory_bytes: 256
from itertools import permutations


def nearlist(N, LIST):  # 隣点リスト
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

ans, near = 0, nearlist(n, ab)
for l in permutations(range(1, n), n - 1):
    s = 0
    for i in l:
        t = i
        if t not in near[s]:
            break
        s = t
    else:
        ans += 1
print(ans)


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

PI a[100100];

int main() {
    li n;
    cin >> n;
    rin{
        cin >> a[i].F;
        a[i].S = i + 1;
    }
    sort(a, a + n);
    rin{
        cout << a[i].S << endl;
    }

    return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define mp make_pair
#define pb push_back
#define pf push_front
#define ss second
#define ff first
#define sz(x) (int)x.size()
#define newl "\n"
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define vl vector<ll>
#define pll pair<ll, ll>
#define vll vector<pll>
#define coutp cout << fixed << setprecision(12)
#define mem(x, val) memset(x, val, sizeof(x))
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define all(v) (v).begin(), (v).end()

const ld pi = 3.14159265359;
ll INF = 1e18 + 10;
ll MOD = 998244353;
ll mod = 1e9 + 7;

inline ll add(ll a, ll b, ll m)
{
    if ((a + b) >= m)
        return (a + b) % m;
    return a + b;
}

inline ll mul(ll a, ll b, ll m)
{
    if ((a * b) < m)
        return a * b;
    return (a * b) % m;
}

ll power(ll x, ll y, ll m)
{
    ll res = 1;
    x = x % m;
    if (x == 0)
        return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % m;
        y = y >> 1;
        x = (x * x) % m;
    }
    return res;
}

void solve()
{
    ll n;
    cin>>n;
    ll ans=0;
    ll x=n;
    for(ll i=2;i*i<=n;i++) {
        if(n%i) continue;
        ll cnt=0;
        while(n%i==0) {
            n/=i;
            cnt++;
        }
        ll res=1;
        for(ll j=1;j<=50;j++) {
            if((j*(j+1))/2<=cnt) res = j;
        }
        ans+=res;
    }
    if(n>1) ans++;
    cout<<ans;
}

int main()
{
    fastio;
    int t;
    
    t = 1;
    //cin >> t;
    //int test=t;
    while (t-- > 0)
    {
        //cout<<"Case #"<<(test-t)<<": ";
        solve();
        cout << newl;
    }

    return 0;
}

Measured memory_bytes: 3588
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			B();
		}

		public static void B()
		{
			Scanner cin = new Scanner();
			int a = cin.NextInt();
			int b = cin.NextInt();
			int c = cin.NextInt();
			int d = cin.NextInt();
			int e = cin.NextInt();

			int[] xx = new int[5];
			xx[0] = a % 10;
			xx[1] = b % 10;
			xx[2] = c % 10;
			xx[3] = d % 10;
			xx[4] = e % 10;

			int min = xx.Min();
			int max = xx.Max();

			int[] temp = xx.Where(x => x != 0).ToArray();
			if (temp.Length != 0) {
				int min2 = temp.Min();
				int k = Hoge(a) + Hoge(b) + Hoge(c) + Hoge(d) + Hoge(e);
				k = k - 10 + min2;
				Console.Write(k);
			} else {
				Console.Write(a + b + c + d + e);
			}
		}

		public static int Hoge(int a) {
			return a % 10 == 0
				? a
				: ((a / 10) + 1) * 10;
		}
	}

	public 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 NextInt()
		{
			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] = NextInt() + add;
			}
			return Array;
		}

		public long NextLong()
		{
			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] = NextLong() + add;
			}
			return Array;
		}

		public double NextDouble()
		{
			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] = NextDouble() + add;
			}
			return Array;
		}
	}
}


Measured memory_bytes: 13396
#![allow(unused_imports)]
use {
   proconio::{fastout, input, marker::*},
   std::cmp::*,
   std::collections::*,
};

#[fastout]
fn main() {
   input! {
      n:usize,
      k:usize,
      mut a:[usize; n]
   }
   let s: usize = a.iter().sum();
   let mut f = vec![];
   a.sort();
   for p in 1.. {
      if p * p >= s {
         if p * p == s {
            f.push(p);
         }
         break;
      }

      if s % p == 0 {
         f.push(p);
         f.push(s / p);
      }
   }

   f.sort_by(|a, b| b.cmp(a));
   for &d in f.iter() {
      let mut r = a.iter().map(|&x| x % d).collect::<Vec<_>>();
      r.sort();
      let mut x = vec![0; n + 1];
      let mut y = vec![0; n + 1];
      for i in 0..n {
         x[i + 1] = x[i] + r[i];
         y[i + 1] = y[i] + d - r[i];
      }
      let mut res = x[n];
      for i in 0..=n {
         res = min(res, max(x[i], y[n] - y[i]));
      }
      if res <= k {
         println!("{}", d);
         return;
      }
   }
}


Measured memory_bytes: 2172
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main() 
{
    string s,t;
    cin>>s>>t;
    s+=t[t.size()-1];
    if(s==t)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0; 
}

Measured memory_bytes: 3628
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
signed main(){
  init_io();
  ll x[5];
  ll ans=0;
  for(int i=0;i<5;i++){
    cin >> x[i];
    if(x[i]==0){
      ans=i+1;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3652
import java.util.Scanner;
public class Main {

	public static void main(String args []){
		Scanner scan = new Scanner(System.in);
			int i = scan.nextInt();
			int h = i / 3600;
			int m = (i / 60) % 60;
			int s = i % 60;
			System.out.print("" + h);
			System.out.print(":" + m);
			System.out.println(":"+ s);
			
	}
}

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


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

	int	n, q;
	cin >> n >> q;

	queue<pair<string, int>> P;
	rep(i, n)
	{
		string	s;
		int		n;
		cin >> s >> n;

		P.push(make_pair(s, n));
	}

	int	past_time;

	past_time = 0;
	while (!P.empty())
	{
		if (P.front().second <= q)
		{
			past_time += P.front().second;
			cout << P.front().first << ' ' << past_time << endl;
			P.pop();
		}
		else
		{
			pair<string, int>	p;

			P.front().second -= q;
			p = P.front();
			P.pop();
			P.push(p);
			past_time += q;
		}
	}
}



Measured memory_bytes: 6228
n = int(input())
a = [int(_) for _ in input().split()]
ans = []
a.append(0)
a.sort()

if a.index(0) == 0:
    x = a.pop(1)
    y = a.pop()
    tmp = x-y
    ans.append([x,y])
    a.append(tmp)
    a.sort()
elif a.index(0) == n:
    x = a.pop(-2)
    y = a.pop(0)
    tmp = x-y
    ans.append([x,y])
    a.append(tmp)
    a.sort()

a.remove(0)
if len(a) == 1:
    print(a[0])
    print(ans[0][0], ans[0][1])
else:
    maximum = a.pop()
    minimum = a.pop(0)
    while len(a) > 0:
        x = a.pop()
        if x > 0:
            ans.append([minimum, x])
            minimum -= x
        else:
            ans.append([maximum, x])
            maximum -= x

    m = maximum-minimum
    print(m)
    ans.append([maximum, minimum])
    for i in ans:
        print(i[0], i[1])

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

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

    //calc
    int i,bit;
    int test, sub;
    for(bit=0; bit<(1<<3); bit++){
        test=S[0]-'0';
        for(i=0;i<3;i++){
           if(bit&(1<<i)){
               test += S[i+1]-'0';
           }else{
               test -= S[i+1]-'0';
           }
        }
        if(test==7){
            break;
        }
    }

    //answer
    for(i=0;i<3;i++){
        cout << S[i]-'0';
        if(bit&(1<<i)){
            cout << '+';
        }else{
            cout << '-';
        }
    }
    cout << S[3] << "=7" << endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 504
import sys
x,n = map(int,input().split())
p = list(map(int,input().split()))

if p.count(x) == 0:
    print(x)
else:
    for i in range(1,110):
        if p.count(x-i) == 0:
            print(x-i)
            sys.exit()
        elif p.count(x+i) == 0:
            print(x+i)
            sys.exit()


Measured memory_bytes: 61924
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

void precalc() {
}

char s[20];

int read() {
  if (scanf("%s", s) < 1) {
    return 0;
  }
  return 1;
}

void solve() {
  char ch = 0;
  swap(s[4], ch);
  printf("%s ", s);
  swap(s[4], ch);
  printf("%s\n", s + 4);
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 256
N=int(input())#=map(int,input().split())
A=list(map(int,input().split()))
sum={}
for i in A:
    if i in sum.keys():
        sum[i]+=1
    else:
        sum[i]=1
for i in range(1,N+1):
    if  i in sum.keys():
        print(sum[i])
    else:
        print(0)

Measured memory_bytes: 33516
A,B,C,D = list(map(int, input().split()))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
l=C*D//gcd(C,D)
print(B+1-A -B//C+(A-1)//C -B//D+(A-1)//D +B//l-(A-1)//l )


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

const int MAXN = 55, C = 10000;
int n,m,s;
int dist[MAXN][4*MAXN*MAXN],c[MAXN],d[MAXN],dp[MAXN][4*MAXN*MAXN];
vector<pair<int,pi>> adj[MAXN];

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  
  cin >> n >> m >> s;
  for(int i=1;i<=m;i++){
    int u,v,a,b;
    cin >> u >> v >> a >> b;
    adj[u].pb({v,{a,b}});
    adj[v].pb({u,{a,b}});
  }
  for(int i=1;i<=n;i++){
    cin >> c[i] >> d[i];
    adj[i].pb({i,{-c[i],d[i]}});
  }
  for(int i=0;i<MAXN;i++){
    for(int j=0;j<MAXN*MAXN*4;j++){
      dp[i][j]=0;
      dist[i][j]=1e18;
    }
  }
  s = min(s,C);
  priority_queue<pair<int,pi>> q;
  q.push({0,{1,s}});
  dist[1][s]=0;
  while(!q.empty()){
    auto it = q.top();q.pop();
    int s = it.sc.fs;
    int money = it.sc.sc;
    // cerr << it << endl;
    if(dp[s][money])continue;
    dp[s][money]=1;
    for(auto t:adj[s]){
      int dest = t.fs;
      int cost = t.sc.fs;
      int dur = t.sc.sc;
      // cerr << t << endl;
      // cerr << dest << " " << cost << " " << dur << endl;
      if(money-cost>=0){
        int nt = dist[s][money]+dur;
        int nm = money-cost;
        nm = min(nm,C);
        if(dist[dest][nm]>nt){
          dist[dest][nm] = nt;
          q.push({-nt,{dest,nm}});
        }
      }
    }
  }
  for(int i=2;i<=n;i++){
    int ans = 1e18;
    for(int j=0;j<=C;j++){
      ans = min(ans,dist[i][j]);
    }
    cout << ans << endl;
  }

return 0;
}
///....


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

AB = AB[::-1]

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)

def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  #print(x, y)
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx == ry:
    return 0
  else:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
    return sx * sy

network = 0
answer = []
for a, b in AB:
  #print(a, b, root)
  answer.append(N * (N - 1) // 2 - network)
  network += merge(a, b)

answer = answer[::-1]
for a in answer:
  print(a)

Measured memory_bytes: 93016
fun main() {
    val MOD = 998244353L
    val (n, k) = readLine()!!.trim().split(' ').map(String::toInt)
    val ranges = List(k){
        val (left, right) = readLine()!!.trim().split(' ').map(String::toInt)
        left to right
    }
    val memo = LongArray(n + 1){0L}
    memo[1] = 1
    memo[2] = -1
    for (pos in 1 .. n) {
        memo[pos] = (memo[pos] + memo[pos - 1] + MOD) % MOD
        for ((left, right) in ranges) {
            if (pos + left in memo.indices) {
                memo[pos + left] += memo[pos]
            }
            if (pos + right + 1 in memo.indices) {
                memo[pos + right + 1] -= memo[pos]
            }
        }
    }
    println((memo.last() + MOD) % MOD)
}

Measured memory_bytes: 49232
#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main() {
	int N;

	cin >> N;

	for (int i = 8; i >= 0; i--) {
		if (N >= pow(2, i)) {
			cout << pow(2, i);
			break;
		}
	}
}


Measured memory_bytes: 256
x = list(input())

cnt_S = 0
cnt_T = 0

for i in range(len(x)):
    if x[i] == "S":
        cnt_S += 1
    
    elif x[i] == "T":
        if cnt_T < cnt_S:
            cnt_T += 1

print(len(x)-2*cnt_T)


Measured memory_bytes: 4840
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>

#define INFINITY 2000000000

using namespace std;

int main(){

	int V,E,from,to,dist;

	scanf("%d %d",&V,&E);
	long long int table[V][V];

	for(int i = 0; i < V; i++){
		for(int k = 0; k < V; k++){
			if(i != k){
				table[i][k] = INFINITY;
			}else{
				table[i][k] = 0;
			}
		}
	}

	for(int i = 0; i < E; i++){
		scanf("%d %d %d",&from,&to,&dist);
		table[from][to] = dist;
	}

	for(int k = 0; k < V; k++){
		for(int i = 0; i < V; i++){
			if(table[i][k] == INFINITY)continue;
			for(int j = 0; j < V; j++){
				if(table[k][j] == INFINITY)continue;
				table[i][j] = min(table[i][j],table[i][k]+table[k][j]);
			}
		}
	}

	bool FLG = true;

	for(int i = 0; i < V; i++){
		if(table[i][i] < 0){
			FLG = false;
			break;
		}
	}

	if(!FLG)printf("NEGATIVE CYCLE\n");
	else{
		for(int i = 0; i < V; i++){
			if(table[i][0] == INFINITY)printf("INF");
			else{
				printf("%lld",table[i][0]);
			}

			for(int k = 1;k < V; k++){
				if(table[i][k] == INFINITY)printf(" INF");
				else{
					printf(" %lld",table[i][k]);
				}
			}
			printf("\n");
		}
	}

    return 0;
}



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

int main() {
    int N,M,sum=0;
    cin>>N;M=N;
    while(N!=0){sum+=N%10;N/=10;}
    if(M%sum==0){cout <<"Yes"<<endl;}
    else{cout <<"No"<<endl;}}


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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

#define MAX 100010
int N,M,X[MAX],used_counter[MAX], mod_counter[MAX];
set<int> freq_set[MAX];

// TODO :: 1 のときバグらないかチェック
void compute() {
  map<int,int> freq;

  rep(i,N) {
    ++mod_counter[X[i]%M];
    freq_set[X[i]%M].insert(X[i]);
    ++freq[X[i]];
  }
  map<int,bool> is_odd;
  rep(i,N) {
    if( freq[X[i]] % 2 == 1 ) is_odd[X[i]] = true;
    else                      is_odd[X[i]] = false;
  }

  int answer = 0;
  rep(i,(int)(M/2)+1) {
    if( i == 0 ) {
      int use = (int)(mod_counter[i]/2);
      answer += use;
      used_counter[i] += use;
      continue;
    }
    int half = M - i;
    if( half == i ) {
      int use = (int)(mod_counter[i]/2);
      used_counter[half] += ( use * 2 );
      answer             += use;
      // cout << half << " :MID: use = " << use <<  "| answer = " << answer<< endl;
    } else {
      int use = min(mod_counter[half],mod_counter[i]);
      used_counter[half] += use;
      used_counter[i]    += use;
      answer             += use;
      /*
      cout << "mod_counter[" << half << "] = " << mod_counter[half] << endl;
      cout << "mod_counter[" << i << "] = " << mod_counter[i] << endl;
      cout << half << " :half: use = " << use << endl;
      cout << i    << " :i   : use = " << use << " | answer = " << answer<< endl;
      */
    }
    //puts("");
  }
  //cout << "中間発表 :: " << answer << endl;
  REP(i,1,M) {
    int remain = used_counter[i];
    for(set<int>::iterator it=freq_set[i].begin();it!=freq_set[i].end();++it) {
      if( remain <= 0 ) break;
      int v = *it;
      if( is_odd[v] ) {
	--remain;
	--freq[v];
	assert( freq[v] >= 0 );
      }
    }  
    for(set<int>::iterator it=freq_set[i].begin();it!=freq_set[i].end();++it) {
      int v = *it;
      int cnt = freq[v];
      if( remain ) {
	assert( cnt % 2 == 0 );
	int sub = min(remain,cnt);
	cnt    -= sub;
	remain -= sub;
      }
      assert( cnt >= 0 );
      answer += (int)(cnt/2);
    }
    assert(remain == 0);
  }
  cout << answer << endl;
}

int bf() {
  vector<int> vec;
  rep(i,N) vec.push_back(X[i]);
  sort(vec.begin(),vec.end());
  int maxi = 0;
  do {
    int cnt = 0;
    for(int i=0;i<N;i+=2) {
      if( i+1 <(int)N && ( (vec[i]+vec[i+1]) % M == 0 || vec[i] == vec[i+1] ) ) {
	++cnt;
      }
    }
    /*
    rep(i,N) {
      cout << vec[i] << ",";
    } puts("");
    */
    maxi = max(maxi,cnt);
  } while( next_permutation(vec.begin(),vec.end()) );
  return maxi;
}

int main(){
  srand((unsigned int)time(NULL));
  /*
  N = 8;
  cout << N << " " << ( M = 4 ) << endl;
  rep(i,N) {
    if( i ) cout << " ";
    cout << rand() % 10 +1;
  } puts(""); return 0;
  */
  
  cin >> N >> M;
  rep(i,N) cin >> X[i];
  //cout << "Answer = " << bf() << endl;
  compute();

  return 0;
}


Measured memory_bytes: 20224
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int m1 = sc.nextInt();
		int d1 = sc.nextInt();
		int m2 = sc.nextInt();
		int d2 = sc.nextInt();
		sc.close();
		if (m1 == m2){
			System.out.println(0);
		} else {
			System.out.println(1);
		}
	}
}

Measured memory_bytes: 23252
#include <iostream>
#define rep(i,n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;

int main() {
    int n, x;
    while (1) {
        cin >> n >> x;
        if (n == 0) return 0;
        int count = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                for (int k = j + 1; k <= n; k++) {
                    if (i + j + k == x) count += 1;
                }
            }
        }
        cout << count << endl;
    }
}


Measured memory_bytes: 3096
#include <cstdio>
#include <iostream>
#include <string.h> //for strlen
using namespace std;

int main(){
	int N, T;
	cin >> N >> T;
	int temp[10000000];
	int total = 0;
	for(int i = 0; i < N; i++){
		
		cin >> temp[i];
		if(i == 0) continue;
		if( temp[i] - temp[i-1] - T > 0 ) total = total + T;
		else total = total + temp[i] - temp[i-1];
	}

	cout << total + T << endl;
}

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

using namespace std;

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

    int keta = N % 10;
    string tani = "";
    if(keta == 0 || keta == 1 || keta == 6 || keta == 8){
        tani = "pon";
    } else if(keta == 3){
        tani = "bon";
    } else {
        tani = "hon";
    }

    cout << tani << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll         = long long;
constexpr ll MOD = 1000000007;
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REP2(i, x, n) for (ll i = x; i < (n); i++)
#define PR(x) cout << (x) << "\n"
#define PS(x) cout << (x) << " "
const long long INF = numeric_limits<long long>::max();
int main() {
    ll D, T, S;
    cin >> D >> T >> S;
    ll d = T * S;
    PR((d >= D) ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>

int main() {
    int n, x, ans, mxr, mxl;
    while (1) {
        scanf("%d %d", &n, &x);
        if (n == 0 && x == 0) break;
        ans = 0;
        for (int i = 1; i <= n; i++) {
            mxr = i - 1, mxl = x - i - mxr;
            if (mxl < 1) mxr += mxl - 1, mxl = 1;
            if (mxl >= mxr) continue;
            ans += (mxr - mxl + 1) / 2;
        }
        printf("%d\n", ans);
    }
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>

//Some constants don't work
#ifndef INT_MAX
#define INT_MAX 2147483647
#endif
#ifndef INT_MIN
#define INT_MIN -2147483648
#endif
//short hand tricks
typedef long long ll;

using namespace std;

int main(int argc, char * argv[]) {
    ios_base::sync_with_stdio(false);
    ll N;
    cin>>N;
    vector<ll> v(N+1, 0);
    for(int i=1; i<=N; i++) {
        cin >> v[i];
    }
    //dp
    //keep track of the maximum money possible upto day i
    //N is small so can do O(N^2)
    //don't even need dp because greedy answer
    vector<ll> maxnet(N+1, 0);//max net
    maxnet[0] = 1000;
    for(int day=1; day<=N; day++) {
        ll mn = 1000;//can always make no trades upto this point
        for(int purch=1; purch<day; purch++) {
            //see how many stocks can be bought at that day
            ll stocks = maxnet[purch]/v[purch];
            ll left = maxnet[purch]-(stocks*v[purch]);
            //sell at current price
            ll tradenet = left+(stocks*v[day]);
            mn = max({mn, tradenet, maxnet[purch]});
        }
        maxnet[day] = mn;
    }
    cout << maxnet[N] << "\n";
    
    return 0;
}


Measured memory_bytes: 3656
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;
 
int main(void){
  lint A,B,C,K;
  cin >> A >> B >> C >> K;
  if(K%2==0) cout << A-B << endl;
  else cout << B-A << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
typedef signed long long ll;
ul over = 1000000007;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  int a, b;
  cin >> a >> b;
  if (a+b==15) cout << "+" << endl;
  else if (a*b==15) cout << "*" << endl;
  else cout << "x" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
  #include <complex>
  #include <vector>
  #include <string>
  #include <algorithm>
  #include <cstdio>
  #include <numeric>
  #include <cstring>
  #include <ctime>
  #include <cstdlib>
  #include <set>
  #include <map>
  #include <unordered_map>
  #include <unordered_set>
  #include <list>
  #include <cmath>
  #include <bitset>
  #include <cassert>
  #include <queue>
  #include <stack>
  #include <deque>
 #include <iomanip>
#include <fstream>
#include <climits>
 
  using namespace std;
   
 
//abcdefghijklmnopqrstuvwxyz
//ABCDEFGHIJKLMNOPQRSTUVWXYZ

  typedef long long ll;
  typedef long double lld;
  typedef unsigned long long ull;
  // int INF = INT_MAX;
  ll mod = 1000000007;
  // lld PI = 3.141592653;



  int main()
  {
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
     int n;
     cin>>n;
     vector<pair<int,int>> a(n);
     for (int i = 0;i<n;i++){
      cin>>a[i].first>>a[i].second;
     }
     vector<int> b(n), c(n);
     for (int i = 0;i<n;i++){
      b[i] = a[i].first + a[i].second;
      c[i] = a[i].first - a[i].second;
     }
     sort(b.begin(), b.end());
     sort(c.begin(), c.end());
     cout<<max(b[n-1]-b[0], c[n-1]-c[0])<<"\n";


}

Measured memory_bytes: 6024
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
bool prime[MAX];
int prime_numbers[9999999],pos;
void sieve()
{
    prime[0]=1;
    prime[1]=1;
    for(int i=4; i<=MAX; i+=2)
        prime[i]=1;
    int root = sqrt(MAX);
    for(int i=3; i<=root; i+=2)
    {
        if(prime[i]==0)
        {
            for(int j=i*i; j<=MAX; j+=i)
            {
                prime[j]=1;
            }
        }
    }
    prime_numbers[pos++]=2;
    for(int i=3; i<MAX; i+=2)
        if(prime[i]==0)
            prime_numbers[pos++]=i;
}
map<int,int>mp;
void recur(int pos,int sum,int taken,vector<int>v)
{
    if(pos>=20)
        return;
    if(taken==5)
    {
        if(sum==67)
        {
           for(int i=0;i<5;i++)
            cout<<v[i]<<" ";
           cout<<endl;
        }

        mp[sum]++;
        return ;
    }
    v.push_back(prime_numbers[pos]);
    recur(pos+1,sum+prime_numbers[pos],taken+1,v);
    v.pop_back();
    recur(pos+1,sum,taken,v);
}
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    sieve();
 //   for(int i=0; prime_numbers[i]<55555; i++)
    //    cout<<prime_numbers[i]<<" "<<mp[prime_numbers[i]]<<endl;
    int n;
    cin>>n;
    for(int i=0;i<pos;i++){
        if(prime_numbers[i]%10==7){
            cout<<prime_numbers[i]<<" ";
         n--;
        }
        if(n==0)
            break;
    }




    return 0;
}


Measured memory_bytes: 4832
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = sum(a)

for i in range(n) :
    ai = a[i]
    a[i] = max(0, ai-b[i])
    a[i+1] = max(0, a[i+1]-max(0, b[i]-ai))

print(s-sum(a))

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

int main(){
	long n, q, C = 0;
	cin >> n;
	vector<long> S(n + 1, 0);
	for (long i = 0; i < n; i++) cin >> S[i];
	cin >> q;
	vector<long> T(q, 0);
	for (long i = 0; i < q; i++) cin >> T[i];
	for (long i = 0; i < q; i++){
		long a = 0, b = n;
		while (a < b){
			if (S[(a + b) / 2] > T[i]){
				b = (a + b) / 2;
			}
			else if (S[(a + b) / 2] == T[i]){
				C++;
				break;
			}
			else {
				a = (a + b) / 2 + 1;
			}
		}
	}
	cout << C << endl;
	return 0;
}

Measured memory_bytes: 2324
#include<bits/stdc++.h>
using namespace std;
int main(){
  int d;cin>>d;
  string s;
  if(d==25)s="Christmas";
  if(d==24)s="Christmas Eve";
  if(d==23)s="Christmas Eve Eve";
  if(d==22)s="Christmas Eve Eve Eve";
  cout<<s;
}

Measured memory_bytes: 764
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define rep(i,n) for(register int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int dx[]={0,1,-1,0},dy[]={1,0,0,-1};
//const int MOD=998244353;
//const int N=2e5+10;

inline int read(){
	int ww=1,xx=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') ww=-ww;ch=getchar();}
	while(isdigit(ch)){xx=(xx<<1)+(xx<<3)+(ch^48);ch=getchar();}
	return ww*xx;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int a=read();
	string str;
	cin>>str; 
	if(a<3200) puts("red");
	else cout<<str<<endl;
	return 0;
}


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

using namespace std;

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define INF 1<<25
#define pb push_back
#define anD &&
#define oR ||

typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef long long ll;

int main() {
	int W, H, x, y, r;
	cin >> W >> H >> x >> y >> r;

	if (r <= x anD x <= W - r anD r <= y anD y <= H - r)cout << "Yes" << endl;
	else cout << "No" << endl;

}

Measured memory_bytes: 1160
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A, B):
    T = [[0] * W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if j < A and i < B:
                T[i][j] = 0
            elif j < A:
                T[i][j] = 1
            elif j >= A and i < B:
                T[i][j] = 1
            else:
                T[i][j] = 0
    for r in T:
        print(''.join(map(str, r)))


def main():
    H, W, A, B = read_int_n()
    (slv(H, W, A, B))


if __name__ == '__main__':
    main()


Measured memory_bytes: 14288
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;

int n;

inline void failed(){
	puts("-1");
	exit(0);
}

vector<int> G[N];
bool vis[N];
int match[N];
int pref[N];
stack<int> stk;

inline bool dfs(int x){
	for(size_t i=0;i<G[x].size();i++){
		int v=G[x][i];if(vis[v])continue;
		vis[v]=1;stk.push(v);
		if(!pref[v] || dfs(pref[v])){
			match[x] = v;
			pref[v] = x;
			return 1;
		}
	}
	return 0;
}

int s[N];
typedef pair<int,int> pi;
vector<pi> tr;
int main()
{
	cin >> n;
	for(int i=1;i<n;i++){
		int c;scanf("%d",&c);
		for(int j=1,e;j<=c;j++){
			scanf("%d",&e);
			G[e].push_back(i);
		}
	}
	for(int i=2;i<=n;i++){
		// cout << i << ":";
		if(!dfs(i))failed();
		while(stk.size()){
			// cout << stk.top();
			vis[stk.top()]=0;
			stk.pop();
		}
		// cout << "?" << endl;
	}
	queue<int> q;
	for(size_t i=0;i<G[1].size();i++){
		s[G[1][i]]=1;
		q.push(G[1][i]);
	}
	tr.resize(n);
	int ss=0;
	while(q.size()){
		++ss;
		int u=q.front();q.pop();
		int v = pref[u];
		// cout << u << ":::" << s[u] << " " << v << endl;
		tr[u] = pi(v,s[u]);
		for(size_t i=0;i<G[v].size();i++){
			if(!s[G[v][i]])s[G[v][i]]=v,q.push(G[v][i]);
		}
	}
	if(ss<n-1){
		failed();
	}
	for(size_t i=1;i<tr.size();i++){
		printf("%d %d\n",tr[i].first,tr[i].second);
	}
	return 0;
}
/* 
10
5 1 2 3 4 5
5 2 3 4 5 6
5 3 4 5 6 7
5 4 5 6 7 8
5 5 6 7 8 9
5 6 7 8 9 10
5 7 8 9 10 1
5 8 9 10 1 2
5 9 10 1 2 3
 */

Measured memory_bytes: 9592
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
# define ld  long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
#define pll pair<ll, ll>
# define mp make_pair
# define ac accumulate
# define mod 1000000007
#define um unordered_map
# define pii pair<ll,ll>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
vector<ll> initializeDiffArray(vector<ll>& A) 
{ 
    ll n = A.size(); 
    vector<ll> D(n + 1); 
  
    D[0] = A[0], D[n] = 0; 
    for (ll i = 1; i < n; i++) 
        D[i] = A[i] - A[i - 1]; 
    return D; 
}  
void update(vector<ll>& D, ll l, ll r, ll x) 
{ 
    D[l] += x; 
    D[r + 1] -= x; 
} 
int  main()
{
	ll n,m;
	cin>>n>>m;
	vector<ll>bha;
	ll k=0;
	for(ll i=0;i<n;i++)
		bha.pb(k);
	vector<ll> ail = initializeDiffArray(bha); 
  ll r=m;
	while(m--)
	{
		ll x,y,z=1;
		cin>>x>>y;
		x--;y--;
		update(ail,x,y,z);
	}
	ll cnt=0;
	for (ll i = 0; i < bha.size(); i++) 
	{ 
		if (i == 0) 
		    bha[i] = ail[i];  
		else
		    bha[i] = ail[i] + bha[i - 1]; 
	 // cout<<bha[i]<<" "<<m<<endl;
		if(bha[i]==r)
			cnt++;
        } 
  	cout<<cnt;
  
}
	

Measured memory_bytes: 1908
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
//	freopen("data.in","r",stdin);
//	freopen("lfr.out","w",stdout);
	string t;int n[5];cin>>t;
	for(int i=1;i<=4;i++)n[i]=t[i-1]-'0';
	if(n[1]+n[2]+n[3]+n[4]==7)printf("%d+%d+%d+%d=7",n[1],n[2],n[3],n[4]);
	else if(n[1]+n[2]+n[3]-n[4]==7)printf("%d+%d+%d-%d=7",n[1],n[2],n[3],n[4]);
	else if(n[1]+n[2]-n[3]+n[4]==7)printf("%d+%d-%d+%d=7",n[1],n[2],n[3],n[4]);
	else if(n[1]-n[2]+n[3]+n[4]==7)printf("%d-%d+%d+%d=7",n[1],n[2],n[3],n[4]);
	else if(n[1]+n[2]-n[3]-n[4]==7)printf("%d+%d-%d-%d=7",n[1],n[2],n[3],n[4]);
	else if(n[1]-n[2]-n[3]+n[4]==7)printf("%d-%d-%d+%d=7",n[1],n[2],n[3],n[4]);
	else if(n[1]-n[2]-n[3]-n[4]==7)printf("%d-%d-%d-%d=7",n[1],n[2],n[3],n[4]);
	else if(n[1]-n[2]+n[3]-n[4]==7)printf("%d-%d+%d-%d=7",n[1],n[2],n[3],n[4]);
	return 0;
}


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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

char a,b,c,d;
int w[4];

int main(){
	cin >> a >> b >> c >> d;
	w[0] = a - '0';
	w[1] = b - '0';
	w[2] = c - '0';
	w[3] = d - '0';
	repp(i,0,8){
		int p = w[0];
		repp(k,0,3){
			p += w[k+1] * (i&(1<<k)?1:-1);
		}
		if(p==7){
			repp(k,0,3) cout << w[k] << (i&(1<<k)?'+':'-');
			cout << w[3] << "=7" << endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define pii pair<int,int>
#define f first
#define se second
using namespace std;
double pi=acos(-1.0);
int m=1000000007;
bool cmp2(int n,pii p)
 {return n<p.f;}
int abst(int a)
{return a<0?-a:a;}
struct HASH{
  size_t operator()(const pii &x)const{
    return (size_t) x.first * 37U + (size_t) x.second;}};
int Pow(int n,int x){int ans=1;
 while(x>0)
 {if(x&1)ans=(ans*n)%m;n=(n*n)%m;x=x>>1;}
 return ans;}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int a,b;
cin>>a>>b;
int x=__gcd(a,b);
cout<<(a*b)/x;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
  
int Merge(int A[],int left,int mid,int right){
  int n1=mid-left;
  int n2=right-mid;
  int i,j,k;
  int L[n1+1],R[n2+1];
    
  for(i=0;i<n1;i++)L[i]=A[left+i];
  for(i=0;i<n2;i++)R[i]=A[mid+i];
  L[n1]=1000000000;
  R[n2]=1000000000;
    
  i=j=0;
  for(k=left;k<right;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    }else{
      A[k]=R[j];
      j++;
    }
  }
  return right-left;
}
  
int Merge_Sort(int A[],int left,int right){
  int mid,res=0;
  if(left+1<right){
    mid=(left+right)/2;
  
    res+=Merge_Sort(A,left,mid);
    res+=Merge_Sort(A,mid,right);
    res+=Merge(A,left,mid,right);
      
  }
  return res;
}
  
int main(){
  int i,x,n,S[500000]; 
  cin>>n;

  int cnt=0;
  
  for(i=0;i<n;i++){
    cin>>S[i];
    assert(S[i]!=1e9);
  }
  
  x=Merge_Sort(S,0,n);
    
  for(i=0;i<n;i++){
    if(i)cout<<" ";
    cout<<S[i];
  }
  cout<<endl;
  cout<<x<<endl;
  return 0;
}

Measured memory_bytes: 6968
#include<stdio.h>
  
 
typedef struct Card{
  char mark;
  int num;
  int index;
}Card;
  
int Partition( Card A[], int p, int r ){
  int x;
  int i,j;
  Card c;
  x = A[r].num;
  i = p - 1;
  for( j = p; j < r; j++ ){
    if( A[j].num <= x){
      i++;
      c = A[i];
      A[i] = A[j];
      A[j] = c;
    }
  }
  c = A[i+1];
  A[i+1] = A[r];
  A[r] = c;
  
  return i+1;
}
  
void QuickSort( Card A[], int p, int r ){
  int q;
  if( p < r ){
    q = Partition( A, p, r );
    QuickSort( A, p, q-1 );
    QuickSort( A, q+1, r );
  }
}
  
int isStable( Card A[], int n ){
  int i;
  for( i = 1; i < n; i++ ){
    if( A[i-1].num == A[i].num ){
      if( A[i-1].index > A[i].index ){
    return 0;
      }
    }
  }
  return 1;
}
  
int main(){
  int n, i;
  Card A[100000];
  
  scanf("%d", &n);
  for( i = 0; i < n; i++ ){
    scanf(" %c %d", &A[i].mark, &A[i].num);
    A[i].index = i;
  }
  
  QuickSort( A, 0, n-1 );
  
  if( isStable(A, n) == 1 ){
    printf("Stable\n");
  }
  else{
    printf("Not stable\n");
  }
  
  for( i = 0; i < n; i++ ){
    printf("%c %d\n", A[i].mark, A[i].num);
  }
  return 0;
}

Measured memory_bytes: 1776