akhauriyash/Code-Regression huggingface dataset:
import heapq

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

dist = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = c + 1
    e[b][a] = c + 1

for i in range(n):
    h = []
    heapq.heappush(h, [0, i])
    temp = set()
    #temp.add(i)
    while len(temp) < n:
        d, p = heapq.heappop(h)
        while p in temp:
            d, p = heapq.heappop(h)
        dist[i][p] = d
        temp.add(p)
        for x in e[p].keys():
            heapq.heappush(h, [d + e[p][x], x])

#for i in range(n): print(dist[i])

ans = m
for a, b, c in abc:
    for i in range(n):
        if c + 1 == dist[a][i] - dist[b][i]:
            ans -= 1
            break
print(ans)

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

using namespace std;

int main(){
    double a,b;
    int c;
    cin >> a >> b >> c;
    
    double cx,cy,bx,by;
    double S,L,h;
    
    cout << fixed << setprecision(6);
    
    double rad = ((double)c * M_PI ) / 180.0;
    cx = a;
    cy = 0;
    bx = cos(rad) * b;
    by = sin(rad) * b;
    h = by;
    
    double diffx = cx - bx;
    double diffy = cy - by;
    
    double diffbc = sqrt((diffx * diffx)+(diffy*diffy));
    
    
    S = (a * h) / 2;
    cout << S << endl;
    cout << (diffbc + a + b) << endl;
    cout << h << endl;

}


Measured memory_bytes: 3484
import java.util.Scanner;

public class Main {

public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int limit = 10000;


		while(true)
		{


		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int x = sc.nextInt();


		if(N == 0 && A == 0 && B == 0 && C == 0 && x == 0)
			return;;

		int[] Y = new int[N];

		for(int i=0;i<N;i++)
		{
			Y[i] = sc.nextInt();

		}

		int count = 0;
		int i;
		boolean flag = true;
		for(i=0;i<N;i++)
		{
			if(count > limit)
				break;

			while(true)
			{
				if(count > limit)
					break;

				if(x == Y[i] && flag)
				{
					flag =false;
					break;
				}
				
				x = (A * x + B)  % C;
				count++;
				flag = true;


			}


		}

		System.out.println( count <= limit ? count : -1 );
		}


	}

}

Measured memory_bytes: 40944
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,0,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
using namespace std;

int main(){
  int H,W;
  cin>>H>>W;
  for(int i=0; i<=H+1; ++i){
    if(i==0 || i==H+1){
      for(int j=0; j<=W+1; ++j) cout<<"#";
    }
    else{
      cout<<"#";
      string S;
      cin>>S;
      cout<<S;
      cout<<"#";
    }
    cout<<endl;
  }
}

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

#define pb push_back
#define fst first
#define snd second
#define INF 0x7fffffff
#define INFLL 0x7FFFFFFFFFFFFFFF
#define lenA(ar) sizeof(ar)/sizeof(*ar)
#define fill(a,c) memset(&a, c, sizeof(a))
#define fore(i,x,y) for(int i=x;i<y;i++)
#define foreI(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sl "\n";
#define ii pair<ll,ll>
#define mk make_pair


typedef long long ll;
typedef unsigned long long ull;

using namespace std;
const int MAXN=3000;
double dp[MAXN][MAXN];
vector<double> arr(MAXN);
int n;
double solve(int pos, int num){
    if(num==0)return 1;
    if(pos>=n)return 0;
    double &r=dp[pos][num];
    if(r!=-1){return r;}
    r=solve(pos+1,num-1)*arr[pos];
    r+=solve(pos+1,num)*(1.0-arr[pos]);
    return r;
}
int main() {FIN;
   
   fore(i,0,MAXN)fore(j,0,MAXN)dp[i][j]=-1;
    cin>>n;
    fore(i,0,n)cin>>arr[i];
    cout<<fixed<<setprecision(10)<<solve(0,n/2+1)<<sl;

    return 0;
}




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

struct edge{
    int to,dist;
};

int main(void){
    int n;
    cin >> n;

    vector<vector<edge>> G(n);
    vector<int> color(n,-1);  //0black,1white
    //vector<int> parent(n);
    
    for(int i=1;i<n;i++){
        int a,b,d;
        cin >> a >> b >> d;
        a--; b--;
        G[a].push_back({b,d});
        G[b].push_back({a,d});
    }

    queue<int> q;
    q.push(0);
    color[0] = 1;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        
        for(int i=0;i<G[cur].size();i++){
            int np = G[cur][i].to;
            int d = G[cur][i].dist;

            //cout << "cur,np = " << cur << ", " << np << endl;

            if(color[np]!=-1) continue;
            
            //parent[G[cur][i]] = cur;
            if(d%2==0) color[np] = color[cur];
            else color[np] = color[cur]^1;
            q.push(np);
        }
    }

    for(int i=0;i<n;i++) cout << color[i] << endl;
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  int N = 3 * n;
  vector<long long> a(N);
  
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  
  long long sum = 0;
  for (int i = 1; i < 2*n; i+=2) {
    sum += a.at(i);
  }
  
  cout << sum << endl;
  
}



Measured memory_bytes: 2560
#include <iostream>
#include<iomanip>
#include <cmath>
#include <climits>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#include <list>
#include <string>
#include <numeric>
#include <utility>
#include <cfloat>

using namespace std;

