akhauriyash/Code-Regression huggingface dataset:
//This is getting accepted!
// I HATE BUG
// God Of The Bugs
// 12/11/2016
#include<bits/stdc++.h>

using namespace std;

#define ms(s, n) memset(s, n, sizeof(s))
#define FI first
#define SE second
#define pb push_back
#define mp make_pair
#define ll long long
#define sz(a) ((int)(a).size())
#define __builtin_popcount __builtin_popcounll
#define ld long double

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> ppi;

const double PI = acos(0) * 2;
const double EPS = 1e-8;
const ll MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int oo = 1e9;
const double foo = 1e30;

template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcounll(s);}
template<class T> T sqr(T x) { return x * x; }

inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}

vector<int> adj[MAXN];
int vs[MAXN], G, n, m, check;
ll has[2];
ll edge;
int co[MAXN];

void dfs(int u, int col) {
	has[col]++;
	vs[u] = G;
	co[u] = col;
	for (int i=0; i<sz(adj[u]); i++) {
		int v = adj[u][i];
		edge++;
		if (vs[v]) {
			if (vs[v] == G && co[v] != col ^ 1) {
				check = 1;
			}
			continue;
		}
		dfs(v, col ^ 1);
	}
}

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

	cin >> n >> m;
	
	for (int i=0; i<m; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	
	ll ans = 0;
	for (int i=0; i<n; i++) {
		if (!vs[i]) {
			check = 0;
			edge = 0;
			G++;
			has[0] = has[1] = 0;
			dfs(i, 0);
//			cout << has[0] << " " << has[1] << " " << check << " " << edge << endl;
			if (!check) ans += has[0] * has[1] - edge / 2;
			else ans += (has[0] + has[1]) * (has[0] + has[1] - 1) / 2ll - edge / 2;
		}
	}
	
	cout << ans;

	return 0;
}


Measured memory_bytes: 7680
/* imports all std modules {{{*/
import
  std.algorithm,
  std.array,
  std.ascii,
  std.base64,
  std.bigint,
  std.bitmanip,
  std.compiler,
  std.complex,
  std.concurrency,
  std.container,
  std.conv,
  std.csv,
  std.datetime,
  std.demangle,
  std.encoding,
  std.exception,
  std.file,
  std.format,
  std.functional,
  std.getopt,
  std.json,
  std.math,
  std.mathspecial,
  std.meta,
  std.mmfile,
  std.net.curl,
  std.net.isemail,
  std.numeric,
  std.parallelism,
  std.path,
  std.process,
  std.random,
  std.range,
  std.regex,
  std.signals,
  std.socket,
  std.stdint,
  std.stdio,
  std.string,
  std.system,
  std.traits,
  std.typecons,
  std.uni,
  std.uri,
  std.utf,
  std.uuid,
  std.variant,
  std.zip,
  std.zlib;
/*}}}*/
/* libnum {{{*/
void amax(N, Args...)(ref N x, Args y) {
  x = x.max(y);
}
void amin(N, Args...)(ref N x, Args y) {
  x = x.min(y);
}
auto maxE(R)(R r) if (isInputRange!R) {
  ElementType!R x = r.front;
  r.popFront();
  foreach (y; r) x.amax(y);
  return x;
}
auto minE(R)(R r) if (isInputRange!R) {
  ElementType!R x = r.front;
  r.popFront();
  foreach (y; r) x.amin(y);
  return x;
}
/*}}}*/

/+---test
3 14
---+/
/+---test
10 123
---+/
/+---test
100000 1000000000
---+/

void main(string[] args) {
  long N, M;
  readf(" %d %d ", &N, &M);

  long ans;
  for (long i = 1; i*i <= M; ++i) {
    if (M%i) continue;
    if (i   <= M/N) ans.amax(i);
    if (M/i <= M/N) ans.amax(M/i);
  }
  ans.writeln;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;


int main(){
  double x[3],y[3];
  repeat(i,3){
    cin >> x[i] >> y[i];
  }
  double vx[3],vy[3];
  repeat(i,3){
    vx[i] = x[(i+2)%3]-x[(i+1)%3];
    vy[i] = y[(i+2)%3]-y[(i+1)%3];
  }
  double edge[3];
  repeat(i,3){
    edge[i] = sqrt(vx[i]*vx[i]+vy[i]*vy[i]);
  }
  debugArray(edge,3);
  double maxedge=max({edge[0],edge[1],edge[2]});
  debug(maxedge);
  double dis[3];
  repeat(i,3){
    double d = vy[i]*vx[(i+1)%3]-vx[i]*vy[(i+1)%3];
    dis[i] = sqrt(d*d)/edge[i];
  }
  debugArray(dis,3);
  double low=0,high=dis[0];
  while(high-low>1e-9){
    double mid = (low+high)/2;
    double ratio=1;
    bool isok=true;
    repeat(i,3){
      ratio *= 1-(mid/(ratio*dis[i]));
      if(ratio<=0){
        isok=false;
        break;
      }
    }
    if(isok){
      isok &= ratio*maxedge>=2*mid;
    }
    if(isok){
      low=mid;
    }else{
      high=mid;
    }
  }
  printf("%.9lf",low);
}


Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    set<int> st;
    rep(i, 3) {
        int a;
        cin >> a;
        st.insert(a);
    }
    cout << st.size() << endl;
}


Measured memory_bytes: 3628
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
s = set()
for i in range(1, 10):
    for j in range(1, 10):
        s.add(i*j)
