akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().Solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    Random rnd = new Random();
    Stopwatch sw = new Stopwatch();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";


    void Solve()
    {
        int N = cin.Nextint;
        int rmax = 0, rmin = int.MaxValue, bmax = 0, bmin = int.MaxValue;
        var R = new int[N];
        var B = new int[N];

        for (int i = 0; i < N; i++)
        {
            int x = cin.Nextint;
            int y = cin.Nextint;
            int r = Math.Min(x, y);
            rmax = Math.Max(rmax, r);
            rmin = Math.Min(rmin, r);
            int b = Math.Max(x, y);
            bmax = Math.Max(bmax, b);
            bmin = Math.Min(bmin, b);

            R[i] = r;
            B[i] = b;
        }

        Array.Sort(R, B);
        /*for (int i = 0; i < N; i++)
        {
            WriteLine($"{R[i]} {B[i]}");
        }*/
        long ans = (long)(rmax - rmin) * (bmax - bmin);

        long diff = R[N - 1] - R[0];

        int m = B[0];//Bの中に入っていた交換した中で一番小さいもの
        int M = R[N - 1];//Bの中に入っていた交換した中で一番大きいもの
        for (int i = 0; i < N; i++)
        {
            diff = Math.Min(diff, M - Math.Min(m, R[i]));
            m = Math.Min(m, B[i]);
            M = Math.Max(M, B[i]);
            
            //WriteLine($"m={m} M={M} diff={diff}");
        }
        ans = Math.Min(ans, diff * (bmax - rmin));
        WriteLine(ans);


    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] Scan { get { return ReadLine().Split(); } }
    public int[] Scanint { get { return Array.ConvertAll(Scan, int.Parse); } }
    public long[] Scanlong { get { return Array.ConvertAll(Scan, long.Parse); } }
    public double[] Scandouble { get { return Array.ConvertAll(Scan, double.Parse); } }
    public string Next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return Next;
        }
    }
    public int Nextint { get { return int.Parse(Next); } }
    public long Nextlong { get { return long.Parse(Next); } }
    public double Nextdouble { get { return double.Parse(Next); } }
}

Measured memory_bytes: 17384
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
ll flr(ll x, int i) {
    return x & ~ ((1ll<<i) - 1);
}
ll acc(ll x, int i) { // the number of integers in [0,x) which has i-th bit
    ll y = flr(x, i);
    ll z = flr(x, i+1);
    return z/2 + (z == y ? 0 : x - y);
}
int main() {
    while (true) {
        // input
        int n; cin >> n;
        if (n == 0) break;
        vector<ll> k(n); repeat (i,n) cin >> k[i];
        // trivial
        bool is_trivial = false; // due to B muse \le 10^{18}
        if (60 < n) is_trivial = true;
        for (ll it : k) {
            if (1000000000000000000ll < it) is_trivial = true;
        }
        // compute
        vector<pair<ll, ll> > cands;
        for (int delta : { -1, 0, 1 }) {
            ll l = k[0] * 2 + delta;
            if (l <= 0) {
                continue;
            } else if (l == 1) {
                ll a = 0;
                repeat (i,n) {
                    if (k[i]) a += 1ll<<i;
                }
                cands.emplace_back(a, a);
            } else {
                int i = n-1;
                ll base = 0;
                while ((k[i] == 0 or k[i] == l) and i != 0) {
                    if (k[i] == l) base += 1ll<<i;
                    -- i;
                }
                ll b = (1ll<<i) + k[i] - 1 + base;
                ll a = b - l + 1;
                if (a <= 0) continue;
                cands.emplace_back(a, b);
            }
        }
        vector<pair<ll, ll> > ans;
        for (auto it : cands) {
            ll a, b; tie(a, b) = it;
            bool is_valid = true;
            if (1000000000000000000ll < b) is_valid = false;
            repeat (j,n) {
                if (acc(b+1, j) - acc(a, j) != k[j]) {
                    is_valid = false;
                    break;
                }
            }
            if (is_valid) {
                ans.emplace_back(a, b);
            }
        }
        // output
        switch (ans.size()) {
            case 0: cout << "None" << endl; break;
            case 1: cout << ans[0].first << ' ' << ans[0].second << endl; break;
            default: cout << "Many" << endl; break;
        }
    }
    return 0;
}

Measured memory_bytes: 3064
// AOJ 2576: Doctor Course Is Recommended
// 2017.10.13 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

int p[22], np;
int q[22], nq;

