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

using namespace std;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
int fac[N], ifac[N]; 

int add(int a, int b){
	a += b;
	a %= mod;
	if(a < 0) a += mod;
	return a;
}
int mul(int a, int b){
	return 1LL * a * b % mod;
}
int f_pow(int val, int idx){
	if(idx == 1) return val;
	if(idx == 0) return 1;
	int k = f_pow(val, idx >> 1);
	k = mul(k, k);
	if(idx  & 1) k = mul(k, val);
	return k;
}
int C(int n, int r){
	if(r > n) return 0;
	if(r == n) return 1;
	if(r == 1) return n;
	return mul(fac[n], mul(ifac[n-r], ifac[r]));
}
int main(){
	int r1, r2, c1, c2, ans = 0;
	scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
	fac[0] = 1;
	for(int i =1; i <= r2 + c2 + 1; i++){
		fac[i] = mul(i, fac[i-1]);
	}
	ifac[r2 + c2 + 1] = f_pow(fac[r2 + c2 + 1], mod - 2), ifac[1] = 1, ifac[0] = 1;
	for(int i = r2 + c2; i > 1; i--){
		ifac[i] = mul(i + 1, ifac[i + 1]);
	}
	for(int i = r1 ; i <= r2; i++){
		//printf("%d , %d\n", C(c2 + i + 1, i + 1), C(c1 + i, i + 1));
		ans = add(ans, add(C(c2 + i + 1, i +1), -C(c1 + i, i + 1)));
	}
	printf("%d", ans);
}

Measured memory_bytes: 15872
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    p = 1
    m = pow(10, 18)
    if 0 in A: return 0
    for n in A:
        p = p * n
        if p > m:
            return -1
    return p


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

if __name__ == '__main__':
    main()


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rept(i,k,n) for(int i = (k); i < (int)(n); i++)
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<long long,long long> Pll;


int main() {
    int k,a,b;
    cin>>k>>a>>b;
    if(b/k*k>=a) cout<<"OK";
    else cout<<"NG";
    return 0;
}


Measured memory_bytes: 3624
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    S = list(input())
    sr = set(S)
    ret = 100
    for s in sr:
        max_cnt = 0
        cnt = 0
        for t in S:
            if s!=t:
                cnt += 1
            else:
                max_cnt = max(max_cnt, cnt)
                cnt = 0
        max_cnt = max(max_cnt, cnt)
#        print(s,max_cnt)
        ret = min(ret, max_cnt)
    print(ret)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        String T = sc.next();
        sc.close();
        int result = 0;

        for(int i=0;i<S.length();i++){
            if(!(S.substring(i,i+1).equals(T.substring(i,i+1)))){
                result ++;
            }
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 55032
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
  int n, k;
  cin >> n >> k;
  if(n % k == 0) cout << 0 << ln;
  else cout << 1 << ln;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int w = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		if(Math.abs(b-a)<=w) {
			System.out.println(0);
		}else {
			System.out.println(Math.abs(a-b)-w);
		}

	}

}


Measured memory_bytes: 21844
#include <iostream>
using namespace std;
int main(){
	string S;
 	cin >> S;
	int a = 700;
 	if(S[0] == 'o') a += 100;
 	if(S[1] == 'o') a += 100;
 	if(S[2] == 'o') a += 100;
 	cout << a << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n;
  scanf("%d", &n);
  
  switch(n % 10){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      printf("hon\n");
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      printf("pon\n");
      break;
    case 3:
      printf("bon\n");
      break;      
  }
  
  return 0;
  
}

Measured memory_bytes: 1660
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
          
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a;
    long long int b = 1;
    cin >> a;
    for ( int i = 1 ; i <= a ; i++ ) {
        b *= i;
        b %= 1000000007;
    }
    cout << b;
}

Measured memory_bytes: 256
#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 Go_ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define llu long long unsigned int
#define pf printf
#define sf scanf
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define pii pair<int ,int>
#define PII pair<ll ,ll>
 
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
 
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
const int Max=1e9+100;
const ll  MAX=1e18+500;
const int sz=2e5+100;
vector<string> test[sz];
map<string,int> mp;

int main()
{
    Go_
    int a,b,c,i,j,k,q,p,x,y,ct,ct1,m,l,r,x1,y1,mn,h,sum1,in,z,mid,n,mx;
    char ch;
    double d;
    string str1,str2,str;
    bool bl,bl1;
    int t,cs=1;
    
    cin>>n;
    mx=0;
    for(i=0;i<n;i++){
        cin>>str;
        ++mp[str];
        mx=max(mx,mp[str]);
    }


    
    for(auto xx: mp){
        if(xx.second==mx) test[xx.second].push_back(xx.first);
    }

    sort(test[mx].begin(),test[mx].end());
    for(auto xx: test[mx]) cout<<xx<<endl;
    
}

