akhauriyash/Code-Regression huggingface dataset:
fun main() {
    var a1 = readLine()!!.split(" ").map { it.toInt() }.toMutableList()
    var a2 = readLine()!!.split(" ").map { it.toInt() }.toMutableList()
    var a3 = readLine()!!.split(" ").map { it.toInt() }.toMutableList()

    for (i in 0 until readLine()!!.toInt()) {
        val num = readLine()!!.toInt()
        when {
            a1.indexOf(num) > -1 -> {
                a1[a1.indexOf(num)] = 0
            }
            a2.indexOf(num) > -1 -> {
                a2[a2.indexOf(num)] = 0
            }
            a3.indexOf(num) > -1 -> {
                a3[a3.indexOf(num)] = 0
            }
        }
    }

//    縦横であっているのかを調べる
    when {
        a1.all { it == 0 } or a2.all { it == 0 } or a3.all { it == 0 } -> {
            println("Yes")
        }
        (a1[0] == 0) and (a2[0] == 0) and (a3[0] == 0) -> {
            println("Yes")
        }
        (a1[1] == 0) and (a2[1] == 0) and (a3[1] == 0) -> {
            println("Yes")
        }
        (a1[2] == 0) and (a2[2] == 0) and (a3[2] == 0) -> {
            println("Yes")
        }
        (a1[0] == 0) and (a2[1] == 0) and (a3[2] == 0) -> {
            println("Yes")
        }
        (a1[2] == 0) and (a2[1] == 0) and (a3[0] == 0) -> {
            println("Yes")
        }
        else -> {
            println("No")
        }
    }

}


Measured memory_bytes: 36356
#include<bits/stdc++.h>
using namespace std;
#define fast                         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int                          long long int
#define double                       long double
#define ff                           first
#define ss                           second
#define pb                           push_back
#define eb                           emplace_back
#define all(x)                       (x).begin(), (x).end()
#define sz(x)                        ((int)(x).size())
#define len(x)                       ((int)(x).length())
#define pii                          pair<int,int>
#define vi                            vector<int>
#define vd                           vector<double>
#define vs                            vector<string>
#define mp                          map<int,int>

#define ump                         unordered_map<int,int>

#define lb                            lower_bound
#define ub                            upper_bound
#define nx                            cout<<"\n";
#define inf                           9223372036854775807
#define PI                            3.14159265

const int MOD = 1e9 + 7;

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a * b / gcd(a, b); }
inline int add(int a, int b) {    return ((a % MOD) + (b % MOD)) % MOD;}

inline int multi(int a, int b) {   return ((a % MOD) * (b % MOD)) % MOD;}

inline int sub(int a, int b) {       a %= MOD; b %= MOD; a -= b; if (a < 0) a += MOD; return a;}

inline int power(int a, int b) {       a %= MOD; int res = 1; while (b > 0) {if (b & 1) {res = multi(res, a);} a = multi(a, a); b >>= 1;}  return res;}

bool isPrime(int  x) {      if (x <= 4 || x % 2 == 0 || x % 3 == 0) {return x == 2 || x == 3;} for (int i = 5; i * i <= x; i += 6) {if (x % i == 0 || x % (i + 2) == 0) { return 0;}} return 1;}

int32_t main()
{
  fast ;


  int n, w; cin >> n >> w;
  int wt[n], val[n];
  for (int i = 0; i < n; i++)cin >> wt[i] >> val[i];
  int dp[n + 5][w + 2];
  memset(dp, 0, sizeof(dp));
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= w; j++)
    {
      dp[i][j] = dp[i - 1][j];
      if (wt[i - 1] <= j)
      {
        dp[i][j] = max(dp[i][j], val[i - 1] + dp[i - 1][j - wt[i - 1]]);
      }
    }
  }
  cout << dp[n][w];

}



Measured memory_bytes: 82304
//A
#include <bits/stdc++.h>
#define reg register

using namespace std;

typedef long long ll;
const int maxn = 100005;

inline ll read() {
    reg ll s = 0, t = 0; reg char ch = getchar();
    while (!isdigit(ch)) t |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return t ? -s : s;
}

