akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(var) var.begin(), var.end()
#define vi vector<int>
int const MOD = 1e9+7;
typedef long long ll;
using namespace std;
 
int main(){
    string s;
    int q;
    cin >> s >> q;
    bitset<1> rev;
    while(q--){
        int n; cin >> n;
        if(n == 1) rev.flip();
        else{
            int x; cin >> x;
            char c;cin >> c;
            if(x == 1 && rev[0] || x == 2 && !rev[0]) s.push_back(c);
            else s.insert(s.begin(),c);
        }
    }

    if(rev[0]) 
        for(auto itr = s.rbegin(); itr != s.rend(); itr++)
            cout << *itr;
    else
        cout << s;
    cout << endl;
}


Measured memory_bytes: 1028
#include<stdio.h>
#include<stdlib.h>

int compare(const void *a, const void *b){
	int *A = (int *)a;
	int *B = (int *)b;
	if (*A > *B) return 1;
	if (*A < *B) return -1;
	return 0;
}

int main(){
	int s[3];
	scanf("%d%d%d",&s[0],&s[1],&s[2]);
	
	qsort(s,3,sizeof(int),compare);
	printf("%d\n",s[0]+s[1]+s[2]*10);
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define umap unordered_map<ll, ll>
using namespace std;

ll gcd(ll x, ll y){
    if(y == 0){
        return x;
    }
    return gcd(y, x%y);
}

ll lcm(ll x, ll y){
    return x*(y/gcd(x, y));
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n, a, ans = 0;
    cin >> n;
    vll x;
    
    for(ll i=0; i<n; i++){
        cin >> a;
        x.push_back(a);
    }
    
    ans = x[0];
    for(ll i=1; i<n; i++){
        ans = lcm(ans, x[i]);
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3568
n = int(input())
a = list(map(int, input().split()))

def ruiseki(a):
    right, left = [], []
    l, r = 0, 0
    for i in range(n):
        l += a[i]
        left.append(l)
    
        r += a[-(i+1)]
        right.append(r)
    return left, right[::-1]

l, r = ruiseki(a)
ans = [abs(l[i] - r[i+1]) for i in range(n-1)]
print(min(ans))

Measured memory_bytes: 40300
#include<cstdio>
#include<algorithm>
#include<climits>
 
#define max_n (1<<18)
 
using namespace std;
 
int dat[max_n],n;
 
void update(int k,int a){
  for(k+=n,dat[k]=a;k>1;k>>=1)
    dat[k>>1]=min(dat[k],dat[k^1]);
}
 
int rmq(int a,int b){
  int res=INT_MAX;
  for(a+=n,b+=n;a<=b;a=(a+1)>>1,b=(b-1)>>1){
    if(a&1)res=min(res,dat[a]);
    if(!(b&1))res=min(res,dat[b]);
  }
    return res;
}
 
int main(void){
  
  fill(dat,dat+max_n,INT_MAX);
  int q;
  scanf("%d %d",&n,&q);
  
  while(q--){
    int com,x,y;
    scanf("%d %d %d",&com,&x,&y);
    if(com)printf("%d\n",rmq(x,y));
    else update(x,y);
  }
  return 0;
}

Measured memory_bytes: 2052
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        long n = scanner.nextLong(), p = scanner.nextLong(), r = 1;
        if (n == 1) {
            System.out.println(p);
        } else {
            for (long i = 2; i * i <= p; i++) {
                int c = 0;
                while (p % i == 0) {
                    c++;
                    p /= i;
                }
                for (long j = 0; j < c / n; j++)
                    r *= i;
            }
            System.out.println(r);
        }
    }
}

Measured memory_bytes: 23892
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a1 = new int[n+1];
        int[] a2 = new int[n+1];
        for(int i = 0; i < n; i++){
            a1[i+1] = a1[i] + sc.nextInt();
            
        }
        for(int i = 0; i < n; i++){
            a2[i+1] = a2[i] + sc.nextInt();
        }
        int max = 0;
        for(int i = 0; i < n; i++){
            max = Math.max(max, a1[i+1] + a2[n] - a2[i]);
        }
        System.out.println(max);
    }
}


Measured memory_bytes: 22100
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
	int N, A, B;
	scanf("%d %d %d", &N, &A, &B);
	if (A*N < B) {
		printf("%d", A*N);
	}
	else {
		printf("%d", B);
	}
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner t = new Scanner(System.in);
        int a = t.nextInt();
        int b = t.nextInt();
        int sum = 0; 
        if (a>=b){
            sum+=a;
            a--;
        } else {
            sum+=b;
            b--;
        }
        if (a>=b){
            sum+=a;
            a--;
        } else {
            sum+=b;
            b--;
        }
        System.out.println(sum);
    }   
}

Measured memory_bytes: 23124
P = 10**9 + 7
N = int(input())
a, b, c = 1, 1, 1
for _ in range(N):
    a = (10 * a) % P
    b = (9 * b) % P
    c = (8 * c) % P
ans = (a - 2 * b + c) % P
print(ans)

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , "; logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

struct edge{
    int from, to; lint cost;
    edge(int f, int t, lint c) : from(f), to(t), cost(c) {}
    edge(int t, lint c) : from(-1), to(t), cost(c) {}
};