bool is_prime[100001];
int like_2017[100001];
int r[100000];
int l[100000];
int main(){
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        cin >> l[i] >> r[i];
    }

    int max_r = *max_element(r, r + Q);

    for(int i = 2; i <= max_r; i++){
        is_prime[i] = true;
    }

    for(int i = 2; i <= max_r; i++){
        if(!is_prime[i]){
            continue;
        }
        for(int j = 2 * i; j <= max_r; j += i){
            is_prime[j] = false;
        }
    }

    for(int i = 1; i <= max_r; i++){
        like_2017[i] = like_2017[i - 1];
        if(is_prime[i] && is_prime[(i + 1)/2]){
            like_2017[i] = 1 + like_2017[i-1];
        }
    }
    
    for(int i = 0; i < Q; i++){
        cout << like_2017[r[i]] - like_2017[l[i] - 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include<map>
#include<string>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<typeinfo>
#include<queue>
#include<iomanip>
using namespace std;
const long long INF = 1LL << 60;
int main() {
	int N, M;
	cin >> N >> M;
	vector<int>a(M);
	for (int i = 0; i < M; i++) {
		cin >> a[i];
	}
	vector<int> dp(N + 1, -1);
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 0; i < M; i++) {
		dp[a[i]] = 0;
	}
	for (int i = 1; i < N; i++) {
		if(dp[i+1]!=0)dp[i + 1] =( dp[i] + dp[i - 1])%1000000007;
	}
	cout << dp[N];
}


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

using namespace std;
using std::string;

int main() {
	int a, b;
	string s, t, u;
	
  	cin >> s >> t >> a >> b >> u;
  	if (u == s) {
      	a--;
    } else {
      	b--;
    }
  
  	cout << a << " " << b << endl;
  
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdint>
#include <utility>
#include <tuple>
#include <map>    
#include <queue> 
#include <set>  
#include <stack> 
#include <deque>  
#include <unordered_map> 
#include <unordered_set> 
#include <bitset>

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;

	int use = 1;
	while (true) {
		if (B == 1) {
			use = 0;
			break;
		}
		int n = A + (A - 1)*(use - 1);
		if (n >= B) {
			break;
		}
		use++;
	}
	cout << use << endl;
}

Measured memory_bytes: 256
from copy import copy,deepcopy
import itertools
k=int(input())
b=[['.']*8 for i in range(8)]
R=set(range(8))
C=set(range(8))
p=set()
m=set()
for i in range(k):
    r,c=map(int,input().split())
    b[r][c]='Q'
    R.remove(r);C.remove(c)
    p.add(r+c)
    m.add(r-c)
for x in itertools.permutations(C):
    P=p.copy()
    M=m.copy()
    ok=True
    for r,c in zip(R,x):
        if r+c in P:
            ok=0
        P.add(r+c)
        if r-c in M:
            ok=0
        M.add(r-c)
    if(ok):
        for r,c in zip(R,x):
            b[r][c]='Q'
        break
for i in range(8):
    print(''.join(b[i]))


Measured memory_bytes: 6356
using System;
class Program
{
	static void Main(string[] args)
	{
      string[] param = Console.ReadLine().Split(' ');
      int X = int.Parse(param[0]);
      int A = int.Parse(param[1]);
      
      int answer = (X < A) ? 0 : 10;
      Console.WriteLine(answer);
	}
}

Measured memory_bytes: 13268
#include <iostream>
#include <cstdio>

template <class T>
inline void read(T &x)
{
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return;
}

int a, b;

int main()
{
    read(a), read(b);
    if (a >= b)  
        for (int i = 1; i <= a; ++i)
            printf("%d", b);
    else    
        for (int i = 1; i <= b; ++i)
            printf("%d", a);
    printf("\n");
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void) {
	int n,m,q,max=0,ten;
	int A[11],a[51],b[51],c[51],d[51];
	scanf("%d %d %d",&n,&m,&q);
	for(int i=0;i<q;i++){
		scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
	}
	for(int i=0;i<n;i++) {
		A[i]=1;
	}
	while(1){
		ten=0;
		for(int i=0;i<q;i++) {
			if(A[b[i]-1]-A[a[i]-1]==c[i])
				ten+=d[i];
		}
		if(max<ten) max=ten;
		if(A[0]==m) break;
		for(int i=n-1;i>=0;i--) {
			if(A[i]<m) {
				A[i]++;
				for(int j=i+1;j<n;j++) {
					A[j]=A[i];
				}
				break;
			}
		}
	}
	printf("%d\n",max);
	return 0;
}
		
		

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

const int _ = 2e5 + 7;
vector < int > nxt[_]; int mx , id , N;

void dfs(int x , int p , int d){
	if(mx < d){mx = d; id = x;}
	for(auto t : nxt[x]) if(t != p) dfs(t , x , d + 1);
}

int main(){
	cin >> N;
	for(int i = 1 ; i < N ; ++i){int p , q; cin >> p >> q; nxt[p].push_back(q); nxt[q].push_back(p);}
	dfs(1 , 0 , 1); dfs(id , 0 , 1);
	cout << (mx % 3 == 2 ? "Second" : "First"); return 0;
}

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const int MOD = 1000000007;

int main() {
  int n;
  cin >> n;
  vector<int> a(n), cnt(200000 + 1, 0);
  rep(i, n) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  vector<int> _a = a;
  sort(all(_a));
  uniq(_a);
  rep(i, n) {
    int s = _a.size();
    if (a[i] != _a[s - 1])
      cout << _a[s - 1] << endl;
    else {
      cout << (cnt[a[i]] == 1 ? _a[s - 2] : _a[s - 1]) << endl;
    }
  }
}


Measured memory_bytes: 3968
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


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

	int N; cin >> N;
	int sum = 0;
	bitset<2000 * 2000 + 10> DP;
	DP[0] = 1;
	rep(i, N) {
		int A; cin >> A;
		sum += A;
		DP |= DP << A;
	}
	for (int i = (sum + 1) / 2; i <= sum; i++) {
		if (DP[i]) {
			cout << i << endl;
			return 0;
		}
	}



    return 0;
}