int cmp(int *a, int *b) { return *b - *a; }
int main()
{
	int d, xy, i, j, ans;
	char buf[10];

	scanf("%d%d", &d, &xy);
	np = 0; while (xy-- > 0) {
		scanf("%s%d", buf, &i);
		if (*buf == 'D') p[np++] = i;
	}
	scanf("%d", &xy);
	nq = 0; while (xy-- > 0) {
		scanf("%s%d", buf, &i);
		if (*buf == 'D' && *(buf+1) == 'D') q[nq++] = i;
	}
	qsort(p, np, sizeof(int), cmp);
	qsort(q, nq, sizeof(int), cmp);
	ans = 0; i = j = 0; while (d > 0 && (i < np || j < nq)) {
		if (d == 1) j = nq;
		if (i < np && j < nq) {
			if (i+1 < np && q[j] >= p[i]+p[i+1] ||
				i+1 == np && q[j] >= p[i]) d-=2, ans += q[j++];
			else d--, ans += p[i++];			
		} else if (i < np) d--, ans += p[i++];
		else if (j < nq) d-=2, ans += q[j++];
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1828
// A.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>

using namespace std;

int main()
{
    int a, b, c;

    cin >> a >> b >> c;

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

    return 0;
}



Measured memory_bytes: 3188
def array_integer(a)
	0.upto(a.count) {|x|
		a[x] = a[x].to_i
	}
	return a
end

n,m,l = array_integer(STDIN.gets.split(" "))

a = Array.new(n).map{Array.new(m, 0)}
b = Array.new(m).map{Array.new(l, 0)}
c = Array.new(n).map{Array.new(l, 0)}

0.upto(n-1) {|i|
	a[i] = array_integer(STDIN.gets.split(" "))
}
0.upto(m-1) {|i|
	b[i] = array_integer(STDIN.gets.split(" "))
}

0.upto(n-1) {|i|
	0.upto(l-1) {|j|
		sum = 0
		0.upto(m-1) {|k|
			sum += a[i][k] * b[k][j]
		}
		c[i][j] = sum
	}
}

0.upto(n-1) {|i|
	0.upto(l-1) {|j|
		print c[i][j]
		print " " if j != l-1
	}
	print "\n"
}



Measured memory_bytes: 7220
#
import sys
import math
import numpy as np
import itertools

# ひとつ入力
n = int(input())
# ひとつ入力
k = int(input())

a=n
p=0
nn=[]
while a>0:
    p+=1
    r=a%10
    nn.insert(0,r)
    a=a//10
#print(p)


dp0=np.zeros((p+1,k+2),dtype="int64")
dp1=np.zeros((p+1,k+2),dtype="int64")
#print(dp0,dp1)
dp1[0][0]=1
for i in range(p):
    for j in range(k+1):
        dp0[i+1][j]    += dp0[i][j] + dp1[i][j] * (nn[i]>0)
        dp0[i+1][j+1]  += dp0[i][j] * 9 + dp1[i][j] * max(nn[i]-1,0)
        dp1[i+1][j]    += dp1[i][j] * (nn[i]==0)
        dp1[i+1][j+1]  += dp1[i][j] * (nn[i]!=0)
        

answer=dp0[p][k]+dp1[p][k]
#print(nn)
#print(dp0,dp1)
print(answer)


Measured memory_bytes: 12504
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}


int main() {

    long long N, K;
    cin >> N >> K;

    vector<long long> a(N), b(N);
    for (int i = 0; i < N; i++) cin >> a[i] >> b[i];

    vector<pair<long, long>> ab(N);
    for (int i = 0; i < N; i++) ab[i] = make_pair(a[i], b[i]);

    sort(ab.begin(), ab.end());
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        sum += ab[i].second;
        if (sum >= K) {
            cout << ab[i].first << endl;
            return 0;
        }
    }

    return 0;
}











































































Measured memory_bytes: 3328
#include<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

int main()
{
  int i,j;
  int t,n,d;

  cin>>t;
  rep(i,t){
    cin>>n>>d;
    int sum=127*(n-1);
    if(n%2)
      sum+=d;
    else
      sum+=127-d;  
    cout<<sum<<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    VL a(n), b(n);
    REP(i, n) cin >> a[i] >> b[i];
    ll ans = 0;
    FORR(i, n - 1, 0) {
        ll mod = (ans + a[i]) % b[i];
        if(mod > 0) ans += b[i] - mod;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
h,w = map(int, input().split())
s = list(map(str, [input() for i in range(h)]))
answer = 'Yes'

for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			continue
		#四方に#が入っているかどうか確認していく
		mawari = []
		if i != 0:
			mawari.append(s[i-1][j])
		if i != h-1:
			mawari.append(s[i+1][j])
		if j != 0:
			mawari.append(s[i][j-1])
		if j != w-1:
			mawari.append(s[i][j+1])
		if '#' not in mawari:
			answer = 'No'
			break

print(answer)

Measured memory_bytes: 3188
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math
 
#import bisect
 
def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta
 
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
 
 
def main():
#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
    n=int(input())
    s=list(map(str,input()))
    a=[]
    for i in range(1000):
        if i<10:
            a.append("00"+str(i))
        elif i>=10 and i<100:
            a.append("0"+str(i))
        else:
            a.append(str(i))
#    print(s)
#    print(a)
    count=0
    for i in range(1000):
        keta1=a[i][0]
        keta2=a[i][1]
        keta3=a[i][2]
   #     print(keta1,keta2,keta3)
        x=my_index(s,keta1,n+1)
        if x>=n-1:
            continue
 
        y = my_index(s[x+1:], keta2,n+1)
        if y>=len(s[x+1:])-1:
            continue
        z = my_index(s[x+y+2:], keta3,n+1)
        if z>len(s[x+y+2:]):
            continue
        if x!=n+1 and y!=n+1 and z!=n+1:
        #    print(s[x],s[y],s[z],i)
            count+=1
    print(count)
 
#  print(c)
 
 
 
 
            #    print(n,kingaku(a,b,x))
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 132708
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vp;
typedef map<ll, ll> mll;
typedef map<string, ll> mstrll;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
#define out(x) cout << (x)
#define indent() cout << '\n'
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
ll gcd(ll a, ll b){return b != 0 ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
ll a, b, c, n, m, x, y, z, w, h, ans, cnt, mx, mn;
string s, t;
ll dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
//vll dx = {-1, 0, 1, -1, 1, -1, 0, 1}, dy = {-1, -1, -1, 0, 0, 1, 1, 1};
string alphabet = "abcdefghijklmnopqrstuvwxyz";

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> n >> m){
        ll sum = 0;
        rep(i, m){
            cin >> a;
            sum += a;
        }
        print(sum / (n + 1) + (sum % (n + 1) ? 1 : 0));
    }
}



Measured memory_bytes: 3224
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            new Main().solve(sc);
        }
    }

    void solve(Scanner sc) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (a + b == 15) {
            System.out.println("+");
        } else if (a * b == 15) {
            System.out.println("*");
        } else {
            System.out.println("x");
        }
    }
}


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