struct dijkstra{
    vector<vector<edge> > G;
    vector<lint> d;
    int V, s;
    dijkstra(vector<vector<edge> > _G, int _s) : G(_G), s(_s){
        init();
    }
    void init(){
        V = G.size();
        d = vector<lint>(V, INF);
        priority_queue<P, vector<P>, greater<P> > que; que.push(P(0, s));
        d[s] = 0;
        while(!que.empty()){
            P p = que.top(); que.pop();
            int v = p.second;
            if(d[v] < p.first) continue;
            for(int i = 0; i < G[v].size(); i++){
                edge e = G[v][i];
                if(d[e.to] > d[v] + e.cost){
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
    }
    int dist(int t){
        return d[t];
    }
};

int main(){
    int n,m,s,t; cin>>n>>m>>s>>t;
    s--; t--;
    vector<vector<edge> > ga(n), gb(n);
    rep(i,m){
        lint u,v,a,b; cin>>u>>v>>a>>b;
        u--; v--;
        ga[u].push_back(edge(v,a));
        ga[v].push_back(edge(u,a));
        gb[u].push_back(edge(v,b));
        gb[v].push_back(edge(u,b));
    }

    dijkstra da(ga, s), db(gb, t);
    
    vector<P> vp;
    const lint L = 1e15;
    rep(i,n){
        lint c = da.d[i] + db.d[i];
        vp.push_back(P(L-c, i));
    }
    sort(all(vp), greater<P>());

    int j = 0;
    rep(i, n){
        while(1){
            if(vp[j].se < i){
                j++; continue;
            }else break;
        }
        out(vp[j].fi);
    }
}


Measured memory_bytes: 40504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=205,INF=1<<30;
vector<int> dy0={1,0,-1,-1,-1,0,0},dy1={1,1,0,-1,0,1,0},dx={0,1,1,0,-1,-1,0};
int X,Y;
int dis[6][MAX][MAX];
bool cant[MAX][MAX];

int to(int x,int y,int t){
    int idx=abs((x-100)*(y-100)*t)%6;
    return idx;
}

bool check(int x,int y){
    //if(abs(x-100)>X||abs(y-100)>Y) return false;
    if(x<100-X||x>100+X||y<100-Y||y>100+Y) return false;
    if(cant[x][y]) return false;
    return true;
}

struct dat{
    int t;
    int x;
    int y;
};

void BFS(int sx,int sy){
    queue<dat> Q;
    Q.push(dat{0,sx,sy});
    
    while(!Q.empty()){
        dat u=Q.front();Q.pop();
        for(int k=0;k<7;k++){
            int go=to(u.x,u.y,u.t);
            
            int tox=u.x+dx[k],toy=u.y,tot=(u.t+1)%6;
            if(u.x&1) toy+=dy1[k];
            else toy+=dy0[k];
            if(check(tox,toy)){
                if(chmin(dis[tot][tox][toy],dis[u.t][u.x][u.y]+int((k!=go)))){
                    Q.push(dat{tot,tox,toy});
                }
            }
        }
    }
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int sx,sy,gx,gy;cin>>sx>>sy>>gx>>gy;
    sx+=100;sy+=100;
    gx+=100;gy+=100;
    int N;cin>>N;
    for(int i=0;i<N;i++){
        int x,y;cin>>x>>y;
        cant[x+100][y+100]=1;
    }
    cin>>X>>Y;
    
    for(int t=0;t<6;t++){
        for(int x=0;x<MAX;x++){
            for(int y=0;y<MAX;y++){
                dis[t][x][y]=INF;
            }
        }
    }
    
    dis[0][sx][sy]=0;
    
    BFS(sx,sy);
    
    int ans=INF;
    for(int t=0;t<6;t++){
        chmin(ans,dis[t][gx][gy]);
    }
    if(ans==INF) ans=-1;
    cout<<ans<<endl;
}




Measured memory_bytes: 4320
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ss second
#define ff first
#define pb push_back
#define mp make_pair
int n,m;
ll sum=0;
int a[100100];
vector<pair<int,int> > v;
int main() {
   cin>>n>>m;
   for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
   for(int i=0;i<m;i++)
   {
       int b,c;
       scanf("%d%d",&b,&c);
       v.pb(mp(c,b));
   }
   sort(a,a+n);
   sort(v.begin(),v.end());
   reverse(v.begin(),v.end());
   int cr=0;
   for(int i=0;i<n;i++)
   {
       if(v[cr].ss==0)
        cr++;
       if(cr>=v.size())
        break;
       if(v[cr].ff<=a[i])
        break;
       a[i]=v[cr].ff;
       v[cr].ss--;
   }
   for(int i=0;i<n;i++)
    sum+=a[i];
   cout<<sum;
   return 0;
}


Measured memory_bytes: 1784
#include <bits/stdc++.h>
using namespace std;
stack<int> S;
int main()
{
    int a,b;
    char s[100];
    while(scanf("%s",s)!=EOF)
    {
        if(s[0]=='+')
        {
            a=S.top();
            S.pop();
            b=S.top();
            S.pop();
            S.push(a+b);
        }
        else if(s[0]=='-')
        {
            b=S.top();
            S.pop();
            a=S.top();
            S.pop();
            S.push(a-b);
        }
        else if(s[0]=='*')
        {
            a=S.top();
            S.pop();
            b=S.top();
            S.pop();
            S.push(a*b);
        }
        else
            S.push(atoi(s));
    }
    printf("%d\n",S.top());
    return 0;
}

Measured memory_bytes: 3228
import sys
from operator import itemgetter
from collections import deque

input = sys.stdin.readline


def main():
    S = input().rstrip()

    stack = deque()
    M = []
    for i, s in enumerate(S):
        if s == "/":
            if len(stack) == 0:
                pass
            else:
                j = stack.pop()
                M.append((j, i))
        elif s == "\\":
            stack.append(i)
        else:
            pass

    M.sort(key=itemgetter(0))
    L = []
    r = -1
    for i, j in M:
        if r < i:
            r = j
            L.append(j - i)
        else:
            L[-1] += (j - i)

    A = sum(L)
    k = len(L)

    print(A)
    if k == 0:
        print(k)
    else:
        print(" ".join([str(k), " ".join(map(str, L))]))


if __name__ == "__main__":
    main()



Measured memory_bytes: 7348
N = int(input())
N_list = [0]*(N+1)

for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
           if(i**2+j**2+k**2+i*j+j*k+k*i<=N):
               N_list[i**2+j**2+k**2+i*j+j*k+k*i]+=1
for i in N_list[1:]:
    print(i)

Measured memory_bytes: 9292
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i = 0; i < N; i++) {
			list.add(sc.nextInt());
		}
		list.sort(Comparator.reverseOrder());
		int count = 0;
		for(int i = 1; i < list.size(); i++) {
			if(list.get(i) == list.get(i-1)) {
				continue;
			}else{
				count++;
			}
		}
		System.out.println(count + 1);
	}

}