Measured memory_bytes: 1792
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

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

    int n;
    cin >> n;
    vector<int> a(1 << n);
    for (int i = 0; i < (1 << n); i++)
    {
        cin >> a[i];
    }
    bool f = true;
    int ret = 0;
    // par[i] := 親に1があるか
    vector<int> par(1 << n, 0);
    vector<int> queued(1 << n, 0);
    queue<int> que;
    que.push(0);
    queued[0] = 1;
    while (!que.empty())
    {
        int cur = que.front();
        que.pop();
        if (a[cur] && par[cur] == 0)
        {
            ret++;
        }
        for (int i = 0; i < n; i++)
        {
            if ((cur >> i) & 1)
                continue;
            int nxt = cur | (1 << i);
            if (a[cur] == 1 && a[nxt] == 0)
            {
                f = false;
            }
            if (a[cur])
            {
                par[nxt] = 1;
            }
            if (queued[nxt] == 0)
            {
                que.push(nxt);
                queued[nxt] = 1;
            }
        }
    }
    cout << (f ? ret : -1) << endl;
}



Measured memory_bytes: 16128
N = int(input())
a = list(map(int,input().split()))

tmp = sum(a)
ave1 = tmp // N
ave2 = ave1 + 1

dev1 = 0
dev2 = 0

for aa in a:
    dev1 += (aa - ave1)**2
    dev2 += (aa - ave2)**2

print(min(dev1,dev2))

Measured memory_bytes: 3060
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,*A = map(int,read().split())

A.sort(reverse = True)

A.append(0)
i = 0
while A[i + 1] > i + 1:
    i += 1

x = A[i] - (i + 1)
y = max(j for j in range(N) if A[j] > i) - i

answer = 'First' if x&1 or y&1 else 'Second'
print(answer)

Measured memory_bytes: 12528
import math

n=int(input())
city=[0]*n
for i in range(n):
    city[i]=list(map(int,input().split()))

dis=[0]*(n*(n-1)//2)
k=0
for i in range(n):
    for j in range(i+1, n):
        dis[k] = math.sqrt(((city[i][0]-city[j][0])**2+(city[i][1]-city[j][1])**2))
        k+=1

ans=sum(dis)*2/n

print(ans)




Measured memory_bytes: 3064
N, Y = [int(i) for i in input().split()]

def ans():
    for i in range(N+1):
        for j in range(N-i+1):
            if i*10000 + j*5000 + (N-i-j)*1000 == Y:
                print(i, j, N-i-j)
                exit()
    print(-1, -1, -1)

ans()

Measured memory_bytes: 3060
#include <cstdio>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;

constexpr long long mod = 1000000007;


// 階乗数n!を最初に計算して、呼ばれた時に返す
class Factorial {
    std::vector<long long> table;
public:
    Factorial(int max) : table(max) // max:テーブルのサイズ
    {
        table[0] = 1;
        for (int i = 1; i < max; ++i){
            table[i] = (table[i - 1] * (i + 1)) % mod;
        }
    }

    long long operator () (int n)
    {
        if (n < 0) return 0;
        if (n == 0) return 1;
        return table[n - 1];
    }
};

class FactorialInverse {
    std::vector<long long> table;
    Factorial& fact;
public:
    FactorialInverse(int max, Factorial fact) : table(max), fact(fact) // max:テーブルのサイズ
    {
        int digit  = 0;
        {
            int temp = mod - 2;
            while (temp > 0){
                temp >>= 1;
                ++digit;
            }
        }
        auto origin = fact(max);
        vector<long long> power2(digit);
        power2[0] = origin;
        for (int i = 1; i < digit; ++i) power2[i] = (power2[i - 1] * power2[i - 1]) % mod;
        {
            long long table_max = 1;
            int temp = mod - 2;
            for (int i = 0; temp > 0; ++i, temp >>= 1){
                if (!(temp & 1)) continue;
                table_max *= power2[i];
                table_max %= mod;
            }
            table[max - 1] = table_max;
        }
        for (int i = max - 2; i >= 0; --i){
            table[i] = (table[i + 1] * (i + 2)) % mod;
        }
    }

    long long operator () (int n)
    {
        if (n < 0) return 0;
        if (n == 0) return 1;
        return table[n - 1];
    }
};

int main()
{
    int H, W, A, B;
    scanf("%d %d %d %d\n", &H, &W, &A, &B);

    Factorial fact(H + W - 2);
    FactorialInverse factinv(H + W - 2, fact);
    auto nCr = [&](int n, int r){
        return (((fact(n) * factinv(r)) % mod) * factinv(n - r)) % mod;
    };

    long long result = 0;
    for (int x = B; x < W; ++x){
        result += (nCr(H - A - 1 + x, x) * nCr(A - 1 + W - x - 1, W - x - 1)) % mod;
        result %= mod;
    }
    printf("%lld\n", result);
}


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

#define thegamebegins   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define fileio          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define int             long long
#define float           long double
#define test            int T; cin>>T; while(T--)
#define in(a,n)         for(int i=0; i<n; ++i)  cin>>a[i]
#define r0              return 0
#define E               "\n"
#define S               " "
#define elif            else if 
#define M               1000000007
#define fi(i,x,y)       for(int i=x; i<y; ++i)
#define fa(i,s)         for(auto i:s)
#define fp(i,s)         for(auto i=(s).begin(); i!=(s).end(); ++i)
#define sz(s)           (int)(s).size()
#define vi              vector <int>
#define vpii            vector <pair <int,int> >
#define mii             map <int,int>
#define pii             pair <int,int>
#define seti            set <int>
#define setd            set <int,greater <int> >
#define all(s)          (s).begin(),(s).end()
#define sortd(a,n)      sort(a, a+n, greater<int>())
#define pb              push_back
#define fr              first
#define sc              second
#define lb              lower_bound
#define ub              upper_bound
#define er              equal_range
 
const int INF = 0x3f3f3f3f;

signed main()
{
    thegamebegins

    int n,ans=0LL;    cin>>n;
    fi(i,1,n+1)     if(i%3 && i%5)  ans+=1LL*i;
    cout<<ans;
    r0;
}


Measured memory_bytes: 3652
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N, M, K = map(int, input().rstrip().split(' '))

comb = cmb(N*M-2, K-2) % 1000000007

cost = 0
for d in range(1, N):
    cost += d * M**2 * (N - d) * comb
    cost %= 1000000007
for d in range(1, M):
    cost += d * N**2 * (M - d) * comb
    cost %= 1000000007
    
print(cost)



Measured memory_bytes: 52788
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vll vector<ll>
#define pb push_back
#define x first
#define y second
#define pii pair<int,int>

const int mod = 1e9+7;

int main()
{
	string s;
  	cin>>s;
  	deque<char> q;
  	int i;
  	for(i=0;i<s.length();i++)
      q.pb(s[i]);
  	int Q,where=0;
  	cin>>Q;
  	while(Q--)
    {
      	int a,b;
      	char c;
      	cin>>a;
      	if(a==1)
        {
          where ^= 1;
          continue;
        }
      	cin>>b>>c;
      	b--;int pos=where^b;
      	if(pos)
          q.pb(c);
      	else
          q.push_front(c);
    }
  	if(where)
      for(auto it=q.rbegin();it!=q.rend();it++)
        cout<<*it;
  	else
      for(auto it=q.begin();it!=q.end();it++)
        cout<<*it;
}

Measured memory_bytes: 896
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {

		Scanner scan = new Scanner (System.in);

		String day = scan.nextLine();

		if(day.equals("22"))
			System.out.println("Christmas Eve Eve Eve");
		else if(day.equals("23"))
			System.out.println("Christmas Eve Eve");
		else if(day.equals("24"))
			System.out.println("Christmas Eve");
		else if(day.equals("25"))
			System.out.println("Christmas");

	}

}