Measured memory_bytes: 31572
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

N = int(input())
W = list(map(int, input().split()))
#print(W)

res = sys.maxsize

max = 0
for i in range(N):
    max += W[i]

for i in range(N):
    sum = 0
    for j in range(i):
        sum += W[j]
    x = max - sum
    tmp = abs(sum-x)
    if res < tmp:
        break
    else:
        res = tmp
print(res)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
long long n,a,b,ans,k,x; 
int main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)
	{
		k=0;
		x=i;
		while(x>0)
		{
			k+=x%10;
			x/=10;
		}
		if(k>=a && k<=b)
			ans+=i;
	}
	cout<<ans<<endl;
	return 0;
}


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

int main() {
  int A, B;
  cin >> A >> B;
  int half = (A + B) / 2;
  
  if(half * 2 == A + B) {
    cout << half << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

long long int max(long long int a, long long int b, long long int c, long long int d)
{
	if(a > b && a > c && a > d) return a;
	else if(b > a && b > c && b > d) return b;
	else if(c > b && c > a && c > d) return c;
	else return d;
}

int main()
{
	long long int a, b, c, d;
	scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
	printf("%lld\n", max(a*c, a*d, b*c, b*d));
}

Measured memory_bytes: 1692
#include <iostream>

using namespace std;

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

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= (n - i); ++j) {
            int k = n - i - j;
            int sum = 10000 * i + 5000 * j + 1000 * k;
            if (sum == y) {
                cout << i << ' ' << j << ' ' << k << '\n';
                goto END;
            }
        }
    }

    cout << "-1 -1 -1\n";

END:
    ;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
#define REP(i,x,y) for(ll i=x; i<=y; i++)
#define BIT(t) ((long long 1) << t)
using namespace std;
typedef long long ll;