int main() {
    reg int a = read(), b = read();
    if (a < 1 || a > 9) { puts("-1"); return 0; }
    if (b < 1 || b > 9) { puts("-1"); return 0; }
    cout << a * b << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main()
{
    int i;

    int sum = 0;
    char W[11], T[1001];

    scanf("%s", W);
    for( i = 0; W[i]; ++i ) W[i] = tolower(W[i]);
    while( 1 ){
        scanf("%s", T);
        if( strcmp("END_OF_TEXT", T) == 0 ) break;
        for( i = 0; T[i]; ++i ) T[i] = tolower(T[i]);
        if( strcmp(W, T) == 0 ) ++sum;
    }

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

    return 0;
}

Measured memory_bytes: 552
#include <stdio.h>          // putchar(), fgets()

#define MAX_L 100
const char NUL = '\0';

int
main(int argc, char **argv)
{
	char line[MAX_L + 1];
	int i;

	while (fgets(line, sizeof(line), stdin) != NULL)
	{
		const char *s = line;
		for (; *s != NUL; ++s)
		{
			if (*s == '@')
			{
				s++;
				int n = *s++ - '0';
				for (i = 0; i < n; ++i)
					putchar(*s);
			}
			else
				putchar(*s);
		}
	}

	return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using i64 = long long;

template <class T>
std::vector<T> getDivisors(T n) {
    std::vector<T> ret;
    for (i64 i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    std::sort(ret.begin(), ret.end());
    return ret;
}

int main() {
    i64 n;
    std::cin >> n;
    auto ds = getDivisors(n);
    i64 ret = 0;
    for (auto r : ds) {
        auto m = n / r - 1;
        if (r < m) ret += m;
    }
    std::cout << ret << std::endl;

    return 0;
}


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

using namespace std;

struct Posx2 {
    int sy;
    int sx;
    int ey;
    int ex;

    Posx2(int sy, int sx, int ey, int ex) 
        : sy(sy)
        , sx(sx)
        , ey(ey)
        , ex(ex){}
};

bool should_move(vector<vector<int>> &board, Posx2 &p) {
    return board[p.sy][p.sx] % 2 == 1;
}

int main(){
    int h, w;
    cin >> h >> w;

    vector<vector<int>> vs(h);
    for (auto &v : vs) {
        v.resize(w);
    }

    for (auto &v : vs) {
        for (auto &vv : v) {
            cin >> vv;
        }
    }
    vector<Posx2> moves;

    auto push = [&](Posx2 &p) {
        if (should_move(vs, p)) {
            moves.push_back(p);
            vs[p.sy][p.sx]--;
            vs[p.ey][p.ex]++;
        }
    };

    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w - 1; x++) {
            Posx2 p(y, x, y, x + 1);
            push(p);
        }
        if (y + 1 < h){
            Posx2 p(y, w - 1, y + 1, w - 1);
            push(p);
            y++;

            for (int x = w - 1; x > 0; x--) {
                Posx2 p(y, x, y, x - 1);
                push(p);
            }
            if (y + 1 < h){
                Posx2 p(y, 0, y + 1, 0);
                push(p);
            }
        }
    }

    cout << moves.size() << endl;
    for (auto &p : moves) {
        p.sy++;
        p.ey++;
        p.sx++;
        p.ex++;
        cout << p.sy << " " << p.sx << " " << p.ey << " " << p.ex << endl;
    }
}

Measured memory_bytes: 5232
#include <bits/stdc++.h>
#define INF64 1LL << 60;
#define INF32 1 << 29;

using namespace std;

void execute()
{
	int n;
	int max = -INF32;
	int min = INF32;
	int pos_max = -1, pos_min = -1;
	bool pm;
	int tmp;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		if (max < tmp)
		{
			max = tmp;
			pos_max = i;
		}
		if (tmp < min)
		{
			min = tmp;
			pos_min = i;
		}
	}

	pm = abs(min) <= abs(max);

	cout << (n * 2 - 1) << endl;
	for (int i = 0; i < n; i++)
	{
		cout << (pm ? pos_max : pos_min) + 1 << " " << i + 1 << endl;
	}
	for (int i = 0; i < n - 1; i++)
	{
		int j = pm ? i : n - 1 - i;
		cout << j + 1 << " " << j + (pm ? 1 : -1) + 1 << endl;
	}

	return;
}

int main()
{
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	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 s = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());

        if (w >= s) {
            System.out.println("unsafe");
        } else {
            System.out.println("safe");
        }

    }
}



Measured memory_bytes: 35744
n = int(input())

table = [[0 for i in range(10)] for j in range(10)]
for i in range(1, n+1):
    i = str(i)
    a, b = int(i[0]), int(i[-1])
    table[a][b] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += table[i][j] * table[j][i]

print(ans)


Measured memory_bytes: 3060
N,A,B,C,D = map(int,input().split())
a = input()
k = A
found = True
ffond = False
b = 0
c = 0
if C <D :
    while  found == True and k < D:
        if a[k] == "#":
            b += 1
        else:
            b = 0
        if b == 2:
            found = False
        k += 1
    if found == False:
        print("No")
    else:
        print("Yes")
else:
    while  found == True and k < C:
        if a[k] == "#":
            b += 1
            if k > B-3 and k <= D:
                c = 0
        else:
            b = 0
            if k > B-3 and k <=D:
                c +=1
        if b == 2:
            found = False
        if c == 3:
            ffond = True
        k += 1
    if found == False or ffond == False:
        print("No")
    else:
        print("Yes")




Measured memory_bytes: 3572
def io_tmp():
    global input
    import io
    f = io.StringIO(open(0).read())
    input = f.readline

io_tmp()


from scipy.sparse.csgraph import floyd_warshall


N, M, L = map(int, input().split())
graph = [[0] * N for _ in range(N)]
for _ in range(M):
    s, t, w = map(int, input().split())
    graph[s-1][t-1] = graph[t-1][s-1] = w
dist = floyd_warshall(graph, directed=False)
graph = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if dist[i][j] <= L:
            graph[i][j] = graph[i][j] = 1
dist = floyd_warshall(graph, directed=False)

Q = int(input())
ans = []
for _ in range(Q):
    s, t = map(int, input().split())
    d = dist[s-1][t-1]
    if d == float("inf"):
        ans.append(-1)
    else:
        ans.append(int(d - 1))
print(*ans, sep='\n')


Measured memory_bytes: 24728
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
input = sys.stdin.readline
N  = int(input())
A = [int(i) for i in input().split()]
keta = [0] * 60
for i in range(N):
    a = 0
    while A[i] != 0:
        if A[i]%2 == 1:
            keta[a] += 1
        A[i] = A[i]//2
        a +=1
ans = 0
for i in range(60):
    ans += (N-keta[i])*keta[i]*(2**i)
    ans = ans%1000000007
print(ans)


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