Measured memory_bytes: 21716
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    void chmax<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? b : a; }
    void chmin<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? a : b; }

    void solve()
    {
        int N = cin.nextint;
        var A = new int[N + 1];
        for (int i = 0; i < N + 1; i++)
        {
            A[i] = cin.nextint;
        }
        Array.Sort(A);
        long ans = A[1] - A[0];
        for (int i = 1; i < N; i++)
        {
            ans = gcd(A[i + 1] - A[i], ans);
        }
        WriteLine(ans);
    }

    long gcd(long a, long b)
    {
        return (b != 0) ? gcd(b, a % b) : a;
    }
    long lcm(long a, long b)
    {
        return a / gcd(a, b) * b;
    }
}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 20448
#include <bits/stdc++.h>
using namespace std;
int g(int x, int i)
{
    return (x>>i)&1;
}
int divide(int x, int i)
{
    return (x>>(i+1)<<i) + (x&((1<<i)-1));
}
int join(int x, int i, int bit)
{
    x=(x>>i<<(i+1)) + (x&((1<<i)-1));
    if (bit) x^=(1<<i);
    return x;
}
void pl(vector<int> &c, vector<int> &a, vector<int> &b)
{
    for(auto x: a) c.push_back(x);
    for(auto x: b) c.push_back(x);
}
vector<int> build(int x, int y, int n)
{
    if (n==1) return {x, y};
    vector<int> v, v1, v2;
    for(int i=0; i<n; ++i) if (g(x, i) != g(y, i))
    {
        int newx=divide(x, i), newy=divide(y, i), middle=newx^1;
        v1=build(newx, middle, n-1);
        v2=build(middle, newy, n-1);
        for(int j=0; j<v1.size(); ++j) v1[j]=join(v1[j], i, g(x, i));
        for(int j=0; j<v2.size(); ++j) v2[j]=join(v2[j], i, g(y, i));
        pl(v, v1, v2);
        return v;
    }
}
int main()
{
    int n, a, b; cin>>n>>a>>b;
    int x=__builtin_popcount(a) % 2;
    int y=__builtin_popcount(b) % 2;
    if (x==y) cout<<"NO"; else
    {
        cout<<"YES\n";
        vector<int> v=build(a, b, n);
        for(auto x: v) cout<<x<<' ';
    }
}


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