int main(){
    ll n;
    string s;
    cin >> s;
    n = s.size();
    ll ans = 0;
    ll cnt = 0;
    REP(i,0,n - 2){
        if(s[i] == 'A'){
            cnt++;
        }else if(s[i] == 'B' && s[i+1] == 'C'){
            ans += cnt;
            i++;
        }else{
            cnt = 0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b;
    cin>>a>>b;
    if(a==1||b==1)cout<<1<<endl;
    else cout<<max((a*b+1)/2,1ll)<<endl;
}

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

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int solve(vi& a,vi& b)
{
	int pos=1;
	rep(i,b.size()){
		pos+=b[i];
		if(pos>=a.size()-1)
			return i+1;
		pos+=a[pos];
		if(pos>=a.size()-1)
			return i+1;
	}
	return -1;	// dummy
}

int main()
{
	for(int n,m;cin>>n>>m,n|m;){
		vi a(n+1),b(m);
		rep(i,n)
			cin>>a[i+1];
		rep(i,m)
			cin>>b[i];
		cout<<solve(a,b)<<endl;
	}
	
	return 0;
}

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

const int N = 510000;

int dp[N], sum[N];
char s[N], t[N];

int main() {
	ios_base::sync_with_stdio(0);
	int n, m; cin >> n >> m >> s + 1 >> t + 1;
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (i > 1 && t[i] != t[i - 1]);
	set<pair<int, int> > S[2];
	S[0].insert(make_pair(0, 0));
	for (int i = 1; i <= n; i++) {
		if (i == 1) {
			dp[i] = (s[i] != t[i]);
		} else {
			dp[i] = dp[i - 1] + (s[i] != t[i]);
			if (i > m) S[sum[i - m] & 1].erase(make_pair(2 * dp[i - m - 1] - sum[i - m], i - m - 1));
			for (int j = 0; j < 2; j++) {
				if (S[j].empty()) continue;
				auto it = S[j].begin();
				if (sum[i] + 1 + j & 1) {
					dp[i] = min(dp[i], (sum[i] + it->first) / 2 + 1);
				} else {
					dp[i] = min(dp[i], (sum[i] + it->first + 1) / 2 + 1);
				}
			}
		}
		if (i < n) S[sum[i + 1] & 1].insert(make_pair(2 * dp[i] - sum[i + 1], i));
	}
	cout << dp[n] << endl;
	return 0;
}



Measured memory_bytes: 31556
#include<iostream>

using namespace std;

int cost[100][100];
int V;
void wf(){
  for(int k=0;k<V;k++){
    for(int i=0;i<V;i++){
      for(int j=0;j<V;j++){
	cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
      }
    }
  }
}

main(){
  int m,s,g1,g2;
  while(cin>>V>>m>>s>>g1>>g2){
    if(V==0)break;
    for(int i=0;i<V;i++){
      for(int j=0;j<V;j++){
	cost[i][j]=100000;
      }
      cost[i][i]=0;
    }

    for(int i=0;i<m;i++){
      int b1,b2,c;
      cin>>b1>>b2>>c;
      --b1;--b2;
      cost[b1][b2]=c;
    }
    --s;--g1;--g2;
    wf();
    int ans=2<<20;
    for(int i=0;i<V;i++){
      ans=min(ans,cost[s][i]+cost[i][g1]+cost[i][g2]);
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 900
fun main(args :Array<String>) {
    val n = readInteger()
    val s = readLine()!!
        .map(Char::toInt)
        .map { it - 'A'.toInt() }
        .map { it + n }
        .map { it % ('Z' - 'A' + 1) }
        .map { it + 'A'.toInt() }
        .map(Int::toChar)
        .joinToString("")
    println(s)
}

fun readInteger() = readLine()!!.toInt()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 33820
INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, m = I()
a = [0] * (n + 10)
for i in range(m):
    x, y = I()
    a[x] += 1
    a[y + 1] -= 1
ans = 0
for i in range(1, n + 10):
    a[i] = a[i] + a[i - 1]
    if a[i] == m:
        ans += 1
print(ans)


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

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll a,b,c;
    cin>>a>>b>>c;
    if((a+b==c)||(b+c==a)||(a+c==b))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


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

const long long MOD = 1000000007;

int main() {
    int n;
    string s[2];
    cin >> n >> s[0] >> s[1];
    long long result = 1;
    for (int i = 0; i < n; ) {
        if (s[0][i] == s[1][i]) {
            if (i == 0) {
                result = result * 3 % MOD;
            } else if (s[0][i - 1] == s[1][i - 1]) {
                result = result * 2 % MOD;
            }
            i++;
        } else {
            if (i == 0) {
                result = result * 6 % MOD;
            } else if (s[0][i - 1] == s[1][i - 1]) {
                result = result * 2 % MOD;
            } else {
                result = result * 3 % MOD;
            }
            i += 2;
        }
    }
    cout << result;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N,M;
    cin >> N >> M;
    int X = 0;
    int Y = 0;
    vector<bool>ok(N);
    vector<int>cnt(N);
    for(int i = 0; i < M; i++) {
        int p;
        string S;
        cin >> p >> S;
        if(!ok[p-1]) {
            if(S == "AC") {
                X++;
                ok[p-1] = true;
            }
            else {
                cnt[p-1]++;
            }
        }
    }
    for(int i = 0; i < N; i++) {
        if(ok[i]) {
            Y+=cnt[i];
        }
    }
    cout << X << " " << Y << endl;
}


Measured memory_bytes: 4016
// Original: https://github.com/tanakh/competitive-rs
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::BTreeMap;

fn main() {
    input!(n: usize, l: i64);

    let mut vs = vec![0i64; n];
    for i in 0..n {
        vs[i] = l + i as i64;
    }
    let total = vs.iter().sum::<i64>();
    let mut ans = 1e9 as i64;
    for i in 0..n {
        let t = total - vs[i];
        if (total - t).abs() < (total - ans).abs() {
            ans = t;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
import java.util.*;

public class Main {

    static int[][] g;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int u = sc.nextInt()-1;
        int v = sc.nextInt()-1;
        g = buildGraph(sc, n, n-1);
        int[] du = new int[n];
        Arrays.fill(du, -1);
        int[] dv = new int[n];
        Arrays.fill(dv, -1);
        dfs(du, u, 0);
        dfs(dv, v, 0);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if(du[i] < dv[i]){
                int t = dv[i]-1;
                if(ans < t) ans = t;
            }
        }
        System.out.println(ans);
        sc.close();

    }

    private static void dfs(int[] dv, int next, int d) {
        if(0 <= dv[next]) return;
        dv[next] = d;
        d++;
        for(int nex : g[next]){
            dfs(dv, nex, d);
        }
    }

    public static int[][] buildGraph(Scanner sc, int n, int m) {
        int[][] graph = new int[n][];
        int[][] edges = new int[m][2];
        int[] deg = new int[n];
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            edges[i][0] = a;
            edges[i][1] = b;
            deg[a]++;
            deg[b]++;
        }
        for (int i = 0; i < n; i++) {
            graph[i] = new int[deg[i]];
        }
        for (int i = 0; i < m; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            graph[a][--deg[a]] = b;
            graph[b][--deg[b]] = a;
        }

        return graph;
    }

}


Measured memory_bytes: 100152
#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

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

int n;
vector<vector<int>> a;

void dfs(vector<int> v, int lev){
	int m = v.size();
	if(m == 1) return;

	vector<int> s, t;
	rep(i, m){
		if(i % 2 == 0) s.push_back(v[i]);
		if(i % 2 == 1) t.push_back(v[i]);
	}

	for(int x : s) for(int y : t) {
		a[x][y] = lev;
		a[y][x] = lev;
	}
	
	dfs(s, lev + 1);
	dfs(t, lev + 1);
}

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

	cin >> n;
	a.resize(n, vector<int>(n));

	vector<int> v(n);
	rep(i, n) v[i] = i;

	dfs(v, 1);
	
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			cout << a[i][j] << (j == n - 1 ? "\n" : " ");
		}
	}
}


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

int main()
{
	string s;
	cin >> s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='9'){
			cout<<"Yes\n";
			return 0;
		}
	}
	cout<<"No\n";
	return 0; 
}

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