if N in s:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 61972
import itertools
import math
n = int(input())
town = []
for _ in range(n):
    l = list(map(int,input().split()))
    town.append(l)

l = []
for i in range(n):
    l.append(i)

def calc (a,b,c,d):
    return math.sqrt(((a-b)**2)+((c-d)**2))

total = 0
for v in itertools.permutations(l):
    for i in range(len(v)):
        if i == n-1:
            pass
        else:
            total += calc(town[v[i]][0],town[v[i+1]][0],town[v[i]][1],town[v[i+1]][1])

print (total/math.factorial(n))


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

#define pb push_back
#define fi first
#define se second
#define eb emplace_back

using namespace std;

typedef pair<int, int> ii;
typedef long long ll;
const int N = 1000007, inf = 0x3f3f3f3f;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll a, b, c;
	scanf("%lld %lld.%lld", &a, &b, &c);
	printf("%lld\n", a * b + a * c/100);
}

Measured memory_bytes: 3840
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
#endif

#ifdef _DEBUG
void init_global_A() {}
#else

#endif

int main_A() {
    cin.tie(0);
    ios::sync_with_stdio(false);
     
    string C1, C2; cin >> C1 >> C2;

    reverse(C2.begin(), C2.end());

    string ans = C1==C2 ? "YES" : "NO";
    cout << ans << endl;

    return 0;
}

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

int main() {
	int N;
	cin >> N;
	int A,B;
	cin >> A >> B;
	
	int max = min(A,B);
	
	int min = (A+B) - N;
	if (min < 0) min = 0;
	cout << max << " " << min;
}


Measured memory_bytes: 256
cnds = [int(i) for i in input().split()]

posX = [int(i) for i in input().split()]
posY = [int(i) for i in input().split()]
posX.sort()
posY.sort()

max_x = posX[-1]
min_y = posY[0]
if cnds[2] < cnds[3]:
    if max_x < min_y and cnds[2] < min_y and max_x < cnds[3]:
        print('No War')
    else:
        print('War')
else:
    print('War')





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

int main() {
    int n, count;
    cin >> n;
    if(n % 2 == 1) n += 1;
    n = n / 2 - 1;
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <limits>
#include <vector>
#define ll long long int
#define rep(i,n) for(int i = 0;i < n;i++)
#define pb push_back
#define mp make_pair

using namespace std;

int main(){
    ll n;
    ll MOD = 1e9 + 7;
    cin >> n;
    vector<ll> m(n+1,0);

    ll ans = 1;

    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    else
    {
        ll tmp;
       for(int i = 2;i < n + 1;i++){
           tmp = i;
           for(int j = 2;j < i + 1;j++){
               if(j >= tmp){
                   if(tmp != 1){
                       m[tmp]++;
                   }
                   break;
               }
               else if(tmp%j == 0){
                   m[j]++;
                   tmp /= j;
                   j = 1;
               }
           }
       }

       for(int i = 0;i < n + 1;i++){
           //cout << m[i] << endl;
            if(m[i] != 0){
                ans *= (m[i] + 1);
                if(ans > MOD){
                    ans = ans%MOD;
                }
            }
       }
    }

    cout << ans%MOD << endl;

    return 0;
}

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

#define EMPTY 0
#define FULL 1
#define DELETED 2
 
#define INF 1000000000
 
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

typedef struct {
	long key;
	int flag;
} Data;

long H, W, N;
long a[100001];
long b[100001];
Data map[3234570] = {0};
int state_map[3234570] = {0};
Data taboo[3234570];
int state_taboo[3234570] = {0};
long ans[10] = {0};
int dx[] = {-1, 0, 1};
int dy[] = {-1, 0, 1};


long hash(long key, long count) {
	return (key + count) % 3234567;
}

void insert_map(long key) {
	int i, k;
	
	i = 0;
	k = hash(key, i++);
	while(state_map[k] == FULL) {
		k = hash(key, i++);
	}
	
	map[k].key = key;
	map[k].flag = 1;
	state_map[k] = FULL;
}

int search_map(long key) {
	int i, k;
	
	i = 0;
	k = hash(key, i++);
	while(state_map[k] != EMPTY) {
		if(state_map[k] == FULL && map[k].key == key) {
			return map[k].flag;
		}
		k = hash(key, i++);
	}
	
	return 0;
}

void insert_taboo(long key) {
	int i, k;
	
	i = 0;
	k = hash(key, i++);
	while(state_taboo[k] == FULL) {
		k = hash(key, i++);
	}
	
	taboo[k].key = key;
	taboo[k].flag = 1;
	state_taboo[k] = FULL;
}

long search_taboo(long key) {
	int i, k;
	
	i = 0;
	k = hash(key, i++);
	while(state_taboo[k] != EMPTY) {
		if(state_taboo[k] == FULL && taboo[k].key == key) {
			return taboo[k].flag;
		}
		k = hash(key, i++);
	}
	
	return 0;
}

int main() {
	int i, j, k, x, y, xx, yy, ii, jj;
	int count;
	long sum;
	
	scanf("%ld %ld %ld", &H, &W, &N);
	for(i=0;i<N;i++) {
		scanf("%ld %ld", &a[i], &b[i]);
		insert_map(a[i] * W + b[i]);
	}
	
	for(k=0;k<N;k++) {
		yy = a[k];
		xx = b[k];
		for(i=0;i<3;i++) {
			for(j=0;j<3;j++) {
				y = yy + dy[i];
				x = xx + dx[j];
				
				if(search_taboo(y * W + x)) continue;
				if(y <= 1 || y >= H || x <= 1 || x >= W) continue;
			
				insert_taboo(y * W + x);
				count = 0;
				for(ii=0;ii<3;ii++) {
					for(jj=0;jj<3;jj++) {
						if(search_map((y+dy[ii]) * W + (x+dx[jj]))) {
							count++;
						}
					}
				}
				ans[count]++;
			}
		}
	}

	sum = 0;
	for(i=1;i<=9;i++) {
		sum += ans[i];
	}
	
	ans[0] = (H * W) - (2 * H + 2 * W) + 4 - sum;

	for(i=0;i<=9;i++) {
		printf("%ld\n", ans[i]);
	}
	
	return 0;
}

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

using namespace std ;
typedef long long ll;
typedef string str;
typedef pair<int, int> pii;
typedef vector<int> vint;
typedef vector<double> vdou ;
typedef vector<ll> vll;
typedef vector<vint> vvint;
typedef vector<str> vstr;
typedef pair<ll,ll> pll ;
typedef vector<pii> vpii ;
typedef vector<pll> vpll ;

#define REP(i, n) for (ll (i) = 0; (i) < (ll)(n); i++) 
#define FOR(i, a, b) for(ll (i) = a; (i) < (ll)b; i++)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define CHI 1000000000000000003
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define NP next_permutation
#define SZ(x)  (ll)x.size()
#define SP(x)  setprecision((ll)x)

const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const double PI = M_PI;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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;} //最小公倍数

