akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define MOD 1000000007
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

ll ans;
string S, S_p, T;
int N, K, cur = -1;

bool canBePlaced(int i){
    rep(j, K){
        if(S_p[i+j] != '?' && S_p[i+j] != T[j]) return false;
    }

    return true;
}

void solve(){
    for(int i = N - K; i >= 0; --i){
        if(canBePlaced(i)){
            cur = i;
            break;
        }
    }

    if(cur >= 0){
        rep(i, K){
            S[cur+i] = T[i];
        }
        cout << S << endl;
        return;
    } else {
        cout << "UNRESTORABLE" << endl;
        return;
    }
}

int main(){
    cin >> S_p >> T;

    K = T.size();
    N = S_p.size();
    
    S = S_p;
    rep(i, N){
        if(S_p[i] == '?') S[i] = 'a';
    }

    solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int main(){

    int n,a,b;
    cin >> n;
    if(n == 1){
        cout << "Hello World" << endl;
    }else{
        cin >> a >> b;
        cout << a+b << endl;
    }


    return 0;
}

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

int main()
{
    int R, G, B, N;
    cin >> R >> G >> B >> N;

    int ans = 0;
    for (int r = 0; r <= N; r++)
    {
        int total = N;
        total -= R*r;
        if (total < 0)
            break;
        
        total += G;
        for (int g = 0; g <= N; g++)
        {
            total -= G;
            // cout << total << endl;
            if (total < 0)
                break;
            
            if (total % B == 0)
            {
                ans++;            
                // cout << r << ' ' << g << ' ' << total / B << endl;
            }

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <map>
#include <cmath>

using namespace std;

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


    int X;scanf("%d",&X);
    int A;scanf("%d",&A);
    int B;scanf("%d",&B);

    X-=A;
    printf("%d",X%B);


    return 0;
}

Measured memory_bytes: 256
from math import log
def main():
    n = int(input())
    a = [int(j) for j in input().split()]
    d = [0]*100001
    for i in range(n):
        d[a[i]]+=1
    q = int(input())
    s = sum(a)
    for i in range(q):
        b,c =[int(j) for j in input().split()]
        tmp = d[b]
        d[b] = 0
        d[c] += tmp
        s += tmp*(c-b)
        print(s)

    # for t in range(int(input())):
        # n = int(input())
        

# "Ashishgup" if he wins, and "FastestFinger"

# for #!/usr/bin/env python
# import os
# import sys
# from io import BytesIO, IOBase


# # region fastio

# BUFSIZE = 8192


# class FastIO(IOBase):
#     newlines = 0

#     def __init__(self, file):
#         self._fd = file.fileno()
#         self.buffer = BytesIO()
#         self.writable = "x" in file.mode or "r" not in file.mode
#         self.write = self.buffer.write if self.writable else None

#     def read(self):
#         while True:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             if not b:
#                 break
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines = 0
#         return self.buffer.read()

#     def readline(self):
#         while self.newlines == 0:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             self.newlines = b.count(b"\n") + (not b)
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines -= 1
#         return self.buffer.readline()

#     def flush(self):
#         if self.writable:
#             os.write(self._fd, self.buffer.getvalue())
#             self.buffer.truncate(0), self.buffer.seek(0)


# class IOWrapper(IOBase):
#     def __init__(self, file):
#         self.buffer = FastIO(file)
#         self.flush = self.buffer.flush
#         self.writable = self.buffer.writable
#         self.write = lambda s: self.buffer.write(s.encode("ascii"))
#         self.read = lambda: self.buffer.read().decode("ascii")
#         self.readline = lambda: self.buffer.readline().decode("ascii")


# sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
# input = lambda: sys.stdin.readline().rstrip("\r\n")

# # endregion

if __name__ == "__main__":
    main()



Measured memory_bytes: 83936
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define GET_BIT(n, i) (((n) & (1LL << ((i)-1))) >> ((i)-1)) // i start from 1
#define SET_BIT(n, i) ((n) | (1LL << ((i)-1)))
#define CLR_BIT(n, i) ((n) & ~(1LL << ((i)-1)))
typedef pair<int, int>  pii;
typedef pair<ll, ll>  pl;
typedef vector<int>   vi;
typedef vector<ll>    vl;
typedef vector<pii>   vpii;
typedef vector<pl>    vpl;
typedef vector<vi>    vvi;
typedef vector<vl>    vvl;
void myInit();
int mpow(int base, int exp);
void ipgraph(int m);
void dfs(int u, int par);
const int MOD = 1000000007;
const int N = 3e5, M = N;
//=========TQR==============
vi g[N];

int main() {
	myInit();
	FIO;
	int a, b, tot = 1, ans = 0;
	cin >> a >> b;
	while (tot < b) {
		tot += a - 1;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

void myInit() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int mpow(int base, int exp) {
	base %= MOD;
	int result = 1;
	while (exp > 0) {
		if (exp & 1) result = ((ll)result * base) % MOD;
		base = ((ll)base * base) % MOD;
		exp >>= 1;
	}
	return result;
}

void ipgraph(int n, int m) {
	int i, u, v;
	while (m--) {
		cin >> u >> v;
		g[u - 1].pb(v - 1);
		g[v - 1].pb(u - 1);
	}
}

void dfs(int u, int par) {
	for (int v : g[u]) {
		if (v == par) continue;
		dfs(v, u);
	}
}

Measured memory_bytes: 10620
import java.util.Scanner;

public class Main {
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt()+1;
        long[] A = new long[N];
        long branch = 0;
        for(int i = 0 ; i < N ; i++){
            A[i] = sc.nextLong();
            branch += A[i];
        }
        branch--;

        long ans = 0;
        long nowLeaf = 1;
        for(int i = 0 ; i < N ; i ++){
            ans += nowLeaf;
            nowLeaf -= A[i];
            if(nowLeaf < 0){
                ans = -1;
                break;
            }
            if(nowLeaf <= branch){
                branch -= nowLeaf;
                nowLeaf *= 2;
            }else{
                nowLeaf += branch;
                branch = 0;
            }
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 60096
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
int main(){
	string s;
	cin >> s;
	int n;
	n = s.size();
	vector<ll> a(n);
	ll sum = 0;
	rep(i, n) {
		a[i] = s[i] - '0';
	}
	ll x;
		for (int bit = 0; bit < (1 << (n-1)); ++bit) {
			x = a[0];
			rep(i, n - 1) {
				if (bit&(1 << i))
				{
					sum += x;
					x = 0;
				}
				x = x * 10 + a[i + 1];
			}
			sum += x;
		}
		cout << sum << endl;
	}

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

const int MAX_H = 210;
const int MAX_W = 210;

ll a[MAX_H][MAX_W];

void init(int H, int W){
	for(int i = 0;i <= H;i++){
		for(int j = 1;j <= W;j++){
			a[i][j] += a[i][j - 1];
		}
	}
	for(int j = 0;j <= W;j++){
		for(int i = 1;i <= H;i++){
			a[i][j] += a[i - 1][j];
		}
	}
}

ll sum(int li, int lj, int ri, int rj){
	return a[ri][rj] - a[ri][lj] - a[li][rj] + a[li][lj];
}

ll calc(int li, int lj, int ri, int rj, int n){
	if(n == 1) return sum(li, lj, ri, rj);
	ll res = 0;
	for(int i = li;i <= ri;i++){
		for(int j = 1;j < n;j++){
			res = max(res, min(calc(li, lj, i, rj, j), calc(i, lj, ri, rj, n - j)));
		}
	}
	for(int j = lj;j <= rj;j++){
		for(int i = 1;i < n;i++){
			res = max(res, min(calc(li, lj, ri, j, i), calc(li, j, ri, rj, n - i)));
		}
	}
	return res;
}

bool judge(int H, int W, int m){
	if(m == 0) return true;
	for(int i = 1;i <= H;i++){
		int j = 0;
		while(j <= W && sum(0, 0,i, j) < m) ++j;
		if(j > W) continue;
		int k = 0;
		while(k <= i && sum(0, j, k, W) < m) ++k;
		if(k > i) continue;
		int l = j;
		while(l <= W && sum(i, 0, H, l) < m) ++l;
		if(l > W) continue;
		if(sum(k, l, H, W) >= m) return true;
	}
	for(int i = 1;i <= W;i++){
		int j = 0;
		while(j <= H && sum(0, 0, j, i) < m) ++j;
		if(j > H) continue;
		int k = 0;
		while(k <= i && sum(j, 0, H, k) < m) ++k;
		if(k > i) continue;
		int l = j;
		while(l <= H && sum(0, i, l, W) < m) ++l;
		if(l > H) continue;
		if(sum(l, k, H, W) >= m) return true;
	}
	return false;
}

int main()
{
	int H, W, N;
	cin >> H >> W >> N;
	for(int i = 0;i < H;i++){
		for(int j = 0;j < W;j++){
			cin >> a[i + 1][j + 1];
		}
	}
	init(H, W);
	ll res = calc(0, 0, H, W, N);
	if(N == 4){
		ll lb = 0, ub = 1e9;
		while(ub - lb > 1){
			ll m = (lb + ub) >> 1;
			if(judge(H, W, m)){
				lb = m;
			}
			else{
				ub = m;
			}
		}
		res = max(res, lb);
	}
	cout << res << endl;
}


Measured memory_bytes: 3440
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll inputValue(){
    ll a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    REP(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    REP(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

int main()
{
  ll A = inputValue();
  ll B = inputValue();
  vector<ll> xA;
  vector<ll> xB;
  ll x = 2;
  ll c = A;
  while(x<=sqrt(A)){
    if(c % x == 0){
      xA.push_back(x);
      while(c % x == 0){
        c /= x;
      }
    }
    x++;
  }
  if(c>1){
    xA.push_back(c);
  }
  x = 2;
  c = B;
  while(x<=sqrt(B)){
    if(c % x == 0){
      xB.push_back(x);
      while(c % x == 0){
        c /= x;
      }
    }
    x++;
  }
  if(c>1){
    xB.push_back(c);
  }
  vector<ll>::iterator itrA = xA.begin();
  vector<ll>::iterator itrB = xB.begin();
  int ans = 1;
  while(itrA!=xA.end() && itrB!=xB.end()){
    if(*itrA == *itrB){
      ans++;
      itrA++;
      itrB++;
    }else if(*itrA > *itrB){
      itrB++;
    }else if(*itrA < *itrB){
      itrA++;
    }
  }
  cout << ans << endl;
}


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

int main(){
  
  int n,k;
  cin >> n >> k;
  vector<int> h(n);
  for(int i=0;i<n;i++){
    cin >> h.at(i);
  }
  sort(h.begin(),h.end());
  
  int ans=0;
  for(int j=0;j<n;j++){
    if(h.at(j)>=k){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
a,b,c = map(int,input().split())
ans = 0
if a%2 == 1 or b%2 == 1 or c%2 == 1:
  ans = 0
elif a == b and b == c:
  ans = -1
else:
  while a%2 != 1 and b%2 != 1 and c%2 != 1:
    aa = b/2 + c/2
    bb = c/2 + a/2
    cc = a/2 + b/2
    a = int(aa)
    b = int(bb)
    c = int(cc)
    ans += 1
print(ans)  

Measured memory_bytes: 9144
#include <stdio.h>

int main(){
  int i, j, n, S[10000], q, T[500], c=0;
  scanf("%d", &n);
  for(i=0;i<n;i++){
  scanf("%d", &S[i]);
  }
  scanf("%d", &q);
  for(i=0;i<q;i++){
    scanf("%d", &T[i]);
  }

  for(j=0;j<q;j++){
    i=0;
    S[n]=T[j];
    while(S[i]!=T[j]){
      i++;
    }
    if(i!=n) c++;
  }

  printf("%d\n", c);

  return 0;
}

Measured memory_bytes: 640
n, m = map(int, input().split())

x = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    x[a-1].append(b-1)

for i in x[0]:
    for j in x[i]:
        if j == n-1:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Measured memory_bytes: 29068
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

int main(void) {
    int i, n, a, b;
    string s;
    cin >> n >> a >> b;
    cin >> s;
    for (auto c: s) {
        bool yes = false;
        if (c == 'a') {
            if (a > 0) {
                a--;
                yes = true;
            }
            else if (b > 0) {
                b--;
                yes = true;
            }
        }
        else if (c == 'b') {
            if (b > 0) {
                b--;
                yes = true;
            }
        }
        if (yes)
            puts("Yes");
        else 
            puts("No");
    }
    return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)


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

	ll A, B, C;
	cin >> A >> B >> C;
	if (B <= C) {
		if (C - B <= A)puts(B + C);
		else puts(2LL * B + A + 1);
	}
	else puts(B + C);
	
	return 0;
}

Measured memory_bytes: 256
from sys import stdin

global time
time = 0

def dfs(graph,start,state,discover,finish):

    state[start-1] = 1
    global time
    time = time + 1
    discover[start-1] = time
    # print str(time) + " go to " + str(start)

    neighbours = sorted(graph[start])

    for neighbour in neighbours:
        if state[neighbour-1] == 0:
            dfs(graph,neighbour,state,discover,finish)

    state[start-1] = 2
    time = time + 1
    finish[start - 1] = time
    # print str(time) + " out of " + str(start)

def main():
    # g = {1: [2, 3],
    #      2: [3, 4],
    #      3: [5],
    #                     4: [6],
    #                     5: [6],
    #                     6: []}



    # deal with input
    n = int(stdin.readline())

    g = {}

    d = [0]*n
    f = [0]*n

    all_vertex = []

    for i in xrange(n):
        entry = [int(s) for s in stdin.readline().split()[2:]]
        g[i+1] = entry
        all_vertex.append(i+1)



    # exp = []
    # state represent vertex visited state: 0 not visited 1 visiting 2 finished
    state = [0]*n

    for node in all_vertex:
        if state[node-1] == 0:
            dfs(g,node,state,d,f)

    # print  'state ' + str(state)

    # print 'd' + str(d)
    # print 'f' + str(f)

    # deal with output
    for i in xrange(n):
        print str(i+1) + ' ' + str(d[i]) + ' ' + str(f[i])

main()


Measured memory_bytes: 4756
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#include <bitset>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;

class UF
{
private:
    int         num;
    vector<int> par;
public:
    vector<int> siz;
    //vector<int> val;
public:
    UF(int n): num(n) {
        par.resize(n);
        siz.resize(n);
        //val.resize(n);
        int i;
        for(i=0; i<n; i++) {
            par[i]=i; siz[i]=1;
            //val[i]=0;
        }
    }
	
    int find(int x) {
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }

    void unite(int x, int y) {
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(siz[x]<siz[y]) {
            par[x]=y;
            siz[y]=siz[x]+siz[y];
            //val[y]=val[x]+val[y];
        }
        else {
            par[y]=x;
            siz[x]=siz[x]+siz[y];
            //val[x]=val[x]+val[y];
        }
    }

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

    int size(int x) {
        return siz[find(x)];
    }

    int ngroup() {
    //int ngroup( int& ans ) {
        int count=0;
        int i;
        for(i=0; i<num; i++) {
            if(par[i]==i) {
                count++;
                //ans += (val[i]? siz[i]: siz[i]-1);
            }
        }
        return count;
    }
};

int main(int argc, char* argv[])
{
    int n,m;
    scanf("%d%d", &n, &m);

    vector<int> a(m), b(m);
    int i;
    for(i=0; i<m; i++) {
        scanf("%d%d", &a[i], &b[i]); a[i]--; b[i]--;
    }

    vector<ll> ans(m);
    ll ans0=0;

    UF uf(n);
    for(i=m-1; i>=0; i--) {
        ans[i]=ans0;

        int tmp0=uf.find(a[i]);
        int tmp1=uf.find(b[i]);
        if(tmp0!=tmp1) {
            ll num0=uf.siz[tmp0];
            ll num1=uf.siz[tmp1];
            ll num=num0+num1;
            ans0 -= (num0*(num0-1)/2);
            ans0 -= (num1*(num1-1)/2);
            ans0 += (num*(num-1)/2);
            uf.unite(a[i],b[i]);
        }
    }

    for(i=0; i<m; i++) {
        printf("%lld\n", (ll)n*(n-1)/2-ans[i]);
    }

    return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
#endif

	
	
		string s;
		cin>>s;
		if(s[1]=='R')
		{
			cout<<"ABC"<<endl;
		}
		else
		{
			cout<<"ARC"<<endl;
		}
	

	return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define vl vector<long long int>
#define vvl vector<vector<ll> > 
#define fo(i,a,b) for(int i=a;i<b;i++)
#define rof(i,a,b)  for(int i=b;i>=a;i--)
using namespace std;
ll mod=1000000007;
int main()
{
    ll n;cin>>n;
    double p[n+1];
    fo(i,1,n+1)
        cin>>p[i];
    double dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=0;j<=n;j++)
        {
            if(j==0)
                dp[i][j]=dp[i-1][j]*(1-p[i]);
            else
            {
                dp[i][j] = dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
            }
        }
    }
    double res=0;
    for(ll i=(n+1)/2;i<=n;i++)
        res+=dp[n][i];
    cout << setprecision(10) << res ;
        
}



Measured memory_bytes: 74108
#include<bits/stdc++.h>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define rep(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007


using namespace std;

int main(void){
    int N;
    cin>>N;
    VI K(N),P(N),ans(N);
    rep(i,N){
        cin>>K[i]>>P[i];
        if(K[i]%P[i]==0)ans[i]=P[i];
        else ans[i]=K[i]%P[i];
    }
    rep(i,N)cout<<ans[i]<<endl;
}




Measured memory_bytes: 3108
#include<stdio.h>

int cnt(int n){
	int cnt=0,i,j,flag[1000000]={0};
	for(i=2;i<=n;i++){
		for(j=2;i*j<=n;j++){
			if(flag[i*j]==0){
				flag[i*j]=1;
			}
		}
	}
	for(i=2;i<=n;i++){
		if(flag[i]==0){
			cnt++;
		}
	}
	return cnt;
}
				
int main(void){
	int n;
	while(scanf("%d",&n)!=EOF){
		printf("%d\n",cnt(n));
	}
	return 0;
}

Measured memory_bytes: 4508
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long a[] = new long[N];
		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		long sum[] = new long[N + 1];
		for (int i = 0; i < N; i++) {
			sum[i + 1] = sum[i] + a[i];
		}
		
		for (int i = N - 1; i >= 0; i--) {
			if (a[i] > 2 * sum[ i ]) {
				System.out.println(N - i);
				return;
			}
		}
		System.out.println(N);
	}
}

Measured memory_bytes: 53032
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

int c,n,m,s,d;
vector<pair<int,int> >  v[101];
int dp[101][11];

int inf = 1111111111;

typedef pair<pair<int,int>,int> p;

void dijkstra(int s,int ticket){
  priority_queue<p,vector<p>,greater<p> > que;
  
  fill((int *)dp,(int *)dp+101*11,inf);
  dp[s][0] = 0;
  que.push(make_pair(make_pair(0,s),0));

  while(!que.empty()){
    p x = que.top();
    que.pop();
    int V = (x.first).second;
    if(dp[V][x.second] < (x.first).first)
      continue;
    for(int i = 0;i<v[V].size();i++){
      pair<int,int> tmp = v[V][i];
      if(dp[tmp.first][x.second] > dp[V][x.second] + tmp.second){
	dp[tmp.first][x.second] = dp[V][x.second] + tmp.second;
	que.push(make_pair(make_pair(dp[tmp.first][x.second],tmp.first),x.second));
      }

      if(x.second < ticket && dp[tmp.first][x.second+1] > dp[V][x.second] + tmp.second/2) {
	//cout<<"a"<<endl;
	dp[tmp.first][x.second+1] = dp[V][x.second] + tmp.second/2;
	que.push(make_pair(make_pair(dp[tmp.first][x.second+1],tmp.first),x.second+1));
      }		

    }

  }
}


int main(){

  while(cin>>c>>n>>m>>s>>d){
    if(c==0&&n==0&&m==0&&s==0&&d==0)
      break;
  
    for(int i = 0;i<101;i++){
      v[i].clear();
    }
    s--;
    d--;
    for(int i = 0;i<m;i++){
      int a,b,f;
      cin>>a>>b>>f;
      a--;b--;
      v[a].push_back(make_pair(b,f));
      v[b].push_back(make_pair(a,f));
    }
    dijkstra(s,c);
    int ans = inf;
    for(int i = 0;i<=c;i++){
      ans = min(ans,dp[d][i]);
    }
    
    /*
    for(int i = 0;i<=c;i++){
      for(int j = 0;j< n;j++){
	cout<<dp[j][i]<<" ";
      }
      cout<<endl;
    }
    */
    cout<<ans<<endl;
  }

  return 0;
}

Measured memory_bytes: 1244
#include <stdio.h>
#define ll long long

int main(void) {
	ll int N, M;
	ll int n, m;

	scanf("%lld %lld", &N, &M);

	if (N * 2 >= M) {
		printf("%lld\n", M/2);
	}
	else {
		m = M - N * 2;
		n = m / 4;
		printf("%lld\n", n+N);
	}
	
	return 0;
}

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

const int MOD = 1e9 + 7;
int N, K;
vector<int> graph[100000];
ll ans = 1;

void dfs(int from, int now) {
    // permtation(nPr)
    int n = K - 2;
    int r = graph[now].size() - 1;
    if (from == -1) {
        n = K;
        r += 2;
    }
    rep(i, r) {
        ans *= n - i;
        ans %= MOD;
    }
    for (int to: graph[now]) {
        if (to == from) continue;
        dfs(now, to);
    }
}

int main() {
    cin >> N >> K;
    rep(i, N-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(-1, 0);
    cout << ans << endl;
}

Measured memory_bytes: 9216
(let ((a (concatenate 'list (read-line)))
      (b (concatenate 'list (read-line)))
      (c (concatenate 'list (read-line))))

  (defun f (chr)
    (cond ((char= chr #\a) (if a (f (pop a)) (format t "A~%")))
          ((char= chr #\b) (if b (f (pop b)) (format t "B~%")))
          ((char= chr #\c) (if c (f (pop c)) (format t "C~%")))))

  (f #\a))


Measured memory_bytes: 5092
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    cout << n - k + 1 << endl;

    return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++)
    {
        cin >> a.at(i);
    }
    
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    int Alice = 0, Bob = 0;
    for (int i = 0; i < N; i++)
    {
    if(i % 2 == 0) Alice += a.at(i);
    else Bob += a.at(i);
    }
    cout << Alice - Bob << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n==7 || n==5 || n==3){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
        
    }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A,B;
int n;
const int N=5010;
int a[N],pos[N];
ll f[N][N];

int main()
{
	scanf("%d%lld%lld",&n,&A,&B);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pos[a[i]]=i;
	}
	for(int i=0;i<=n;i++)f[0][i]=B*i;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			f[i][j]=f[i-1][j];
			if(j) f[i][j]=min(f[i][j],f[i][j-1]+(pos[j]>i ? B:A) );
			if(j&&pos[j]==i) f[i][j]=min(f[i][j],f[i-1][j-1]);
//			cout<<i<<" "<<j<<" :: "<<f[i][j]<<endl;
		}
	}
	cout<<f[n][n]<<endl;
}


Measured memory_bytes: 195968
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {a: usize, b: usize};

    println!("{}", lcm(a, b));
}

fn lcm(a: usize, b: usize) -> usize {
    let mut a = a;
    let mut b = b;

    let x = a * b;

    if a > b {
        let tmp = a;
        a = b;
        b = tmp;
    }

    let mut r = a % b;

    while r != 0 {
        a = b;
        b = r;
        r = a % b;
    }

    return x / b;
}


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

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var k = int.Parse(Console.ReadLine());
            var ab = Console.ReadLine().Split(' ').Select(num => int.Parse(num)).ToArray();
            if (ab[0] % k == 0)
            {
                Console.WriteLine("OK");
                return;
            }
            Console.WriteLine((ab[0] + k - ab[0] % k) <= ab[1] ? "OK" : "NG");
        }
    }
}

Measured memory_bytes: 28136
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e09)


def main():
    # sys.stdin = open("sample.txt")
    N, Ma, Mb = Scanner.map_int()
    A = [0] * N
    B = [0] * N
    C = [0] * N

    for i in range(N):
        a, b, c = Scanner.map_int()
        A[i], B[i], C[i] = a, b, c
    dp = [[[INF for _ in range(401)] for _ in range(401)] for _ in range(41)]
    dp[0][0][0] = 0
    for i in range(N):
        for j in range(401):
            for k in range(401):
                if dp[i][j][k] == INF:
                    continue
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                dp[i+1][j + A[i]][k + B[i]] = min(
                    dp[i+1][j + A[i]][k + B[i]], dp[i][j][k] + C[i])

    ans = INF
    for i in range(1, 401):
        for j in range(1, 401):
            if dp[N][i][j] == INF:
                continue
            if Ma * j == Mb * i:
                ans = min(ans, dp[N][i][j])
    if ans == INF:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 96732
console.log((args=>{
  const [HW,CC,DD,...S] = args.trim().split`\n`;
  const [H,W] = HW.split` `.map(v=>v|0);
  const C = CC.split` `.map(v=>v-1);
  const D = DD.split` `.map(v=>v-1);
  const map = Array.from({length:H},_=>Array(W).fill(0));
  const done= Array.from({length:H},_=>Array(W).fill(false));
  let stack = [C];
  let _stack =  [], step = 1;
  while (stack.length) {
    const [px,py] = stack.pop();
    if ( px === D[0] && py === D[1] ) return step-1;
    if ( !done[px][py] ) {
      done[px][py] = true;
      map[px][py] = step;
      for ( let x = px-2; x <= px+2; x++ ) {
        if ( x < 0 || H <= x ) continue;
        for ( let y = py-2; y <= py+2; y++ ) {
          if ( y < 0 || W <= y || S[x][y] === '#' || done[x][y] ) continue;
          if (Math.hypot(x-px,y-py)<=1) {
            map[x][y] = step;
            stack.push([x,y]);
          } else if ( !map[x][y] ) {
            map[x][y] = step+1;
            _stack.push([x,y]);
          }
        }
      }
    }
    if ( stack.length === 0 ) {
      [stack,_stack] = [_stack,[]];
      step++;
    }
  }
  return -1;
})(require('fs').readFileSync('/dev/stdin','utf8')));

Measured memory_bytes: 82528
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = ni()
a = na()
b = []
for i in range(n):
    b.append((a[i],i))
 
b.sort(reverse=True)

dp = [[0]*(n+1) for i in range(n+1)]

for i in range(1,n+1):
    x,y = b[i-1]
    for j in range(i+1):
        left = dp[i-1][j-1] + x*abs(y-j+1) if j > 0 else -1
        right = dp[i-1][j] + x*abs(n-i+j-y) if j < i else -1
        dp[i][j] = max(left,right)

print(max(dp[-1]))

Measured memory_bytes: 100272
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
//#inlcude<stringstream>
#define ll long long
#define MODD 1000000007
using namespace std;

int main() {
    /*int n ,k;cin>>n>>k;
    int sum=0;
    for(int i=k;i<n;i++){
        sum+=n-i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>0;j--){
            if()
            if(i%j>=k)sum++;
        }
    }
    cout<<sum<<endl;*/
    ll n , m;cin >>n>>m;
    ll sum=0;
    sum=(m-2)*(n-2);
    cout<<abs(sum)<<endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(2,3)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#define re register
using namespace std;
map <string,int> mp;

int n,m,k;
inline int read(){
	re int t=0;
	re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0'){
	t=(t<<3)+(t<<1)+v-48;
	v=getchar();}
	return t;
}
string s[200002];
signed main(){
n=read();
for(re int i=1;i<=n;++i){
	cin>>s[i];
	++mp[s[i]];
}
sort(s+1,s+n+1);
for(re int i=1;i<=n;++i){
	if(mp[s[i]]>k)k=mp[s[i]];
}
for(re int i=1;i<=n;++i){
	if(mp[s[i]]==k){cout<<s[i]<<endl;--mp[s[i]];
	}
}
}


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

class B {
    static void Main(string[] args) {
        var st = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int N = st[0];
        int K = st[1];

        int keta = (int)Math.Floor(Math.Log(N) / Math.Log(K)) + 1;

        Console.WriteLine(keta);



    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n, p; scanf("%d%d", &n, &p);
	std::string s; cin >> s;

	if(p == 2 or p == 5) {
		i64 ans = 0;
		for(i64 i = 0; i < n; i++) {
			if((s[i] - '0') % p) continue;
			ans += i + 1;
		}
		printf("%lld\n", ans);
		return 0;
	}

	reverse(begin(s), end(s));
	std::vector<int> tan(n + 1, 1);
	for(int i = 1; i < n + 1; i++) tan[i] = tan[i - 1] * 10 % p;
	
	std::vector<int> vec(1, 0);
	for(int i = 0; i < n; i++) {
		int d = s[i] - '0';

		vec.push_back((vec.back() + d * tan[i]) % p);
	}

	i64 ans = 0;
	std::map<int, i64> mp;
	for(int i = n; i >= 0; i--) {
		ans += mp[vec[i]];
		mp[vec[i]]++;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 2552
import java.util.Scanner;

public class Main {
	
	public static void main (String[] ags) {
		
		Scanner scanner = new Scanner(System.in);
		
		int a = scanner.nextInt();
		
		scanner.close();
		
		int b = 2;
		int c = 3;
		
		System.out.println(a + (int) Math.pow(a, b) + (int) Math.pow(a, c));
	}

}


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

#define F first
#define S second
#define pb push_back
#define mp make_pair

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

ll lcm(ll a, ll b){
	return (a/gcd(a, b))*b;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll n;
	cin >> n;

	ll x;
	if(n >= 400 && n <= 599)
		x = 8;
	else if(n >= 600 && n <= 799)
		x = 7;
	else if(n >= 800 && n <= 999)
		x = 6;
	else if(n >= 1000 && n <= 1199)
		x = 5;
	else if(n >= 1200 && n <= 1399)
		x = 4;
	else if(n >= 1400 && n <= 1599)
		x = 3;
	else if(n >= 1600 && n <= 1799)
		x = 2;
	else if(n >= 1800 && n <= 1999)
		x =1;

	cout << x << endl;







}

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

const int maxn = 200005, MOD = 1e9 + 7;
int ans[maxn], cs[maxn], cs_[maxn];

int binpow(int x, int pw, int m = MOD) {
    if (pw == 1) return x;
    if (pw == 0) return 1;
    if (pw % 2 == 1) return binpow(x, pw - 1, m) * x % m;
    int k = binpow(x, pw / 2, m);
    return k * k % m;
}

int fac(int x, int m = MOD) {
    int ans = 1;
    for (int i = 2; i <= x; i++) ans *= i, ans %= m;
    return ans;
}

int C(int n, int k) {
    return fac(n) * binpow(fac(k), MOD - 2) % MOD * binpow(fac(n - k), MOD - 2) % MOD;
}

int n, k;

int get(int k) {
    if (k <= 0) return ans[k];
    return (ans[k - 1] % MOD + C(2 * n - k - 1, n - k) % MOD) % MOD;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    ans[0] = 1;
    cs[0] = cs_[0] = 1;

    for (int i = 1; i <= n; i++) cs[i] = cs[i - 1] * (n - i + 1) % MOD * binpow(i, MOD - 2) % MOD;
    for (int i = 1; i <= n; i++) cs_[i] = cs_[i - 1] * ((n - 1) - i + 1) % MOD * binpow(i, MOD - 2) % MOD;

    for (int i = 1; i <= min(k, n); i++) ans[i] = ans[i - 1] + cs_[i] * cs[n - i] % MOD, ans[i] %= MOD;
    cout << ans[min(k, n)];
}


Measured memory_bytes: 4992
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


int main(){
  ll N; cin >> N; ll a = N/11;
  if(N%11==0) cout << 2*a << endl;
  else if(N%11<=6) cout << 2*a+1 << endl;
  else cout << 2*a+2 << endl;
 }

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

using namespace std;

typedef long long int ll;

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;


struct union_find{
  vector<int> par,r;
  int n;

  union_find(){};

  union_find(int x){
    n = x;
    par.resize(n);
    r.resize(n);

    init(n);
  }

  void init(int n){
    for(int i = 0; i < n; i++) par[i] = i;
    for(int i = 0; i < n; i++) r[i] = 0;
  }

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

  void unite(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y){
      return;
    }else if(r[x] < r[y]){
      par[x] = y;
    }else{
      par[y] = x;
      if(r[x] == r[y]) r[x]++;
    }
  }

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

int main()
{
  int n,m;
  cin >> n >> m;
  vector<int> p(n),x(m),y(m);
  for(int i = 0; i < n; i++){
    cin >> p[i];
  }
  for(int i = 0; i < m; i++){
    cin >> x[i] >> y[i];
  }

  union_find uf(n);

  for(int i = 0; i < m; i++){
    uf.unite(x[i],y[i]);
  }

  int sol = 0;
  for(int i = 0; i < n; i++){
    if(uf.same(i+1,p[i])) sol++;
  }

  cout << sol << endl;
  return 0;
}

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

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define EACH(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

struct Node{
  int id,val,parent,size,in,out;
  vector<int> children;
  Node(){}
  Node(int id,int v,vector<int>ch):id(id),val(v),children(ch){}
};

typedef vector<Node> Tree;

struct HeavyLight {
  int pathCount,n;
  vector<int>path, pathSize, pathPos, pathRoot;
  Tree tree;
  
  HeavyLight(Tree tree)
    :pathCount(0),n(tree.size()),path(n),pathSize(n),pathPos(n),pathRoot(n),tree(tree){
    int time=0;
    dfs(0,-1,time);
    buildPaths(0,newPath(0));
  }

  void dfs(int u, int p, int &k){
    tree[u].in=k++, tree[u].parent=p, tree[u].size=1;
    EACH(v,tree[u].children){
      if(*v!=p){
	dfs(*v, u, k);
	tree[u].size += tree[*v].size;
      }
    }
    tree[u].out=k++;
  }

  int newPath(int u){
    pathRoot[pathCount] = u;
    return pathCount++;
  }

  void buildPaths(int u, int pt){
    path[u]=pt, pathPos[u]=pathSize[pt]++;
    EACH(v,tree[u].children)
      if(*v != tree[u].parent)
	buildPaths(*v, 2* tree[*v].size >= tree[u].size ? pt : newPath(*v));
  }

  bool isAncestor(int p, int ch){
    return tree[p].in <= tree[ch].in && tree[ch].out <= tree[p].out;
  }

  int lca(int a,int b){
    for(int root; !isAncestor(root=pathRoot[path[a]],b);a=tree[root].parent);
    for(int root; !isAncestor(root=pathRoot[path[b]],a);b=tree[root].parent);
    return isAncestor(a,b)?a:b;
  }
};


int main(void){
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  Tree tree(n);
  
  REP(i,n){
    tree[i].id=i;
    int k;
    cin >> k;
    REP(j,k){
      int ch;
      cin >> ch;
      tree[i].children.push_back(ch);
    }
  }

  HeavyLight hl = HeavyLight(tree);

  int q;
  cin >> q;
  while(q--){
    int u,v;
    cin >> u >> v;
    cout << hl.lca(u,v) << "\n";
  }
  
  return 0;
}

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

int main() {
    string s;
    cin >> s;
    int d[4] = {0};  // N W S E
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'N') {
            d[0]++;
        } else if (s[i] == 'W') {
            d[1]++;
        } else if (s[i] == 'S') {
            d[2]++;
        } else {
            d[3]++;
        }
    }

    if (d[0] * d[2] == 0 && d[0] != d[2]) {
        puts("No");
    } else if (d[1] * d[3] == 0 && d[1] != d[3]) {
        puts("No");
    } else {
        puts("Yes");
    }
}


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

using namespace std;
typedef long long ll;

const int MAX = 110000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
        fac[i] = fac[i - 1] * i % MOD, inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD,
        finv[i] = finv[i - 1] * inv[i] % MOD;
    
}

long long COM(int n, int k)
{
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
    COMinit();

    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    
    sort(A.begin(), A.end());

    ll minsum = 0;
    ll maxsum = 0;
    
    REP(i,N-K+1)
    {
        ll combi = COM( N-1-i, K-1 ) % MOD;
        minsum += A[i] * combi % MOD;
        maxsum += A[N-1-i] * combi % MOD;
    }
    
    cout << ((maxsum + MOD) - minsum) %MOD << endl;
}


Measured memory_bytes: 3584
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main 
{

	public static void main(String[] args) 
	{
		Scanner scan = new Scanner(System.in);
		
		while(true)
		{
			int n = scan.nextInt();
			int sum = 0;
			
			if(n == 0) {break;}
				
			List<Integer> l = new ArrayList<Integer>();
			
			for(int i = 0; i < n; i++)
			{
				int input = scan.nextInt();
				l.add(input);
				sum += input;
			}
			
			int ans = 0;
			for(int x : l)
			{
				if(x <= (sum/n))
				{
					ans += 1;
				}
			}
			System.out.println(ans);
		}
		
	}

}



Measured memory_bytes: 59140
#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <array>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <algorithm>
#include <cmath>
using namespace std;

int a, b;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define MAX(a,b) a>b? a:b
#define MIN(a,b) a>b? b:a
typedef double db;
typedef long long ll;
const int MOD = 1e9 + 7;
const db PI = acos(-1.0);


int main() {
	int N, L,eat,sum;
	cin >> N>> L;
  	sum=(2*L+N-1)*N/2;
	if (L <= 0 && N + L - 1 >= 0)  eat = 0;
	else if(L<0&&N+L-1<0){eat=MIN(abs(L),abs(N+L-1));
                         eat=eat*(-1);
                         
                         }
    else if(L>0&&N+L-1>0)eat=MIN(L,N+L-1);
	sum-=eat;
	cout << sum << endl;
	return 0;
}

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

using namespace std;
#define LL long long

const int MAXN = 212345;

LL a, b;

int main () {

	scanf("%lld %lld", &a, &b);

	LL s = (a + b);

	if (s & 1) printf("IMPOSSIBLE\n");
	else printf("%lld\n", (s >> 1));

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
//#define f(i,a,n) for(ll i=a;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll isPrime(int n) 
{ 
	// Corner cases 
	if (n <= 1) 
		return 1; 
	if (n <= 3) 
		return 2; 

	// This is checked so that we can skip 
	// middle five numbers in below loop 
	if (n % 2 == 0 || n % 3 == 0) 
		return 1; 

	for (int i = 5; i * i <= n; i = i + 6) 
		if (n % i == 0 || n % (i + 2) == 0) 
			return 1; 

	return 2; 
} 

ll fact(ll n){ll res = 1;for (ll i = 2; i <= n; i++)res = res * i,res%=1000000007; 
    return res; } 
 
 int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b); 
} 
  
 
ll findlcm(ll arr[], int n) 
{ 
   
    ll ans = arr[0]; 
  
    
    for (int i = 1; i < n; i++) 
        ans = (((arr[i] * ans)) / 
                (gcd(arr[i], ans))); 
  
    return ans; 
} 
 
 
int main() 
{
    fast;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        ll n,sum=0;
        cin>>n;
        ll A[n];
        map<ll,ll>B;
        for(ll i=0;i<n;i++)
        {
            cin>>A[i];
            B[A[i]]++;
            
        }
      sort(A,A+n);
        for(ll i=0;i<n;i++)
        {
            sum=sum+(B[A[i]]%2);
          i=i+B[A[i]]-1;
        }
        cout<<sum;
    } 
    return 0;
}


Measured memory_bytes: 10644
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    ll N,A,B,C,D,E;
    cin>>N>>A>>B>>C>>D>>E;
    ll m=min({A,B,C,D,E});
    ll answer;
    if(N%m!=0) answer=N/m+1;
    else answer=N/m;
    answer+=4;
    cout<<answer<<endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

dicA =  {}
for i in range(1, N+1):
    dicA[i] = A[i-1]

sort_dicA = sorted(dicA.items(), key=lambda x:x[1])
for i in range(N):
    print(sort_dicA[i][0], end=' ')


Measured memory_bytes: 102356
N = int(input())
H = input().split()
cnt = 0

for i in range(N-1):
    if (int(H[i+1]) > int(H[i])):
        H[i+1] = int(H[i+1])-1
    if (int(H[i]) > int(H[i+1])):
        cnt += 1

if (cnt != 0):
    print("No")
else:
    print("Yes")


Measured memory_bytes: 12784