int main() {
	
	string s;
	cin >> s;
	int dif = 1000;
	for(int i=0; i<s.size()-2; i++){
		int x = (s.at(i)-48)*100 + (s.at(i+1)-48)*10 + s.at(i+2)-48;
		dif = min(dif, abs(x-753));
	}
	cout << dif << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<string>
using namespace std;
map<string, int> mem;
string m = "";
string ss = "";
int n = 0;
int main()
{
  string s;
  while(cin >> s)
  {
    if(mem.find(s) == mem.end())
      mem[s] = 1;
    else
      mem[s]++;
    if(mem[s] > n)
    {
      n = mem[s];
      ss = s;
    }
    m = m.length() < s.length() ? s : m; 
  }
  cout << ss << " " << m << endl;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
const ll LINF = 1e18 + 5;
int n, m, in[N], dp[N];
vector <int> G[N];
void solve()
{
	queue <int> q;
	for(int i=1; i<=n; i++) if(!in[i]) q.push(i);
	while(sz(q))
	{
		int u = q.front(); q.pop();
		for(int v : G[u])
		{
			in[v]--;
			if(!in[v]) 
			{
				q.push(v);
				dp[v] = max(dp[v], dp[u]+1);
			}
		}
	}
}
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n >> m;
 	for(int i=1; i<=m; i++)
 	{
 		int u, v;
 		cin >> u >> v;
 		G[u].pb(v);
 		in[v]++;
 	}
 	solve();
 	int ans = *max_element(dp+1, dp+n+1);
 	cout << ans;
	return 0;
}


Measured memory_bytes: 6528
#include<cstdio>
using namespace std;
int main()
{
	int n,m,i,j,mx,c;
	int a[1001],x[1001],b[1001];
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(i=1;i<=m;i++){
		scanf("%d",&b[i]);
	}
	for(i=1;i<=n;i++){
		x[i]=0;
	}
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			if(a[j]<=b[i]){
				x[j]++;
				break;
			}
		}
	}
	mx=0;
	for(i=1;i<=n;i++){
		if(mx<x[i]){
			mx=x[i];
			c=i;
		}
	}
	printf("%d\n",c);
	return 0;
}



Measured memory_bytes: 2632
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
#define p_b push_back
    
ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
    
//-------------------------↓↓↓↓↓↓------------------------
    
//------ 自分を天才だと信じる ------
    
int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>a>>b;
    Cout(abs(a-b));
    return 0;
}


Measured memory_bytes: 3224
#include<stdio.h>
#include<ctype.h>
int main(void){
   char w[11];
   char t[1001];
   char s[12];
   int n;
   int i,tl;

   scanf("%s",w);
   scanf("%s",t);
   sprintf(s,"END_OF_TEXT");

   n=0;

   while(strcmp(t,s)){
      tl = strlen(t);
      for(i=0;i<tl;i++){
         t[i]=tolower(t[i]);
      }
      if(!strcmp(t,w))n++;
      scanf("%s",t); 
   }
   printf("%d\n",n);

   return 0;
}