int main()
{
  ll n; cin>>n;
  vector<ll> s(n, 0);
  rep(i, n) cin>>s[i];
  sort(s.begin(),s.end());
  ll q; cin>>q;
  ll ans = 0;
  rep(i, q) {
    ll t; cin>>t;
    if (*lower_bound(s.begin(), s.end(), t) == t) ans++;
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3556
N = int(input())
p = list(map(float,input().split()))

dp = [[0.0]*(N+1) for i in range(N+1)]
dp[0][0] = 1.0

for i in range(1,N+1):
    for j in range(0,N+1):
        dp[i][j] = dp[i-1][j-1]*(p[i-1]) + dp[i-1][j]*(1-p[i-1])

res = 0.0
for i in range((N+1)//2,N+1):
    res += dp[-1][i]
print(res)

Measured memory_bytes: 112092
#include <iostream>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

inline int toint(string str){
	istringstream iss(str);
	int ret;
	iss >> ret;
	return ret;
}

int main(void){
	int m,n;
	while(cin >> m >> n){
		if(!(m|n)) break;
		string str;
		bool isleft[m];
		bool ended = false;
		int turn = 0;
		memset(isleft,true,sizeof(isleft));
		
		for(int i=1;i<=n;i++){
			cin >> str;
			if(ended) continue;
			if(i%5==0&&i%3==0){
				//FizzBuzz
				if(str != "FizzBuzz") isleft[turn] = false;
			}else if(i%5==0){
				//Buzz
				if(str != "Buzz") isleft[turn] = false;
			}else if(i%3==0){
				//Fizz
				if(str != "Fizz") isleft[turn] = false;
			}else{
				bool bad = false;
				for(int j=0;j<str.size();j++){
					if(!( '0' <= str[j] && str[j] <= '9')) bad = true;
				}
				if(toint(str) != i || bad) isleft[turn] = false;
				//else
			}
			int begin=turn;
			do{
				turn++;
				turn %= m;
			}while(isleft[turn] == false);
			
			int cnt=0;
			for(int j=0;j<m;j++){
				if(isleft[j]) cnt++;
			}
			if(cnt==1) ended = true;
		}
		
		vector<int> v;
		for(int i=0;i<m;i++){
			if(isleft[i]){
				v.push_back(i+1);
			}
		}
		for(int i=0;i<v.size()-1;i++){
			cout << v[i] << " ";
		}
		cout << v.back() << endl;
	}
}

Measured memory_bytes: 944
#include<stdio.h>
int main(){
  int N;
  
  scanf("%d",&N);
  
  int A[N];
  int B[N];
  int C[N-1];
  int total=0;
  
    
  
  for(int i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  for(int i=0;i<N;i++){
    scanf("%d",&B[i]);
  }
  for(int i=0;i<N-1;i++){
    scanf("%d",&C[i]);
  }
  for(int i=0;i<N;i++){
    total=total+B[i];
  }
  for(int i=0;i<N-1;i++){
    if(A[i+1]==A[i]+1){
      total=total+C[A[i]-1];
    }
  }
  
  printf("%d\n",total);
  
  
  return 0;
}



Measured memory_bytes: 128
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    int n,yes=1,no=0,four=0; cin>>n; 
    while (n--){
        int a; cin>>a;
        if (a%4==0) yes++;
        else {
            if (a&1) no++;
            else four=1;
        }
    }
    if (yes<no+four) cout << "No" << endl;
    else cout << "Yes" << endl;
    
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		a[0] = sc.nextLong();
		for(int i = 1; i < n; i++) {
			a[i] = sc.nextLong()+a[i-1];
		}
		long min = Long.MAX_VALUE;
		for(int i = 0; i < n; i++) {
			min = Math.min(min, Math.abs(a[n-1]-a[i]*2));
		}
		System.out.println(min);
	}
}


Measured memory_bytes: 61764
#include <iostream>
#include <set>
using namespace std;
typedef long long ll;
ll C[32];
ll S[366][32];
ll T[366];
ll P[32];
ll L[32];
set<int> H[32];

ll calcSum(int D) {
  ll ret = 0;
  for (int i=1; i<=D; i++) {
    ret += S[i][T[i]];
  }
  return ret;
}
ll calcPenalty(int con, int D) {
  ll ret = 0;
  ll prev = 0;
  for (auto& it: H[con]) {
    ll dif = it - prev;
    ret += (dif - 1) * dif / 2;
    prev = it;
  }
  ll dif = D + 1 - prev;
  ret += (dif - 1) * dif / 2;
  ret *= C[con];
  return ret;
}

int main() {
  ios::sync_with_stdio(false);
  int D;
  cin >> D;
  for (int i=1; i<=26; i++) {
    cin >> C[i];
  }
  for (int i=1; i<=D; i++) {
    for (int j=1; j<=26; j++) {
      cin >> S[i][j];
    }
  }
  for (int day=1; day<=D; day++) {
    ll ocon = 1;
    ll oval = S[day][ocon] + (day - L[ocon]) * C[ocon];
    for (int con=2; con<=26; con++) {
      ll val = S[day][con] + (day - L[con]) * C[con];
      if (val > oval) {
        ocon = con;
        oval = val;
      }
    }
    T[day] = ocon;
    L[ocon] = day;
    H[ocon].insert(day);
  }
  for (int day=1; day<=D; day++) {
    cout << T[day] << endl;
  }
}

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

int a, b, c;

int calc() {
  set<pair<int, int> > s;
  for(int m = 0; ; ++m) {
    pair<int, int> p(m % 60, m % (a+b));
    if(s.count(p)) break;
    s.insert(p);
    if(m % 60 == c && m % (a+b) <= a) return m;
  }
  return -1;
}

int main() {
  for(; cin >> a >> b >> c; ) {
    cout << calc() << endl;
  }
  return 0;
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int n, x;
ll a[maxn];
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

  string x,y;
  cin>>x>>y;
  int same = 0;
  for (int i=0; i<3; i++) {
    same += x[i]==y[i];
  }
  cout<<same;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Main m = new Main();
		m.run();
	}
	
	Scanner sc = new Scanner(System.in);
	
	void run(){
		int N = sc.nextInt();
		
		int prevT = 0;
		int prevX = 0;
		int prevY = 0;
		boolean mutFlag = true;
		for (int i = 0; i < N ; i++){
			int t = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			mutFlag = check(t,x,y,prevT,prevX,prevY);
			if(!mutFlag){
				break;
			}
			prevT = t;
			prevX = x;
			prevY = y;
		}
		System.out.println(mutFlag ?"Yes" :"No");
		
		
	}
	
	boolean check(int t1,int x1,int y1, int t0,int x0,int y0){
		int time = t1 - t0;
		
		int distance = Math.abs(x1 - x0) + Math.abs(y1 - y0);
		if((distance + time) % 2 == 1){
			return false;
		}
		return distance <= time;
	}
}


Measured memory_bytes: 88556
#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
	double a, l, x;
	while (cin >> a >> l >> x) {
		x = (l+x) / 2.0;
		double s1, s2;
		double M1, M2;
		s1 = (a + l*2.0) / 2.0;
		s2 = (l + x*2.0) / 2.0;
		M1 = sqrt(s1 * (s1 - a) * (s1 - l) * (s1 - l));
		M2 = sqrt(s2 * (s2 - l) * (s2 - x) * (s2 - x));
		printf("%.10f\n", M1+M2*2);
	}
	return 0;
}

