akhauriyash/Code-Regression huggingface dataset:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

import itertools
pattern = itertools.permutations(xy, n)

import numpy as np

distances = []
for p in pattern:
    distance = 0
    for i, (x, y) in enumerate(p):
        if i == 0:
            base = (x, y)
            continue
    
        b_x, b_y = base
        d2 = (b_x - x) ** 2 + (b_y - y) ** 2
        d = np.sqrt(d2)
        distance += d
    
        base = (x, y)

    distances.append(distance)

print(np.mean(distances))

Measured memory_bytes: 28544
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let (n,m) =  {
        let t = read_vec::<usize>();
        (t[0],t[1])
    };
    let (n,m) = (std::cmp::max(n, m),std::cmp::min(n,m));
    let ans = if n == 1 && m == 1{
        1
    } else if m == 1{
        (n-2)
    } else {
        (n-2)*(m-2)
    };
    println!("{}",ans );
}

Measured memory_bytes: 4352
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

const double PI = acos(-1);

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int> > G;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No", "Yes"};
string YES[2] = {"NO", "YES"};
string Psb[2] = {"Impossible", "Possible"};
string psb[2] = {"impossible", "possible"};

ll inq(ll x, ll y)
{
    if (!y) re 1 % MOD;
    ll l = inq(x, y / 2);
    if (y % 2) re l * l % MOD * x % MOD;
    re l * l % MOD;
}

ll rev(ll x)
{
    return inq(x, MOD - 2);
}

bool __precomputed_combinatorics = 0;
vector<ll> __fact, __ufact, __rev;

void __precompute_combinatorics()
{
    __precomputed_combinatorics = 1;
    __fact.resize(FN);
    __ufact.resize(FN);
    __rev.resize(FN);
    __rev[1] = 1;
    for (int i = 2; i < FN; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
    __fact[0] = 1, __ufact[0] = 1;
    for (int i = 1; i < FN; i++) __fact[i] = __fact[i - 1] * i % MOD, __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}

ll fact(int x)
{
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[x];
}

ll cnk(int n, int k)
{
    if (k < 0 || k > n) return 0;
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    vi a;
    forn(i, n)
    {
        int x;
        cin >> x;
        if (a.size() && a.back() == x) continue;
        a.push_back(x);
    }
    ll ans = 1;
    ll d = 0;
    for (int i = 1; i < a.size(); i++)
    {
        if (d == 0 && a[i] > a[i - 1]) d = 1;
        if (d == 0 && a[i] < a[i - 1]) d = -1;
        if (d == -1 && a[i] < a[i - 1]) continue;
        if (d == 1 && a[i] > a[i - 1]) continue;
        ans++;
        d = 0;
    }
    cout << ans;
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/


Measured memory_bytes: 892
#pragma region Include
#include <bits/stdc++.h>
// #include <algorithm>
// #include <bitset>
// #include <climits>
// #include <cmath>
// #include <iostream>
// #include <iterator>
// #include <map>
// #include <queue>
// #include <sstream>
// #include <stack>
// #include <string>
// #include <unordered_map>
// #include <unordered_set>
// #include <vector>
#pragma endregion

using namespace std;

#pragma region Macros
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define all(c) (c).begin(), (c).end()
#define newl "\n"
#define out(x) cout << (x) << newl
#define dump(x) \
  cout << "Line " << __LINE__ << " : " << #x << " = " << (x) << newl
template <class T>
using VV = vector<vector<T>>;
#define Uni(v) (v).erase(unique((v).begin(), (v).end()), (v).end());

template <typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
  os << "[";
  rep(i, vec.size()) os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
  os << "]";
  return os;
}

template <typename T>
ostream& operator<<(ostream& os, vector<vector<T>>& mat) {
  os << "[";
  rep(i, mat.size()) os << mat[i] << (i + 1 == mat.size() ? "" : ",\n ");
  os << "]";
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x;
  return is;
}

template <typename V, typename H>
void resize(vector<V>& vec, const H head) {
  vec.resize(head);
}

template <typename V, typename H, typename... T>
void resize(vector<V>& vec, const H& head, const T... tail) {
  vec.resize(head);
  for (auto& v : vec) resize(v, tail...);
}
constexpr double EPS = 1e-10;
const int INF = 0x3f3f3f3f;

string tostring(int i, int digit) {
  auto cur = cout.flags();
  stringstream ss;
  ss << setw(4) << setfill('0') << i;
  string ret = ss.str();
  cout.flags(cur);
  return ret;
}

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

#pragma endregion

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int A, B;
  cin >> A >> B;
  if (0 < A && A < 10 && 0 < B && B < 10)
    out(A * B);
  else
    out(-1);
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define No {puts("No");return 0;}
#define Yes {puts("Yes");return 0;}
using namespace std;

typedef long long LL;

inline int read()
{
	char c=getchar();int num=0;
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())
		num=num*10+c-'0';
	return num;
}

const int N=1e6+5;
const int INF=1<<30;

int T,n,maxn,minn;
int a[N];