int main(){
    int n, h; cin >> n >> h;
    vector<int> a(n), b(n);
    int ma = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        ma = max(ma, a[i]);
    }
    int ans = 0;
    bool ok = false;
    sort(b.begin(), b.end(), greater<int>());
    for(int i = 0; i < n; i++){
        if(ma < b[i]){
            ans++;
            h -= b[i];
        }
        if(h <= 0){
            ok = true;
            break;
        }
    }
    if(!ok){
        ans += (h+ma-1)/ma;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4028
#include <iostream>
#include <memory.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)

const int sz = 100000;
bool prime[sz];

int main(){
  memset(prime, true, sizeof(prime));
  prime[0] = prime[1] = false;
  for(int i = 2; i * i < sz; i++){
    if(prime[i]){
      for(int j = 2; i * j < sz; j++){
	prime[i*j] = false;
      }
    }
  }
  
  int n;
  while(cin >> n && n){
    for(int i = n; i >= 2; i--){
      if(prime[i] && prime[i-2]){
	cout << i - 2 << " " << i << endl;
	break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 960
S = input()
if 1 <= int(S[0:2]) <= 12:
    if 1 <= int(S[2:]) <= 12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if 1 <= int(S[2:]) <= 12:
        print("YYMM")
    else:
        print("NA")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define rusha scanf("%d",&n);rep(i,1,n)scanf("%d",&a[i]);
#define rushb scanf("%d",&t);while(t--)
#define debug(x) cout<<" L-B-W-- "<<x<<" --N-B\n"
#define pb push_back
//#define pii pair<int,int>
#define vii vector<int>
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof a)
#define all(x) (x.begin(),x.end())
#define judgef printf("%s\n",f?"Yes":"No")
#define Judgef printf("%s\n",f?"YES":"NO")
#define sz(x) ((int)(x).size())
#define sf(x) (sizeof(x))
using namespace std;
typedef long long ll;
typedef double db;
const double pai = acos(-1.0);
const double eps = 1e-8;
const int mod=998244353;
//const int mod=1e9+7;
const int inf=1e9+7;
//const ll inf=0x7f7f7f7f1234abcd;
const int maxn=40010;
inline ll ksm(ll x,ll y){ ll res=1; while(y){if(y&1) res=res*x%mod;x=x*x%mod; y>>=1;} return res; }
inline ll inv(ll a,ll p){if(a==1)return 1;return (p-p/a)*inv(p%a,p)%p;}
ll lcm(ll a, ll b) { return a * b / __gcd(a, b); }

int t,n,m,k;

char a[maxn];
int main(){
    scanf("%s",a);
    printf("A%cC",a[1]=='R'?'B':'R');
    return 0;
}


Measured memory_bytes: 3716
#include <iostream>
using namespace std;
static const int MAX = 100, INFTY = (1 << 21), WHITE = 0, GRAY = 1, BLACK = 2;

int N, M[MAX][MAX];

int prim() {
	int u, minv;
	int D[MAX], P[MAX], C[MAX];

	for (int i = 0; i < N; i++) {
		D[i] = INFTY;
		P[i] = -1;
		C[i] = WHITE;
	}

	D[0] = 0;
	while (true) {
		minv = INFTY;
		u = -1;
		for (int i = 0; i < N; i++) {
			if (minv > D[i] && C[i] != BLACK) {
				u = i;
				minv = D[i];
			}
		}
		if (u == -1) break;
		C[u] = BLACK;
		for (int v = 0; v < N; v++) {
			if (C[v] != BLACK && M[u][v] != INFTY) {
				if (D[v] > M[u][v]) {
					D[v] = M[u][v];
					P[v] = u;
					C[v] = GRAY;
				}
			}
		}
	}
	int sum = 0;
	for (int i = 0; i < N; i++) {
		if (P[i] != -1) sum += M[i][P[i]];
	}
	return sum;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int e; cin >> e;
			M[i][j] = (e == -1) ? INFTY : e;
		}
	}
	cout << prim() << endl;
}


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

int main(){
    
    int h,w;
    cin>>h;
    cin>>w;
    int x=0;
    int board[h][w];
    int a=0,b=1;
    int t=0;
    int counter=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            board[i][j]=a;
        }
    }
    cin>>b;
    if(h<=w){
        x=1;
        
    }else if(h>w){
        x=2;
    }
    if(x==1){
        t=0;
        while(counter<b){
        for(int j=0;j<w;j++){
            board[t][j]=a;
            counter+=1;
        }
        t++;
        }
    }else if(x==2){
        t=0;
        while(counter<b){
        for(int j=0;j<h;j++){
            board[j][t]=a;
            counter+=1;
        }
        t++;
        }
    }
    cout<<t;
}


Measured memory_bytes: 888
import java.util.*
fun main(args: Array<String>){
	val cin = Scanner(System.`in`)
    val n = cin.nextInt()

    var odd = 0
    for (i in 1..n) {
        val a = cin.nextInt()
        if (a % 2 == 1) {
            odd += 1
        }
    }
    if (odd % 2 == 0) {
        println("YES")
    } else {
        println("NO")
    }
}

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

int main() {
    int H, W;
    cin >> H >> W;

    char s[100][100];
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> s[i][j];
        }
    }

    bool ans = true;
    int x[4] = {0, 1, 0, -1}, y[4] = {1, 0, -1, 0};

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (s[i][j] == '#') {
                bool check = false;
                for (int k = 0; k < 4; ++k) {
                    if (0 <= i+x[k] && i+x[k] <= H && 0 <= j+y[k] && j+y[k] <= W && s[i+x[k]][j+y[k]] == '#') check = true;
                }
                if (!check) ans = false;
            }
        }
    }
    if (ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int n,a,cnt,i,j;
	scanf("%d",&n);
	cnt=0;
	for(i=0;i<n;i++)	{
		scanf("%d",&a);
		while(a%2==0)	{
			cnt++;
			a/=2;
		}
	}
	printf("%d\n",cnt);
	return 0;
}

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

#define ll long long
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll mod = 1000000007;
ll INF = 1e9 + 5;
ll M = 1e9+7;

int main(){
    FAST;
    ll h,w;
    cin >> h >> w;
    vector<vector<char>> a(h,vector<char>(w));
    vector<vector<ll>> dp(h+1,vector<ll>(w+1,0));
    for(int i=0;i<h;i++)
    {
      for(int j=0;j<w;j++)
      {
        cin >> a[i][j];
      }
    }
    ll c=1;
    for(int i=1;i<=w;i++)
    {
      if(a[0][i-1] == '#' || c == 0)
      {
        dp[1][i] = 0;
        c = 0;
      }
      else
      {
        dp[1][i] = 1;
      }
    }
    c=1;
    for(int i=1;i<=h;i++)
    {
      if(a[i-1][0] == '#' || c == 0)
      {
        dp[i][1] = 0;
        c = 0;
      }
      else
      {
        dp[i][1] = 1;
      }
    }
    for(int i=2;i<=h;i++)
    {
      for(int j=2;j<=w;j++)
      {
        if(a[i-1][j-1] == '#')
        {
          dp[i][j] = 0;
        }
        else
        {
          dp[i][j] = (dp[i-1][j]%M + dp[i][j-1]%M)%M;
        }
      }
    }
    cout << dp[h][w] << endl;
    return 0;
}