Measured memory_bytes: 1240
K, N = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
A.extend([K+A[0]])
diff = []
for i in range(N):
    diff.append(A[i+1] - A[i])
sum_d = sum(sorted(diff)[:N-1])
print(sum_d)

Measured memory_bytes: 26436
#include <iostream>
#include <queue>
#include<cassert>
using namespace std;
int h;
int w;
int numb = 0;
char in[50][50];
int out[50][50] = {};
queue<int> q;

void solve(int i,int j,int truei,int truej){
    //cout << "from " << truei << " " << truej << endl;
    //cout <<"to" <<  i << " " << j << endl;
    if(i<=0 || j <= 0 || i > h || j > w){
        return;
    }
    if(out[i-1][j-1] != -1){
        return;
    }
    if(in[i-1][j-1] == '#'){
        return;
    }
    out[i-1][j-1] = out[truei-1][truej-1] +1;
    q.push(i*100 + j);
    return;
}
int main(){
    cin >> h >> w;
    numb = 0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> in[i][j];
            out[i][j] = -1;
            if(in[i][j] == '#'){
                numb ++;
            }
        }
    }
    out[0][0] = 0;
    q.push(101);
    while(!q.empty()){
        int n = q.front();
        int i = n/100;
        int j= n%100;
        solve(i,j-1,i,j);
        solve(i,j+1,i,j);
        solve(i-1,j,i,j);
        solve(i+1,j,i,j);
        q.pop();
    }
    /*for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout << out[i][j];
        }
        cout << endl;
    }*/
    int ans = w*h - out[h-1][w-1]- numb-1;
    if(out[h-1][w-1] != -1){
        cout << ans << endl;
    }
    else{
        cout << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include<cstdio>
int main(){
  int n;
  scanf("%d",&n);
  char s[n+1]={};
  scanf("%s",s);
  int r=0;
  int b=0;
  for(int i=0;i<n;i++){
    if(s[i]=='R')r++;
    else b++;
  }
  if(r>b)printf("Yes\n");
  else printf("No\n");
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll MOD=1e9+7;

ll f(pair<string,ll>&x ,pair<string,ll>&y) 
{
	if(x.first == y.first) 
	{
		return x.second>y.second;
	}
	else 
	{
		return x.first<y.first;
	}
}
 
void solve()
{
	ll n;
	cin>>n;
	vector<ll> a(n+1),pre(n+2),suf(n+2);
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		pre[i]=gcd(pre[i-1],a[i]);
	}
	ll ans=1;
	for(ll i=n;i>=1;i--)
	{
		suf[i]=gcd(suf[i+1],a[i]);
	}
	for(ll i=1;i<=n;i++)
	{
		ans=max(ans,gcd(pre[i-1],suf[i+1]));
	}
	cout<<ans;
	return;
}

int main()
{
        fast;
        ll q;
        q=1;
        // cin>>q;
        while(q--)
        	solve();
        
        return 0;
}


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

int main() {
  int n,k;cin>>n>>k;
  int cnt=0;
  for(int i=1;i<=n;i+=2)cnt++;
  if(cnt>=k)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}

Measured memory_bytes: 3592
#define _GLIBCXX_DEBUG
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<string>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep2(i,s,n) for(int i=s;i< (int)n; i++)
#define ll long long 
#define all(v) v.begin(),v.end()
using namespace std;
ll POW(int n){
  ll ans=1;
  rep(i,n){
    ans*=10;
  }
  return ans;
}
int main(){
  ll k; cin >>k;
  ll key=7;
  ll count=1;
  rep(i,k+2){
    if(key%k==0){
      cout <<count<<endl;
      return 0;
    }
    count++;
    //key+=7*POW(i+1);
    key*=10;
    key+=7;
    key=key%k;
   // if(i<30)cout <<key<<endl;
  }
  cout <<-1<<endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int N, M, n, m;
int mmax = 1000000000;

int main() {
	ios_base::sync_with_stdio(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> N >> M >> n >> m;
	if (N % n == 0 && M % m == 0) {
		cout << "No";
	} else {
		cout << "Yes\n";
		int l = 0;
		int r = mmax;
		while (r - l > 1) {
			int mid = (r + l) >> 1;
			if (1LL * mid * (n * m - 1) + 1 <= mmax) {
				l = mid;
			} else {
				r = mid;
			}
		}
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (i % n == 0 && j % m == 0) {
					cout << "-" << l * (n * m - 1) + 1 << " ";
				} else {
					cout << l << " ";
				}
			}
			cout << "\n";
		}
	}
	return 0;
}

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


def main():
    r, g, b, n = map(int, input().split())
    comb = list()
    ans = 0

    for i in range(3000 + 1):
        for j in range(3000 + 1):
            comb.append(r * i + g * j)

    for c in comb:
        if (n - c) >= 0 and (n - c) % b == 0:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 170732
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<assert.h>
#include<string>
#include<cstdlib>
#include<cctype>
#include<unordered_map>
#include<sstream>
#include<numeric>
#include<stack>
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 9e18;
constexpr int inf = 1e9;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
};
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
};