int main()
{
//	T=read();
//	while(T--)
//	{
		n=read();
		maxn=-INF,minn=INF;
		for(int i=1;i<=n;++i)
		{
			a[i]=read();
			maxn=max(maxn,a[i]),minn=min(minn,a[i]);
		}
		if(maxn-minn>1) No
		if(maxn==minn)
		{
			if(minn==n-1) Yes
			if(2*minn<=n) Yes
			No
		}
		int cnt=0;
		for(int i=1;i<=n;++i)
			if(a[i]==minn)
				++cnt;
		if(minn<cnt||n-cnt<2*(maxn-cnt))
				No
		Yes
//	}
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int calcNumOfCombination(int n, int r){
    int num = 1;
    for(int i = 1; i <= r; i++){
        num = num * (n - i + 1) / i;
    }
    return num;
}
int main() {
    string s;
    cin>>s;
    int flag1 = 1;
    int flag2 = 1;
    if(s.size()%2!=0){
        for(int i=0;i<((s.size()-1)/2);i++){
            if(s[i]!=s[(s.size()-1)/2-1-i]){
                flag1 = 0;
                break;
            }
        }
        for(int j=((s.size()+3)/2-1);j<s.size();j++){
            if(s[j]!=s[s.size()-1-j]){
                flag2 = 0;
                break;
            }
        }
        if(flag1 == 1 && flag2 == 1){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
        
    }
    else{
        printf("No\n");
    }
    
    return 0;
}

Measured memory_bytes: 888
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():

    N=int(input())
    A=list(map(int,input().split()))

    print(sum(A)-N)
resolve()

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
using namespace std;
using ll = long long;
using Int = long long;

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e8;

//少数点表示
//cout <<std::fixed << std::setprecision(14)

int main(){
    cin.tie( 0 ); ios::sync_with_stdio( false );
    int k;
    vector<int> a(5,0);
    cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> k;
    sort(a.begin(),a.end());
    rep(i,5){
        rep(j,5){
            if(abs(a[i]-a[j])>k){
                cout<<":("<<endl;
                return 0;
            }
        }
    }

    cout << "Yay!"<<endl;


}

Measured memory_bytes: 892
import Data.List

solve :: [Int] -> [Int]
solve xs = [minimum xs , maximum xs , sum xs]

main :: IO ()
main  = getLine
    >> getLine
    >>= return . map read . words
    >>= return . solve
    >>= return . intersperse " " . map show
    >>= mapM_ putStr
    >> putStrLn ""

Measured memory_bytes: 11308
#include<bits/stdc++.h>
using namespace std;
int dp[1000000];
int main(){
    int n,k,j;
    cin>>n>>k;
    int h[n+1];
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=0;i<=n;i++){
        dp[i]=-1;
    }
    for(int i=1;i<=n;i++){
    if(i==1){
        dp[i]=0; 
    }
    else if(i==2){
        dp[i]=abs(h[2]-h[1]);
    }
    else{
       int m=dp[i-1]+abs(h[i]-h[i-1]);
        for(j=max(1,i-k);j<i;j++){
         if(dp[j]+abs(h[i]-h[j])<m){
             m=dp[j]+abs(h[i]-h[j]);
         }
        }
        dp[i]=m;
    }
    //cout<<dp[i]<<" "<<i<<endl;
    }
    cout<<dp[n];

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<(int)(r); i++)
#define rep_eq(i,l,r) for(int i=l; i<=(int)(r); i++)
#define all(vec) vec.begin(),vec.end()
#define allr(vec) vec.rbegin(),vec.rend()
using namespace std;

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

using ll=long long;

using vb=vector<bool>;
using vc=vector<char>;
using vs=vector<string>;
using vi=vector<int>;
using vll=vector<ll>;
using vvi=vector<vi>;

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

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

  int N; cin >>N;
  ll ans; cin >>ans;
  rep(i,0,N-1) {
    ll x; cin >>x;
    ans=gcd(ans,x);
  }

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


Measured memory_bytes: 3612
x,y=map(int,raw_input().split())
a=[map(int,raw_input().split()) for i in range(x)]
for i in range(x):
	a[i].append(sum(a[i]))
	for j in range(y+1):
		print a[i][j],
	print
for i in range(y+1):
	print sum([row[i] for row in a]),

Measured memory_bytes: 4304
s = input()
l = len(s)
ans1 = 0
ans2 = 0
#print(s[0])

if int(s[0])==0:
    for i in range(l):
        #print("a")
        n1 = i % 2
        n2 =(i+1) %2
        #print(n1)
        #print(n2)
        if int(s[i])!=n1:
            ans1 += 1
        if int(s[i])!=n2:
            ans2 += 1
else:
    for i in range(l):
        #print("b")
        n1 =(i+1) % 2
        n2 = i % 2
        if int(s[i])!=n1:
            ans1 += 1
        if int(s[i])!=n2:
            ans2 += 1

#print(ans1)
#print(ans2)
if ans1>=ans2:
    print(ans2)
else:
    print(ans1)


Measured memory_bytes: 3188
#include<iostream> 
#include<string> 
#include<vector> 
#include<algorithm> 
#include<cmath> 
using namespace std; 
int main()
{ 
	int y; 
	cin >> y; 
	string s; 
	cin >> s;  
	int n = 0;
	int ans = 0; 
	for (int i = 0; i < s.size(); i++)
	{
		if (s.at(i) == 'D')
		{ 
			n -= 1;
		} 
		else
		{
			n++;
		} 
		if (ans<n)
		{
			ans = n;
		}

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

Measured memory_bytes: 256
use proconio::input;
use proconio::marker::Usize1;
use std::cmp::{Ordering, min};
use std::mem::swap;

fn next_permutation<T>(mut v: Vec<T>) -> Option<Vec<T>>
    where T: Ord {
    let mut t = Vec::new();
    t.push(v.pop().unwrap());
    while let Some(mut lst) = v.pop() {
        if lst.cmp(t.last().unwrap()) != Ordering::Less {
            t.push(lst);
            continue;
        }
        t.sort();
        for i in 0..t.len() {
            if t[i] > lst {
                swap(&mut t[i], &mut lst);
                break;
            }
        }
        v.push(lst);
        return Some(v.into_iter().chain(t).collect::<Vec<T>>());
    }
    None
}

fn main()
{
    input! {
    n:usize,
    m:usize,
    r:usize,
    mut v:[Usize1;r],
    edge:[(Usize1,Usize1,i64);m]
    }
    v.sort();

    let inf = 1i64 << 60;

    let mut cost = vec![vec![inf; n]; n];
    for i in 0..n {
        cost[i][i] = 0;
    }
    for &(a, b, c) in edge.iter() {
        cost[a][b] = c;
        cost[b][a] = c;
    }

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }

    let mut ans = inf;
    loop {
        let mut sum = 0;
        for i in 0..(v.len() - 1) {
            sum += cost[v[i]][v[i + 1]];
        }
        ans = min(ans, sum);
        if let Some(nxt) = next_permutation(v) {
            v = nxt;
        } else {
            break;
        }
    }

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

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

int main(){
  int n, m;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  cin >> m;
  vector<int> b(m);
  for(int i = 0; i < m; i++){
    cin >> b[i];
  }
  for(int i : b){
    if(!binary_search(a.begin(), a.end(), i)){
      cout << 0 << endl;
      return 0;
    }
  }
  cout << 1 << endl;
  return 0;
}



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

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

//pow(llpow,modpow)
template<class T> ll llpow(T x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main(){
    string s;
    cin>>s;
    bool a=false,b=false;
    rep(i,3){
        if(s.at(i)=='A')a=true;
        else b=true;
    }
    if(a&&b)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x)  x.begin(),x.end()
#define vi vector<int>
#define print(x) for(auto it=x.begin();it!=x.end();it++) cout<<*it<<' '; cout<<'\n';
#define in(x,n) for(int e=0;e<n;e++){int y;cin>>y;x.pb(y);}
#define lower(sl)  transform(sl.begin(), sl.end(), sl.begin(), ::tolower); 
//Available in Snips
#define fi(i, x, y)   for (__typeof(x) i = x; i < y; i ++)
#define fir(i, x, y)  for (__typeof(x) i = x; i > y; i --)
#define fv(x)   for (auto itr = x.begin(); itr != x.end(); itr ++)
#define fvr(x)  for (auto itr = x.end() - 1; itr != x.begin() - 1; itr --)

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//code here
	int n;
	cin >> n;
	vi a(n+1,0);
	for(int i=0;i<n-1;i++){
		int x;
		cin >> x;
		a[x] += 1;
	}
	for(int i=1;i<n+1;i++){
		cout << a[i] << endl;
	}
}


Measured memory_bytes: 4000
#include <cstdio>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)

typedef long long ll;

//------------------------------------------------------------------------------
int extgcd(int a, int b, int &x, int &y) {
  int ret = a;
  if (b == 0) {
    x = 1;
    y = 0;
  } else {
    ret = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
  return ret;
}

int mod_inverse(int a, int m) {
  int x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}

//------------------------------------------------------------------------------
const int N_MAX = 200000;

ll fact[N_MAX + 1];

void init_fact(ll n, ll mod) {
  fact[0] = 1;
  FOR(i, 1, n) fact[i] = fact[i - 1] * i % mod;
}

ll mod_comb(ll n, ll k, ll mod) {
  if (n < 0 || k < 0 || n < k) return 0;
  ll a1 = fact[n];
  ll a2 = fact[k] * fact[n - k] % mod;
  return a1 * mod_inverse(a2, mod) % mod;
}

//------------------------------------------------------------------------------
const ll MOD = 1000000007;

int H, W, A, B;

void solve() {
  init_fact(H + W, MOD);
  ll ans = 0;
  REP(i, H - A) {
    ll a = mod_comb(i + B - 1, B - 1, MOD);
    ll b = mod_comb(H - i + W - B - 2, W - B - 1, MOD);
    ans = (ans + (a * b % MOD)) % MOD;
  }
  printf("%lld\n", ans);
}

void input() {
  scanf("%d%d%d%d", &H, &W, &A, &B);
}

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


Measured memory_bytes: 1664
n = int(input())
t = h = 0
for i in range(n):
    cards = list(input().split())
    if cards[0] < cards[1]:
        h += 3
    elif cards[0] > cards[1]:
        t += 3
    else:
        t += 1
        h += 1
print("{} {}".format(t, h))        


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

const int MAXN = 2.1e5;
int N;
int P[MAXN];
int invP[MAXN];
const int S = 1 << 18;
pair<int, int> seg[2][2 * S];
pair<int, int> query(int z, int l, int r) {
	assert(l <= r);
	pair<int, int> ans(1e9,1e9);
	for (int a = S + l, b = S + r + 1; a < b; a /= 2, b /= 2 ){
		if (a & 1) {
			ans = min(ans, seg[z][a]);
			a++;
		}
		if (b & 1) {
			--b;
			ans = min(ans, seg[z][b]);
		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> P[i], invP[P[i]] = i;
	for (int z = 0; z < 2; z++) {
		for (int i = S; i < 2 * S; i++) {
			seg[z][i] = {1e9, 1e9};
		}
	}
	for (int i = 0; i < N; i++) {
		seg[i&1][S+i] = {P[i], i};
	}
	for (int z = 0; z < 2; z++) {
		for (int i = S-1; i > 0; i--) {
			seg[z][i] = min(seg[z][2*i], seg[z][2*i+1]);
		}
	}

	using pii = pair<int, int>;
	using evt = pair<pii, pii>;
	priority_queue<evt, vector<evt>, greater<evt>> pq;
	auto solve = [&](int L, int R) {
		if (L > R) return;
		assert((R - L) & 1);
		int i = query(L&1, L, R-1).second;
		int j = query(!(i&1), i+1, R).second;
		pq.push({{P[i], P[j]}, {L, R}});
	};

	solve(0, N-1);
	while (!pq.empty()) {
		auto e = pq.top(); pq.pop();
		int l = e.second.first, r = e.second.second;
		int i = invP[e.first.first], j = invP[e.first.second];
		cout << P[i] << ' ' << P[j] << ' ';
		solve(l, i-1);
		solve(i+1, j-1);
		solve(j+1, r);
	}
	cout << '\n';

	return 0;
}


Measured memory_bytes: 12020
#include<bits/stdc++.h>
using namespace std;
int a[200005],n,b[200005];
int c[200005],d[200005];
long long k;
int t=1;
int main()
{
  memset(c,0,sizeof(c));
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {
  	cin>>a[i];
    b[d[a[i]]]=i;
    if(c[a[i]]==0)
	  c[a[i]]=i;
	b[i]=c[a[i]];
	d[a[i]]=i;
  }
  if(n>1)
  {
    int p=1;
    while(1)
	{
      if(b[p]<=p)
	    t++;
      p=b[p];
      if(p==n)
	    break;
      p++;
    }
    k%=t;
    p=1;
    t=1;
    while(t<=k)
	{
	  if(b[p]<=p)
		t++;
	  if(t<=k)
	  {
		p=b[p];
		p++;
	  }
	}
    for(int i=p;i<=n;i++)
      if(b[i]>i)
	    i=b[i];
      else 
        cout<<a[i]<<" ";
    }
    else
    { 
      if(k%2)
        cout<<a[1];
    } 
    return 0;
}

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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const vector<int> bs = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2, 1, 0};

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    int m = bs.size(), l = 0, r = 0;
    vector<int> p, q;
    while (l < m && bs[l] != a) l++, r++;
    while (r < m && bs[r] != b) p.emplace_back(bs[r++]);
    r = ++l;
    while (l < m && bs[l] != a) l++, r++;
    while (r < m && bs[r] != b) q.emplace_back(bs[r++]);
    if (int(p.size()) > int(q.size())) swap(p, q);
    for (int j = 0; j < int(p.size()); j++) {
      cout << p[j] << " ";
    }
    cout << b << endl;
  }  
  
  return 0;
}


Measured memory_bytes: 3128
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[200009],c[200009],ans=0;
void add(int x,int d)
{
    while(x<=n)
    {
        c[x]+=d;
        x+=x&-x;
    }
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=x&-x;
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int tmp=query(a[i]-1);
        if(!tmp)
            ans++;
        add(a[i],1);
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

ll N, u, v;
vector<ll>path[101010];
ll U[101010], V[101010], parent[101010];
ll V2[101010];
ll ha[101010];

void dep(){
    rep1(i, N)U[i] = INF;
    rep1(i, N)V[i] = INF;
    rep1(i, N)parent[i] = -1;
    queue<ll>Q;
    priority_queue<P>PQ;
    U[u] = 0;
    Q.push(u);
    for(; !Q.empty(); Q.pop()){
        ll idx = Q.front();
        rep(i, path[idx].size()){
            ll to = path[idx][i];
            if(U[to] < INF)continue;
            U[to] = U[idx] + 1;
            Q.push(to);
        }
    }
    V[v] = 0;
    Q.push(v);
    for(; !Q.empty(); Q.pop()){
        ll idx = Q.front();
        ll flg = 1;
        rep(i, path[idx].size()){
            ll to = path[idx][i];
            if(V[to] < INF)continue;
            V[to] = V[idx] + 1;
            Q.push(to);
            parent[to] = idx;
            flg = 0;
        }
        if(flg){
            PQ.push(P(V[idx], idx));
            ha[idx] = 1;
        }
    }
    for(; !PQ.empty(); ){
        ll d = PQ.top().first;
        ll idx = PQ.top().second;
        PQ.pop();
        if(V2[idx])continue;
        V2[idx] = d;
        ll to = parent[idx];
        if(to < 0)continue;
        if(V2[to])continue;
        if(V[to] > V[idx])continue;
        PQ.push(P(V2[idx], to));
    }
}

int main(){

    cin >> N >> u >> v;
    rep1(i, N - 1){
        ll a, b;
        cin >> a >> b;        
        path[a].push_back(b);
        path[b].push_back(a);
    }
    dep();
    // rep1(i, N)cout << i << " : " << U[i] << ", " << V[i] << ", " << V2[i] << endl;

    ll cnt = 0;
    ll idx = u;
    for(;;){
        ll p = parent[idx];
        if(ha[idx] && V[p] <= cnt)break;
        if(ha[idx] && V[p] <= cnt + 1){
            cnt++;
            break;
        }
        if(ha[idx]){
            idx = p;
            cnt++;
            continue;
        }
        if(V[p] > cnt + 1){
            idx = p;
            cnt++;
            continue;
        }
        ll tmp = -1;
        rep(i, path[idx].size()){
            ll to = path[idx][i];
            if(V2[to] == V2[idx] && V[to] > V[idx])tmp = to;
        }
        idx = tmp;
        cnt++;

    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 11328
#include<stdio.h>
int main(void){
  int N, D, a;
  scanf("%d %d",&N, &D);
  if(N%(D*2+1) == 0){a=N/(D*2+1);}
  else{a=N/(D*2+1)+1;}
  printf("%d", a);
  return 0;
}


Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); } }_io;
typedef long long ll; typedef long double db;

int main()
{
	string str;
	cin >> str;

	int len = (int)str.size();

	int sum = 0;
	for (int i = 0; i < len; ++i)
	{
		sum += str[i] - '0';
	}

	if (sum % 9 == 0) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 3724
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl
#define show2(a, n, m) rep(i, n) { rep(j, m) {cout << a[i][j] << ' ';} cout << endl;} 
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef long double ld;

const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

int main() {
//	cout << fixed << setprecision(15);
	int n, m;
	cin >> n >> m;
	vi a(n);
	rep(i, n) cin >> a[i];
	int sa = 0;
	rep(i, n) sa += a[i];
	sort(a.begin(), a.end(), greater<int>());
	string ans;
	if(a[m-1] * 4 * m >= sa) ans = "Yes";
	else ans = "No";
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int s;
  double w,h;
  while(scanf("%d,%lf,%lf",&s,&w,&h)!=EOF){
    double BMI = w / (h*h);
    if(BMI>=25) printf("%d\n",(int)s);
  }
  return 0;
}

Measured memory_bytes: 2600
/* Fairy dandy tickling the fancy of his lady friend */

#include <iostream>

#include <vector>

#include <algorithm>

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

#define rep(i,a,b) for(int i=int(a); i<int(b); i++)

#define rip(i,a,b) for(int i=(int)a; i>=(int)b; i--)

#define pb push_back

#define mp make_pair

#define fst first

#define snd second

#define sz(x) int(x.size())

#define all(v) (v).begin(), (v).end()

#define trace(x) cerr << #x << ": " << x <<endl;



using namespace std;



typedef long long int lli;

typedef pair<lli, lli> ii;

typedef vector<int> vi;

typedef vector<ii> vii;



int main(){

    fastio;

	int n, a, b; cin>>n>>a>>b;
	cout<< min(n*a, b) << endl;

    return 0;

}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
#include<map>
#include<deque>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define erep(i, n) for (int i = 0; i <= (int)(n); i++)
ll MOD = 1000000007;

int main() {
    ll n, k; cin >> n >> k;
    ll ans = 0;
    for (ll i = k; i <= n + 1; i++) {
        ll start = i * (i - 1) / 2;
        ll end = (2 * n - i + 1) * i / 2;
        ans = (ans + end - start + 1) % MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3140
#define _GLIBCXX_DEBUG
#include <iostream>
#include <string>
#include <algorithm>

int main(int argc, char* argv[])
{
  std::string s, t, ans;
  std::cin >> s >> t;

  std::string::iterator it;
  for (it = s.begin(); it != s.end(); it++) {
    int idx = std::distance(s.begin(), it);
    ans += s[idx];
    ans = idx < (int)t.size() ? ans + t[idx] : ans;
  }

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iomanip>

#include <map>
#include <set>
#include <queue>
#include <stack>

#define ALL(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdbl vector<double>
#define vstr vector<string>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	ll N,K;
	cin >> N >> K;

	ll c[100001] = {};

	rep(i,N){
		ll a,b;
		cin >> a >> b;
		c[a] += b;
	}

	ll pos = 0;
	ll nowK = K;
	while(true){
		nowK -= c[pos];
		if(nowK <= 0) {
			cout << pos << endl;
			return 0;
		}
		pos++;
	}
}

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

int N, M;
static int par[100000], Rank[100000];

void init(int x) {
	for (int i = 0; i < N; i++) {
		par[i] = i;
		Rank[i] = i;
	}
}

int root(int x) {
	if (par[x] == x) return x;
	return par[x] = root(par[x]);
}

bool same(int x, int y) {
	return par[x] == par[y];
}

void unite(int x, int y) {
	x = root(x), y = root(y);
	if (Rank[x] < Rank[y]) par[x] = y;
	else {
		par[y] = x;
		if (Rank[x] == Rank[y]) Rank[x]++;
	}
}

int main() {
	cin >> N >> M;
	map<int, int> mp;
	int ans = 0;
	init(N);
	for (int i = 0; i < M; i++) {
		int X, Y, Z;
		cin >> X >> Y >> Z;
		unite(X, Y);
	}
	for (int i = 0; i < N; i++) {
		mp[root(i)] = 1;
	}
	for (auto it = mp.begin(); it != mp.end(); it++) {
		ans++;
	}
	cout << ans;
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);++i)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int gcd(int a,int b) { return b ? gcd(b,a%b) : a;}
int lcm(int a,int b) { return a/gcd(a,b)*b;}
void printb(unsigned int v) {
  unsigned int mask = (int)1 << (sizeof(v) * CHAR_BIT - 1);
  do putchar(mask & v ? '1' : '0');
  while (mask >>= 1);
}
void putb(unsigned int v) {putchar('0'), putchar('b'), printb(v), putchar('\n');}
#define ALL(W) (W).begin(),(W).end()

signed main(){
  int c[3][3]={};
  rep(i,3)rep(j,3) cin >> c[i][j];
  rep(i,2){
    if(c[i][0]-c[i][1]==c[i+1][0]-c[i+1][1]);
    else{
      cout << "No" << endl;
      return 0;
    }
    if(c[i][1]-c[i][2]==c[i+1][1]-c[i+1][2]);
    else{
      cout << "No" << endl;
      return 0;
    }
    if(c[0][i]-c[1][i]==c[0][i+1]-c[1][i+1]);
    else{
      cout << "No" << endl;
      return 0;
    }
    if(c[1][i]-c[2][i]==c[1][i+1]-c[2][i+1]);
    else{
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


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

using namespace std;

#define ull unsigned long long int
#define ll long long int 

template <typename T>std::string NumberToString ( T Number ){std::ostringstream ss; ss << Number;return ss.str(); } // Usages NumberToString(3)
template <typename T>T StringToNumber ( const string &Text ){istringstream ss(Text);T result;return ss >> result ? result : 0;} // StringToNumber<int>("3")

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    string str;
    cin >> str;
     if(str[3] == str[2] && str[5] == str[4]) cout << "Yes" << endl;
     else cout << "No" << 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 REP(i,n) for(int i=1;i<=n;i++)
typedef long long ll;

int main(){
	ll n;
	cin >> n;
	vector<ll> d(5,0);
	rep(i,n){
		string s;
		cin >> s;
		if(s[0] == 'M') d[0]++;
		if(s[0] == 'A') d[1]++;
		if(s[0] == 'R') d[2]++;
		if(s[0] == 'C') d[3]++;
		if(s[0] == 'H') d[4]++;
	}
	
	ll ans = 0;
	
	ans += d[0]*d[1]*d[2];
	ans += d[0]*d[1]*d[3];
	ans += d[0]*d[1]*d[4];
	ans += d[0]*d[2]*d[3];
	ans += d[0]*d[2]*d[4];
	ans += d[0]*d[3]*d[4];
	ans += d[1]*d[2]*d[3];
	ans += d[1]*d[2]*d[4];
	ans += d[1]*d[3]*d[4];
	ans += d[2]*d[3]*d[4];
	
	cout << ans << endl;
	
    return 0;
}



Measured memory_bytes: 256
N = int(input())
monster = list(input().split())
hero = list(input().split())
monster = [int(monster[i]) for i in range(N+1)]
hero = [int(hero[i]) for i in range(N)]

count = 0
for i in range(N):
    count += min(monster[i+1] + monster[i], hero[i])
    monster[i+1] = min(monster[i+1], max(monster[i+1] - (hero[i] - monster[i]), 0))

print(count)

Measured memory_bytes: 21824
#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;

const int maxn = 2e2 + 5;
LL dis[maxn][maxn];
LL sum,w,inf = 1e14;
int n,m,r,x,y,a[10];

void Init(){
	sum = inf;
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++){
			if(i == j) dis[i][j] = 0,dis[j][i] = 0;
			else dis[i][j] = inf,dis[j][i] = inf;
		}
	}
}

void floyd(){//求任意两点最短路。
	for(int k = 1;k <= n;k++){
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				if(dis[i][k] + dis[k][j] < dis[i][j]){
					dis[i][j] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
}

void slove(){
	sort(a + 1,a + 1 + r);  
    while (next_permutation(a + 1,a + 1 + r)){//求a[i]的全排列。
    	LL all = 0;
		for(int i = 2;i <= r;i++) all += dis[a[i]][a[i - 1]];
		sum = min(sum,all);
	}
}

int main(){
	scanf("%d %d %d",&n,&m,&r);
	Init(); 
	for(int i = 1;i <= r;i++) scanf("%d",&a[i]);
	for(int i = 1;i <= m;i++){
		scanf("%d %d %lld",&x,&y,&w);
		dis[x][y] = w,dis[y][x] = w;
	}
	floyd();
	slove();
	printf("%lld",sum);
}

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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i= 0; i < N; i++) cin >> A[i];
  
  int next = 1;
  for (int a : A) {
    if (a == next) next++;
  }
  
  if (next == 1) {
    cout << -1 << endl;
    return 0;
  }
  cout << N - (next -1) << endl;
  
}

Measured memory_bytes: 1024
#ifdef Prateek
  #include "Prateek.h"
#else
  #include <bits/stdc++.h>
  using namespace std;
  #define debug(...) 42
#endif
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   cin >> n;
   int ans = 0;
   f(i,0,n){
      int x;
      cin >> x;
      if(i % 2 == 0){
         if(x & 1) ans++;
      }
   }
   cout << ans;
   return 0;
} 


Measured memory_bytes: 3608
#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 int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int cnt[50][25];

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int pos = -1;
		for(int j = 0; j < s.length(); j++) {
			if(s[j] == '.') {
				pos = j;
				break;
			}
		}
		int cnt = 9;
		if(pos != -1) {
			for(int j = pos + 1; j < s.length(); j++) {
				cnt--;
			}
		}
		while(cnt--) {
			s += '0';
		}
		a[i] = 0;
		for(auto it : s) {
			if(it != '.') {
				a[i] = 10 * a[i] + (it - '0');
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		int x = 0, y = 0;
		int tmp = a[i];
		while(tmp % 2 == 0) {
			tmp /= 2;
			x++;
		}
		while(tmp % 5 == 0) {
			tmp /= 5;
			y++;
		}
		for(int j = max(0LL, 18 - x); j < 50; j++) {
			for(int k = max(0LL, 18 - y); k < 25; k++) {
				ans += cnt[j][k];
			}
		}
		cnt[x][y]++;
	}
	cout << ans;

	return 0;
}

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;

void solve() {
    i64 n, k;
    cin >> n >> k;
    vector<i64> a(n);
    for (auto& e : a) cin >> e;
    i64 asum = reduce(all(a));
    vector<i64> c(n);
    for (i64 i = 0; i < n; i++) c[i] = k * a[i] / asum;
    k -= reduce(all(c));

    auto f = [](p64 x, p64 y) { return x.first * y.second < y.first * x.second; };
    priority_queue<p64, vector<p64>, decltype(f)> q(f);
    for (i64 i = 0; i < n; i++) q.emplace(a[i], c[i] + 1);
    for (i64 i = 0; i < k; i++) {
        p64 t = q.top(); q.pop();
        t.second++;
        q.push(t);
    }

    auto& [ ansl, ansc ] = q.top();
    cout << (ansl + ansc - 1) / ansc << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 10536
#include<iostream>
#include<algorithm>
#include<functional>
#include<unordered_map>
#include<cmath>

using namespace std;

//int mod_num_counter[2030];


int main()
{
  string s, t ,t2;
  cin >> s >> t;
  int len = s.length();
  t2 = t.substr(0, len);
  
  string ans;
  if (s == t2)
  {
    ans = "Yes";
  }
  else
  {
    ans = "No";
  }
  
  cout << ans << endl;
    
  return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<char,int>;


int main(){
   string s;
   cin >> s;
   
   //連続する2文字
   rep(i, s.size() - 1){
       if(s[i] == s[i+1]){
           cout << i + 1 << " " << i + 2 << endl;
           return 0;
       }
   }

   //一個飛ばし
   for(int i = 0; i < s.size() - 2; i++){
       if(s[i] == s[i+2]){
           cout << i + 1 << " " << i + 3 << endl;
           return 0;
       }
   }
   cout << -1 << " " << -1 << endl;
}



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

using ll = long long;

class union_find {
public:
    union_find(int n)
        : par_(n, -1)
    {}
    void init(int n) {
        par_.assign(n, -1);
    }

    int root(int x) {
        return par_[x] < 0 ? x : par_[x] = root(par_[x]);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) {
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int size(int x) {
        return -par_[root(x)];
    }

private:
    std::vector<int> par_;
};

struct edge {
    int u, v, cost, id;
    bool operator<(const edge& that) const {
        return cost < that.cost;
    }
};

using edges = vector<edge>;
using graph = vector<edges>;

void add_edge(graph& g, int from, int to, int cost, int id) {
    g[from].push_back(edge{from, to, cost, id});
    g[to].push_back(edge{to, from, cost, id});
}

int main() {
    int n, m; cin >> n >> m;
    vector<ll> x(n), sum(n);
    for(int i = 0; i < n; ++i) {
        cin >> x[i];
        sum[i] = x[i];
    }
    edges es(m);
    graph g(n);
    for(int i = 0; i < m; ++i) {
        cin >> es[i].u >> es[i].v >> es[i].cost;
        es[i].id = i;
        es[i].u--, es[i].v--;
        add_edge(g, es[i].u, es[i].v, es[i].cost, i);
    }
    sort(begin(es), end(es));

    vector<bool> cand(m);
    union_find uf(n);
    for(int i = 0; i < m; ++i) {
        int u = uf.root(es[i].u), v = uf.root(es[i].v);
        if(uf.unite(es[i].u, es[i].v)) {
            const ll s = sum[u] + sum[v];
            sum[u] = sum[v] = s;
        }
        u = uf.root(es[i].u);
        if(es[i].cost <= sum[u]) {
            cand[es[i].id] = true;
        }
    }

    reverse(begin(es), end(es));
    vector<bool> used(m), visited(n);
    function<void(int, int)> dfs = [&] (int v, int ub) {
        visited[v] = true;
        for(auto const& e : g[v]) {
            const int to = e.v;
            if(e.cost <= ub) used[e.id] = true;
            if(visited[to] || e.cost > ub) continue;
            dfs(to, ub);
        }
    };
    for(int i = 0; i < m; ++i) {
        if(cand[es[i].id] && !visited[es[i].u]) {
            dfs(es[i].u, es[i].cost);
        }
    }

    cout << count(begin(used), end(used), false) << endl;
}


Measured memory_bytes: 17536
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;


int main(){
  string s,t; cin >> s >> t;
  int n = s.size();
  int m = t.size();

  vector<string> ans;

  for (int i = 0; i+m <= n; i++) {
    string tmp = s.substr(i, m);
    bool ok = true;
    rep(j, m) if(tmp[j] != '?' && tmp[j] != t[j]) ok = false;
    if(!ok) continue;
    tmp = s.substr(0,i) + t + s.substr(i+m);
    rep(j, n) if(tmp[j] == '?') tmp[j] = 'a';
    ans.pb(tmp);
  }
  if(ans.empty()){
    std::cout << "UNRESTORABLE" << '\n';
    return 0;
  }
  sort(all(ans));

  std::cout << ans[0] << '\n';
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace ABC104_B
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var flag1 = s.Contains("A") && s.Where(x => x == 'C').Count() == 1 && s[1] != 'C' && s[s.Length - 1] != 'C';
            if (!flag1)
            {
                Console.WriteLine("WA");
                return;
            }

            s = s.Replace("A", "");
            s = s.Replace("C", "");

            var flag2 = true;
            for (int i = 0; i < s.Length; i++)
            {
                if (char.IsUpper(s[i])) flag2 = false;
            }
            Console.WriteLine(flag2 ? "AC" : "WA");

        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int h, a;
    cin >> h >> a;
    cout << (h + a - 1) / a << endl;
}   


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

int main(){
    string sd,t; cin >> sd >> t;
    int ssd = sd.size(), st = t.size();
    if(ssd<st){
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    string s = "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz";
    for(int i=0;i+st<=ssd;i++){
        bool NG = false;
        for(int j=i;j<i+st;j++){
            if(sd.at(j)!= '?' && sd.at(j)!=t.at(j-i)){
                NG = true;
                break;
            }
        }
        if(NG == false){
            string kouho = "";
            for(int j=0;j<ssd;j++){
                if(i<=j && j<i+st){
                    kouho.push_back(t.at(j-i));
                }else if(sd.at(j) == '?'){
                    kouho.push_back('a');
                }else{
                    kouho.push_back(sd.at(j));
                }                
            }
          s = min(s,kouho);            
        }
    }
    if(s == "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"){
        cout << "UNRESTORABLE" << endl;
    }else{
    	cout << s << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

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

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

#define SUM(vec) accumulate(all(vec),0LL) // 配列の中身を全部足す
template<typename T>void print(T&& x){cout<<x<<endl;}// 改行付き出力
ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
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 ctoi(char c){return c-'0';}



// TODO: write
int main() { 
  int A,B,M;cin>>A>>B>>M;
  vector<int> a(A),b(B);
  rep(i,A)cin>>a[i];
  rep(i,B)cin>>b[i];
  
  vector<int> tmp;
  
  rep(i,M){
    int x,y;cin>>x>>y;
    int c;cin>>c;
    tmp.pb(a[x-1]+b[y-1] - c);
  }
  sort(all(a));
  sort(all(b));
  tmp.pb(a[0]+b[0]);
  sort(all(tmp));
  print(tmp[0]);
  return 0;
}



Measured memory_bytes: 1660