Measured memory_bytes: 22996
a = int(input())
list = input().split()
for j in range(a):
	list[j] = int(list[j])
gcd = list[0]
for i in range(a):
	m = list[i] 
	n = gcd
	while n != 0:
		m,n = n,m%n
	if(m<gcd):
		gcd = m
print(gcd)

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

int energy(int N, int X[], int ave){

    int sum = 0;
    for(int i = 0; i < N; i++){
        sum += pow((X[i] - ave), 2);
    }

    return sum;
}

int main(){

    int N;
    cin >> N;
    int X[N];
    int sum = 0;
    for(int i = 0; i < N; i+=1){
        cin >> X[i];
        sum += X[i];
    }

    int ave_cut = sum/N;
    int ave_up = ave_cut + 1;

    cout << min(energy(N, X, ave_cut), energy(N, X, ave_up)) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
    {
        return a;
    }
    else{return gcd(b,a%b);}
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int k;cin>>k;long long sum=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=k;j++)
        {
            for(int l=1;l<=k;l++)
            {
                int b=gcd(i,j);int t=gcd(b,l);
                sum+=t;

            }
        }
    }
    cout<<sum;
}


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

using namespace std;
#define ll         long long
#define f(n)       for(int i = 0; i < n; i++)
#define pb         push_back
#define mp         make_pair
#define vi         vector<int>
#define w(t)       while(t--)
#define all(v)     v.begin(),v.end()

int main()
{
    int n, k, dist;
    cin >> k >> n;
    vi v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    dist = v[n - 1] - v[0];
    for(int i = 1; i < n; i++){
        dist = min(dist, k - (v[i] - v[i - 1]));
    }
    cout << dist << endl;
    return 0;
}


Measured memory_bytes: 1024
x,k,d = map(int, input().split())

if x > 0:
    kaisu = x//d
    if x//d <= k:
        k -= kaisu
        x -= kaisu*d
    else:
        x -= k*d
        k = 0
else:
    kaisu = -(x//d) 
    if kaisu <= k:
        k -= kaisu
        x += kaisu*d
    else:
        x += k*d
        k = 0

if k%2 == 0:
    print(abs(x))
else:
    print(abs(x-d))


Measured memory_bytes: 61700
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s,t;
  cin>>s>>t;
  int m=s.length();
  bool flag=false;
  for(int i=0;i<m;i++)
  {
    if(s[i]!=t[i])
    {
      flag=true;break;
    }
  }
  if(flag)
    cout<<"No";
  else
    cout<<"Yes";
  return 0;
}

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

#define F first
#define S second
#define PB push_back

using namespace std;

typedef long long ll;

int n, k;
ll h[100005];
ll memo[100005];

ll dp(int i){
	if(i == n-1)	return 0;
	if(i >= n)	return 10000000000;
	if(memo[i] != -1){
		return memo[i];
	}
	
	ll mmin = 1e10;

	for(int j = 1; j <= k; j++){
		mmin = min(abs(h[i] - h[i+j]) + dp(i+j), mmin);
	}

	return memo[i] = mmin;

}

int main(){

    memset(memo, -1, sizeof(memo));
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

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

	cout << dp(0) << "\n";

	return 0;
}

Measured memory_bytes: 6528
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
life = 0

for i in range(n):
  life += b[a[i]-1]
  if i != 0 and a[i-1] == a[i]-1:
    life += c[a[i-1]-1]