Measured memory_bytes: 9088
#include<vector>
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<cmath>
#include<unordered_set>
#include <numeric>
using namespace std;

typedef long long ll;

#define FOR(i,n) for(int i=0;i<n;i++)
#define out(a) for(auto i:a)cout<<i<<" ";
#define outl(a) for(auto i:a)cout<<i<<endl;


vector<vector<ll> >tree;



int main(){
    int n;
    cin>>n;
    vector<int>vec(n);
    FOR(i,n){
        cin>>vec[i];
    }
    vector<int>last(n);
    last[0]=-1;
    int ans=0;
    for(int i=1;i<n;i++){
        if(vec[i]==vec[i-1]){
            last[i]=last[i-1];
            continue;
        }
        
        if(vec[i]>vec[i-1]){
            if(last[i-1]==1){
                ans++;
                last[i]=-1;
            } else{
                last[i]=0;
            }
        }
        if(vec[i]<vec[i-1]){
            if(last[i-1]==0){
                ans++;
                last[i]=-1;
            } else{
                last[i]=1;
            }
        }
    }
    cout<<ans+1<<endl;
    
    return 0;
    
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
#define all(a) begin(a),end(a)
#define D1(a) cerr<<#a<<":"<<a<<endl
#define D2(a,b) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<endl
#define D3(a,b,c) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl
#define DH(c) do{rep(__i, c.size())cerr<<c[__i]<<(__i==c.size()-1?'\n':' ');}while(0)
#define int ll
signed main()
{
    int N, K; cin >>N>> K;
    vector<int> neg, pos;
    rep(i, N) {
        int a; cin >> a;
        if (a > 0) pos.push_back(a);
        else if (a < 0) neg.push_back(a);
    }
    sort(all(pos));
    sort(all(neg));

    int n_neg = neg.size();
    int n_pos = pos.size();
    int n_zero = N - n_neg - n_pos;

    ll pairs = (ll)N * (N - 1) / 2;
    ll neg_pairs = (ll)n_neg * n_pos;
    ll zero_pairs = (ll)n_zero * (n_zero - 1) / 2 + (ll)n_zero * (N - n_zero);
    ll pos_pairs = (ll)pairs - neg_pairs - zero_pairs;

    ll l = (ll)(-1e18)-1, r = 1e18;
    while (r - l > 1) {
        ll m = l + (r - l) / 2;

        ll cnt = 0;
        if (m < 0) {
            for (auto ne : neg) {
                auto it = lower_bound(all(pos), (m + ne + 1) / ne);
                // if (it == pos.end()) break;
                cnt += distance(it, pos.end());
            }
        } else if (m == 0) {
            cnt = neg_pairs + zero_pairs;
        } else {
            for (auto po : pos) {
                auto it = upper_bound(all(pos), m / po);
                if (it == pos.begin()) break;
                cnt += distance(pos.begin(), it);
                if (po <= *(it-1))
                    cnt -= 1;
            }
            for (auto ne : neg) {
                auto it = lower_bound(all(neg), m / ne);
                cnt += distance(it, neg.end());
                if (it != neg.end() && ne >= *it)
                    cnt -= 1;
            }
            cnt /= 2;
            cnt += neg_pairs + zero_pairs;
        }
// D4(l, r, m, cnt);

        if (cnt >= K) {
            r = m;
        } else {
            l = m;
        }
    }

    cout << r << endl;
}


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

int main() {
	
long long int N,A,B,tot;
	cin>>N>>A>>B;
	
	if(A==0)
	{
		cout<<0<<endl;
	}
	else
	{
    	tot=A*(N/(A+B));
    	if(N%(A+B)<=A)
    	{
    		tot+=(N%(A+B));
    	}
    	else
    	{
    		tot+=A;
    	}
	    cout<<tot<<endl;
	}
	
	
	
	
	return 0;
}

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

for i in range(n):
    if a[i]%2!=0:
        a[i]=3
flag = True
for i in range(n):
    if a[i]%3==0 or a[i]%5==0:
        continue
    else:
        flag = False
if flag:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 3064
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [n, k] <- getIntList
    hs <- VU.fromList <$> getIntList
    dp <- VUM.replicate n (10^9)
    VUM.write dp 0 0
    forM_ [0..n-1] $ \i -> do
        forM_ [1..(min k (n - i - 1))] $ \j -> do
            let dk = abs $ (hs VU.! (i + j)) - (hs VU.! i)
            next <- VUM.read dp (i + j)
            now <- VUM.read dp i
            VUM.write dp (i + j) $ min next (now + dk)
    ans <- VUM.read dp (n - 1)
    print ans

Measured memory_bytes: 5628
#include <bits/stdc++.h>
using namespace std;
bool prime[10000001];
int main() {
    for(int i=3;i<3162;i++)if(!prime[i])for(int j=i*2;j<10000001;j+=i)prime[j]=1;
    int n;
    while(cin>>n,n){
        if(!(n%2))n--;
        while(prime[n]||prime[n-2]||prime[n-6]||prime[n-8])n-=2;
        cout<<n<<endl;
    }
}

Measured memory_bytes: 10924
def main():
	s = str(input())
	t = str(input())
	
	
	if len(s) == len(t):
		ans = 0
		for i in range(len(t)):
			if list(s)[i] == list(t)[i]:
				ans += 1
		print(len(t)-ans)

	else:
		l = []
		for i in range(len(s)-len(t)):
			l.append(s[i:i+len(t)])
		
		ans = []
		for c in l:
			counter = 0
			for i in range(len(c)):
				if list(c)[i] == list(t)[i]:
					counter += 1
			ans.append(counter)

		if not ans:
			print(len(t))
		else:
			print(len(t)-max(ans))





	

if __name__ == '__main__':
	main()

Measured memory_bytes: 86784
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { //Simulate flip processes
	//UPD: Don't always need to take max rows
 
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		int M = input.nextInt();
		int K = input.nextInt();
		System.out.println(Valid(N,M,K)?"Yes":"No");
	}	
	public static boolean Valid(int N,int M,int K) {
		for (int r = 0; r <= N; r++) {
			int numB = r*M;
			for (int c = 0; c <= M; c++) {
				int leftrows = N-r;
				int net = leftrows-r;
				int total = numB+c*net;
				if (total==K) {
					return true;
				}
			}
		}
		return false;
	}
}

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