using namespace std;

int main(){
    string S;
    cin >> S;
    int N = S.size();
    char c[100000];
    int x[100001] = {0};
    int cnt = 0;
    for(int i = 0; i < N; i++){
        if(S[i]!='x'){
            c[cnt] = S[i];
            cnt++;
        }else{
            x[cnt]++;
        }
    }
    for(int i = 0; i*2-1 < cnt; i++){
        if(c[i] != c[cnt-i-1]){
            cout << -1 << endl;
            return 0;
        }
    }
    int ans = 0;
    for(int i = 0; i*2-1 < cnt; i++){
        ans += abs(x[i]-x[cnt-i]);
    }
    cout << ans << endl;
} 

Measured memory_bytes: 960
#include <stdio.h>

int check(int num)
{
    int returnVal = 0;
    returnVal += num / 10000;
    num %= 10000;
    returnVal += num / 1000;
    num %= 1000;
    returnVal += num / 100;
    num %= 100;
    returnVal += num / 10;
    returnVal += num % 10;
    return returnVal;
}

int main(void)
{
    int n, a, b, sum = 0;
    scanf("%d %d %d", &n, &a, &b);

    for (int i = 1; i <= n; i++)
    {
        int checkVal = check(i);
        if (a <= checkVal && checkVal <= b)
        {
            sum += i;
        }
    }

    printf("%d", sum);

    return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
char str[maxn];
int a[maxn],b[maxn];
int main(){
	int n;
	scanf("%d",&n);
	getchar();
	scanf("%s",str);
	int sum=maxn;
	if(str[0]=='W'){
		a[0]=1;
		b[0]=0;
	}else{
		a[0]=0;
		b[0]=1;
	}
	for(int i=1;i<n;i++){
		a[i]=a[i-1];
		b[i]=b[i-1];
		if(str[i]=='W'){
			a[i]++;
		}else{
			b[i]++;
		}
	}
	for(int i=0;i<n;i++){
		int temp1=0,temp2=0;
		if(i==0){
			temp1=0;
			temp2=b[n-1]-b[i];
		}else{
			temp1=a[i-1];
			temp2=b[n-1]-b[i];
		}
		sum=min(sum,temp1+temp2);
	}
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 2944
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (lli i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

const lli mod = 1e9 + 7;
lli n, c[200001], dp[200001];
vector<lli> pos[200001];
using P = pair<lli, lli>;
vector<P> span;

int main() {
  cin >> n; read_n(c, n);

  for (lli i=0; i<n; ++i) {
    pos[c[i]].push_back(i);
  }

  for (lli i=0; i<200001; ++i) {
    for (lli j=1; j<pos[i].size(); ++j) {
      lli l = pos[i][j-1] + 1, r = pos[i][j] - 1;
      if (l <= r) span.emplace_back(l, r);
    }
  }

  sort(begin(span), end(span), 
      [](const P& p, const P& q){return p.second < q.second; });
  
  dp[0] = 1;
  for (lli i=1, si = 0; i<n; ++i) {
    dp[i] = dp[i-1];
    if (si < span.size()) {
      lli l = span[si].first - 2, r = span[si].second;
      if (r == i) {
        lli d = l >= 0 ? dp[l] : 1;
        dp[i] = (dp[i] + d) % mod;
        ++si;
      }
    }
  }
  //cerr << "span.size\t" << span.size() << endl;

  //for (auto& p : span) cerr << p.first << ',' << p.second << endl;


  // for (lli i = 0; i<n; ++i) cout << i << '\t' << dp[i] << endl;

  cout << dp[n-1] << endl;
  return 0;
}


Measured memory_bytes: 17396
#include<iostream>
#include<unordered_set>

using namespace std;

int main(){

    int size,query;
    unordered_multiset<int> ans;
    cin >> size;
    for (int i=0;i<size;i++){
        cin >> query;
        if (ans.find(query) == ans.end()){
            ans.insert(query);
        }
        else{
            ans.erase(query);
        }

    }
    cout << ans.size() << endl;
    return 0;
}

Measured memory_bytes: 4388
#解説解法
n = int(input())
xp = []
xm = []
yp = []
ym = []
for _ in range(n):
  x,y = map(int,input().split())
  if x == 0:
    if y == 0:
      n -= 1
    elif y > 0:
      yp.append([0,x,y])
    else:
      ym.append([0,x,y])
  elif x > 0:
    xp.append([y/x,x,y])
  else:
    xm.append([y/x,x,y])
xp.sort()
xm.sort()
xy = xp + yp + xm + ym
can = []
for i in range(-n,0):
  X = 0
  Y = 0
  for j in range(i+1,i+n+1):
    x,y = xy[j][1],xy[j][2]
    X += x
    Y += y
    can.append(X**2+Y**2)
if n == 0:
  print(0)
else:
  print(max(can)**.5)

Measured memory_bytes: 3444
#include <iostream>
using namespace std;
const long long OO = (long long) 1e18;
 
const int N = 200008;
int n;
long long a[N];
 
long long dp[N][3];
// dp[i][j] is maximum possible sum choosing (i+1-j)/2 elements from first i
// elements. This is NOT a floor! So half the dp elements will be impossible
// solely because it's impossible to choose half an element.
 
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
 
	dp[0][0] = -OO;
	dp[0][1] = 0;
	dp[0][2] = -OO;
	dp[1][0] = a[0];
	dp[1][1] = -OO;
	dp[1][2] = 0;
 
	for (int i = 2; i <= n; i++) {
		// note that we are computing dp[i] using a[i-1] and dp[i-1]
		for (int j = 0; j < 3; j++) {
			// take a[i-1]
			dp[i][j] = dp[i-2][j] + a[i-1];
 
			if (j) {
				// we have slack; don't take a[i-1]
				dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
			}
		}
	}
 
	cout << dp[n][n % 2 == 0 ? 1 : 2];
}

Measured memory_bytes: 9860
import sys
from scipy.misc import comb

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n = ni()
str_list = [''.join(sorted(input())) for _ in range(n)]

check = ''
cnt = 1
ans = 0
for s in sorted(str_list):
    if s == check:
        cnt += 1
    else:
        if cnt >= 2:
            ans += comb(cnt, 2, exact=True)
        cnt = 1
    check = s
if cnt >= 2:
    ans += comb(cnt, 2, exact=True)
print(ans)

Measured memory_bytes: 22748
import java.util.*;
public class Main {
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int N;
  	N = sc.nextInt();
  	if(N==0) System.exit(0);

  	int[] a = new int[N];
  	for (int i=0;i<N;i++){
		a[i] = sc.nextInt();
	}
  	
  	for (int j=0;j<N;j++){
      	if(a[j]%2 == 0){
          	//System.out.println("a["+j+"]="+a[j]);
          	if((a[j]%3!=0)&&(a[j]%5!=0)){
              	System.out.println("DENIED");
              	System.exit(0);
            }
        }
    }

  	System.out.println("APPROVED");
	
  	System.exit(0);
	}
}

Measured memory_bytes: 23252
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
if 400 <= n <= 599:
    print(8)
elif 600 <= n <= 799:
    print(7)
elif 800 <= n <= 999:
    print(6)
elif 1000 <= n <= 1199:
    print(5)
elif 1200 <= n <= 1399:
    print(4)
elif 1400 <= n <= 1599:
    print(3)
elif 1600 <= n <= 1799:
    print(2)
elif 1800 <= n <= 1999:
    print(1)



Measured memory_bytes: 61772
#include <bits/stdc++.h>
#define int long long
#define moder 1000000007
#define inf 1000000000000000000
#define rep(i,n) for(int i=0;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int kai(int x) {
	if (x == 0)return 1;
	return (kai(x - 1)*x) % moder;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
/*--------Library Zone!--------*/

int n,a,b,t[100006];
bool solve(int k){
	int me=0;
	rep(i,n){
		if(t[i]-b*k>0){
			me+=(t[i]-b*k+(a-b)-1)/(a-b);
		}
	}
	if(me>k)return false;
	else return true;
}
signed main() {
	cin>>n>>a>>b;
	rep(i,n)cin>>t[i];
	int ri=moder,le=0;
	while(ri-le>1){
		if(solve((ri+le)/2))ri=(ri+le)/2;
		else le=(ri+le)/2;
	}
	cout<<ri<<endl;
}


Measured memory_bytes: 1024
N=int(input())
H=list(map(int, input().split()))
L=[float('inf')]*N
L[N-1]=H[N-1]
for i in range(1,N):
  a=H[N-i-1]
  if a-1>L[N-i]:
    print('No')
    exit()
  L[N-i-1]=min(a,L[N-i])
else:
  print('Yes')

Measured memory_bytes: 85876
#include<bits/stdc++.h>
using namespace std;
int main(void) {
    int n;
    scanf("%d", &n);
    vector<int> a(n), b(n), c(n - 1);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &b[i]);
    for (int i=0;i<n-1;i++)
        scanf("%d", &c[i]);
    int ans = b[a[0]-1];
    for(int i=1;i<n;i++){
        ans+=b[a[i]-1];
        if(a[i-1]==a[i]-1){
            ans+=c[a[i]-2];
        }
    }
    printf("%d", ans);
}