print(life)

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline
s=input().replace('\n','')
q=int(input())
num1=0
sento=''
matsubi=''

for i in range(q):
    query=input()
    if query[0]=='1':
        num1+=1
    else:
        query=query.replace('\n','')
        _,f,c=map(str,query.split())
        if f=='1':
            if num1%2==0:
                sento=c+sento
            else:
                matsubi+=c
        else:
            if num1%2==0:
                matsubi+=c
            else:
                sento=c+sento
ans=sento+s+matsubi
if num1%2==0:
    print(ans)
else:
    print(ans[::-1])


Measured memory_bytes: 4628
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <bitset>
using namespace std;
typedef long long int lli;
int main(void)
{
    int N;
    cin >> N;
    vector<int> h;
    int tmp;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        h.push_back(tmp);
    }
    int ans = 0;
    int cnt = 0;
    vector<int> cntarray;
    for (int i = 0; i < N - 1; i++)
    {
        if (h[i] >= h[i + 1])
        {
            cnt++;
            ans = max(ans, cnt);
        }
        else
        {
            cnt = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

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

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

    bool appear[26] = {};
    for(int i = 0; i < s.length(); i++){
        appear[s[i]-'a'] = true;
    }

    for(int i = 0; i < 26; i++){
        if(!appear[i]){
            cout << (char)(i+'a') << endl;
            return 0;
        }
    }

    cout << "None" << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
using P = pair<int,int>;
using ivec = vector<int>;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }


const int MOD=1000000007;
int INF=100100100100100;
int x,y,z;
signed main(){
  int n;cin>>n;
  int a,b;cin>>a>>b;
  rep(i,n){
    int p;cin>>p;
    if(p<=a)x++;
    if(a<p && p<=b)y++;
    if(b<p)z++;
  }
  cout<<min(x,min(y,z))<<endl;
  return 0;
}

Measured memory_bytes: 3588
def calc(K, N, A):
    B = [A[i + 1] - A[i] for i in range(N - 1)] + [A[0] + K - A[N - 1]]
    return K - max(B)


(K, N) = tuple([int(s) for s in input().split()])
A = [int(s) for s in input().split()]
print(calc(K, N, A))

Measured memory_bytes: 26436
import java.util.*;

public class Main {
	static class Node {
		int day=0;
		int inNum;
		ArrayList<Node> out = new ArrayList<>();
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[][] A = new int[N][N-1];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N-1; j++) {
				A[i][j] = sc.nextInt()-1;
			}
		}
		
		Node[][] n = new Node[N][N];
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				n[i][j] = new Node();
				n[j][i] = n[i][j];
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N-2; j++) {
				n[i][A[i][j]].out.add(n[i][A[i][j+1]]);
				n[i][A[i][j+1]].inNum++;
			}
		}
	
		ArrayDeque<Node> q = new ArrayDeque<>();
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				if(n[i][j].inNum==0) {
					n[i][j].day=1;
					q.add(n[i][j]);
				}
			}
		}
		if(q.isEmpty()) {
			System.out.println(-1);
			sc.close();
			return;
		}
		
		for(int i=0; i<1000000 && q.size()>0; i++) {
			Node cur = q.poll();
			for(Node next : cur.out) {
				next.day = Math.max(next.day, cur.day+1);
				next.inNum--;
				if(next.inNum==0) {
					q.add(next);
				}
			}
		}
		
		
		int max = 0;
		int min = 1;
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				max = Math.max(max, n[i][j].day);
				min = Math.min(min, n[i][j].day);
			}
		}
		
		System.out.println(min==0 ? -1 : max);
		
		sc.close();
	}
}



Measured memory_bytes: 329164
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;

const ll mod = 1000000007;
ll fact[200200];
ll invfact[200200];

inline ll take_mod(ll a) { return (a % mod + mod) % mod; }

inline ll add(ll a, ll b) { return take_mod(a + b); }

inline ll sub(ll a, ll b) { return take_mod(a - b); }

inline ll mul(ll a, ll b) { return take_mod(a * b); }

inline ll pow(ll x, ll n) {
  ll res = 1LL;
  while (n > 0) {
    if (n & 1) res = mul(res, x);
    x = mul(x, x);
    n >>= 1;
  }
  return res;
}

ll mod_inv(ll x) { return pow(x, mod - 2); }

void make_fact(ll n) {
  fact[0] = 1;
  ll res = 1;
  for (int i = 1; i <= n; i++) {
    fact[i] = res;
    res = mul(res, i + 1);
  }
}

void make_invfact(ll n) {
  invfact[0] = 1;
  invfact[n] = mod_inv(fact[n]);
  for (int i = n - 1; i >= 1; i--) {
    invfact[i] = mul(invfact[i + 1], i + 1);
  }
}

ll perm(ll n, ll k) { return mul(fact[n], invfact[n - k]); }

ll comb(ll n, ll k) { return mul(mul(fact[n], invfact[n - k]), invfact[k]); }

const ll INF = 1 << 30;