void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}
//-----------------------------------------




















//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n ;
  cin >> n ;
  vint num(n) ;
  REP(i,n){
    cin >> num[i] ;
  }
  stack<int> S ;
  
  REP(i,n){
    int m = SZ(num) ;
    for(int j=m-1;j>=0;j--){
      if(num[j]==j+1){
        S.push(num[j]) ;
        num.erase(num.begin() + j) ;
        break ;
      }
    }
  }
  
  if(SZ(S)!=n){
    cout << -1 <<endl ;
  }
  else{
    REP(i,n){
      int x = S.top() ;
      cout << x <<endl;
      S.pop() ;
    }
  }
    
  
  
  
  return 0 ;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (n);i++)
using ll = long long;
const ll MOD=1000000007;





int main() 
{
  ll N; cin>>N;
  vector<ll> h(N);
  ll maxh=0;
  rep(i,N)
  {
    cin>>h.at(i);
    maxh=max(maxh,h.at(i));
  }
  /*rep(i,N)
  {
    if(i!=0) {cout<<" ";}
    cout<<h.at(i);
    if(i==N-1) {cout<<endl;}
  }*/
  ll count=0;
  for(ll i=0;maxh>0;i++)
  {
    rep(j,N)
    {
      if(j==N-1&&h.at(N-1)>0) {count++; h.at(N-1)--; /*cout<<h.at(j)<<" "<<count<<endl;*/ continue;}
      if(h.at(j)>0&&h.at(j+1)==0) {count++;}  
      if(h.at(j)>0) {h.at(j)--;}
      //cout<<h.at(j)<<" "<<count<<endl;
    }
    maxh--;
  }
  cout<<count<<endl;
  return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

sv = sum(A)
res = True
for i in range(M):
    if A[i] < sv/4/M:
        res = False
        break
if res:
    print('Yes')
else:
    print('No')

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



int main() {

	//int x[10];
	long double x[10];
	long double ans=0;
	char u[10];
	char jpy[10]="JPY";
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x[i];
		cin >> u;
		if (!strncmp(u,jpy,4) ){
			ans += (long double)x[i];
		}
		else {
			ans += (long double)x[i] * 380000.0;

		}
	}
	
	cout << ans;

}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
from collections import defaultdict
from operator import itemgetter
INF = float("inf")