Measured memory_bytes: 256
from math import sqrt


import sys
input = sys.stdin.readline


def solve(N, D, X):
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            dist = sqrt(sum((X[i][d] - X[j][d])**2 for d in range(D)))
            if dist == int(dist):
                ans += 1

    return ans


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

X = []
for i in range(N):
    X.append(
        list(map(int, input().split()))
    )

print(solve(N, D, X))


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

int main(){
	int n,m,x,a=0,b=0;
	vector<int>y(100000);
	cin>>n>>m>>x;

	for(int i=0;i<m;i++){
		cin>>y[i];
		if(y[i]<x){
			a++;
		}
		else{
			b++;
		}
	}
	cout<<min(a,b)<<endl;
    return 0;
}

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


int main(){
	int X;
	scanf("%d",&X);
	int count500 = 0;
	int count5 = 0;
	int sum;
	while(X >= 500){
		X -=500;
		count500++;
	}
	while(X>=5){
		X -=5;
		count5++;
	}
	sum = count500*1000 + count5*5;
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std ;
typedef  long long int ll ;
#define inf ll(1e18)
#define mod 1000000007
#define mod1 998244353
#define mod2 999983
ll power(ll a,ll n,ll m) ;
ll power(ll a,ll n,ll m)
{  if(n==0)
   return 1 ;
   ll x=power(a,n/2,m) ;
   if(n%2!=0)
    return (((a*x)%m)*(x)%m)%m ;
    else return (x*x)%m ;
}
map<ll,ll>::iterator itr ;
ll ans ;
double PI=3.14159265357 ;
bool comp(pair<ll,ll> a,pair<ll,ll> b)
{
    if(a.first!=b.first)
        return a.first<b.first ;
    return a.second>b.second ;
}
int32_t main()
{ ll n,i,j,x,y,m,k,t,sum,count,cnt,b,c,d,j1,z,a,o,temp;
  ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  string s ;
  cin>>s ;
  n=s.length() ;
  for(i=0;i<n;i++)
  {if(s[i]=='?')
      cout<<"D" ;
      else cout<<s[i] ;
  } return 0; }


Measured memory_bytes: 3752
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using bint = boost::multiprecision::cpp_int;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repSE(i,s,n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int N;
    cin >> N;
    ll sum = 0;
    repSE(i,1,N+1) {
        if (i % 3 != 0 && i % 5 != 0)
            sum += i;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <atcoder/all>
#define ll long long int
#define MOD 1000000007
#define P pair<ll,ll>
#define INF 1000000000000000000

using namespace atcoder;
using namespace std;

int main(void){
  ll n, q;
  cin >> n >> q;
  
  fenwick_tree<ll> fw(n);
  for (int i = 0; i < n; i++){
    ll a;
    cin >> a;
    
    fw.add(i, a);
  }

  for (int i = 0; i < q; i++){
    ll c, p, x;
    cin >> c >> p >> x;
    
    if (c){
      cout << fw.sum(p, x) << endl;
    }
    else
      fw.add(p, x);
  }

  return 0;
}


Measured memory_bytes: 8204
#include<iostream>
using namespace std;
int main(){
  long long a,b,c,k,ans=0;
  cin >> a >> b >> c >> k;
  if(a>=k){
    ans=k;
  }
  else if(a+b>=k){
    ans=a;
  }
  else{
    ans=a-(k-a-b);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3676
# M = a ** x * b ** y * c ** z
# の約数の個数は(x + 1)*(y + 1)*(z + 1)
# なので約数が75個になるには、以下パターンが考えられる
# 75
# 25 * 3
# 15 * 5
# 5 * 5 * 3
# よって1～Nまで素因数分解して、各素因数の指数部分の値を求めて
# 計算する

import itertools

def main():
    N = int(input())
    d = [0] * (N+1)

    for i in range(2,N+1):
        cur = i
        for j in range(2, i+1):
            while cur % j == 0:
                d[j] += 1
                cur = cur // j

    ans = 0
    for i in d:
        if i >= 74:
            ans += 1
    for (x, y, z) in itertools.combinations(d,3):
        for a, b, c in [[4, 4, 2],[4, 2, 4],[2, 4, 4]]:
            if x >= a and y >= b and z >= c:
                ans += 1

    for (x, y) in itertools.combinations(d,2):
        for a, b in [[24,2],[14,4],[4,14],[2,24]]:
            if x >= a and y >= b:
                ans += 1

    print(ans)


    

main()

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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    int N;
    string a,b,c;
    cin >> N;
    cin >> a >> b >> c;

    int ans=0;
    for(int i=0;i<N;i++){
        if(a[i]==b[i]){
            if(b[i]!=c[i]) ans++;
        }else{
            if(b[i]==c[i] || a[i]==c[i]) ans++;
            else ans += 2;
        }
    }

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

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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

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

const int N = 3e2 + 2;

int DP[N][N][N];

int main() {

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

	string s; cin >> s;
	int n = sz(s), k; cin >> k;
	for (int l = n; l >= 1; l--) for (int r = l; r <= n; r++) for (int i = 0; i <= k; i++) {
		if (l == r) DP[l][r][i] = 1;
		else DP[l][r][i] = max(max(DP[l + 1][r][i], DP[l][r - 1][i]), max((i > 0) * (DP[l + 1][r - 1][i - 1] + 2), (s[l - 1] == s[r - 1]) * (DP[l + 1][r - 1][i] + 2)));
	}
	cout << DP[1][n][k] << endl;

	return 0;
}


Measured memory_bytes: 106368
#include <iostream>

void call(int n)
{
	for (int i = 1; i <= n; i++) {
		int x = i;
		if (x % 3 == 0) {
			std::cout << " " << i;
		}
		else {
			do {
				if (x % 10 == 3) {
					std::cout << " " << i;
					break;
				}
				else {
					x /= 10;
				}
			} while (x);
		}
	}
	std::cout << std::endl;
}

int main(void)
{
	int n;
	std::cin >> n;
	call(n);
	return 0;
}

Measured memory_bytes: 1160
package main

import "fmt"

func main() {
	var a, b, c, d int
	fmt.Scanf("%d %d %d %d", &a, &b, &c, &d)
	time_ta := c / b
	if c%b != 0 {
		time_ta += 1
	}
	time_ao := a / d
	if a%d != 0 {
		time_ao += 1
	}
	if time_ta <= time_ao {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1816
# frozen_string_literal: true

n, k = gets.chomp.split.map(&:to_i)
array = readlines.map { |e| e.chomp!.to_i }

func = proc do |p|
  array_c = array.dup
  nimotu = 0
  k.times do
    loop do
      break if array_c.empty?

      if nimotu + array_c.first <= p
        nimotu += array_c.shift
      else
        break
      end
    end

    nimotu = 0
  end

  array_c.empty?
end

left = 0
right = 100000 * 10000
ans = 0

while left <= right
  mid = (left + right) / 2
  if func.call(mid)
    ans = mid
    right = mid - 1
  else
    left = mid + 1
  end
end

puts ans



Measured memory_bytes: 13704
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
using namespace std;


int main()
{
	int a, b;
	string s;
	cin >> a >> b >> s;
	for (int i = 0; i < s.length(); i++) {
		if (i != a + 1 - 1 && s[i] == '-')return cout << "No" << endl, 0;
		else if (i == a + 1 - 1 && s[i] != '-')return cout << "No" << endl, 0;
	}
	cout << "Yes" << endl;
}





Measured memory_bytes: 384
#include<bits/stdc++.h>
#ifndef LOCAL_PROJECT
#define cerr if(0)cerr
#endif
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll> pll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int mn=1e3+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll mod=998244353;
#define mid ((l+r)>>1)
int main(){
#ifdef LOCAL_PROJECT
    freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
#else
    cin.tie(0);
    cin.sync_with_stdio(0);
#endif
    int n;
    cin>>n;
    int a,b,c,d;
    a=b=c=d=0;
    while(n--){
        string s;
        cin>>s;
        if(s=="AC")a++;
        else if(s=="WA")b++;
        else if(s=="TLE")c++;
        else d++;
    }
    printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n",a,b,c,d);
}

Measured memory_bytes: 3724
N = int(input())
p = list(map(int,input().split()))
ans = 0
for i in range(N-1):
    if p[i] == i+1:
        p[i],p[i+1] = p[i+1],p[i]
        ans += 1
if p[N-1] == N:
    ans += 1
print(ans)

Measured memory_bytes: 13880
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            final String s = reader.readLine();

            final String sl[] = s.split(" ");
            int n = Integer.parseInt(sl[0]);
            int m = Integer.parseInt(sl[1]);

            System.out.println((n - 1) * (m - 1));
        }
    }
}


Measured memory_bytes: 21076
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <tuple>
using namespace std;
typedef pair<int,int> P;
int V[100][100];//[v][i] leads to
int isDark[100];//-1テ」ツ?ェテ」ツつ嘉ヲツ伉偲」ツつ凝」ツ??0~M-1テ」ツ?ァテヲツ堋療」ツ??
const int INF = 100000;
int D[16];
int N,M,K;

int dist[1<<16];
int move_to[1<<16][100];
bool isvisit[1<<16];

int main(){
    cin>>N>>M>>K;
    fill(isDark,isDark+100,-1);
    fill(dist,dist+(1<<16),INF);
    fill(isvisit,isvisit+(1<<16),false);
    for(int i=0;i<M;i++){
        cin>>D[i];
        D[i]--;
        isDark[D[i]]=i;
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<K;j++){
            cin>>V[i][j];
            V[i][j]--;
        }
    }
    for(int b=0;b<(1<<M);b++){
        for(int k=0;k<K;k++){
            move_to[b][k]=0;
            for(int m=0;m<M;m++){
                if(b&(1<<m)){
                    int to = V[D[m]][k];
                    if(isDark[to]!=-1){
                        move_to[b][k]|=1<<isDark[to];
                    }
                }
            }
        }
    }
    deque<P> que;
    dist[(1<<M)-1]=0;
    que.emplace_back(0,(1<<M)-1);
    while(!que.empty()){
        int d,v;
        tie(d,v)= que.front(); que.pop_front();
        if(!v){
            cout<<d<<endl;
            return 0;
        }
        if(isvisit[v]) continue;
        isvisit[v]=true;
        for(int k=0;k<K;k++){
            int to = move_to[v][k];
            if(dist[to]>d+1){
                que.emplace_back(d+1,to);
                dist[to]=d+1;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 29268
#include"bits/stdc++.h"
#define N 200001
#define ZERO 0
using namespace std;
int n;
long long maxn=ZERO;
long long c[N];
int h[N];
int lowbit(int x)
{
	return x&(-x);
}
void updatemax(int index,long long value)
{
	while(index<=n)
	{
		c[index]=max(c[index],value);
		index+=lowbit(index);
	}
}
long long maxrange(int index)
{
	long long cnt=0;
	while(index)
	{
		cnt=max(cnt,c[index]);
		index-=lowbit(index);
	}
	return cnt;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&h[i]);
	for(int i=1;i<=n;i++)
	{
		long long a;
		scanf("%lld",&a);
		long long t=maxrange(h[i]-1)+a;
		maxn=max(maxn,t);
		updatemax(h[i],t);
	}
	printf("%lld",maxn);
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define N 100000

int n, f[N * 2 + 5], cx[N * 2 + 5], cy[N * 2 + 5];

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

int main() {
#ifdef whyqx
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif
    cin >> n;
    for (int i = 1; i <= N << 1; ++i)
        f[i] = i;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        f[find(x)] = find(y + N);
    }
    for (int i = N + 1; i <= N << 1; ++i)
        cy[find(i)]++;
    for (int i = 1; i <= N; ++i)
        cx[find(i)]++;
    long long ans = 0;
    for (int i = 1; i <= N << 1; ++i)
        ans += 1ll * cx[i] * cy[i];
    cout << ans - n;
    return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
    cin >> s;
    int cur = 0, res = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'A' || s[i] == 'T' || s[i] == 'C' || s[i] == 'G'){
            cur++;
        }
        else cur = 0;
        res = max(res, cur);
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <functional>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin >> n;
    map<string,int> dict;
    int mx = 0;
    for(int i = 0;i < n;i++){
        string s;
        cin >> s;
        dict[s]++;
        mx = max(mx,dict[s]);
    }

    for(auto p:dict){
        if(p.second == mx)cout << p.first << endl;
    }
}

Measured memory_bytes: 25216
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

//-------------------------------------------------------------------
struct segtree_in{
  ll M=1;
  vector<vll> dat;
  segtree_in(ll N, vll num){
    while(M<N) M*=2;
    for(int i=0;i<M*2-1;i++)  dat.push_back(num);
  }
  void update(vll x, int k, int l=0, int r=-1){
    if(r==-1) r = M;
    k+=M-1;
    dat[k] = x;
    while(k>0) {
      k = (k-1)/2;
      dat[k] = (dat[k*2+1][0]>dat[k*2+2][0]?dat[k*2+1]:dat[k*2+2]);
    }
  }
  vll query(int a, int b=-1, int k=0, int l=0, int r=-1){
    if(r==-1) r = M;
    if(b==-1) b = M;
    if(r<=a || b<=l) return vll{-1000000000, -1};
    if(a<=l && r<=b) return dat[k];
    vll A = query(a, b, k*2+1, l, (l+r)/2);
    vll B = query(a, b, k*2+2, (l+r)/2, r);
    return (A[0]>B[0]?A:B);
  }
};
//-------------------------------------------------------------------
int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  vll a(n+1), uke(n+1, 0), ans;
  re(i, n) {
    std::cin >> a[i+1];
    uke[a[i+1]]++;
  }
  segtree_in segin(n+1, vll{-1000000000, -1});
  set<ll> s;
  rep(i, 1, n+1) {
    segin.update(vll{uke[i], i}, i);
    s.insert(i);
  }

  if(n==2){
    std::cout << -1 << '\n';
    return 0;
  }
  for(int i=0;i<n;i++){
    vll k = segin.query(1, n+1);
    ll p;
    if(k[0]==(n-1-i)&&(i==0||a[ans[i-1]]!=k[1])) p = k[1];
    else {
      if(s.size()==3){
        for(auto t = s.begin();t!=s.end();t++){
          p = *t;
          ll A=10000000000, B=0;
          for(auto x = s.begin();x!=s.end();x++) if(x!=t) A = min(A, *x), B = max(B, *x);
          if((a[A]==B&&a[B]==A)||(i!=0&&a[ans[i-1]]==p)) continue;
          break;
        }
      }else{
        auto itr = s.begin();
        if(i!=0&&a[ans[i-1]]==*itr) itr++;
        p = *itr;
      }
    }
    segin.update(vll{-1000000000, -1}, p);
    if(i>0) {
      ll to = a[ans[i-1]];
      vll g = segin.query(to, to+1);
      segin.update(vll{g[0]-1, to}, to);
    }

    ans.push_back(p);
    s.erase(p);
  }
  re(i, n) std::cout << ans[i] << (i==n-1?"\n":" ");
  return 0;
}


Measured memory_bytes: 22956
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define PB push_back
#define SP << " " <<

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VLL;

__attribute__((constructor))
void initial(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed <<setprecision(15);
}


int main(void){
	ll H;
    cin >> H;

    ll a = 1;
    ll b = 0;
    ll ans;
    rep(i,42){
        if(a > H){
            ans = b;
            //cout << ans << endl;
            
        }else{
            b = a + b;
            a = a * 2;
            
            //cout << a SP b << endl;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,k,l,r,ans=0;
    cin>>n>>k>>l>>r;
    ll a[n];
    for(int i=0;i<n;i++){
    	cin>>a[i];
    }
    ll m=n/2,maki=(1<<m);
    vector<ll> v1[21],v2[21];
    for(int bit=0;bit<maki;bit++){
    	ll sum=0,num=0;
    	for(int i=0;i<m;i++){
    		if(bit>>i&1){
    			sum+=a[i];
    			num++;
    		}
    	}
    	v1[num].pb(sum);
    }
    ll x=n-m;maki=(1<<x);
    for(int bit=0;bit<maki;bit++){
    	ll sum=0,num=0;
    	for(int i=0;i<x;i++){
    		if(bit>>i&1){
    			sum+=a[i+m];
    			num++;
    		}
    	}
    	v2[num].pb(sum);
    }
    for(int i=0;i<=20;i++){
    	sort(be(v1[i]));
    	sort(be(v2[i]));
    }
    m=min(20LL,k);
    for(int i=0;i<=m;i++){
    	if(k-i>20)continue;
    	maki=v1[i].size();
    	for(int j=0;j<maki;j++){
    		ans+=(upper_bound(be(v2[k-i]),r-v1[i][j])-lower_bound(be(v2[k-i]),l-v1[i][j]));
    	}
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 23436
// TEMPLATE {{{
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#define OJ 1
#else
#define OJ 0
#endif
 
#define endl '\n'
#define TIMESTAMP merr << "Execution time: " << (double)clock()/CLOCKS_PER_SEC << " s.\n"
class C_ {}; template <typename T> C_& operator <<(C_& __m, const T& __s) { if (!OJ) cerr << "\E[91m" << __s << "\E[0m"; return __m; }
C_ merr;
 
struct __s { __s() { if (OJ) { ios_base::Init i; cin.sync_with_stdio(0); cin.tie(0); } } ~__s(){ TIMESTAMP; } } __S;
/// END OF TEMPLATE }}}

#define size_t unsigned long long

size_t C[111111];
vector<pair<size_t,size_t>> G[111111];
void dfs(size_t v, size_t c) {
    if (C[v] != 0) return;
    C[v] = c;
    for (auto p : G[v]) {
        size_t vv, w;
        tie(vv, w) = p;
        if (w%2 == 0) {
            dfs(vv, c);
        } else {
            dfs(vv, c == 1 ? 2 : 1);
        }
    }
}

int main(void) {
    size_t n;
    cin >> n;
    vector<size_t> U(n-1), V(n-1), W(n-1);
    for (size_t i = 0; i < n-1; i++) {
        cin >> U[i] >> V[i] >> W[i];
        U[i]--;
        V[i]--;
        G[U[i]].emplace_back(V[i], W[i]);
        G[V[i]].emplace_back(U[i], W[i]);
    }
    dfs(0, 1);
    for (size_t i = 0; i < n; i++) {
        cout << C[i]-1 << endl;
    }
}


Measured memory_bytes: 12672
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ll long long
long long cnt = 1, ans;
int main() {

	int n;
	cin >> n;
	vi arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		
	}
	int mn=arr.back();
	for (int i = n-1; i>=0; i--) {
		mn=min(mn,arr[i]);
		if(arr[i]-mn>1)return cout<<"No",0;
	}
	cout << "Yes";
	return 0;
}



Measured memory_bytes: 640
/*
Mangal bhavan amangal haari
Drabahu su Dasharath achar Bihari
Raam Siya Raam Siya Raam jai jai Raam
Raam Siya Raam Siya Raam jai jai Raam
Ho hoi hai wohi jo Raam rachi raakha
Ko kari tarak badhave saakha
Raam Siya Raam Siya Raam jai jai Raam
Ho dheeraj dharam mitra aru naari
Aapad kaal parakhiye chaari
Ho jehike jehi par satya sanehu
So tehi milay na kachhu sandehu
Ho jaaki rahi bhawana jaisi
Prabhu murati dekhi tin taisi
Ho Raghukul reet sada chali aayi
Praan jaaye par vachan na jaayi
Raam Siya Raam Siya Raam jai jai Raam, Raam
Raam Siya Raam Siya Raam jai jai Raam
Ho hari anant hari katha ananta
Kahahi sunahi bahuvidhi sab santa
Raam Siya Raam Siya Raam jai jai Raam, Raam
Raam Siya Raam Siya Raam jai jai Raam
Raam Siya Raam Siya Raam jai jai Raam
*/


#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
//auto->.
//map<int,int>::iterator i
vector<int> sieve(int n) 
{ 

    vector<bool> prime(n+1,true); 
       
    prime[0] = false; 
    prime[1] = false; 
    int m = sqrt(n); 
   vector<int> ans;

    for (int p=2; p<=m; p++) 
    { 
    
        if (prime[p]) 
        { 
         
            for (int i=p*2; i<=n; i += p) 
            prime[i] = false; 
        } 
    }  
    //vector<int> ans; 
    for (int i=0;i<n;i++) 
        if (prime[i]) 
            ans.push_back(i); 
    return ans; 
}

int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int mod = 1e9 + 7;
int power(int a , ll b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)
			res = 1LL * res * a ;//% mod;
		a = 1LL * a * a ;//% mod;
		b >>= 1;
	}
	return res;
}
bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
}
ll min(int a,ll b)
{
	if(a>b)
	return b;
	return a;
}
ll max(int a,ll b)
{
	if(a>b)
	return a;
	return b;
}
ll myXOR(ll x, ll y) 
{ 
   return (x | y) & (~x | ~y); 
}
int conti(int x)
{
	if(x<1)
	return 0;
	if(x%4==0)
	return x;
	if(x%4==1)
	return 1;
	if(x%4==2)
	return x+1;
	if(x%4==3)
	return 0;
}
 
bool ispfsq(long double x) 
{   
  // Find floating point value of  
  // square root of x. 
  long double sr = sqrt(x); 
  
  // If square root is        an integer 
  return ((sr - floor(sr)) == 0); 
}
#define PI 3.141592653589793


vector<int > adj[200005];
bool visited[2005][2005];
int ch[100005],dep[100005];
void solve()
{
ll n;
cin>>n;
if(n%1000==0)
{
	cout<<0;
	return ;
}
cout<<1000-n%1000;
}

int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
int mul=0;
if(mul==1)
{
 int t;
    cin>>t;
   while(t--)
    {
		solve();
	cout<<"\n";
    }
    
}
else
{
//	fun();
	solve();
}
}

Measured memory_bytes: 8360