int main() {
  ll N, K;

  cin >> N >> K;

  vll ts(N + 1);

  for (ll i = 1; i <= N; i++) {
    ll tmp;
    cin >> tmp;
    ts[i] = (ts[i - 1] + tmp + K - 1) % K;
  }

  ll ans = 0;
  map<ll, ll> mp;
  queue<ll> q;
  for (ll i = 0; i <= N; i++) {
    ans += mp[ts[i]];
    mp[ts[i]]++;
    q.push(ts[i]);
    if ((ll)q.size() > K - 1) {
      mp[q.front()]--;
      q.pop();
    }
  }

  cout << ans << endl;

  return 0;
}


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

int main(){
    int a, n, k, q;
    std::cin >> n >> k >> q;
    std::vector<int> b(n, k-q); 
    for(int i=0; i<q; i++){
        std::cin >> a;
        b[a-1]++;
    }
    for(int i=0; i<n; i++){
        // std::cout <<b[i] << "  ";
        if(b[i]>0) std::cout << "Yes" << std::endl;
        else       std::cout << "No"  << std::endl;
    }
	return 0;
}


Measured memory_bytes: 1024
n,k=map(int,input().split())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
d=[False]*(n+1)
q=[[0,1]]
c=0
a=k
while q:
    t=[]
    c=0
    for i,j in q:
        c=0
        for p in s[j]:
            if p!=i:
                t.append([j,p])
                c+=1
        r=(k-1 if j==1 else k-2)
        for h in range(r,r-c,-1):
            a=(a*h)%(10**9+7)
    q=t
print(a)

Measured memory_bytes: 32948
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

int main() {
    fastio();

    int n;
    cin >> n;
    ll ans = 0;
    forn1(i, n) {
        if (i % 3 != 0 && i % 5 != 0) {

            ans += i;
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main () {
  int N;
  cin >> N;
  vector<long long>A(N);
  long long sum = 0;
  int count = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    if (A.at(i) < 0){
      count++;
    }
    A.at(i) = abs(A.at(i));
  }
  
  if (count % 2 == 0){
    for (int i = 0; i < N; i++) {
      sum += A.at(i);
    }
  }
  
  else {
    sort(A.begin(), A.end());
    for (int i = 0; i < N; i++) {
      sum += A.at(i);
    }
    sum -= A.at(0)*2;
  }
  
  cout << sum << endl;
}
    
  
    

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

typedef long long ll;
typedef pair<int,int> P;

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> a(n+2);
    a[0] = -1;
    a[1] = 0;
    a[2] = 1;
    for (int i = 1;i < n;++i) {
        if (s[i] == s[i-1]) a[i+2] = a[i-1]+2;
        else a[i+2] = a[i+1]+1;
    }
    cout << a[n+1] << endl;
    return 0;
}

Measured memory_bytes: 1412
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
//import std.regex;
import std.container;

void main()
{
	int n;
	while (n = readln.chomp.to!int, n) {
		auto mem = new int[][](n, 2);
		foreach (i; 0..n) {
			auto m = readln.split.map!(to!int);
			auto score = m[1..m.length].reduce!("a+b");
			
			int j = 1;
			foreach (_; 1..10) {
				if (m[j] == 10) {
					score += m[j+1] + m[j+2];
					j++;
				} else if (m[j] + m[j+1] == 10) {
					score += m[j+2];
					j += 2;
				} else {
					j += 2;
				}
			}
			mem[i][0] = m[0];
			mem[i][1] = score;
		}
		foreach (e; mem.sort!("a[1] == b[1] ? a[0] < b[0] : a[1] > b[1]")) {
			writeln(e[0], " ", e[1]);
		}
	}
}

Measured memory_bytes: 1252
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<60);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  a=abs(a);
  b=abs(b);
  if(a==0)return b;
  if(b==0)return a;
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(std::string T){
  for (auto &&i : T)
  {
    if(i=='?')i='D';
  }
  cout<<T<<endl;
}

int main(){
  cout<<setprecision(1000);
    std::string T;
    std::cin >> T;
    solve(T);
    return 0;
}


Measured memory_bytes: 3920
def isInt?(a)
    Integer(a)
    true
rescue ArgumentError
    false
end

def calc(ope, a, b)
    case ope
    when "+" then
        a + b
    when "-" then
        a - b
    when "*" then
        a * b
    end
end

def main()
    stack = []
    inData = gets.chomp.split(" ")
    inData.each{|x|
        if isInt?(x) then
            stack.push(x.to_i)
        else
            b = stack.pop
            a = stack.pop
            stack.push(calc(x, a, b))
        end
    }
    puts stack
end

main()

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

typedef long long ll;
#define pii pair<int , int>
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 1005

int n , m;