def solve(N: int, M: int, iPY):
    d = defaultdict(list)
    iPY.sort(key=itemgetter(2))
    for i, p, y in iPY:
        d[p].append([i, p, y])
    ans = []
    for k in d:
        for j, (i, p, y) in enumerate(d[k]):
            ans.append([i, "{0:06d}{1:06d}".format(p, j+1)])
    ans.sort()
    for a in ans:
        print(a[1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    iPY = [[]] * (M)
    for i in range(M):
        iPY[i] = [i, int(next(tokens)), int(next(tokens))]
    solve(N, M, iPY)


if __name__ == '__main__':
    main()


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

int main() {
	int A, B;

	cin >> A >> B;

	int ans = 0;
	if( A > B ) {
		ans += A;
		if( A - 1 > B ) {
			ans += A - 1;
		}
		else {
			ans += B;
		}
	}
	else {
		ans += B;
		if( B - 1 > A ) {
			ans += B - 1;
		}
		else {
			ans += A;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	static class Updown implements Comparable<Updown>{
		int up;
		int minup;
		public Updown(int a , int b) {
			up = a;
			minup = b;
		}
		@Override
		public int compareTo(Updown o) {
			return o.minup - minup;
		}
	}
	static Updown calcUpdown(String bracket){
		int u = 0;
		int mu = 0;
		for(char c : bracket.toCharArray()){
			if(c == '('){
				++u;
			}else{
				--u;
				mu = Math.min(mu, u);
			}
		}
		return new Updown(u, mu);
	}
	
	static boolean checkNegative(List<Updown> updowns){
		int cur = 0;
		Collections.sort(updowns);
		for(Updown u : updowns){
			if(cur + u.minup < 0){
				return false;
			}
			cur += u.up;
		}
		return true;
	}
	static boolean canArrange(Updown uds[]){
		int tot = 0;
		List<Updown> lefts = new ArrayList<>();
		List<Updown> rights = new ArrayList<>();
		for(Updown u : uds){
			tot += u.up;
			if(u.up >= 0){
				lefts.add(u);
			}else{
				rights.add(new Updown(- u.up , u.minup - u.up));
			}
		}
		if(tot != 0){
			return false;
		}
		return checkNegative(lefts) && checkNegative(rights);
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Updown uds[] = new Updown[N];
		for(int i = 0 ; i < N ; ++i){
			String bracket = sc.next();
			Updown ud = calcUpdown(bracket);
			uds[i] = ud;
		}
		if(canArrange(uds)){
			System.out.println("Yes");
		}else{
			System.out.println("No");			
		}
	}
}


Measured memory_bytes: 88440
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
using mat=vector<vec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
#define endl "\n"
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}while(0)
using datas=pair<ll,ll>;
using tdata=pair<ll,datas>;

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

void printmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  For(i,0,H+2){
    For(j,0,W+2){cout<<a[i*(W+2)+j];}
    cout<<endl;
  }
}
void inputmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  string ss;
  For(i,1,H+1){
    cin>>ss;
    For(j,1,W+1){
      if(ss[j-1]=='#'){
        a[i*(W+2)+j]=1;
      }else{
        a[i*(W+2)+j]=0;
      }
    }
  }
}
ll lpow(ll a,ll b){
  ll i,res=1;
  rep(i,b){
    res*=a;
  }
  return res;
}

struct sumsegtree{
  ll N;
  vec tree;
  sumsegtree(ll K){
    N=1;
    while(N<K)N*=2;
    tree.resize(2*N-1,0);
  }
  void input(ll i,ll a){
    i+=N-1;
    tree[i]+=a;
    while(i){
      i=(i-1)/2;
      tree[i]=tree[i*2+1]+tree[i*2+2];
    }
  }
  ll res(ll a,ll b,ll k,ll l,ll r){
    if(r<0)r=N;
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return tree[k];
    ll vl=res(a,b,2*k+1,l,(l+r)/2);
    ll vr=res(a,b,2*k+2,(l+r)/2,r);
    return vl+vr;
  }
  ll q(ll a,ll b){
    return res(a,b,0,0,-1);
  }
  void prt(){
    output(tree);
  }
};
int main(){
  ll N,i,q,a,b,c;
  cin>>N>>q;
  sumsegtree p(N);
  rep(i,q){
    cin>>a>>b>>c;b--;
    if(a){
      cout<<p.q(b,c)<<endl;
    }else{
      p.input(b,c);
    }
  }
  return 0;
}


Measured memory_bytes: 4900
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pll;

pll add(const pll &a, const pll &b){
	return pll(a.first + b.first, a.second + b.second);
}

pll sub(const pll &a, const pll &b){
	return pll(a.first - b.first, a.second - b.second);
}

pll mul(LL t, const pll &a){
	return pll(a.first * t, a.second * t);
}

LL cross(const pll &a, const pll &b){
	return a.first * b.second - b.first * a.second;
}

LL div(const pll &a, const pll &b){
	if(b.first != 0){ return a.first / b.first; }
	return a.second / b.second;
}

vector<pll> input(int n){
	vector<pll> pts(n);
	for(int i = 0; i < n; ++i){
		cin >> pts[i].first >> pts[i].second;
	}
	rotate(pts.begin(), min_element(pts.begin(), pts.end()), pts.end());

	vector<pll> vec(n);
	for(int i = 0; i < n; ++i){
		vec[i] = sub(pts[i + 1], pts[i]);
	}
	vec[n - 1] = sub(pts[0], pts[n - 1]);
	return vec;
}

LL area(const vector<pll> &v){
	int n = v.size();
	pll p;
	LL s = 0;
	for(int i = 0; i < n; ++i){
		pll q = add(p, v[i]);
		s += cross(p, q);
		p = q;
	}
	return s;
}

int main(){
	int n, m;
	while(cin >> n >> m && n){
		vector<pll> v1 = input(n);
		vector<pll> v2 = input(m);
		if(area(v1) > area(v2)){ v1.swap(v2); }
		vector<int> idxs;
		while(true){
			int s1 = v1.size(), s2 = v2.size();
			idxs.assign(s1, -1);
			int j = 0;
			LL u = 1LL << 50;
			for(int i = 0; i < s1; ++i){
				for(; j < s2; ++j){
					if(cross(v1[i], v2[j]) == 0){ break; }
				}
				if(j >= s2){
					u = 0;
					break;
				}
				idxs[i] = j;
				LL t = div(v2[j], v1[i]);
				u = min(t, u);
				++j;
			}
			if(u <= 0){ break; }
			for(int i = 0; i < s1; ++i){
				int k = idxs[i];
				v2[k] = sub(v2[k], mul(u, v1[i]));
			}
			v2.erase(remove(v2.begin(), v2.end(), pll()), v2.end());
			v1.swap(v2);
		}
		LL a1 = area(v1);
		LL a2 = area(v2);
		cout << (a1 + a2) << endl;
	}
}


Measured memory_bytes: 3168
// 2018, Sayutin Dmitry.

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

#define pb push_back
#define eb emplace_back

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

    // code here
    int n = input<int>();
    vector<int> a(n);
    input_seq(ALL(a));

    sort(ALL(a));
    int xr = 0;
    for (int i = 0; i < n; ++i) {
        int val = a[i];
        int prev = (i == 0 ? 0 : a[i - 1]);

        if ((val - prev) % 2)
            xr ^= (n - i);
    }

    cout << (xr == 0 ? "second" : "first") << "\n";
    
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
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; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 100000009;
const int INF = 1e9;
const ll INFLONG = 1e18;

int main(){
  ll a,b;
  cin >> a >> b;
  cout << a * b << endl;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstring>

typedef long long ll;
constexpr double PI = 3.141592653589793;
constexpr ll INF = 1e18 + 10;
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 (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}

using namespace std;
//    cout << setprecision(20) << ans << "\n";

vector<pair<ll, ll>> primeFactorize(ll N)
{
    vector<pair<ll, ll>> res;
    for (ll a = 2; a * a <= N; ++a)
    {
        if (N % a != 0)
            continue;
        ll ex = 0;

        while (N % a == 0)
        {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }

    if (N != 1)
        res.push_back({N, 1});
    return res;
}

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

    string s;
    cin >> s;
    vector<bool> dup(27, false);
    for (char c : s)
    {
        int p = c - 'a';
        if (dup[p])
        {
            cout << "no"
                 << "\n";
            return 0;
        }
        dup[p] = true;
    }
    cout << "yes"
         << "\n";
         
    return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<(n);i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
const double PI = acos(-1);
int main(){
	string  s;cin>>s;
	rep(i,s.length()){
		if(s[i]=='?')s[i]='D';
	}
	cout<<s<<endl;
}

Measured memory_bytes: 3736
/*
memo for solution
*/
#include <cstdlib> 
#include <numeric>
#include <cstring>
#include <cstdio> 
#include <cfloat> 
#include <map> 
#include <cassert>
#include <cmath> 
#include <climits> 
#include <utility> 
#include <set> 
#include <iostream> 
#include <memory> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <functional> 
#include <sstream> 
#include <complex> 
#include <stack> 
#include <queue> 
#include <iomanip>
#include<sys/time.h>
using namespace std; 
double e_time(void){static struct timeval now;gettimeofday(&now, NULL);return (double)(now.tv_sec  + now.tv_usec/1000000.0);}
#define REP(i,b,n) for(int i=b;i<n;i++) 
#define rep(i,n)      REP(i,0,n) 
#define pb push_back  
#define mp make_pair 
#define ALL(C)   (C).begin(),(C).end() 
#define fe(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr != (c).end();itr++)
#define BITSHIFT(X)     ( (1<<(X)) )
#define CONTAIN(S,X) ( ((S)&BITSHIFT(X)) != 0)
typedef complex<double>P; 
typedef long long ll; 
typedef unsigned long long ull; 
typedef pair<int,int> pii; 
typedef vector<int> vint;
template<class T> void vp(T &a,int p){rep(i,p)cout << a[i]<<" ";cout << endl;}  
template<class T> T ceilUp(const T& a,const T& b){return (a+b-1)/b;}
const ll mod =   1000000009;
inline ll modadd(ll a,ll b){a %= mod;b %= mod;return (a+b)%mod;}
inline ll modsub(ll a,ll b){a %= mod;b %= mod;a-=b;a%=mod;if (a<0)a+=mod;return a;}
inline ll modmul(ll a,ll b){a %= mod;b %= mod;return (a*b)%mod;}
inline ll modeq(ll a,ll b,ll m){a = (a%m+m)%m; b = (b%m+m)%m;return a == b;}
//ll modpow(ll n,ll p){if (p == 0)return 1;if (p == 1)return n;ll ret=mypow(n,p/2);ret=ret*ret%mod;if (p&1)ret=ret*n%mod;return ret;}
//ll getinv(ll a){return mypow(a,mod-2);}
ll mypow(ll n,ll p){
  if (p == 0)return 1;
  if (p == 1)return n;
  ll ret=mypow(n,p/2);
  ret=ret*ret;
  if (p&1)ret=ret*n;
  return ret;
}
 
int main(){
  int n,w,h;
  cin >> n >> h >> w;
  cout << (n-h+1) * (n-w+1) << endl;
  return 0;
}
 
 


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define fst first
#define sc second
#define snd second
#define sz(X) (int)(X).size()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fornr(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define forab(i, a, b) for(int i = int(a); i < int(b); i++)
#define all(X) X.begin(), X.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ld;
typedef vector<int> vi;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    forn(i, sz(s)) {
        if (i % 2 == 0 && s[i] == 'L') {
            cout << "No\n";
            return 0;
        }
        if (i % 2 == 1 && s[i] == 'R') {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#define N 100005
#define F first
#define S second
using namespace std;

typedef long long ll;
#define PI pair<ll, ll>
ll n, m, k, s[N];
bool v[N];
vector<PI> a[N];
void f(ll p, ll q, ll u){
	ll i;
	if (v[p]) return;
	v[p] = true;
	s[p] = q;
	for (i = 0; i < a[p].size(); i++) {
		if (a[p][i].F == u) continue;
		f(a[p][i].F,q + a[p][i].S, p);
	}
}

int main()
{
	ll i, j, t1, t2, t3;
//	freopen ("input.txt", "r", stdin);
	cin >> n;
	for (i = 0; i < n - 1; i++) {
		scanf ("%lld %lld %lld", &t1, &t2, &t3);
		a[t1].push_back(PI(t2, t3));
		a[t2].push_back(PI(t1, t3));
	}
	cin >> m >> k;
	f(k, 0, -1);
	while (m--) {
		scanf ("%lld %lld", &t1, &t2);
		printf("%lld\n", s[t1] + s[t2]);
	}
    return 0;
}



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

const int MAX_D = (int)(10 + 5);

int d, g;
int p[MAX_D], c[MAX_D];

int ans;

int main(void){
  scanf("%d %d", &d, &g);
  for (int i = 1; i <= d; ++i) {
    scanf("%d %d", &(p[i]), &(c[i]));
  }

  vector<int> v;

  for (int i = 1; i <= d; ++i) {
    v.push_back(i);
  }

  ans = 100 * 10 + 5;
  do {
    int cur_ans = 0;
    int total = 0;
    for (auto i: v) {
      if ((g - total) > p[i] * i * 100 + c[i]) {
        cur_ans += p[i];
        total += p[i] * i * 100 + c[i];
      }
      else {
        if ((g - total) > (p[i] * i * 100)) {
          cur_ans += p[i];
          total += p[i] * i * 100 + c[i];
        }
        else {
          int part_num = ceil((g - total) / (i * 100));
          cur_ans += part_num;
          total += part_num * i * 100;
        }
      }
      if (total >= g) break;
    }

    ans = min(ans, cur_ans);

  } while (next_permutation(v.begin(), v.end()));

  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 256
# Date [ 2020-09-13 21:00:56 ]
# Problem [ b.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    a, b, c, d = read_ints()
    ans = -10 ** 18
    for x in [a, b]:
        for y in [c, d]:
            ans = max(ans, x*y)
    print(ans)

if __name__ == '__main__':
    Main()

Measured memory_bytes: 9240
#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define rn(i,n) for(int i=1;i<=n;i++)

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

  vector<pair<int, int> > a(n);
  int tmp;
  r(i,n){
    cin>>tmp;
    a[i]=make_pair(tmp,i);
  }
  sort(a.begin(),a.end());
  r(i,n){
    cout<<a.at(i).second+1<<" ";
  }
  cout<<endl;



  return 0;
}


Measured memory_bytes: 1664
open System
open System.Collections.Generic

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f
    let readChars() = read string |> Seq.toArray
    let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

[<AutoOpen>]
module Cout =
    let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
    let print (s: string) = writer.Write s
    let println (s: string) = writer.WriteLine s
    let inline puts (s: ^a) = string s |> println

// -----------------------------------------------------------------------------------------------------

// -----------------------------------------------------------------------------------------------------

let main() =
    let s = readChars()
    let xs = Array.zeroCreate 3
    for c in s do
        let c = int c - int 'a'
        xs.[c] <- xs.[c] + 1

    let xs = xs |> Array.sort
    let mutable ok = true
    for i in 0 .. 2 do
        if abs (xs.[0] - xs.[i]) >= 2 then ok <- false

    if ok then "YES" else "NO"
    |> puts

    ()

// -----------------------------------------------------------------------------------------------------
main()
writer.Dispose()


Measured memory_bytes: 14168
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
const double EPS = 1e-10;

signed main() {
	int N(10010000);
	vector<bool>p(N, true); p[0] = p[1] = false;
	for (int i = 2; i*i <= N; i++) {
		if (p[i]) {
			for (int j = i + i; j < N; j += i)p[j] = false;
		}
	}
	int n;
	while (cin >> n, n) {
		for (int i = n; i >= 13; i--) {
			if (p[i] && p[i - 2] && p[i - 6] && p[i - 8]) {
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3884
h, w = map(int, input().split())
f = [list(input()) for i in range(h)]

i = w-1
while i >= 0:
    col = ""
    for j in range(h):
        col += f[j][i]
    if col == "."*h:
        for j in range(h):
            del f[j][i]
    i -= 1

i = h-1
while i >= 0:
    if set(f[i]) == {"."}: del f[i];
    i -= 1

for i in f:
    print("".join(i))

Measured memory_bytes: 3064
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
cd=[list(map(int,input().split())) for i in range(m)]

def manh(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])


ans=[]
for i in range(n):
    ans_sub=[0,manh(ab[i],cd[0])]
    for j in range(m):
        k=manh(ab[i],cd[j])
        if k<ans_sub[1]:
            ans_sub=[j,k]
    ans.append(ans_sub[0])
for i in range(n):
    print(ans[i]+1)


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

typedef long long ll;

struct Edge {
	int to, cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
};

const ll INF = (ll)1e15;
int N, M;
vector<ll> dist;
vector<bool> neg;
vector<vector<Edge> > G;

void bellman_ford(int s) {
	dist.resize(N, INF);
	dist[s] = 0;
	for (int i = 0; i < N - 1; ++i) {
		for (int v = 0; v < N; ++v) {
			for (int k = 0; k < (int)G[v].size(); ++k) {
				Edge e = G[v][k];
				if ((dist[v] != INF) && (dist[v] + e.cost < dist[e.to]))
					dist[e.to] = dist[v] + e.cost;
			}
		}
	}
}

void check_loop(void) {
	neg.resize(N, false);
	for (int i = 0; i < N; ++i) {
		for (int v = 0; v < N; ++v) {
			for (int k = 0; k < (int)G[v].size(); ++k) {
				Edge e = G[v][k];
				if ((dist[v] != INF) && (dist[v] + e.cost < dist[e.to])) {
					dist[e.to] = dist[v] + e.cost;
					neg[e.to] = true;
				}
				if ((dist[v] != INF) && (neg[v] == true))
					neg[e.to] = true;
			}
		}
	}
}

int main(void) {
	cin >> N >> M;
	G.resize(N);
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a - 1].push_back(Edge(b - 1, -c));
	}

	bellman_ford(0);
	ll ans = -dist[N - 1];
	check_loop();

	if (neg[N - 1])
		cout << "inf" << '\n';
	else
		cout << ans << '\n';
	return 0;
}


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

string grid[500];
int posy[26][2],posx[26][2];
int pos[26][2][2];
bool use[26];
int n,m;
int res;

bool cluck(int y,int x){
  int k;
  int cnt[26];
  for(int i=0;i<26;i++)cnt[i] = 0;

  k = 1;
  while(y+k<n && grid[y+k][x] == '.')k++;
  if(y+k<n)cnt[grid[y+k][x]-'A']++;

  k = 1;
  while(x+k<m && grid[y][x+k] == '.')k++;
  if(x+k<m)cnt[grid[y][x+k]-'A']++;

  k = 1;
  while(y-k>=0 && grid[y-k][x] == '.')k++;
  if(y-k>=0)cnt[grid[y-k][x]-'A']++;

  k = 1;
  while(x-k>=0 && grid[y][x-k] == '.')k++;
  if(x-k>=0)cnt[grid[y][x-k]-'A']++;

  bool f = false;
  for(int i=0;i<26;i++){
    if(cnt[i]>=2){
      res += 2;
      f = true;
      for(int j=0;j<n;j++){
	for(int k=0;k<m;k++){
	  if(grid[j][k] == 'A'+i)grid[j][k] ='.';
	}
      }
    }
  }
  return f;
}

int main(){
  cin >> n >> m;
  for(int i=0;i<n;i++)cin >> grid[i];

  for(int i=0;i<26;i++){
    posy[i][0] = -1;
    posx[i][0] = -1;
    posy[i][1] = -1;
    posx[i][1] = -1;
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(grid[i][j] != '.'){
	if(posy[grid[i][j]-'A'][0]<0){
	  posy[grid[i][j]-'A'][0] = i;
	  posx[grid[i][j]-'A'][0] = j;
	}else{
	  posy[grid[i][j]-'A'][1] = i;
	  posx[grid[i][j]-'A'][1] = j;
	}
      }
    }
  }

  res = 0;
  while(1){
    bool f = false;
    for(int i=0;i<26;i++){
      if(posy[i][0] == posy[i][1]){
	int s = min(posx[i][0],posx[i][1]),g = max(posx[i][0],posx[i][1]);
	for(int j=s+1;j<g;j++){
	  if(grid[posy[i][0]][j]=='.')f |= cluck(posy[i][0],j);
	}
      }else if(posx[i][0] == posx[i][1]){
	int s = min(posy[i][0],posy[i][1]),g = max(posy[i][0],posy[i][1]);
	for(int j=s+1;j<g;j++){
	  if(grid[j][posx[i][0]]=='.')f |= cluck(j,posx[i][0]);
	}
      }else{
	if(grid[posy[i][0]][posx[i][1]] == '.')f |= cluck(posy[i][0],posx[i][1]);
	if(grid[posy[i][1]][posx[i][0]] == '.')f |= cluck(posy[i][1],posx[i][0]);
      }
    }
    if(!f)break;
  }

  cout << res << endl;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define PB push_back
#define X first
#define Y second
#define INF 1000 * 1000 * 1000

#define LL long long
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;
const int MAX = 1 << 17;

int main()
{
	ios_base::sync_with_stdio(0);
	int n;
	string a , b , c;
	cin >> n >> a >> b >> c;
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		set<char> s;
		s.insert(a[i]);		s.insert(b[i]);		s.insert(c[i]);
		ans += s.size() - 1;
	}
	cout << ans;
}


Measured memory_bytes: 256
#include <stdio.h>
int main() {
  int a, b;
  int ans;

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

  if (a < 10 && b < 10) {
    ans = a * b;
    printf ("%d\n", ans);
  }

  else {
    printf ("-1\n");
  }

  return 0;
}


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

int main()
{
  int x, a, b;
  cin >> x >> a >> b;
  int ans = x - a;
  ans %= b;
  cout << ans;
}


Measured memory_bytes: 3572
program prob2
    implicit none
    integer::i,j,k,L
    character(len=100)::S
    read(*,*) S
    L = len_trim(S)
    if(S(1:7) .eq. "keyence")then
        write(*,*) "YES"
        stop
    else if(S(L-6:L) .eq. "keyence")then
        write(*,*) "YES"
        stop
    else if(S(1:1) .eq. "k" .and. S(2:2) .ne. "e") then
        if(S(L-5:L) .eq. "eyence") then
            write(*,*) "YES"
            stop
        end if
    else if(S(1:2) .eq. "ke" .and. S(3:3) .ne. "y") then
        if(S(L-4:L) .eq. "yence") then
            write(*,*) "YES"
            stop
        end if
    else if(S(1:3) .eq. "key" .and. S(4:4) .ne. "e") then
        if(S(L-3:L) .eq. "ence") then
            write(*,*) "YES"
            stop
        end if
    else if(S(1:4) .eq. "keye" .and. S(5:5) .ne. "n") then
        if(S(L-2:L) .eq. "nce") then
            write(*,*) "YES"
            stop
        end if
    else if(S(1:5) .eq. "keyen" .and. S(6:6) .ne. "c") then
        if(S(L-1:L) .eq. "ce") then
            write(*,*) "YES"
            stop
        end if
    else if(S(1:6) .eq. "keyenc" .and. S(7:7) .ne. "e") then
        if(S(L:L) .eq. "e") then
            write(*,*) "YES"
            stop
        end if
    end if

    write(*,*) "NO"
    stop
end program prob2

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;

ll solve(ll X, ll K, ll D)
{
    X = abs(X);
    ll left_cnt = X / D;

    if (left_cnt >= K)
        return X - K * D;
    else
        return min(abs(X-left_cnt*D), abs(X-(left_cnt+1)*D));
}

int main()
{
    ll X, K, D;
    cin >> X >> K >> D;

    ll ans = 1e15;
    if (K&1)
        ans = min(solve(X+D, K/2, D*2), solve(X-D, K/2, D*2));
    else
        ans = solve(X, K/2, D*2);

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


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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  int Alice=0;
  int Bob=0;
  for(int i=0;i<N;i++){
    if(i%2==0){
      Alice+=a.at(i);
    }
    else{
      Bob+=a.at(i);
    }
  }
  cout << Alice-Bob << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multi_array.hpp>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int dp[1010][5050];

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  vector<int> c(m);
  rep(i, m) {
    cin >> a[i] >> b[i];
    rep(j, b[i]) {
      int temp;
      cin >> temp;
      c[i] += (1 << (temp - 1));
    }
  }
  rep(j, 1 << n) {
    if ((j & ~c[0]) != 0)
      dp[0][j] = 100010000;
    else
      dp[0][j] = a[0];
  }
  dp[0][0] = 0;
  rep(i, m - 1) {
    rep(j, 1 << n) {
      dp[i + 1][j] = min(dp[i][j], dp[i][j & ~c[i + 1]] + a[i + 1]);
    }
  }
  int ans;
  if (dp[m - 1][(1 << n) - 1] == 100010000)
    ans = -1;
  else
    ans = dp[m - 1][(1 << n) - 1];

  cout << ans << endl;

  return 0;
}


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

W=[]
for i in range(N):
    W.append(input())

flg=0

if len(W)!=len(set(W)):
    flg+=1

for i in range(len(W)-1):
    if W[i][-1]!=W[i+1][0]:
        flg+=1
        break

if flg==0:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 3060
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Main {

	
    public static void main(String[] args) {
    	
        Scanner in = new Scanner(System.in);
        
        int N = in.nextInt();
        int D = in.nextInt()-1;
        int X = in.nextInt();
        
        for(int i = 0;i<N;i++){
        	 int number = in.nextInt();
        	 X += D/number + 1;
        }
        
        System.out.println(X);
        in.close();
    }

	
}


Measured memory_bytes: 21844
#include <iostream>
using namespace std;
int main(){
    int a,b,c,n;
    cin >> n;
    for (;0<n;n--){
        cin >> a >> b >> c;
        if (a*a+b*b == c*c)
            cout << "YES" << endl;
        else if (a*a+c*c == b*b)
            cout << "YES" << endl;
        else if (b*b+c*c == a*a)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

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

#define ll long long

using namespace std;

ll f(ll a, ll b, ll x) {
    return (a * x - (a * x) % b) / b - a * (x - x % b) / b;
}

int main() {
    ll a, b, n;
    cin >> a >> b >> n;
    ll ans = 0;
    if (n <= (b - 1)) {
        ans = f(a, b, n);
    } else {
        ans = f(a, b, b - 1);
        /*for (ll i = b - 1; i < n; i += b) {
            ans = max(ans, f(a, b, i));
        }*/
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
import Control.Monad.State
main = do
  [n,a,b] <-map read.words<$>getLine
  s <- getLine 
  let res = evalState (ans'' (a,b) s) (0,0)
  (mapM putStrLn) res

type St = (Int,Int)

solve :: St -> Char -> State St String
solve (a,b) 'a' =
  state (\(jpn,wld) ->
  if jpn+wld < a+b
    then ("Yes",(jpn+1,wld))
    else ("No",(jpn,wld)))
solve (a,b) 'b' =
  state (\(jpn,wld) ->
  if jpn+wld < a+b && wld < b
    then ("Yes",(jpn,wld+1))
    else ("No",(jpn,wld)))
solve _ 'c' =
  state (\s -> ("No",s))


ans :: St -> [Char] -> State St [String]
ans s c = do
  c1 <- solve s (c!!0)
  c2 <- solve s (c!!1)
  c3 <- solve s (c!!2)
  return [c1,c2,c3]


ans' :: St -> [Char] -> State St [String]
ans' s c = 
  solve s (c!!0) >>= (\x ->
  solve s (c!!1) >>= (\y ->
  solve s (c!!2) >>= (\z ->
  return [x,y,z])))

ans'' :: St -> [Char] -> State St [String]
ans'' s [] = return []
ans'' s (fc:sc) = 
  solve s fc >>= (\x -> ans'' s sc >>= (\y -> return (x:y)))
{-loop :: Int -> St -> Char -> (String,St)
loop 0 _ _ = (" ",(0,0))
loop n (a,b) c = solve (a,b) c >>= loop (n-1) (a,b) c-}

Measured memory_bytes: 7676
n = int(input())
w = list(map(int, input().split()))
diffs = []
for i in range(n):
    small = sum(w[i] for i in range(0, i + 1))
    big = sum(w[i] for i in range(i + 1, n))
    diffs.append(abs(small - big))
print(min(diffs))


Measured memory_bytes: 3060