int getDig(ll N){
	return to_string(N).length();
}

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	ll N;
	cin >> N;
	int ans = 12;
	for (ll i = 1; i*i <= N; i++)
	{
		if(N%i==0){
			ll A = i;
			ll B = N/i; 
			int tmp = max(getDig(A), getDig(B));
			if(tmp < ans) ans = tmp;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y;
  cin >> x >> y;
  if(y%2==1) {
    cout << "No" << endl;
    return 0;
  }
  
  if(y/2-x>=0&&2*x-y/2>=0) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}

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

#define int long long

#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
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001001001001ll;

struct CHT{
    deque<pint>deq;

    bool check(pint f1,pint f2,pint f3){
       	int a1=f1.fi,b1=f1.se;
      	int a2=f2.fi,b2=f2.se;
      	int a3=f3.fi,b3=f3.se;
     	return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);
    }

  	void add(int a,int b){
    	pint f(a,b);
      	while(deq.size()>=2&&check(f,deq[0],deq[1]))deq.pop_front();
     	deq.push_front(f);
    }
  	int query(int x){
        while(deq.size()>=2&&deq[0].first*x+deq[0].second>=deq[1].first*x+deq[1].second)deq.pop_front();
        return deq[0].first*x+deq[0].second;
    }
};

int N;
int T[333333];
int S[333333];
int predp[333333],sufdp[333333];

vint calcdp(){
    vint sum(N+1);
    rep(i,N)sum[i+1]=sum[i]+T[i];

    vint dp(N+1);


    CHT cht;
    cht.add(0,0);
    for(int i=1;i<=N;i++){
        dp[i]=dp[i-1];
        chmax(dp[i],-cht.query(i)-sum[i]+i*i+i);
        cht.add(2*i,-dp[i]-sum[i]-i*i+i);
    }
    return dp;
}

int ans[333333];
void solve(int l,int r){
    if(l==r)return;
    int m=(l+r)/2;

    solve(l,m);
    solve(m+1,r);

    CHT cht;
    for(int i=m;i>=l;i--){
        cht.add(-2*i,-predp[i]-S[i]-i*i+i);
    }


    int ma=-INF;
    for(int i=r;i>m;i--){
        chmax(ma,-cht.query(-i)-S[i]+i*i+i+sufdp[i]);
        chmax(ans[i-1],ma);
    }

    cht=CHT();

    for(int i=m+1;i<=r;i++){
        cht.add(2*i,-sufdp[i]+S[i]-i*i-i);
    }

    ma=-INF;
    for(int i=l;i<=m;i++){
        chmax(ma,-cht.query(i)+S[i]+i*i-i+predp[i]);


        chmax(ans[i],ma);
    }
}

signed main(){
    cin>>N;
    rep(i,N)cin>>T[i],T[i]*=2;

    rep(i,N)S[i+1]=S[i]+T[i];


    vint latte=calcdp();
    rep(i,N+1)predp[i]=latte[i];

    reverse(T,T+N);
    latte=calcdp();
    rep(i,N+1)sufdp[i]=latte[N-i];
    reverse(T,T+N);

    fill_n(ans,N,-INF);
    solve(0,N);

    int M;cin>>M;



    rep(i,M){
        int p,x;
        cin>>p>>x;
        x*=2;
        p--;
        cout<<max(predp[p]+sufdp[p+1],ans[p]+T[p]-x)/2<<endl;
    }
    return 0;
}

Measured memory_bytes: 20656
import sys
from bisect import bisect
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