// intやllをstringに変換
template<typename T> inline string toString(const T &a){
  ostringstream oss;
  oss << a;
  return oss.str();
};
// ----------------------------------------------------------------------------
ll dp[1000005][2];
int main(){
  string S;
  cin >> S;
  for(int i=0; i<1000005; i++){
    for(int j=0; j<2; j++){
      dp[i][j] = 1e9;
    }
  }
  dp[0][0] = 0;
  reverse(S.begin(),S.end());
  S += '0';
  for(int i=0; i<S.size(); i++){
    for(int j=0; j<2; j++){
      int d = S[i] - '0';
      d += j;
      if(d < 10) chmin(dp[i+1][0],dp[i][j]+d);
      if(d > 0) chmin(dp[i+1][1],dp[i][j]+(10-d));
    }
  }
  cout << dp[S.size()][0] << endl;
  return 0;
}


Measured memory_bytes: 17028
#include <bits/stdc++.h>
using namespace std;
#define Int int64_t
#define dump(x) cout << (x) << endl
#define fi first
#define se second
Int mod = 1e9+7;
//Int mod = 998244353;
Int INF = 1e18;
double EPS = 0.00000001;

Int n, q;
vector<Int> G[200001];
Int d[200001];

int main() {
    cin >> n >> q;
    for (Int i = 0; i < n - 1; i++) {
        Int a, b;
        cin >> a >> b;
        G[a].push_back(b);
    }
    for (Int i = 0; i < q; i++) {
        Int p, x;
        cin >> p >> x;
        d[p] += x;
    }
    queue<Int> q;
    q.push(1);
    while (!q.empty()) {
        Int x = q.front();
        q.pop();
        for (Int i = 0; i < (Int)G[x].size(); i++) {
            Int to = G[x][i];
            d[to] += d[x];
            q.push(to);
        }
    }
    for (Int i = 1; i <= n; i++) cout << d[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 14848
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long A[] =new long[4];
        long a = sc.nextInt();
        long b = sc.nextInt();
        long c = sc.nextInt();
        long d = sc.nextInt();
        
        
        
        A[0]=a*c;
        A[1]=a*d;
        A[2]=b*c;
        A[3]=b*d;
        
        Arrays.sort(A);
        
        System.out.println(A[3]);
        
    }
}