int main()
{
    _FastIO;
    cin >> n;
    string s , t;
    cin >> s >> t;
    for(int i = 0; i < n; i++){
        cout << s[i] << t[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 384
N=int(input())
A=list(map(int,input().split()))
list.sort(A,reverse=True)
if A[-1]==0:
  print(0)
  exit()
ans=A[0]
for i in range(1,len(A)):
  ans*=A[i]
  if 10**18<ans:
    print(-1)
    exit()
print(ans)


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

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

    if (n <= 1 || m <= 1) {
        int l = n + m - 1;
        if (l == 1) {
            cout << 1;
            return 0;
        }
        cout << l - 2;
        return 0;
    }

    long long ans = 1ll * (n - 2) * (m - 2);

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


Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int r, c;
    int i, j, num;
    int a[101][101]={};
    
    scanf("%d%d", &r, &c);
    for(i=0; i<r; i++) {
        for(j=0; j<c; j++) {
            scanf("%d", &num);
            a[i][j]+=num;
        }
    }

    for(i=0; i<r; i++) {
        for(j=0; j<c; j++)
            a[i][c]+=a[i][j];
    }
    
    for(j=0; j<c+1; j++) {
        for(i=0; i<r; i++)
            a[r][j]+=a[i][j];
    }
    
    for(i=0; i<r+1; i++) {
        for(j=0; j<c+1; j++) {
            printf("%d", a[i][j]);
            if(j<c) putchar(' ');
            if(j==c) putchar('\n');
        }
    }
    return 0;
}



Measured memory_bytes: 2100
# -*- coding: utf-8 -*-

W, H, N = map(int, input().split())
xs = ys = 0
xe = W
ye = H
for i in range(N):
    x, y, a = map(int, input().split())
    if a == 1 and x > xs:
        xs = x
    elif a == 2 and x < xe:
        xe = x
    elif a == 3 and y > ys:
        ys = y
    elif a == 4 and y < ye:
        ye = y

w = xe - xs
h = ye - ys
if w > 0 and h > 0:
    ans = w * h
else:
    ans = 0

print(ans)


Measured memory_bytes: 9140
#include <iostream>
using namespace std;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a + c == b)
		cout << "Yes" << "\n";
	else if (a + b == c)
		cout << "Yes" << "\n";
	else if (b + c == a)
		cout << "Yes" << "\n";
	else
		cout << "No" << "\n";
}

Measured memory_bytes: 3596
S = str(input())
if S[-1] == '2' or S[-1]=='4' or S[-1] == '5'or S[-1]=='7' or S[-1]=='9':
    print('hon')
elif S[-1] == '0' or S[-1] == '1' or S[-1] == '6' or S[-1] == '8':
    print('pon')
else:
    print('bon')

Measured memory_bytes: 61636
#pragma region include
#include <stdio.h>
#include <string>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <bitset>
#include <cmath>
#include <tuple>
#pragma endregion
using namespace std;

#pragma region 定数
#define INF_VAL (2147483647 - 1)
#define INF_VAL_MINUS -INFVAL
#pragma endregion

#pragma region マクロ
// 型
#define ll long long

// 配列の長さを取得する(ただし関数内ではポインタサイズに注意)
#define SIZE_OF_ARRAY(array) sizeof(array) / sizeof(*array)

// for文
#define forn(i, size) for (long long(i) = 0; (i) < (size); (i)++)
#define for0(size) for (long(i) = 0; (i) < (size); (i)++)

// ソート
#define Sort(array, length) sort(array, array + length)
#define SortDESC(array, length, type_name) sort(array, array + length, std::greater<type_name>())

// 配列の最大値、最小値取得
#define MAX_OF_ARRAY(array, length) *max_element(array, array + length)
#define MIN_OF_ARRAY(array, length) *min_element(array, array + length)

// 結果出力系
#define YES                    \
    {                          \
        cout << "YES" << endl; \
        return 0;              \
    }
#define NO                    \
    {                         \
        cout << "NO" << endl; \
        return 0;             \
    }
#define Yes                    \
    {                          \
        cout << "Yes" << endl; \
        return 0;              \
    }
#define No                    \
    {                         \
        cout << "No" << endl; \
        return 0;             \
    }
#define println(str) cout << str << endl;

#pragma endregion

#pragma region Utility
#pragma region 最大公約数
ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}
#pragma endregion

#pragma region 最小公倍数
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
#pragma endregion

#pragma region 配列要素の合計値を取得
template <typename T>
T getSum(T array[], int length)
{
    T sum = 0;
    for (int i = 0; i < length; i++)
    {
        sum += array[i];
    }
    return sum;
}
#pragma endregion

#pragma region ToString(int)
string ToString(int i)
{
    char buffer[1000];
    sprintf(buffer, "%d", i);
    return string(buffer);
}
#pragma endregion

#pragma region 10進数からN進数(<= 10) へ変換
string convertToN(long n, int base)
{
    string ans = "";
    while (n != 0)
    {
        int temp = n % base; // 1桁取得
        ans = ToString(temp) + ans;
        n /= base;
    }
    return ans;
}
#pragma endregion

#pragma region 連想配列のkeyが存在するか
template <typename T>
bool containsKey(map<string, T> map, string key)
{
    if (map.count(key) == 0)
    {
        return false;
    }
    return true;
}
#pragma endregion
#pragma endregion