class LCA():
	def __init__(self, adj_given, root_given):
		self.adj = adj = adj_given
		self.root = root_given
		self.n = n = len(adj)
		self.maxlog = 0
		while (1 << self.maxlog) < n:
			self.maxlog += 1
		maxlog = self.maxlog
		self.par = [[-1 for _ in range(n)] for _ in range(maxlog)]
		self.dep = [0 for _ in range(n)]
		self.num_key = [[0] for _ in range(n)]
		self.num_value = [[0] for _ in range(n)]
		self.sum_value = [[0] for _ in range(n)]
		self.first = [10**6 for _ in range(n)]
		self.first[self.root] = 0
		self.visited = 1
		self.cnt = 1
		self.dist = [0 for _ in range(n)]

	def dfs(self, x, pa, de, co, le):
		par = self.par
		dep = self.dep
		root = self.root
		
		par[0][x] = pa
		dep[x] = de

		if x != root and self.visited < n:
			self.num_key[co].append(self.cnt)
			self.num_value[co].append(self.num_value[co][-1] + 1)
			self.sum_value[co].append(self.sum_value[co][-1] + le)
			if self.first[x] == 10**6:
				self.visited += 1
				self.first[x] = self.cnt
			self.cnt += 1
			self.dist[x] = self.dist[pa] + le

		for v, c, l in adj[x]:
			if v != pa:
				self.dfs(v, x, de+1, c, l)

		if x != root and self.visited < n:
			self.num_key[co].append(self.cnt)
			self.num_value[co].append(self.num_value[co][-1] - 1)
			self.sum_value[co].append(self.sum_value[co][-1] - le)
			self.cnt += 1

		return

	def calc(self):
		root = self.root
		par = self.par
		maxlog = self.maxlog
		self.dfs(root, -1, 0, -1, 0)

		for k in range(maxlog-1):
			for v in range(n):
				if par[k][v] < 0:
					continue
				else:
					par[k+1][v] = par[k][par[k][v]]
		return

	def get_lca(self, u, v):
		par = self.par
		dep = self.dep
		maxlog = self.maxlog
		if dep[u] > dep[v]:
			u, v = v, u
		for k in range(maxlog):
			if ((dep[v] - dep[u]) >> k) & 1:
				v = par[k][v]

		if u == v:
			return u
		else:
			for k in range(maxlog-1, -1, -1):
				if par[k][u] != par[k][v]:
					u = par[k][u]
					v = par[k][v]
			return par[0][u]

n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b, c, d = map(int, input().split())
	adj[a-1].append((b-1, c-1, d))
	adj[b-1].append((a-1, c-1, d))

lca = LCA(adj, 0)
lca.calc()

for _ in range(q):
	x, y, u, v = map(int, input().split())
	x, u, v = x-1, u-1, v-1
	a = lca.get_lca(u, v)
	id_u = max(bisect(lca.num_key[x], lca.first[u])-1, 0)
	id_v = max(bisect(lca.num_key[x], lca.first[v])-1, 0)
	id_a = max(bisect(lca.num_key[x], lca.first[a])-1, 0)

	dist_u = lca.dist[u] + lca.num_value[x][id_u] * y - lca.sum_value[x][id_u]
	dist_v = lca.dist[v] + lca.num_value[x][id_v] * y - lca.sum_value[x][id_v]
	dist_a = lca.dist[a] + lca.num_value[x][id_a] * y - lca.sum_value[x][id_a]
	print(dist_u + dist_v - 2 * dist_a)

Measured memory_bytes: 179588
import java.io.*;
// import java.math.*;
// import java.util.*;
// import java.util.Map.*;
// import java.util.stream.*;

public class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader reader =
            new BufferedReader (new InputStreamReader (System.in));
        int N = Integer.parseInt (reader.readLine());
        String S = reader.readLine();
        System.out.println (
            N % 2 == 0 ? S.substring (0, N / 2).equals (S.substring (N / 2))
                             ? "Yes"
                             : "No"
                       : "No");
        return;
    }
}

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

int main(){
    ull x,y,k;
    cin>>x>>y;
    for(k=0;x*(ull)pow(2,k)<=y;k++);
    cout<<k<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int mod=1e9+7;
int Pow(int x,int y) {
	int res=1;
	while(y) {
		if(y&1) res=res*(ll)x%mod;
		x=x*(ll)x%mod,y>>=1;
	}
	return res;
}
inline void Add(int &x,int y) { x+=y; if(x>=mod) x-=mod; }
inline void Dec(int &x,int y) { x-=y; if(x<0) x+=mod; }
int f[1<<16],g[1<<16],sz[1<<16];
int A[20],m,n;
int N;
int fac[(1<<16)+10],inv[(1<<16)+10];
void getfac(int n) {
	fac[0]=1; for(int i=1;i<=n;++i) fac[i]=fac[i-1]*(ll)i%mod;
	inv[n]=Pow(fac[n],mod-2); for(int i=n;i>=1;--i) inv[i-1]=inv[i]*(ll)i%mod;
}
int C(int n,int m) { return fac[n]*(ll)inv[m]%mod*inv[n-m]%mod; }
int main() {
	rd(n),rd(m); N=1<<n,getfac(N);
	for(int i=1;i<=m;++i) rd(A[i]);
	f[0]=1;
	for(int i=m;i>=1;--i)
		for(int s=N-1;s>=0;--s) if(f[s]) {
			for(int j=0;j<n;++j) if(!(s>>j&1)&&N-A[i]+1>=s+(1<<j))
				Add(f[s|1<<j],f[s]*(ll)C(N-A[i]-s,(1<<j)-1)%mod);
		}
	int ans=0;
//	for(int i=0;i<N;++i) printf("%d ",f[i]); puts("");
	for(int i=1;i<N;++i) sz[i]=sz[i&(i-1)]+1;
	for(int x=0;x<N;++x) {
		int tot=N-1-x;
		for(int j=n-1;j>=0;--j)
			if(tot>=(1<<j)) f[x]=f[x]*(ll)C(tot,1<<j)%mod,tot-=(1<<j);
		if(sz[x]&1) Dec(ans,f[x]);
		else Add(ans,f[x]);
	}
	for(int i=1;i<N;i<<=1) ans=ans*(ll)fac[i]%mod;
	for(int i=1;i<=n;++i) ans=ans*2ll%mod;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int W,H,N;
  cin >> W >> H >> N;
  int u=H,d=0,l=0,r=W;
  rep(i,N) {
    int x,y,a;
    cin >> x >> y >> a;
    switch(a) {
      case 1:
        l = max(l,x);
        break;
      case 2:
        r = min(r,x);
        break;
      case 3:
        d = max(d,y);
        break;
      case 4:
        u = min(u,y);
        break;
    }
  }
  cout << max(0,u-d) * max(0,r-l) << endl;
  return 0;
}

Measured memory_bytes: 256