Measured memory_bytes: 35788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
#define FOR(i, a, b) for(ll i=(a); i < (ll)(b); ++i)
template<class T> inline bool chmax(T& a, T b) { if(a < b){ a=b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if(a > b){ a=b; return 1; } return 0;}

ll func(ll x, ll y){
	ll a,b,c,ret;
	a = (x/3)*y;
	if(y%2==0){
		b = (x-x/3)*(y/2);
		c = b;
	}else{
		b = (x-x/3)*(y/2);
		c = (x-x/3)*(y/2+1);
	}
	ret = max(a,max(b,c)) - min(a,min(b,c));
	
	a = (x/3+1)*y;
	if(y%2==0){
		b = (x-x/3-1)*(y/2);
		c = b;
	}else{
		b = (x-x/3-1)*(y/2);
		c = (x-x/3-1)*(y/2+1);
	}
	chmin(ret,max(a,max(b,c)) - min(a,min(b,c)));
	return ret;
}

int main(){
	ll h,w;
	cin >> h >> w;
	
	if(h%3==0 || w%3==0){
		cout << 0 << endl;
		return 0;
	}
	
	ll ans;
	ans = min(h,w);
	chmin(ans, func(h,w));
	chmin(ans, func(w,h));
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3588
/*author @dhanush*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define se second
#define fi first
ll MOD = 1e9 + 7;
vector<ll>adj[100005];
ll factor[1000005];
void build(ll n)
{
  factor[1] = 1;
  for (int i = 2; i <= 1000000; i++)
  {
    factor[i] = 0;
  }
  for (ll i = 2; i <= 1000000; i++)
  {
    factor[i] += 2;
    for (ll j = i + i; j <= 1000000; j += i)
    {
      factor[j] += 1;
    }
  }
}
void icchhipadey()
{

  ll n;
  cin >> n;
  ll ans = 0;
  build(n);
  for (ll i = 1; i <= n - 1; i++)
  {
    ll xx = n - i;
    ll cnt = 0;
    // if (xx == 1)
    // {
    //   cnt = 1;
    // }
    // else
    // {
    //   cnt = 2;
    // }
    // for (ll j = 2; j * j <= xx; j++)
    // {
    //   if (xx % j == 0)
    //   {
    //     cnt++;
    //     if (xx / j != j)
    //     {
    //       cnt++;
    //     }
    //   }
    // }
    ans += factor[xx];

  }
  cout << ans << endl;

}


int main()
{


  boost;
  icchhipadey();
}









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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};


const int MOD = 1000000007;
using mint = Fp<MOD>;

int main(){
    ll N; cin>>N;
    mint res = 1;
    rep(i,N)res*=10;
    mint n = 1;
    rep(i,N)n*=9;
    n*=2;
    res -= n;
    mint e = 1;
    rep(i,N)e*=8;
    res+=e;
    cout<<res<<endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
queue<long long>q;
int k,now=0;
int main(){
	cin>>k;
	for(int i=1;i<=9;i++)
		q.push(i);
	for(int i=1;i<k;i++){
		long long tmp=q.front();
		q.pop();
		if(tmp%10!=0)
		q.push(tmp*10+tmp%10-1);
		q.push(tmp*10+tmp%10);
		if(tmp%10!=9)
		q.push(tmp*10+tmp%10+1);
	}
	cout<<q.front();
}

Measured memory_bytes: 1792
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
vector<int> al[2005];
int depth[2005];

queue<int> q;

int bfs(int i,int j){
    memset(depth,-1,sizeof(depth));
    depth[i]=0,q.push(i);
    if (j!=-1) depth[j]=0,q.push(j);
    
    int node;
    int res=0;
    while (!q.empty()){
        node=q.front(),q.pop();
        res++;
        if (depth[node]==(k>>1)) continue;
        for (auto &it:al[node]){
            if (depth[it]==-1){
                depth[it]=depth[node]+1;
                q.push(it);
            }
        }
    }
    
    return res;
}
int main(){
    scanf("%d%d",&n,&k);
    int a,b;
    for (int x=1;x<n;x++){
        scanf("%d%d",&a,&b);
        al[a].push_back(b);
        al[b].push_back(a);
    }
    
    int ans=0;
    if (k&1){
        for (int x=1;x<=n;x++){
            for (auto &it:al[x]){
                ans=max(ans,bfs(x,it));
            }
        }
    }
    else{
        for (int x=1;x<=n;x++){
            ans=max(ans,bfs(x,-1));
        }
    }
    
    printf("%d\n",n-ans);
}

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



// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    int ary[5];
    rep(i,5) cin >> ary[i];
    cout << (ary[2] - ary[0]) * 60 + (ary[3] - ary[1]) - ary[4] << endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
int main()
{
 
    int h,n;
    cin>>h>>n;
    int arr[n],w[n];
    vector<int> ans(h+2,INF);
    for(int i=0;i<n;i++)
        cin>>arr[i]>>w[i];
        ans[0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=h;j++)
        {
            int k=min(h,j+arr[i]);
            ans[k]=min(ans[k],ans[j]+w[i]);
        }
    }
   cout<<ans[h];
}

Measured memory_bytes: 256
def main():
  import sys
  input = sys.stdin.readline
  n=input()
  a=tuple(map(int,input().split()))
  cnt=[0]*(max(a)+3)
  for i in a:
    cnt[i]+= 1
  x,y,z=cnt,cnt[1:],cnt[2:]
  print(max(map(sum,zip(x,y,z))))  
if __name__=='__main__':
  main()

Measured memory_bytes: 14004
#pragma GCC optimize("O3")
        #pragma comment(linker, "/stack:200000000")
        #pragma GCC optimize("unroll-loops")
         
        #include <algorithm>
        #include <bitset>
        #include <cassert>
        #include <chrono>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <functional>
        #include <iomanip>
        #include <iostream>
        #include <iterator>
        #include <limits>
        #include <climits>
        #include <list>
        #include <map>
        #include <numeric>
        #include <queue>
        #include <random>
        #include <ratio>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <string>
        #include <unordered_map>
        #include <unordered_set>
        #include <utility>
        #include <vector>
        using namespace std;
         
        typedef long long ll;
        typedef long double LD;
        #define int ll
        #define double LD
        #define pb push_back
        #define mp make_pair
        #define REP(i,n) for (int i = 0; i < n; i++)
        #define loop(i,n) for (int i = 0; i < n; i++)
        #define FOR(i,a,b) for (int i = a; i < b; i++)
        #define REPD(i,n) for (int i = n-1; i >= 0; i--)
        #define FORD(i,a,b) for (int i = a; i >= b; i--)
        #define remax(a,b) a = max(a,b)
        #define remin(a,b) a = min(a,b)
        #define mem(a, b) memset(a, b, sizeof a)
        #define append push_back
        #define all(v) v.begin(),v.end()
        #define F first
        #define S second
        #define print(x) cout << (x) << endl
        #define PRECISION(x) cout << fixed << setprecision(x)
        #define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
        #define N 300010
        #define pb push_back
        const double PI=acos(-1);
        const int MOD = 1000000007;
        const int FMOD = 998244353;
        const double eps = 1e-9;
         
        mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
        
        signed main()
        {
        	int n;
        	cin>>n;
        	
        	int a[n];
        	int sum=0;
        
        	loop(i,n)
        	cin>>a[i];
        	
        	int xo=0;
        	loop(i,n)
        	{
        		xo = xo^a[i];
			}
        	loop(i,n)
        	cout<<(xo^a[i])<<" ";
		}

Measured memory_bytes: 5152
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long 
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld",n)
#define pri(n) printf("%d",n)
#define pln() printf("\n")
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define pb push_back     
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN
const int mod=1e9+7;         
const int N=2e5+4;

ll f(int x)
{
	return 1LL*x*(x+1)/2;
}

int main()
{
	int n,k; scn(n); scn(k);

	ll ans=0;

	if(k==0)
	{
		lpri(1LL*n*n); return 0;
	}

	rep(i,k+1,n+1)
	{
		ll here=0;

		//(i-1)+x*i<=n
		int x=(n-(i-1))/i;

		ll cnt=(i-1)-k+1;

		here=(cnt*(x+1));

		int left = n - (x+1)*i;

		if(left>=k)
		here+=(left-k+1);

		ans+=here; //cout<<i<<" "<<here<<endl;
	}

	lpri(ans);

	return 0;
}



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

const int MOD = (int)1e9+7;

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

	if((A<C && C<B) || (B<C && C<A))	cout << "Yes" << endl;
	else	cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
#define rer(i,l,n) for(int i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pii;

int main(){
	while(1){
		int d[3]={},n,r;
		rep(i,0,3) cin>>d[i];
		if(d[0]==0&&d[1]==0&&d[2]==0) break;
		sort(d,d+3);
		double l;
		l=pow(d[0]*d[0]+d[1]*d[1],0.5)*0.5;
		cin>>n;
		rep(i,0,n){
			cin>>r;
			o((l<r?"OK":"NA"));
		}
	}
}

Measured memory_bytes: 1208
fun main(args: Array<String>) {
    // Your code here!
    var s = readLine()!!
    var msg = "No"
    var len = s.length
    var num1 = (len-1)/2
    var num2 = ((len+3)/2) -1
    
    
    if(s.substring(0,num1) == s.substring(num2,len)){
        msg = "Yes"
    }
    
    print(msg)
    
}



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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
 return x;

}

Node treeSearch(Node u, int k){
  if(u==NIL || k == u->key){
    return u;
  }
  if(k<u->key){
    return treeSearch(u->left,k);
  }
  else return treeSearch(u->right,k);
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL){
    return treeMinimum(x->right);
  }
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z->left==NIL || z->right== NIL){
    y = z;
  }
  else y = treeSuccessor(z);

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

  if(x!=NIL){
    x->parent= y->parent;
  }
  if(y->parent==NIL){
    root=x;
  }
  else if(y == y->parent->left){
    y->parent->left = x;
  }
  else y->parent->right = x;

  if(y != z){
    z->key = y->key;
  }
}

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

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

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

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


int main(){
  int n, i, x;
  Node a;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
  return 0;
}



Measured memory_bytes: 20452
#include<bits/stdc++.h>
using namespace std;
int c[200005];
vector<long long> G[200005];
long long path_num[200005];
long long ch_num[200005];
long long n;
long long ans;
long long dfs(long long u,long long v){
	long long pre = ch_num[c[u]];
	long long cnt_ch_num = 1;
	long long update = ch_num[c[u]];
	for(auto i:G[u]){
		if(i!=v){
			long long cntt = dfs(i,u);
			cnt_ch_num += cntt;
			long long delta = ch_num[c[u]] - update;
			long long k = cntt - delta;
			path_num[c[u]] += (k+1)*k/2;
			update = ch_num[c[u]];
		}
	}
	
	
	ch_num[c[u]] = pre + cnt_ch_num;
	return cnt_ch_num;
}
int main(){
	//freopen("in.txt","r",stdin);
	cin>>n;
	for(long long i=0;i<n;i++) {
		cin>>c[i];
		c[i]--;
	}
	
	long long t1,t2;
	for(long long i=0;i<n-1;i++){
		cin>>t1>>t2;
		t1--;t2--;
		G[t1].push_back(t2);
		G[t2].push_back(t1);
	}
	
	dfs(0,-1);
	for(long long i=0;i<n;i++){
		
			long long k=n-ch_num[i];
			ans = (n+1)*n/2 - path_num[i] - (k+1)*k/2;
		
		cout<<ans<<endl;
	}
	return 0;
}

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

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

  if (A==B && A!=C){
    cout << "Yes" << endl;
  }
  else if (A==C && A!=B){
    cout << "Yes" << endl;
  }
  else if (C==B && A!=C){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}
  

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

int main(void) {
    int x, y, z, k;
    vector<long long> a, b, c;
    vector<long long> dp;
    vector<long long> rank;
    cin >> x >> y >> z >> k;
    for (int j = 0; j < x; j++) {
        long long e;
        cin >> e;
        a.push_back(e);
    }
    for (int j = 0; j < y; j++) {
        long long e;
        cin >> e;
        b.push_back(e);
    }
    for (int j = 0; j < z; j++) {
        long long e;
        cin >> e;
        c.push_back(e);
    }
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            dp.push_back(a[i] + b[j]);
        }
    }
    sort(c.begin(), c.end());
    reverse(c.begin(), c.end());
    sort(dp.begin(), dp.end());
    reverse(dp.begin(), dp.end());
    for (int i = 0; i < k && i < z; i++) {
        for (int j = 0; j < k && j < x * y; j++) {
            rank.push_back(c[i] + dp[j]);
        }
    }
    sort(rank.begin(), rank.end());
    reverse(rank.begin(), rank.end());
    for (int i = 0; i < k; i++) {
        cout << rank[i] << "\n";
    }
}


Measured memory_bytes: 43256
input()
s = [i for i in input()]
cnt = 0
j = 0
for i in range(len(s)-1):
    if j == 1:
        j = 0
    elif s[i]+s[i+1] == 'OX' or s[i]+s[i+1] == 'XO':
        cnt += 1
        j = 1
print(cnt)


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

#define ll  long long
#define mp  make_pair
#define pb  push_back
#define fi  first
#define se  second
#define mod 1000000007
#define pi  2.0*acos(0.0)

int n, a, b;

int main() {
    cin >> n >> a >> b;

    bool turn = true;
    while(true) {
        if (turn) {
            if (b > a) {
                if (a + 1 == b) {
                    if (a - 1 == 0) {
                        cout << "Borys" << endl;
                        return 0;
                    }
                    else a -= 1;
                }
                else a += 1;
            }
            else {
                if (a - 1 == b) {
                    if (a + 1 == n + 1) {
                        cout << "Borys" << endl;
                        return 0;
                    }
                    else a += 1;
                }
                else a -= 1;
            }
        }
        else {
            if (a > b) {
                if (b + 1 == a) {
                    if (b - 1 == 0) {
                        cout << "Alice" << endl;
                        return 0;
                    }
                    else b -= 1;
                }
                else b += 1;
            }
            else {
                if (b - 1 == a) {
                    if (b + 1 == n + 1) {
                        cout << "Alice" << endl;
                        return 0;
                    }
                    else b += 1;
                }
                else b -= 1;
            }
        }

        if (turn) turn = false;
        else turn = true;
    }
}


Measured memory_bytes: 256
ip = list(map(int,input().split()))
a = ip[0]
b = ip[1]
c = ip[2]
xy = []
xy.append(ip[3])
xy.append(ip[4])

ans = (a+b+c)*max(xy)
for k in range(max(xy)+1):
	aa = xy[0] - k
	bb = xy[1] - k
	cc = 2*k
	if aa < 0:
		aa = 0
	if bb < 0:
		bb = 0
	tmp = aa*a + bb*b + cc*c
	if tmp < ans:
		ans = tmp

print(ans)


Measured memory_bytes: 3064
import java.util.Scanner;
import java.util.Arrays;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int a[] = new int[10];
		int i;
 
		Scanner cin = new Scanner(System.in);
		for (i = 0; i < 10; i++){
			a[i] = cin.nextInt();
		}
 
		Arrays.sort(a);
 
		for (i = 9; i > 6; i--){
			System.out.println(a[i]);
		}
	}
}

Measured memory_bytes: 26136
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,x,y) for(int i=(x);i<(y);i++)

struct S {
	bool flag;
	bool turnend;
	int id;
	char dir;

	S()
	{

	}

	S(bool f)
	{
		flag = f;
		turnend = false;
	}
};

int main()
{
	while (true) {
		int n, l;

		cin >> n >> l;

		if (n == 0 && l == 0) {
			break;
		}

		vector<vector<S>> tunnel(l + 1, vector<S>(4, S(false)));

		rep(i, 0, n) {
			char d;
			int p;

			cin >> d >> p;

			tunnel[p][0].flag = true;
			tunnel[p][0].id = i + 1;
			tunnel[p][0].dir = d;
		}

		int turn = 0;

		while (n != 0) {
			turn++;

			rep(i, 0, l + 1) {
				rep(j, 0, 4) {
					tunnel[i][j].turnend = false;
				}
			}

			//?§????
			rep(i, 1, l) {
				rep(j, 0, 4) {
					if (tunnel[i][j].flag == false) {
						continue;
					}

					if (tunnel[i][j].turnend == true) {
						continue;
					}

					if (tunnel[i][j].dir == 'R') {
						if (tunnel[i + 1][0].flag == false) {
							swap(tunnel[i][j], tunnel[i + 1][0]);
							tunnel[i + 1][0].turnend = true;
						}
						else if (tunnel[i + 1][1].flag == false) {
							swap(tunnel[i][j], tunnel[i + 1][1]);
							tunnel[i + 1][1].turnend = true;
						}
						else if (tunnel[i + 1][2].flag == false) {
							swap(tunnel[i][j], tunnel[i + 1][2]);
							tunnel[i + 1][2].turnend = true;
						}
						else {
							swap(tunnel[i][j], tunnel[i + 1][3]);
							tunnel[i + 1][3].turnend = true;
						}
					}
					else {
						if (tunnel[i - 1][0].flag == false) {
							swap(tunnel[i][j], tunnel[i - 1][0]);
							tunnel[i - 1][0].turnend = true;
						}
						else if (tunnel[i - 1][1].flag == false) {
							swap(tunnel[i][j], tunnel[i - 1][1]);
							tunnel[i - 1][1].turnend = true;
						}
						else if (tunnel[i - 1][2].flag == false) {
							swap(tunnel[i][j], tunnel[i - 1][2]);
							tunnel[i - 1][2].turnend = true;
						}
						else {
							swap(tunnel[i][j], tunnel[i - 1][3]);
							tunnel[i - 1][3].turnend = true;
						}
					}
				}
			}

			//????????¢???
			rep(i, 1, l) {
				rep(j, 0, 4) {
					if (tunnel[i][j].flag == true) {
						rep(k, j + 1, 4) {
							if (tunnel[i][k].flag == true) {
								swap(tunnel[i][j].dir, tunnel[i][k].dir);
							}
						}
					}
				}
			}

			//??´?????????????\´??????????????????
			if (tunnel[l][0].flag == true) {
				if (n == 1) {
					cout << turn << " " << tunnel[l][0].id << endl;
				}
				tunnel[l][0].flag = false;
				n--;
			}

			if (tunnel[0][0].flag == true) {
				if (n == 1) {
					cout << turn << " " << tunnel[0][0].id << endl;
				}
				tunnel[0][0].flag = false;
				n--;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 3084