int main()
{
    // 標準入力から値を取得
    char C;
    cin >> C;

    C = C + 1;

    // 結果出力
    println(C);
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;
const char k[20][20]={{" "},{" KIHBR"},
{" AKIHBR"},{" KIHABR"},{" KIHBAR"},{" KIHBRA"},
{" AKIHABR"},{" AKIHBAR"},{" AKIHBRA"},
{" KIHABAR"},{" KIHABRA"},{" KIHBARA"},
{" AKIHABAR"},{" AKIHABRA"},{" AKIHBARA"},
{" KIHABARA"},{" AKIHABARA"}};
char c[51];
int main(){
	scanf("%s",c+1);
	int n=strlen(c+1);
	if(n<5 || n>9){
		printf("NO");
		return 0;
	}
	for(register int i=1;i<=16;i++){
		bool flag=1;
		for(register int j=1;j<=strlen(k[i]+1);j++){
			if(c[j]!=k[i][j]){
				flag=0;
				break;
			}
		}
		if(flag){
			printf("YES");
			return 0;
		}
	}
	printf("NO");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
#define BOOST        std::ios::sync_with_stdio(false);  cin.tie(NULL); cout.tie(NULL);
#define sp           <<" "<<
#define ll           long long
#define ld           long double
#define AZI(i,x)     for(auto i=x.begin();i!=x.end();i++)
#define AZ(x)        x.begin(),x.end()
#define P(x,y)       pair < x,y >
#define V(x)         vector < x >
#define fi           first
#define se           second
#define pb           push_back
#define mp           make_pair
#define PI           3.14159265358979323846264338327950288419716939937510

// find_by_order(int k) - returns k'th smallest element (0-indexed)
// order_of_key(int k) - returns number of elements strictly smaller than k.
// using namespace __gnu_pbds;
// #define ordered_set tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>

const ll mod=1e9+7,N=1e5+5,INF = 1e18;

ll power(ll a,ll b)
{
    a = a%mod;
    ll result = 1;

    while(b)
    {
        if(b&1)
            result = (result*a)%mod;
        b >>= 1, a = (a*a)%mod;
    }
    return result;
}


/*

1. Make sure you're taking all the inputs.
2. In case of nested loops, remember to use different variables.
3. If in doubt, do int -> ll
4. Don't fight the question, try solving the next one.

*/



//  Don't code anything above this //


bool cmp(P(int,int) a,P(int,int) b)
{
    if(a.fi == b.fi)
        return a.se < b.se;
    return a.fi < b.fi;
}


int main() 
{ 
    BOOST

    int n;
    cin>>n;

    P(int,int) job[n];

    for(auto &i : job)
    {
        int a,b;
        cin>>a>>b;
        i = {b, a};
    }

    sort(job,job+n,cmp);

    int cur_time = 0;
    for(auto i : job)
    {
        if(cur_time + i.se > i.fi)
            return cout<<"No\n",0;
        cur_time += i.se;
    }
    cout<<"Yes\n";
    return 0;    
}

Measured memory_bytes: 1920
#include <map>
#include <vector>
#include <cstdio>
using namespace std;
int main(){
	int n=0,N,i,j,k,c;
	scanf("%d",&N);
	vector<map<int,int> >dist(N);
	vector<bool>used(N);
	vector<int>cost(N);
	for(;n<N;n++){
		cost[n]=1e9;
		for(scanf("%d%d",&i,&k);k--;dist[i][j]=c)scanf("%d%d",&j,&c);
	}
	for(cost[0]=0;;){ //dijkstra
		int m=1e9;
		for(i=0;i<N;i++)if(!used[i]&&m>cost[i])m=cost[i];
		if(m==1e9)break;
		for(j=0;j<N;j++)if(m==cost[j]){
			map<int,int>::iterator it=dist[j].begin();
			for(used[j]=1;it!=dist[j].end();it++)if(cost[it->first]>it->second+cost[j])cost[it->first]=it->second+cost[j];
		}
	}
	for(i=0;i<n;i++)printf("%d %d\n",i,cost[i]);
}

Measured memory_bytes: 24488
using System;

class Program{
    static void Main(){
        string s = Console.ReadLine();
        int i;
        int bc=0;
        long ret=0;
        for (i = 0; i < s.Length; i++){
            if (s[i] == 'W'){
                ret += bc;
            }else{
            bc++;
            }
        }
        Console.WriteLine(ret);
    }
}

Measured memory_bytes: 11616
#include <bits/stdc++.h>
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;
#define PI 3.14159265359
#define tMOD 998244353
#define mkpr(x,y) make_pair(x,y)

int main(){
    ll N,M;
    cin>>N>>M;

    cout<<((N*(N-1))/2)+((M*(M-1))/2)<<endl;




}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
int num[200005];
bool cmp(int x, int y) {
	return x > y;
}
long long sum = 0;
int main() {
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++) {
		cin >> num[i];
	}
	sort(num + 1, num + n + 1,cmp);
	for (int i = 1;i <= n-1;i++) {
		int k = i / 2 + 1;
		sum += num[k];
	}
	cout << sum << endl;
}


Measured memory_bytes: 4408
using System;
using System.Collections.Generic;
using System.Linq;

namespace AIZU
{
	class Program
	{
		#region Reserve
		static int cin() { return cin(-1); }
		static int cin(int D)
		{
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return int.Parse(s);
		}
		static int[] cins(char spliter)
		{
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return new int[] { };
			string[] ss = s.Split(spliter);
			int[] Res = new int[ss.Length];
			int g;
			for (int i = 0; i < ss.Length; i++) { 
				if(int.TryParse(ss[i],out g))
					Res[i] = g;
			}
			return Res;
		}
		static int[] cins() { return cins(' '); }
		static void print(object j) { Console.WriteLine(j.ToString()); }
		static void print(string j) { Console.WriteLine(j); }
		#endregion
		static void Main(string[] args)
		{
			int n = cin();
			int[] Fish = new int[n];
			int[] I;
			for (int iop = 0; iop < n; iop++) {
				I = cins();
				Fish[I[0] - 1] = I[1];
			}
			int Max = Fish.Max();
			int Win = Array.IndexOf(Fish,Max);
			Console.WriteLine("{0} {1}", Win+1 , Max);
		}
	}
}

Measured memory_bytes: 9920
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

pair<map<ll, ll>, set<ll>> prime_factor(ll n){
    map<ll, ll> res;
    set<ll> primes;
    for(ll i = 2; i*i <= n; ++i) {
        if(n%i==0) primes.insert(i);

        while(n%i == 0){
            res[i]++;
            n /= i;
        }
    }
    if(n != 1) {
        res[n] = 1;
        primes.insert(n);
    }
    return make_pair(res, primes);
}

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

    ll n, p;
    cin >> n >> p;
    
    if(n==1) {
        cout << p << endl;
        return 0;
    }

    pair<map<ll, ll>, set<ll>> primes = prime_factor(p);
    map<ll, ll> mp = primes.first;
    set<ll> st = primes.second;

    ll res = 1;
    for(ll i: st){
        if(mp[i] >= n) res *= pow(i, mp[i]/n);
    }
    
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*
import kotlin.math.*

fun str() = readLine()!!
fun int() = str().toInt()
fun long() = str().toLong()

fun read(d:String = " ") = str().split(d)
fun <T> list(d:String = " ",f:String.()->T) = read(d).map {f(it)}
fun list() = list {toInt()}

const val mod = 998244353L

fun main() {
	abc000X()
}

fun abc000X() {
	val n=int()
	println((n+999)/1000*1000-n)
}


Measured memory_bytes: 34444
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll mod=1e9+7;			
	   
int main() {
			fast
			// #ifndef ONLINE_JUDGE
			// freopen("input.txt","r",stdin);
			// freopen("output.txt","w",stdout);
			// #endif

			ll t;
			t=1;
			while(t--)
			{
				ll n;
				cin>>n;
				ll arr[n];
				for(ll i=0;i<n;i++)
				cin>>arr[i];
				sort(arr,arr+n);

				ll ans=arr[n-1];
				ll need=n-2;
				reverse(arr,arr+n);

				for(ll i=1;i<=need/2;i++)
				ans+=(2*arr[i]);

				if(need%2!=0)
				{
					ans+=arr[(need+1)/2];
				}
				cout<<ans<<endl;

			}
			return 0;
		 }	




Measured memory_bytes: 5212
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  string s;
  R s;
  cout << s[0] << (s.size()-2) << s[s.size()-1] << endl;
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>
#include <iomanip>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[20][20];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}

ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}
ll dp[20500];
int main() {
	ll k;
	cin >> n >> k;
	vector<ll> H(n);
	rep(i, n) {
		cin >> H[i];
	}
	ll res = INF;
	sort(H.begin(), H.end());
	rep(i, n - k + 1) {
		chmin(res, H[i + k - 1] - H[i]);
	}
	cout << res << endl;
}