Measured memory_bytes: 552
#include <iostream>
using namespace std;
int main(void){
  
    int a,b;
    
    cin >> a >> b;
    
    if(a < 6) cout << 0;
    else if(a > 12) cout << b;
    else cout << b/2;
    
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

int main(){
  ll n,m,k;
  cin >> n >> m >> k;
  vector<int> a(n);
  vector<int> b(m);
  rep(i,n) cin >> a[i];
  rep(i,m) cin >> b[i];
  vector<ll> sa(n+1);
  vector<ll> sb(m+1);
  rep1(i,n) sa[i] = sa[i-1]+a[i-1];
  rep1(i,m) sb[i] = sb[i-1]+b[i-1];
  int ans = 0;
  rep(i,n+1){
    if(sa[i] > k) break;
    int ok = 0;
    int ng = m+1;
    while(abs(ok-ng)>1){
      int mid = (ok+ng)/2;
      if(sa[i]+sb[mid] > k) ng = mid;
      else ok = mid;
    }
    ans = max(ans,i+ok);
  }
  cout << ans << endl;
}


Measured memory_bytes: 7948
n = int(input())
s = input()

l = [0]*(n+1)
if s[0] == "I":
    l[0] = 1
else:
    l[0] = -1

for i in range(1,n):
    if s[i] == "I":
        l[i] = l[i-1] + 1
    else:
        l[i] = l[i-1] - 1

print(max(l))



Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define INF 1145141919
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int ny, nx;
typedef long long int ll;
using namespace std;

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

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
////////////////////////////////////////////////////////////////////
int main()
{
    string S; cin >> S;
    int cnt=0, ans=-100;
    bool flag=false;
    REP(i,S.size()){
        if(S[i]=='A' or S[i]=='T' or S[i]=='C' or S[i]=='G'){
            flag=true;
        }else{
            flag=false;
        }
        if(flag==true){
            cnt++;
        }else{
            cnt=0;
        }
        if(cnt>ans) ans=cnt;
        //cout << "flag= " << flag << endl;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

#define MAX_N 200001

using namespace std;

typedef long long int LL;

struct fenwick_tree {
    int N;
    vector<int> bit;
    fenwick_tree(int num) : bit(num + 1, 0) { N = num; }
    int Sum(int a) {
        int ret = 0;
        for (int x = a; x > 0; x -= x & -x) {
            ret += bit[x];
        }
        return ret;
    }
    void Add(int a, int w) {
        for (int x = a; x <= N; x += x & -x) {
            bit[x] += w;
        }
    }
};

int main() {
    int n, a[MAX_N], b[MAX_N];
    LL ans = 0;
    map<int, int> mp;

    cin >> n;
    fenwick_tree bit(n);

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

    sort(b, b+n);

    for (int i = 0; i < n; i++) {
        mp[b[i]] = i+1;
    }
    for (int i = 0; i < n; i++) {
        ans += i - bit.Sum(mp[a[i]]);
        bit.Add(mp[a[i]], 1);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 14452
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>

int main(){
    long long sum=0;
    int N;
    std::cin >> N;
    std::vector<long long> S(5);
    std::string s;
    for(int i=0;i<N;i++){
        std::cin >> s;
        if(s[0]=='M'){
            S[0]++;
        }else if(s[0]=='A'){
            S[1]++;
        }else if(s[0]=='R'){
            S[2]++;
        }else if(s[0]=='C'){
            S[3]++;
        }else if(s[0]=='H'){
            S[4]++;
        }
    }
    sum=S[0]*S[1]*S[2]+S[0]*S[1]*S[3]+S[0]*S[1]*S[4]+S[1]*S[2]*S[3]+S[1]*S[2]*S[4]+S[2]*S[3]*S[4]+S[0]*S[2]*S[3]+S[0]*S[2]*S[4]+S[0]*S[3]*S[4]+S[1]*S[3]*S[4];
    std::cout << sum <<std::endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define pai 3.14159265358979323846
ll gcd(ll a, ll b){if (a%b == 0)  return(b);else  return(gcd(b, a%b));}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
// setprecision(n)
/* map<string,int> */
/* 大文字を小文字に変換 tolower*/
/* 小文字を大文字に変換 toupper*/
/* 辞書順 next_permutation(a.begin(),a.end()) */
int main() {
  int s;
  cin >> s;
  int h = s / 3600;
  s -= 3600 *h;
  int m = s / 60;
  s -= 60 * m;
  cout << h << ':' << m << ':' << s << endl;
}


Measured memory_bytes: 3100
while(1):
	n = int(input())
	if n == 0:
		break
	elif n == 1:
		print(int(input()))
	else:
		a = [0 for i in range(n+1)]
		for i in range(n):
			b = int(input())
			a[i+1] = a[i] + b
		c = [0 for i in range(n)]
		for i in range(n):
			c[i] = max(a[i+1:]) - a[i]
		print(max(c))
			


Measured memory_bytes: 5676
#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define pii pair<int,int>
#define ll long long
#define N (int)(1e5+10)
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define nd second
#define st first
#define inf mod
#define endl '\n'
#define sag (sol|1)
#define sol (root<<1)
#define ort (bas+son)/2
#define bit(x,y) ((x>>y)&1)

ll n;

int main(){

	cin >> n;
	ll ans = 0;

	//(i+1)*x = n
	for (ll i = 1; i*i <= n ; i++) {
		if (n % i == 0 ) {
			ll k = i-1;
			if (k and (n/k == n%k)) {
				ans += k;
			}
			k = (n/i) - 1;


			if (k and (n/k == n%k) and (i*i != n)) {
				ans += k;
			}

		}

	}
		
		cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 205;
const int MAXM = 50005;
const int INF = 0x3f3f3f3f;

namespace Flow
{
	struct Edge
	{
		int p, v, w;
	} e[MAXM];

	int e_cnt, S, T, V, ql, qr, q[MAXN], hed[MAXN], dis[MAXN], cur[MAXN];

	inline void Init(int n)
	{
		V = n;
		for (int i = 0; i < V; i ++)
			hed[i] = 0;
		e_cnt = 1;
	}

	inline void Addedge(int x, int y, int w)
	{
		e[++ e_cnt] = {y, hed[x], w}; hed[x] = e_cnt;
		e[++ e_cnt] = {x, hed[y], 0}; hed[y] = e_cnt;
	}

	inline bool Bfs()
	{
		for (int i = 0; i < V; i ++)
			dis[i] = 0;
		dis[q[ql = 0] = S] = qr = 1;
		while (ql ^ qr)
		{
			int x = q[ql ++];
			for (int i = hed[x]; i; i = e[i].v)
				if (e[i].w && !dis[e[i].p])
					dis[q[qr ++] = e[i].p] = dis[x] + 1;
		}
		return dis[T];
	}

	inline int Dfs(int x, int f)
	{
		if (x == T)
			return f;
		int ret = 0, t = 0;
		for (int &i = cur[x]; i; i = e[i].v)
			if (e[i].w && dis[e[i].p] == dis[x] + 1)
			{
				t = Dfs(e[i].p, min(f, e[i].w));
				f -= t; ret += t; e[i].w -= t; e[i ^ 1].w += t;
				if (!f)
					return ret;
			}
		return dis[x] = -1, ret;
	}

	inline int Dinic()
	{
		int ret = 0;
		while (Bfs())
		{
			for (int i = 0; i < V; i ++)
				cur[i] = hed[i];
			ret += Dfs(S, INF);
			if (ret >= INF)
				return ret;
		}
		return ret;
	}
}

int n, m, ans;
char s[MAXN];

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read(), m = Read(), Flow::Init(n + m + 2), Flow::T = n + m + 1;
	for (int i = 1; i <= n; i ++)
	{
		scanf("%s", s + 1);
		for (int j = 1; j <= m; j ++)
			if (s[j] == 'o')
				Flow::Addedge(i, j + n, 1), Flow::Addedge(j + n, i, 1);
			else if (s[j] == 'S')
				Flow::Addedge(0, i, INF), Flow::Addedge(0, j + n, INF);
			else if (s[j] == 'T')
				Flow::Addedge(i, n + m + 1, INF), Flow::Addedge(j + n, n + m + 1, INF);
	}
	ans = Flow::Dinic();
	if (ans >= INF)
		ans = -1;
	return printf("%d\n", ans), 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int(i)=0;i<(n);i++)

int main(){
  long long n,ans=1;cin>>n;
  REP(i,n){
    ans*=i+1;
    ans=ans%((long long)(1e9+7));
  }
  cout<<ans;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,K;
int A[505];
int S;

int hoge(int v) {
	vector<ll> V;
	vector<ll> SS;
	int i;
	FOR(i,N) V.push_back(A[i]%v);
	sort(ALL(V));
	SS.push_back(0);
	FORR(v,V) SS.push_back(SS.back()+v);
	
	FOR(i,N) {
		ll A=SS[i];
		ll B=(N-i)*1LL*v-(SS[N]-SS[i]);
		
		if(max(A,B)<=K) return 1;
	}
	return 0;
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		S+=A[i];
	}
	int ret=0;
	for(x=1;x*x<=S;x++) if(S%x==0) {
		if(hoge(x)) ret=max(ret,x);
		if(hoge(S/x)) ret=max(ret,S/x);
	}
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
void main()
{
    long[][] c = 3.rdMat;

    foreach (i; 1 .. 3)
    {
        long[] d = new long[3];
        d[] = c[i][] - c[i-1][];
        if (!d.all!(x => x == d[0]))
        {
            "No".writeln;
            return;
        }
    }

    "Yes".writeln;
}

enum long mod = 10L^^9 + 7;
enum long inf = 1L << 60;
enum double eps = 1.0e-9;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.mathspecial;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;
import core.bitop;

Measured memory_bytes: 256
class Problem
  attr_accessor *(?a..?z).to_a.map(&:to_sym)

  def initialize
    @n, @m = gets.to_s.split.map { |v| v.to_i }
    @g = Array.new(n){ [] }
    m.times do
      a,b = gets.to_s.split.map{ |v| v.to_i }
      a -= 1
      b -= 1
      @g[a] << b
      @g[b] << a
    end
  end

  def solve
    @g[0] & @g[n-1]
  end

  def show(ans)
    puts ans.empty? ? "IMPOSSIBLE" : "POSSIBLE"
  end
end

Problem.new.instance_eval do
  show(solve)
end


Measured memory_bytes: 35684
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;

ll n_layers(int n){
  if (n==0) return 1;
  return 2*n_layers(n-1)+3;
}

ll n_patties(int n){
  if (n==0) return 1;
  return 2*n_patties(n-1)+1;
}

ll runrun(int n, ll x){
  if(x<=0) return 0; 
  if(n==0) return 1;
  if(x<=n_layers(n-1)+1) return runrun(n-1, x-1);
  if(x==n_layers(n-1)+2) return n_patties(n-1)+1;
  if(x<=n_layers(n)-1){
    return n_patties(n-1)+1+runrun(n-1, x-n_layers(n-1)-2);
  }
  return n_patties(n);
}

int main(){
  int N;cin>>N;ll X;cin>>X;
  ll ans=runrun(N, X);
  cout << ans << endl;
  return 0;
}

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


int main()
{
int h,a;
cin>>h>>a;
if(a<h){
    int l=h/a;
        if(l*a>=h){
           cout<<h/a<<endl;
     return 0;
        }
else   {        cout<<l+1<<endl;
     return 0;
}
}
else if(a==h || h<a){
    cout<<1<<endl;
      return 0;
}







    return 0;
}


Measured memory_bytes: 384
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N;
char S[6060];

string dp[6060];
vector<int> loca, locb;
int ord[6060];

int main()
{
	scanf("%d%s", &N, S);

	for (int i = 0; i < 2 * N; ++i) {
		if (S[i] == 'a') {
			ord[i] = loca.size();
			loca.push_back(i);
		} else {
			ord[i] = locb.size();
			locb.push_back(i);
		}
	}

	for (int i = 2 * N - 1; i >= 0; --i) {
		dp[i] = dp[i + 1];

		int p = ord[i];
		int i2 = loca[p] + locb[p] - i;
		if (!(i < i2)) continue;

		if (S[i] == 'a') {
			dp[i] = max(dp[i], string("ab") + dp[i2 + 1]);
		} else {
			string tmp;

			int q = p;
			for (;;) {
				if (max(loca[q], locb[q]) == q * 2 + 1) break;
				++q;
			}

			for (int j = 0; j < 2 * N; ++j) {
				if (p <= ord[j] && ord[j] <= q) {
					tmp.push_back(S[j]);
				}
			}

			tmp += dp[q * 2 + 2];

			dp[i] = max(dp[i], tmp);
		}
	}

	printf("%s\n", dp[0].c_str());

	return 0;
}


Measured memory_bytes: 14592
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int A, B;
    cin >> A >> B;
    if (A * B % 2 == 0){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;

int main() {
    string s; cin >> s;
    int x,y; cin >> x >> y;
    s += 'a';

    int cnt_t = 0;
    int cnt_f = 0;
    bool before = true;
    vector<int> p;
    vector<int> q;

    for (int i = 0; i < s.size() - 1 ; i ++ ) {
        if (s.at(i) == 'T') {
            cnt_t ++;
        }

        else if (s.at(i) == 'F' && s.at(i+1) == 'F') {
            cnt_f ++;
        }

        else {
            cnt_f ++;
            if (cnt_t == 0)  {
                x -= cnt_f;
            }

            else if (cnt_t%2 == 0) {
                if (before) p.push_back(cnt_f);
                else q.push_back(cnt_f);
            }
            
            else {
                if (before) {
                    q.push_back(cnt_f);
                    before = false;
                }
                else {
                    p.push_back(cnt_f);
                    before = true;
                }
            }
            cnt_t = 0;
            cnt_f = 0;
        }
    }


    sort(p.begin(),p.end(),greater<int>());
    sort(q.begin(),q.end(),greater<int>());

  
    int a = 0;
    int b = 0;
    for (int i = 0; i < p.size(); i ++ ) {
        if (a <= x) a += p[i];
        else a -= p[i];
    }
    for (int i = 0; i < q.size(); i ++) {
        if (b <= y) b += q[i];
        else b -= q[i];
    }

    if (a == x && b == y) cout << "Yes" <<  endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define task "tst"
using namespace std;
const ll N = 2e5 + 9;
const ll inf = 1e8;
typedef pair<ll,ll> LL;

ll n,a[N],i,fr[N],b[N],ans;
ll bpow(ll a,ll b){
    if (b == 0) return 1;
    ll t = bpow(a,b/2);
    if (b%2 == 0) return t*t;
    return t*t*a;
}
ll min3(ll x,ll y,ll z){
    return min(x,min(y,z));
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n; n++;
    for (i = 1;i <= n;i++){
        cin>>a[i]; b[i] = b[i - 1] + a[i];
    }
    if (n == 1){
        if (a[1] == 1) cout<<1;
        else cout<<-1;
        return 0;
    }
    fr[1] = 1 - a[1];
    for (i = 2;i <= n;i++){
        if (i < 45) fr[i] = min3(fr[i - 1]*2 - a[i],b[n] - b[i],bpow(2,i - 1) - a[i]);
        else fr[i] = min(fr[i - 1]*2 - a[i],b[n] - b[i]);
        if (fr[i] < 0){
            cout<<-1; return 0;
        }
        ans += fr[i] + a[i];
    }
    ans++;
    cout<<ans;
}


Measured memory_bytes: 5984
#include <stdio.h>

int a;
int b;

int area (int a,int b)
{
  return a*b;
}

int perimeter(int a,int b)
{
  return (a+b)*2;
}

int main(int argc, char*argv[]) {
  scanf("%d%d",&a,&b);
  printf("%d %d\n",area(a,b),perimeter(a,b));
  return 0;
}

Measured memory_bytes: 1796
N = int(input())
ls = [0]*(N+2)
 
for i in range(1,151):
    for j in range(1,151):
        for k in range(1,151):
            t = i*i + j*j + k*k + i*j + j*k + k*i 
            if t <= N :
                ls[t] += 1
 
for p in range(1,N+1):
    print(ls[p])

Measured memory_bytes: 9300
fn main() {
    proconio::input! {
        s: String,
        t: String,
    }
    let s=s.as_bytes();
    let t=t.as_bytes();
    let a=(0..s.len()).all(|i|s[i]==t[i]);
    println!("{}", if a {"Yes"} else {"No"});
}

Measured memory_bytes: 2140
import numpy as np
N, Q = map(int, raw_input().split())
S = raw_input()
L = np.zeros(Q)
R = np.zeros(Q)
for i in range(Q):
    L[i], R[i] = map(int, raw_input().split())
num = np.zeros(N)
num_tmp = 0
for i in range(1,N):
    if S[i-1:i+1] == "AC":
        num_tmp += 1
    num[i] = num_tmp
for i in range(Q):
    print int(num[int(R[i]-1)] - num[int(L[i]-1)])      

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

using namespace std;
typedef long long ll;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define each(i,mp) for(auto& i:mp)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;
const ll m=1LL<<32;

int main(){

  ll n,k;cin>>n>>k;
  ll a[n];rep(i,0,n)cin>>a[i];
  ll b[2*n];
  rep(i,0,n){
    b[i]=b[n+i]=a[i];
  }

  ll one[n];
  rep(i,0,n){
    ll count=0;
    rep(j,i+1,n){
      if(a[i]>b[j])count++;
    }
    one[i]=count;
  }

  ll multi[n];
  rep(i,0,n){
    ll count=0;
    rep(j,i+1,n+i){
      if(b[j]>b[n+i])count++;
    }
    multi[i]=count;
  }

  ll ans=0;
  rep(i,0,n){
    ans+=(((k*(k-1)/2)%mod)*multi[i])%mod;
    ans%=mod;
    (ans+=(one[i]*k)%mod)%=mod;
  }

  out(ans);

  return 0;
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;
    int n = s.size();
    set<char> st;
    rep(i,n){
        if(s[i] == t[i]) st.insert(s[i]);
        else if(st.find(s[i]) != st.end() || st.find(t[i]) != st.end()){
            cout << "No" << endl;
            return 0;
        }
        else{
            st.insert(t[i]);
            char u = s[i];
            char v = t[i];
            for(int j = i; j < n; ++j){
                if(s[j] == u) s[j] = v;
                else if(s[j] == v) s[j] = u;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3792
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static void Main(){
		Sc sc=new Sc();
		var s=sc.S+"X";
		for(int i = 0;i<s.Length-1;i+=2) {
			if(s[i]=='h'&&s[i+1]=='i'){ }
			else{
				Console.WriteLine("No");
				return;
			}
		}
		Console.WriteLine("{0}","Yes");
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 13140