akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
const double EPS = 1e-10;
class Team {
public:
	int order, win, lose;
	char name;
	bool operator<(const Team &other) {
		if (win != other.win)return win > other.win;
		else if (lose != other.lose)return lose < other.lose;
		else return order < other.order;
	}
};
signed main() {
	int n;
	while (cin >> n, n) {
		vector<Team>v(n);
		rep(i, 0, n) {
			char c; cin >> c;
			v[i].name = c; v[i].order = i;
			rep(j, 0, n - 1) {
				int x; cin >> x;
				if (x == 0)v[i].win++;
				else if (x == 1)v[i].lose++;
			}
		}
		sort(all(v));
		rep(i, 0, n)cout << v[i].name << endl;
	}
	return 0;
}

Measured memory_bytes: 3112
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

	int a[5];
	for(int i = 0; i < 5; i++)
		cin>>a[i];
	
	sort(a,a+5,greater<int>());
	
	for(int i = 0; i < 5; i++){
		cout<<a[i];
		if(i==4)
			cout<<endl;
		else
			cout<<" ";
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <queue>
#include <set>
#include <vector>
#include <cmath>
#include <bitset>
#include <functional>
#include <limits>
#include <map>
using namespace std;

typedef long long ll;
#define rep1(i, n) for(ll i = 1; i <=(ll)(n); i++)
#define rep0(i, n) for(ll i = 0; i <=(ll)(n); i++)

ll pow(ll a, ll n) { //compute a^n with o(logn)
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

ll pow(ll a, ll n, ll mod) { //compute a^n (mod mod) with o(logn)
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

const int MAX = 199;
const int MOD = 1000000007;
ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//順列計算
ll PER(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[n - k] % MOD) % MOD;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> P(N), C(N);
    rep0(i, N-1) cin >> P[i], --P[i];
    rep0(i, N-1) cin >> C[i];
    ll INF = 1e18;
    ll ans = -INF;
    rep0(i, N-1) {
        int v = i;
        ll cycle_sum = 0;
        int cycle_cnt = 0;
        while (true) {
            cycle_cnt++;
            cycle_sum += C[v];
            v = P[v];
            if (v == i) break;
        }
        ll path = 0;
        int cnt = 0;
        while (true) {
            cnt++;
            path += C[v];
            if (cnt > K) break;
            int num = (K - cnt) / cycle_cnt;
            ll score = path + max(0ll, cycle_sum) * num;
            if (ans < score) ans = score;
            v = P[v];
            if (v == i) break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3216
# coding: utf-8

N = int(input())

old = -1
count = 0
while (N > 0):
    new = N % 10
    if (new == old):
        count += 1
    else:
        count = 1
    if count > 2:
        print("Yes")
        break
    old = new
    N //= 10
else:
    print("No")

Measured memory_bytes: 3060
N = int(input())
a = []
b = []
C = 0
A = list(map(int,input().split()))
for i in range(N):
    if i%2 == N%2:
      a.append(A[i])
    else:
      b.append(A[i])
b.reverse()
ans = ""
for i in range(len(b)):
  ans += str(b[i])
  ans += " "
for i in range(len(a)):
  ans += str(a[i])
  if i != len(a)-1:
    ans += " "
print(ans)

Measured memory_bytes: 25876
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            int ans = 0;
            switch(s)
            {
                case "SSS":
                    ans = 0;
                    break;
                case "SRS":
                    ans = 1;
                    break;
                case "SSR":
                    ans = 1;
                    break;
                case "SRR":
                    ans = 2;
                    break;
                case "RSS":
                    ans = 1;
                    break;
                case "RRS":
                    ans = 2;
                    break;
                case "RSR":
                    ans = 1;
                    break;
                case "RRR":
                    ans = 3;
                    break;
            }
            Console.WriteLine(ans);
        }
    }
    
}

Measured memory_bytes: 25932
#include <bits/stdc++.h>
using namespace std;
int main(){
    int k,n;
    scanf("%d %d",&n,&k);
    int p[n];
    int t=INT_MAX;
    int o=0;
    int e=0;
    for(int i=0;i<n;i++)scanf("%d",&p[i]);
    for(int j=0;j<k;j++){
        for(int i=0;i<n;i++){
            if(p[i]<t){
                t=p[i];
                o=i;
            }
        }
        e+=p[o];
        p[o]=INT_MAX;
        o=0;
        t=INT_MAX;
    }
    printf("%d",e);
    return 0;
}

Measured memory_bytes: 3828
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>

using namespace std;
typedef long long ll;

ll a, b, c, d, e, k;

int main() {
	cin >> a;
	cin >> b;
	cin >> c;
	cin >> d;
	cin >> e;
	cin >> k;
	if (e - a > k) {
		cout << ":(" << endl;
	}
	else {
		cout << "Yay!" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main () {
	int x, n, a, b, c, y=0;
	while (1) {
		cin >> n >> x;
		if (n == 0 && x == 0) break;
		for (a=1;a<=n;a++) {
			for (b=1;b<=n;b++) {
				for (c=1;c<=n;c++) {
					if (a!=b && b!=c && c!=a && a+b+c==x) y++;
				}
			}	
		}
		cout << y/6 << endl;
		y=0;
	}
}


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

int main() {
  
  int k, x;
  cin >> k >> x;
  
  if(500*k >= x)  cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

struct Prime {
  long long n = 0;
  vector<bool> ch;
  vector<long long> ary;
  Prime(long long N = 2000000) {
    ch.resize(N + 1);
    ch[0] = ch[1] = 1;
    for (int i = 2; i <= N; ++i)
      if (!ch[i]) {
        ary.push_back(i);
        for (int j = 2; (long long)i * j <= N; ++j) ch[i * j] = 1;
      }
    n = ary.size();
  }
  inline const bool isprime(int n) { return !ch[n]; }
  inline const long long &operator[](int k) const {
    return k < n ? (ary[k]) : -1;
  }
};

int n;
vector<int> a;
set<int> st;
Prime pr;

int solve();

int main() {
  cin >> n;
  long long g = 0;
  bool ch = 0;
  for (int i = 0; i < n; ++i) {
    int p;
    cin >> p;
    g = gcd(p, g);
    if (pr.isprime(p)) {
      if (st.find(p) != st.end()) {
        ch = 1;
      }
      st.insert(p);
    } else
      a.push_back(p);
  }
  int res = solve();
  if (ch) {
    if (g == 1)
      cout << "setwise coprime" << endl;
    else
      cout << "not coprime" << endl;
  } else {
    if (res)
      cout << "pairwise coprime" << endl;
    else if (g == 1)
      cout << "setwise coprime" << endl;
    else
      cout << "not coprime" << endl;
  }
  return 0;
}

int solve() {
  n = a.size();
  for (int i = 0; i < n; ++i) {
    long long p = a[i];
    for (long long j = 2; j * j <= p; ++j)
      if (p % j == 0) {
        if (st.count(j)) return 0;
        while (p % j == 0) p /= j;
        st.insert(j);
      }
    if (p > 1) {
      if (st.count(p)) return 0;
      st.insert(p);
    }
  }
  return 1;
}

Measured memory_bytes: 11624
#include<iostream>
#include<string>
#include<vector>
#include<boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int infinit;
using namespace std;
#define END return 0
int main()
{

	int a, b;
	cin >> a >> b;
	if (a < b * 2)
	{
		cout << 0 << endl;
		END;
	}

	cout << a - b * 2 << endl;

	END;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define FORR(x, arr) for(auto& x:arr)
#define ITR(x, c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;
typedef pair<int, int> P;

int n;
string s[605], t[305];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n;
	FOR(i, n) {
		cin >> s[i];
		s[n+i] = s[i];
	}
	int ret = 0;
	FOR(i, n) {
		FOR(j, n) t[j] = s[i+j];
		bool ok = true;
		FOR(x, n) {
			FOR(y, n) {
				if (t[x][y] != t[y][x]) ok = false;
			}
		}
		if (ok) ret += n;
	}
	cout << ret << endl;
	return 0;
}

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

using namespace std;

int a, b;

int main(void)  {
	cin >> a >> b;
	for(int i = 1; i <= 3; ++ i) if (a * b * i % 2 == 1) return 0 * puts("Yes");
	puts("No");
	
	return 0;
}

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

struct Node {
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;

Node * find(Node *u, int k) {
    while(u != NIL && k != u->key) {
        if (k < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while(x != NIL) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;
    if (y == NIL) {
        root = z;
    } else {
        if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

void inorder(Node *u) {
    if (u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}
void preorder(Node *u) {
    if (u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main() {
    int n, i, x;
    string com;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        cin >> com;
        if (com[0] == 'f') {
            scanf("%d", &x);
            Node *t = find(root, x);
            if (t != NIL) printf("yes\n");
            else printf("no\n");
        } else if (com == "insert"){
            scanf("%d", &x);
            insert(x);
        } else if (com == "print") {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


Measured memory_bytes: 22032
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sstream>

using namespace std;

int main(){
    int K, X;
    cin >> K >> X;
    int start, end;

    start = max(X-K+1, -1000000);
    end = min(X+K-1, 1000000);

    for(int i = start; i < end; ++i){
        cout << i << " ";
    }
    cout << end << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for ( int i = 0; i < (n); ++i )
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long int;
const long long int INF = 1001001001001001LL;
const int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;


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

    int n, k;
    cin >> n >> k;
    queue<double> q;
    vector<double> e(n-k+1, 0);

    rep(i,k) {
        double x;
        cin >> x;
        double ex = x / 2.0 + 0.5;
        q.push(ex);
        e[0] += ex;
    }

    rep(i, n-k) {
        double ex = q.front(); q.pop();
        double y; cin >> y;
        double ey = y / 2.0 + 0.5;
        q.push(ey);
        e[i+1] = e[i] - ex + ey;
    }

    cout << *max_element( all(e) ) << endl;
    return 0;
}

Measured memory_bytes: 1920
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())
xy = [[int(i) for i in readline().split()] for _ in range(n)]

p = sum(xy[0])%2
for x,y in xy:
    if p != (x+y)%2:
        print(-1)
        exit()

d = [2**i for i in range(38,-1,-1)]
if not p: d += [1]

print(len(d))
print(*d)

for x,y in xy:
    ans = []
    xx = yy = 0
    for di in d:
        dx = x-xx
        dy = y-yy
        if dy > dx:
            if dy > -dx:
                ans.append("U")
                yy += di
            else:
                ans.append("L")
                xx -= di
        else:
            if -dy > dx:
                ans.append("D")
                yy -= di
            else:
                ans.append("R")
                xx += di
    print("".join(ans))







    

Measured memory_bytes: 3316
#include <bits/stdc++.h>
 
#define forn(i, n) for (llong i = 0ll; i < (llong) n; ++i)
#define fornn(i, l, r) for (llong i = (llong) l; i < (llong) r; ++i)
#define size(x) ((int) (x.size()))
 
using namespace std;
 
typedef long long llong;
const llong inf = (llong) 1e+9 + 7ll;
const llong linf = (llong) 1e+18 + 7ll;
const long double eps = (long double) 1e-9;
const long double pi = acosl((long double) -1.0);
const int alph = 26;

mt19937 mrand(random_device{} ()); 

template<typename T, typename U> inline llong umin(const T& a, const U& b) { return a < b ? a : b; }
template<typename T, typename U> inline llong umax(const T& a, const U& b) { return a > b ? a : b; }
 
static char buff[(int) 2e6 + 17]; // reads std::string
const int maxn = (int) 2e5 + 17;

int n;
int a[maxn];

bool read()
{
	if (scanf("%d", &n) != 1)
		return false;

	forn (i, n)
		scanf("%d", a + i);

	return true;
}

void solve()
{
	deque<int> d;

	forn (i, n)
		if (i & 1 ^ 1)
			d.push_back(a[i]);
		else
			d.push_front(a[i]);

	if (n & 1)
		reverse(d.begin(), d.end());

	for (auto i : d)
		printf("%d ", i);

	printf("\n");
}

int main()
{
#if SEREZHKA
	freopen("file.in", "r", stdin);
#endif

	while (read())
		solve();

	return 0;
}


Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int *h = new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>h[i];
    }
    int *dp = new int[n];
    dp[0] = 0;
    dp[1] = abs(h[1]-h[0]);
    for(int i=2;i<n;i++)
    {
        int mini = INT_MAX;
        for(int j=i-1;(j>=i-k&&j>=0);j--)
        {
            if((abs(h[j]-h[i])+dp[j])<mini)
            {
                mini = abs(h[i]-h[j])+dp[j];
            }
        }
        dp[i] = mini;
    }
    cout<<dp[n-1];
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(){

    int H, N;
    cin>>H>>N;
    int arr[N];
    int i;
    int sum = 0, res = 0;
    for(i=0; i<N; i++){
        cin>>arr[i];
    }

    for(i=0; i<N; i++){
        sum += arr[i];
    }

    res = H - sum;

    if(res > 0){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }




}


Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int N;
    cin >> N;
    int arr[N];
    long long dp[N][N];
    for (int i = 0 ; i < N ; i++)
        cin >> arr[i];
    for (int k = 0 ; k < N ; k++){
        for (int i = 0 ; i < N - k ; i++){
            int l = i , r = i + k;
            if (l == r){
                if (N & 1)//jika N ganjil maka giliran penambah
                    dp[l][l] = arr[l];
                else
                    dp[l][l] = -arr[l];
            }
            else if ((l + N - 1 - r & 1) == 0)//jika genap maka langkahnya penambah
                 dp[l][r] = max(dp[l + 1][r] + arr[l] , dp[l][r - 1] + arr[r]);
            else //giliran ganjil , giliran pengurang
                dp[l][r] = min(dp[l + 1][r] - arr[l] , dp[l][r - 1] - arr[r]);
        }
    }
    cout << dp[0][N - 1] << endl;
}


Measured memory_bytes: 49816
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iostream>


using namespace std;

int main()
{
	int n;
	int nums[101];
	memset(nums, 0, sizeof(nums));
	int m = 0;
	while (scanf("%d", &n) != EOF)
		m = max(m, ++nums[n]);
	for (int i = 1; i < 101; ++i)
	{
		if (nums[i] == m)
			printf("%d\n", i);
	}

	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		int ta,tb;
		if(i%2==0){
			ta=a/2;
			tb=b+a/2;
		}else{
			tb=b/2;
			ta=a+b/2;
		}a=ta;b=tb;
	}
	printf("%d %d\n",a,b);
}


Measured memory_bytes: 128
import sys
input = sys.stdin.readline
H,W = [int(i) for i in input().split()]
nes = ['0'] * H
for i in range(H) :
    li = list(input())
    nes[i] = li
yoko = [False] * H
tate = [False] * W
for i in range(H) :
    for j in range(W) :
        if nes[i][j] == "#" :
            yoko[i] = True
            tate[j] = True
for i in range(H) :
    if yoko[i] :
        for j in range(W) :
            if tate[j] :
                print(nes[i][j],end = '')
        print()

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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;
int x[11000],y[11000];
signed main() {
    cin>>N>>M>>X>>Y;
    for(int i=0;i<N;i++)cin>>x[i];
    for(int j=0;j<M;j++)cin>>y[j];
    sort(x,x+N);
    sort(y,y+M);
    for(int i=-200;i<=200;i++){
        if(X<i&&i<=Y){
            if(x[N-1]<i&&y[0]>=i){
                cout<<"No War"<<endl;
                return 0;
            }
        }
    }
    cout<<"War"<<endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力(n:点の個数，d:d以下のものを数える)
		int n = Integer.parseInt(sc.next());
      	int d = Integer.parseInt(sc.next());
      
      	double[] result = new double[n];
      	double tmp = 0;
      	int count = 0;
      
      
      	//距離の計算
      for(int i = 0; i < n; i++){
        tmp = Math.pow(Double.parseDouble(sc.next()), 2) + Math.pow(Double.parseDouble(sc.next()), 2);
    	result[i] = Math.sqrt(tmp);
        //カウント
        if(result[i] <= d){
          count++;
         // System.out.println(result[i]);
        }
      }
  //--------------------------
	//出力
      //System.out.println("n：" + n);
      //System.out.println("d：" + d);
      System.out.println(count);
	}
}



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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;

#define mt make_tuple
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sqr(x) ((ll)(x) * (x))

const ll MOD = 998244353;

ll fact[200001], fact2[200001];

ll modPow(ll a, ll n, ll m)
{
    if(n == 0)
        return 1LL;

    ll pola = modPow(a, n/2, m)%m;
    ll celo = (pola*pola)%m;

    if(n % 2 == 0)
    {
        return celo;
    }
    else
    {
        return (celo*a)%MOD;
    }
}

ll nCr(ll n, ll k)
{
    return (((fact[n] * fact2[k])%MOD) * fact2[n-k])%MOD;
}

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

    int n, m, k;
    cin >> n >> m >> k;

    fact[0] = 1LL;

    for(int i = 1; i <= 200000; ++i)
        fact[i] = (fact[i-1] * (i%MOD))%MOD;

    for(int i = 0; i <= 200000; ++i)
        fact2[i] = modPow(fact[i], MOD-2, MOD);

    ll resenje = 0LL;

    for(int i = 0; i <= k; ++i)
    {
        ll izraz = ((((m%MOD) * modPow(m-1, n-1-i, MOD))%MOD) * nCr(n-1, i))%MOD;
        resenje = (resenje + izraz) % MOD;
    }

    cout << resenje << '\n';

    return 0;
}


Measured memory_bytes: 6820
//ANTIHYPE
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int n;
char a[N];
ll cnt[N];

int main()
{

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

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], ++cnt[a[i]];
    ll ans = 1;
    for (int i = 'a'; i <= 'z'; ++i)
    {
        ans = ans * (cnt[i] + 1) % mod;
    }
    cout << ans - 1;
    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(void)
{
	int count[5][4][11] = {0};
	int i,j,k,n,b,f,r,v;
	scanf("%d",&n);
	for(i = 0;i <= n-1;i++){
		scanf("%d %d %d %d",&b,&f,&r,&v);
		count[b][f][r] += v;
	}
	for(i = 1;i <= 4;i++){
		for(j = 1;j <= 3;j++){
			for(k = 1;k <= 10;k++){
				printf(" %d",count[i][j][k]);
			}
			printf("\n");
		}
		if(i <= 3){
			printf("####################\n");
		}
	}
	return 0;
}

Measured memory_bytes: 612
/* Bismillahirrahmanirrahim */
#include<bits/stdc++.h>
#define forA for(int i=0; i<a; i++)
using namespace std;

int main(){
	int a, b;
	char c;
	cin >> a;
	string str;
	cin >> str;
	cin >> b;
	c=str[b-1];
	forA{
		if(str[i]!=c) str[i]='*';
	}
	cout << str;
}


Measured memory_bytes: 256
using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace debug
{

    class ProgramC
    {

        static int[] a = new int[50];
        static int[] b = new int[50];
        static int[] c = new int[50];
        static int[] d = new int[50];
        static List<int> ans = new List<int>();
        static int n;
        static int m;
        static int q;
        static int[] array = new int[10];

        static void Main(string[] args)
        {
            string[] z = Console.ReadLine().Split(' ');
            n = int.Parse(z[0]);
            m = int.Parse(z[1]);
            q = int.Parse(z[2]);



            for (int i = 0; i < q; i++)
            {
                string[] y = Console.ReadLine().Split(' ');
                a[i] = int.Parse(y[0]);
                b[i] = int.Parse(y[1]);
                c[i] = int.Parse(y[2]);
                d[i] = int.Parse(y[3]);

            }

            //DFS
            dfs(1, 0);

            Console.WriteLine(ans.Max());



        }

        static void dfs(int f,int j)
        {
            if (j == n)
            {
                int count = 0;
                for (int i = 0; i < q; i++)
                {
                    int bi = array[b[i] - 1] - '0';
                    int ai = array[a[i] - 1] - '0';
                    if (bi == 0)
                        bi = 10;
                    if (ai == 0)
                        ai = 10;
                    if (bi - ai == c[i])
                        count += d[i];

                }

                ans.Add(count);


            }
            else
            {
                for (int c = f; c <= m; c++)
                {
                    array[j] = c;
                    dfs(c,j+ 1);
                }
            }
        }
    }



}


Measured memory_bytes: 29152
from sys import stdin

N, T, *ct = map(int, stdin.read().split())

cost = 1001
for i in range(N):
    c, t = ct[2*i:2*(i+1)]
    if t > T:
        continue
    cost = min(cost, c)

if cost > 1000:
    print('TLE')
else:
    print(cost)

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

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#define FOR(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REP(i, n) for(int i=0; i<(int)(n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SQ(n) (n) * (n)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
  int a, b, c, d, e, f;
  while(cin >> a >> b >> e >> c >> d >> f) {
    float D = 100.0f / (a * d - b * c);
    int x = round((d * e - b * f) * D);
    int y = round((-c * e + a * f) * D);
    printf("%.3f %.3f\n", x / 100.0f, y / 100.0f);
  }
}

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

using namespace std;
using ll = long long;

const int MAX = 2e3;
const int MOD = 1e9 + 7;

ll t[MAX];

void update(int pos, int x = 1) {
    for (; pos < MAX; pos |= pos+1)
        t[pos] += x;
}

int get(int r) {
    ll sum = 0;
    for (; r >= 0; r &= r+1, --r)
        sum += t[r];
    return sum;        
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a)
        cin >> x, update(x);
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 1+i; j < n; ++j) {
            int mx = a[i]+a[j]-1;
            int mn = abs(a[i]-a[j])+1;
            update(a[i], -1), update(a[j], -1);
            ans += get(mx) - get(mn-1);
            update(a[i]), update(a[j]);
        }
    }
    cout << ans/3;
    return 0;
}                                                               
    
                

Measured memory_bytes: 256
n = int(input())
l = 0
r = n-1
mid = (l+r)/2
print(l)
s1 = raw_input()
if s1 == 'Vacant':
    exit(0)
print(mid)
s2 = raw_input()
if s2 == 'Vacant':
    exit(0)
while True:
    #print("before:",l,r)
    if (mid-l) % 2 == int(s1 != s2):
        l = mid
        s1 = s2
    else:
        r = mid
    #print("after:",l,r)
    mid = (l+r)/2
    if mid == l:
        break
    print(mid)
    s2 = raw_input()
    if s2 == 'Vacant':
        exit(0)
print(mid+1)
s1 = raw_input()


Measured memory_bytes: 29120
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N, M, X, Y;
int x[102], y[102];

int main() {
  INCANT;
  cin >> N >> M >> X >> Y;
  rep(i, N) cin >> x[i];
  rep(i, M) cin >> y[i];

  bool flag = true;
  for (int z=X+1; z<=Y; z++) {
    bool ok = true;
    rep(i, N) {
      if (x[i]>=z) {
        ok=false;
        break;
      }
    }
    rep(i, M) {
      if (y[i]<z) {
        ok=false;
        break;
      }
    }
    if (ok) {
      flag=false;
      break;
    }
  }
  string ans = flag?"War":"No War";
  cout << ans << "\n";
  return 0;
}

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

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
  string s; int cnt = 0;
  cin >> s;
  for(int i=0;i<s.size();i++) if(s[i] == 'o') cnt++;
  if(cnt+(15-s.size()) >= 8) cout << "YES\n";
  else cout << "NO\n";
  return 0;
}

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

#define sz(x) (int)x.size() 
#define pb push_back 
#define mp make_pair 
#define fi(a, b) for(int i=a; i<=b; i++) 
#define fj(a, b) for(int j=a; j<=b; j++) 
#define fo(a, b) for(int o=a; o<=b; o++) 
#define fdi(a, b) for(int i=a; i>=b; i--) 
#define fdj(a, b) for(int j=a; j>=b; j--) 
#define fdo(a, b) for(int o=a; o>=b; o--) 

#ifdef LOCAL
#define err(...) fprintf(stderr, __VA_ARGS__)
#else
#define err(...) while(false) {}
#endif

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<int> vi; 
typedef vector<pii> vpii; 
typedef vector<pll> vpll; 
typedef long double ld;

/////////////////////////////////

int const MAX = 55;

int d[MAX][MAX][MAX];

int n;
int a[MAX];
int b[MAX];
ll ans;
int can[MAX][MAX];

bool bit(int m, int i) {
	return (m & (1 << i));
}

int rec(int a, int b, int m) {
	if (a == b) return true;
	if (a < b) return false;
	if (d[a][b][m] != -1) return d[a][b][m];
	int res = 0;
	fi(1, m) {
		if (i > a) break;
		res = max(res, rec(a % i, b, m));
	}	
	d[a][b][m] = res;
	return res;
}

void solve() {
 	memset(d, 255, sizeof(d));
	bool f = true;
	fi(1, n) {
		f &= rec(a[i], b[i], MAX - 1);
	}
	if (!f) {
		printf("-1\n");
		return;
	}
	fi(1, n) {
		can[i][a[i]] = 1;
	}
 	fdi(MAX - 1, 1) {
		bool f = false;
		fj(1, n) {
			bool g = false;
			fo(0, MAX - 1) {
				if (can[j][o]) {
					g |= rec(o, b[j], i - 1);
				}
			}
			f |= (!g);
		} 		
		if (f) {
			ans |= (1LL << i);
			err("i = %d\n", i);
			fj(1, n) {
				fo(0, MAX - 1) {
					if (can[j][o]) {
						can[j][o % i] = 1;
					}
				}
			}
		}
 	}
 	printf("%lld\n", ans);
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	scanf("%d", &n);
	fi(1, n) {
		scanf("%d", &a[i]);
	}
	fi(1, n) {
		scanf("%d", &b[i]);
	}
	solve();		

	
#ifdef LOCAL
	err("ELAPSED TIME: %.3Lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	return 0;
}

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  for(int i = 0; i < s.length(); i++) {
    if(s[i] + n <= 90) {
      cout << char(s[i] + n);
    }else if (s[i] + n > 90) {
      cout << char(s[i] + n - 26);
    }
  }
}
  

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

int main() {
    string s;
    cin >> s;
    string text;
    cin >> text;
    int cnt = 0;
    while (text != "END_OF_TEXT") {
        for (int i = 0; i < text.size(); i++) {
            if (text[i] >= 'A' && text[i] <= 'Z') {
                text[i] += 'a' - 'A';
            }
        }
        if (text == s) {
            cnt++;
        }
        cin >> text;
    }

    cout << cnt << endl;
}


Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define re return
typedef long long ll;
typedef pair<int, int> pii;
int r,g,b;
int n;
int ans;
int main() { 
typedef vector<int> vi;
    //freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>r>>g>>b>>n;
	for(int i=0;i*r<=n;i++){
		for(int j=0;i*r+j*g<=n;j++){
			int lft=n-r*i-g*j;
			if(lft%b==0)ans++;
		}
	}
	cout<<ans<<endl;
    return 0; 
}

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

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

    std::map<char, std::size_t> m;

    std::size_t pos = 0;
    for (auto c : s) {
        // forward
        std::size_t rf = 0;
        if (pos != s.size()) {
            rf = s.find(c, pos + 1);
            if (rf == std::string::npos) rf = s.size() - (pos + 1);
            else rf = rf - pos - 1;
        }
        // backward
        std::size_t rb = 0;
        if (pos != 0) {
            rb = s.rfind(c, pos - 1);
            if (rb == std::string::npos) rb = pos;
            else rb = pos - rb - 1;
        }
        auto r = std::max(rf, rb);
        auto it = m.find(c);
        if (it == m.end()) {
            m[c] = r;
        }
        else {
            if (it->second < r) it->second = r;
        }
        ++pos;
    }
    auto it = std::min_element(m.begin(), m.end(), [](auto lhs, auto rhs) { return lhs.second < rhs.second; });
    std::cout << it->second << std::endl;
}


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

int main (){
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A.at(i);
    ll Q;
    cin >> Q;
    vector<ll> B(Q), C(Q);
    rep(i, Q){
        cin >> B.at(i) >> C.at(i);
    }
    int MAX = 100001; 
    vector<ll> S(Q);
    vector<int> count(MAX,0);
    rep(i, N){
        count.at(A.at(i))++;
    }

    long sum = 0;
    rep(i, N){
        sum += A.at(i);
    }

    rep(i, Q){
        int num = count.at(B.at(i));
        int diff = C.at(i)-B.at(i);
        count.at(B.at(i)) = 0;
        count.at(C.at(i)) += num;
        sum += diff * num;
        S.at(i) = sum;
    }

    rep(i, Q){
        cout << S.at(i) << endl;
    }
}

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

using namespace std;

#define INF 1e9

struct P{
  int x,y;
  P(int x,int y) : x(x),y(y) {}
};

vector<int> v;

P getPos(int x){
  x--;
  return P(x%4,x/4);
}

int getMD(){
  int res = 0;
  for(int i = 0 ; i < 16 ; i++){
    if(v[i] == 0){ continue; }
    P tp = getPos(v[i]);
    res += abs(i%4-tp.x) + abs(i/4-tp.y);
  }
  return res;
}

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

bool inField(int x,int y){
  return (0 <= x && x < 4 && 0 <= y && y < 4);
}

bool solve(int sp,int step,int prev){
  int md = getMD();
  if(md == 0){ return true; }
  if(md + step > LIMIT){
    return false;
  }
  int x = sp%4,y = sp/4;
  for(int i = 0 ; i < 4 ; i++){
    int nx = x + dx[i],ny = y + dy[i];
    if(abs(i-prev) == 2){ continue; }
    if(!inField(nx,ny)){ continue; }
    int nsp = ny*4 + nx;
    swap(v[sp],v[nsp]);
    if(solve(nsp,step+1,i)){
      return true;
    }
    swap(v[sp],v[nsp]);
  }
  return false;
}

int main(){
  int sp = -1;
  v.resize(16);
  for(int i = 0 ; i < 16 ; i++){
    cin >> v[i];
    if(v[i] == 0){ sp = i; }
  }
  for(LIMIT = 0 ; LIMIT <= 50 ; LIMIT++){
    if(solve(sp,0,INF)){
      cout << LIMIT << endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 1192
let () =
    let main () =
        let n = int_of_string (read_line ()) in
        let find_index arr v col =
            let rec loop l r =
                if l = r then l else
                    let m = (l + r) / 2 in
                    if arr.(m) >= v then loop (m + 1) r else
                                         loop l m
            in
            loop 1 col
        in
        let rec loop arr i col =
            if i = 0 then col else
                let p = int_of_string (read_line ()) in
                if p <= arr.(col) then (
                    let col = col + 1 in
                    arr.(col) <- p;
                    loop arr (i - 1) col
                ) else (
                    let j = find_index arr p col in
                    let () = arr.(j) <- p in
                    loop arr (i - 1) col
                )
        in
        let arr = Array.make (n + 1) 0 in
        let () = arr.(1) <- int_of_string (read_line ()) in
        Printf.printf "%d\n" (loop arr (n - 1) 1)
    in
    main ()

Measured memory_bytes: 5376
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    set<int> st;
    for(int i = 0;i < 3;i++)
    {
        int a;
        cin >> a;
        st.insert(a);
    }
    if(st.size() == 2)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
// Package main provides
//
// File:  main.go
// Author: ymiyamoto
//
// Created on Sun Jan 27 21:01:38 2019
//
package main

import (
	"fmt"
	"sort"
)

func min(slice ...int) int {
	sort.Ints(slice)
	return slice[0]
}

func max(slice ...int) int {
	sort.Ints(slice)
	return slice[len(slice)-1]
}

func main() {
	var N, A, B int
	fmt.Scan(&N, &A, &B)
	sum := A + B - N
	fmt.Println(min(A, B), max(sum, 0))
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;

int main() {
    ll n, v = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ll s;
        cin >> s;
        v += s;
    }
    cout << v - n * (n + 1) / 2 << endl;

}


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

struct UnionFind {
	vector<int> par;
	int cnt;
	UnionFind(int size_) : par(size_, -1), cnt(size_) {}
	void unite(int x, int y) {
		if((x = find(x)) != (y = find(y))) {
			if(par[y] < par[x]) swap(x, y);
			par[x] += par[y]; par[y] = x; cnt--;
		}
	}
	bool same(int x, int y) { return find(x) == find(y); }
	int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
	int size(int x) { return -par[find(x)]; }
	int size() { return cnt; }
};

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

	int N, K, L;
	cin >> N >> K >> L;

	UnionFind uf1(N), uf2(N);
	for(int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		uf1.unite(a, b);
	}
	for(int i = 0; i < L; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		uf2.unite(a, b);
	}

	typedef pair<int, int> P;
	map<P, int> m;
	for(int i = 0; i < N; i++) {
		int a = uf1.find(i);
		int b = uf2.find(i);
		m[P(a, b)]++;
	}

	for(int i = 0; i < N; i++) {
		int a = uf1.find(i);
		int b = uf2.find(i);
		cout << m[P(a, b)] << " ";
	}
	cout << endl;
}

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

int main()
{
    long long n, a, max = -1e+18, min = 1e+18, sum = 0;
    cin >> n;
    while(n--)
    {
        cin >> a;
        if (a > max) max = a;
        if (a < min) min = a;
        sum += a;
    }
    cout << min << " " << max << " " << sum << endl;
    return 0;
}


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

namespace ConsoleApp15
{
    class Class386
    {
        static void Main()
        {
            var HW = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int H = HW[0], W = HW[1];
            var c = new int[10, 10];
            for (int i = 0; i < 10; i++)
            {
                var r = Console.ReadLine().Split().Select(int.Parse).ToArray();
                for (int j = 0; j < 10; j++)
                {
                    c[i, j] = r[j];
                }
            }
            var nums = new int[10];
            for(int i = 0;i < 10; i++)
            {
                if (i == 1) continue;
                var frags = Enumerable.Repeat(int.MaxValue, 10).ToArray();
                frags[i] = 0;
                var que = new Queue<Tuple<int,int>>();
                que.Enqueue(Tuple.Create(i,0));
                while (que.Count > 0)
                {
                    var t = que.Dequeue();
                    if (t.Item1 == 1) continue;
                    for (int j = 0; j < 10; j++)
                    {
                        if (frags[j] <= t.Item2 + c[t.Item1, j]) continue;
                        frags[j] = t.Item2 + c[t.Item1, j];
                        que.Enqueue(Tuple.Create(j, t.Item2 + c[t.Item1, j]));

                    }
                }
                nums[i] = frags[1];
            }

            var A = new int[H, W];
            for (int i = 0; i < H; i++)
            {
                var r = Console.ReadLine().Split().Select(int.Parse).ToArray();
                for (int j = 0; j < W; j++)
                {
                    A[i, j] = r[j];
                }
            }

            long ans = 0;
            for (int i = 0; i < H; i++)
            {
                for (int j = 0; j < W; j++)
                {
                    if (A[i, j] == -1||A[i,j]==1) continue;
                    
                    ans += nums[A[i, j]];
                }
            }
            Console.WriteLine(ans);
        }
    }
}


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

using namespace std;

int main() {
	string S, T;
	
  cin >> S;
  cin >> T;

  int A, B;
  cin >> A;
  cin >> B;

  string U;
  cin >> U;

  if (S == U) {
    A--;
  } else {
    B--;
  }

  cout << A << " " << B << endl;
}



Measured memory_bytes: 256
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())
d = getInputListInt()

d.reverse()

print(*d, sep=" ")


Measured memory_bytes: 6936
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define lowbit(x) (x&-x)
#define pb push_back
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#ifdef __linux__
#define getchar getchar_unlocked
#endif
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
typedef long long LL;
using namespace std;
const int N=200010;
const int inf=0x3f3f3f3f;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifdef ztzshiwo
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int n,t[N],cnt,tot;
LL ans;
char s[N];
vector<int>G[26];
struct node
{
	int l,r;
	node(){}
	node(int l,int r):l(l),r(r){}
}a[N];
inline bool operator<(const node&A,const node&B){return A.l<B.l;}
inline void add(int x){for(;x<=n;x+=lowbit(x))t[x]++;}
inline int sum(int x){int r=0;for(;x;x-=lowbit(x))r+=t[x];return r;}
int main()
{
	file();
	scanf("%s",s+1);
	n=strlen(s+1);
	For(i,1,n)G[s[i]-'a'].pb(i);
	For(i,0,25)
	{
		if(SZ(G[i])&1)cnt++;
		int l=0,r=SZ(G[i])-1;
		while(l<=r)a[++tot]=node(G[i][l],G[i][r]),l++,r--;

	}
	if(cnt>(n&1)){puts("-1");exit(0);}
	sort(a+1,a+tot+1);
	For(i,1,tot)
		if(a[i].l==a[i].r)ans+=(tot-i)*2;
		else ans+=n-i+1-a[i].r+sum(a[i].r),add(a[i].r);
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 2680
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
//int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
int a[10010];

int main(){
	while(1){
		int sum=0;
		cin>>n;
		if(n==0){
			break;
		}
		
		for(int i=0;i<n;i++){
			cin>>a[i];
			sum+=a[i];
		}
		double ave;
		ave=(double)sum/n;
		int ans=0;
		for(int i=0;i<n;i++){
			if(ave>=a[i])
				ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
#define LL long long
#define MOD (LL)1000000007
#define pi acos(-1.0)
#define ULL unsigned long long
#define mem_1(str) memset(str,-1,sizeof(str))
#define mem0(str) memset(str,0,sizeof(str))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define INF 999999999
using namespace std;
LL num[500000]; 
LL f[500000],e[500000];
priority_queue<LL> qt;
priority_queue<LL , vector<LL> , greater<LL> > qtt;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=3*n;i++)
	{
		scanf("%lld",&num[i]);
	}
	LL sum=0;
	for(int i=1;i<=3*n;i++)
	{
		qtt.push(num[i]);
		sum+=num[i];
		if(qtt.size()>n)
		{
			sum-=qtt.top();
			qtt.pop();
		}
		f[i]=sum;
	}
	sum=0;
	for(int i=3*n;i>0;i--)
	{
		qt.push(num[i]);
		sum+=num[i];
		if(qt.size()>n)
		{
			sum-=qt.top();
			qt.pop();
		}
		e[i]=sum;
	}
	LL ans=(LL)-1e18;
	for(int i=n;i<=2*n;i++)
	{
		ans=max(ans,f[i]-e[i+1]);
	 } 
	 printf("%lld",ans);
}

Measured memory_bytes: 12148
import sys
#from collections import deque
#from functools import *
#from fractions import Fraction as f
from copy import *
from bisect import *	
#from heapq import *
from math import gcd
from itertools import permutations as prm,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)

t=1
	

while t>0:
	t-=1
	s=input().rstrip()
	if s[-1]=='s':
		print(s+"es")
	else:
		print(s+"s")	


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

int main() {

	ll i, j, k, n;
	ll a, b;

	cin >> n >> a >> b;
	if (b > a) {
		
		if ((b - a) % 2 == 0) cout << (b - a) / 2;
		else {
			ll sum = 0;
			if (a - 1 < n - b) {
				
				b -= a - 1;
				sum = a - 1;
				if (b == 2) {
					cout << ++sum;
					return 0;
				}
				else {
					b--;
					cout << sum + 1 + (b - 1) / 2 ;
				}
			}
			else {
				ll sum = 0;
				a += (n - b);
				sum += n - b;
				if (a == n - 1) {
					cout << ++sum;
					return 0;
				}
				else {
					a++;
					cout << sum + 1 + (n - a) / 2;
				}
			}
		}

	}
}

Measured memory_bytes: 256