Measured memory_bytes: 1024
import java.util.Scanner;
class Main{
	public static void main(String[]args){
		Scanner sc;
		int n,m,ans=0;
		String s=new String();
		String tmpl=new String("I");
		sc=new Scanner(System.in);
		while(true){
			n=sc.nextInt();
			if(n==0){break;}
			m=sc.nextInt();
			s=sc.next();
			for(int i=0;i<n;i++){
				tmpl+="OI";
			}
			for(int i=1;i<=m-2*n;i++){
				int j=s.indexOf(tmpl);
				if(j>=0){
					ans++;
					s=s.substring(j+1,s.length());
				}else{break;}
			}
			System.out.println(ans);
			ans=0;tmpl="I";
		}
	}
}

Measured memory_bytes: 59664
import sys
from itertools import accumulate

input = sys.stdin.readline


def binary_search(a, key):
    """Meguru type binary search"""
    ok = -1
    ng = len(a)

    while (ng - ok > 1):
        mid = (ok + ng) // 2
        if a[mid] <= key:
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N, M, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    B = tuple(map(int, input().split()))

    B_cumsum = tuple(accumulate(B))
    ans = 0
    time = 0
    for i in range(N + 1):
        if time > K:
            break
        j = binary_search(B_cumsum, K - time) + 1
        ans = max(ans, i + j)

        if i < N:
            time += A[i]

    print(ans)


if __name__ == "__main__":
    main()


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

#define INF 2140000000
#define MOD 1000000007
#define MaxN 105

using namespace std;

int N,d[2][MaxN];

int main()
{
    cin>>N;
    for(int i=0;i<2;i++)
        for(int j=1;j<=N;j++)
            cin>>d[i][j];
    for(int i=1;i<=N;i++)
    {
        d[0][i]+=d[0][i-1];
        d[1][i]+=max(d[0][i],d[1][i-1]);
    }
    cout<<d[1][N];
    return 0;
}


Measured memory_bytes: 256