akhauriyash/Code-Regression huggingface dataset:
import scala.io.StdIn

object Main {

  def main(args: Array[String]): Unit = {

    val n = StdIn.readLine().toInt
    val vs = StdIn.readLine().split(' ').toVector.map(_.toDouble).sorted
    assert(!vs.isEmpty)
    val ans = vs.tail.foldLeft(vs.head)((acc, v) => (acc + v) / 2)
    println(ans)

  }

}


Measured memory_bytes: 25416
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[3005],s;
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		s+=a[i];
	}
	s-=n;
	cout<<s<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e3+5;
int N,T;
int dp1[maxn][maxn],dp2[maxn][maxn];
int a[maxn],b[maxn];
int main()
{
	cin>>N>>T;
	for(int i=1;i<=N;i++)
	{
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<=T;j++)
		dp1[i][j]=dp1[i-1][j];
		for(int j=a[i];j<=T;j++)
		dp1[i][j]=max(dp1[i][j],dp1[i-1][j-a[i]]+b[i]);
	}
	for(int i=N;i>=1;i--)
	{
		for(int j=0;j<=T;j++)
		dp2[i][j]=dp2[i+1][j];
		for(int j=a[i];j<=T;j++)
		dp2[i][j]=max(dp2[i][j],dp2[i+1][j-a[i]]+b[i]);	
	}	
	int ans=0;
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<T;j++)
		ans=max(ans,dp1[i-1][j]+dp2[i+1][T-1-j]+b[i]);
	}
	cout<<ans;
}

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

int  main()
{
	int x; cin >> x;
	if (x == 3 || x == 5 || x == 7) printf("YES\n");
	else printf("NO\n");
	return (0);
}

Measured memory_bytes: 256
/*siddharth goyal*/
#include<bits/stdc++.h>
using namespace std;
#define   pb              push_back
#define   REP(i,n)        for(i=1;i<=n;i++)
#define   FOR(i,a,b)      for(i=a;i<=b;i++)
#define   all(v)          v.begin(),v.end()
#define   F               first
#define   S               second
#define   vl              vector<LL>
#define   itr             ::iterator it
#define   lb              lower_bound
#define   ub              upper_bound
#define   LL              long long
#define   ULL             unsigned long long
#define   ret             return 
LL n,i,j,m;
vl V ; 
LL a[1000000] ; 
LL sticks[10] = {0,2,5,5,4,5,6,3,7,6} ;
LL dp[1000000],digits[1000000] ;  
int main()
{   // Read the constraints,highlights,Time Limit,Test Cases
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m ;
    REP(i,m) cin>>a[i] ;  
    sort(a+1,a+1+m) ;
    REP(i,m)
    { if(dp[sticks[a[i]]]<a[i])    
        dp[sticks[a[i]]] = a[i],digits[sticks[a[i]]] = 1 ; 
    }
     
    REP(i,m)
    {  LL x = sticks[a[i]] ; 
       for(j=x;j<=n;j++)
       {  if(dp[j-x]==0) continue ; 
          if(digits[j]<1+digits[j-x])
          {  digits[j] = 1 + digits[j-x] ;
             dp[j] = a[i] ; 
          }
          else if(digits[j]==1+digits[j-x] and dp[j]<a[i]) 
          {  dp[j] = a[i] ;  
          }

       }
    }
    
    j = n ; 
    while(V.size()<digits[n])
    {  V.pb(dp[j]) ; 
       j = j - sticks[V.back()] ; 
    } 
    sort(all(V)) ; 
    for(i=V.size()-1;i>=0;i--) 
    { cout<<V[i] ;
      LL f = 0  ; 
      REP(j,m) if(V[i]==a[j]) f++ ; 
      assert(f>0) ; 
    } 
    cout<<endl ; 
}
//Check for 0,1 and other corner cases.

Measured memory_bytes: 4608
#include <iostream>
#include <cmath>
#include <vector>

int main(){
   int N;
   std::cin >> N;

   std::vector<int> v = {3, 5, 7};
   for(int i=0; i<v.size(); ++i){
      int n = v[i];
      for(int j=3; j<=7; j+=2){
	 v.push_back(n*10 + j);
      }
      if(v[v.size()-1]>N) break;
   }

   int count = 0;
   for(int i=0; i<v.size(); ++i){
      if(v[i]>N) continue;
      bool flag[3] = {false, false, false};
      int n = v[i];
      for(int j=0; j<10; ++j){
	 if(n%10==3) flag[0] = true;
	 else if(n%10==5) flag[1] = true;
	 else if(n%10==7) flag[2] = true;
	 n /= 10;
      }
      if(flag[0] && flag[1] && flag[2]) ++count;
   }
   std::cout << count << std::endl;
   return 0;
}


Measured memory_bytes: 704
import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean b = false;
		for(int i = 1 ; i < 10 ; i++) {
			for(int j = i ; j < 10 ; j++) {
				if(i * j == n)
					b = true;
			}
		}

		sc.close();
		System.out.println(b ? "Yes" : "No");

	}
}



Measured memory_bytes: 35664
from sys import stdin

input=[int(x) for x in stdin.readline().rstrip().split()]
N=input[0]
M=input[1]

order_list=[]
for m in range(M):
    order_list.append([int(x) for x in stdin.readline().rstrip().split()])

order_list.sort(key=lambda x: x[1])

a=0
b=0
output=0
for i in order_list:
    a=i[0]
    if a>=b:
        output+=1
        b=i[1]
print(output)

Measured memory_bytes: 22812
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
	public static void main(String args[]){
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			while(true){
				String strs[] = br.readLine().split(" ");
				int n = Integer.parseInt(strs[0]);
				int h = Integer.parseInt(strs[1]);
				if(n == 0) return;
				
				boolean xy[][] = new boolean[n][n];
				boolean xz[][] = new boolean[n][n];
				boolean yz[][] = new boolean[n][n];
				int answer = n * n * n;
				
				for(int i = 0; i < h; i++){
					strs = br.readLine().split(" ");
					int arg1 = Integer.parseInt(strs[1]) - 1;
					int arg2 = Integer.parseInt(strs[2]) - 1;
					if(strs[0].equals("xy")){
						// xy
						xy[arg1][arg2] = true;
						for(int j = 0; j < n; j++){
							if(xz[arg1][j]) continue;
							if(yz[arg2][j]) continue;
							answer--;
						}
					}else if(strs[0].equals("xz")){
						// xz
						xz[arg1][arg2] = true;
						for(int j = 0; j < n; j++){
							if(xy[arg1][j]) continue;
							if(yz[j][arg2]) continue;
							answer--;
						}
					}else{
						// yz
						yz[arg1][arg2] = true;
						for(int j = 0; j < n; j++){
							if(xy[j][arg1]) continue;
							if(xz[j][arg2]) continue;
							answer--;
						}
					}
				}
				System.out.println(answer);
			}
		} catch (Exception e) {
		}
	}
}

Measured memory_bytes: 34392
import sys
N, Y = map(int, input().split())

for x in range(N+1):
  for y in range(N+1):
    z = N-(x+y)
    if 10000*x + 5000*y + 1000*z == Y and z >= 0:
      print(x,y,z)
      sys.exit()

print(-1,-1,-1)

Measured memory_bytes: 3060
n = int(input())
s = input()

if n % 2 == 1:
    print("No")
else:
    c = int(n/2)
    s_1 = s[:c]
    s_2 = s[c:n]

    if s_1 != s_2:
        print("No")
    else:
        print("Yes")

Measured memory_bytes: 2940
// Code by ajcxsu
// Geometry template

#include<bits/stdc++.h>
#define EPS (1e-9)
using namespace std;

struct Point {
    double x,y;
    Point(double x=0,double y=0):x(x), y(y) {}

    Point operator +(Point p) { return Point(x+p.x,y+p.y); }
    Point operator -(Point p) { return Point(x-p.x,y-p.y); } // 加减
    Point operator *(double a) { return Point(x*a,y*a); }
    Point operator /(double a) { return Point(x/a,y/a); } // 数乘

    double norm() { return x*x+y*y; } // 范数
    double abs() { return sqrt(norm()); } // 大小

    bool operator < (const Point &p) { return x!=p.x?x<p.x:y<p.y; }
    bool operator == (const Point &p) { return fabs(p.x-x) < EPS && fabs(p.y-y) < EPS; }
} ;
typedef Point Vector;

double dot(const Point &a, const Point &b) {
    return a.x*b.x+a.y*b.y;
} // 内积
double cross(const Point &a, const Point &b) {
    return a.x*b.y-a.y*b.x;
} // 外积
bool equals(double a, double b) { return fabs(a-b)<EPS; } // 误差相等

struct Line {
    Point p1,p2;
} ;
typedef Line Seg;

/* 1 正交 2 平行 0 其他 */
int PO(Vector a, Vector b) {
    if(equals(dot(a,b), 0)) return 1;
    else if(equals(cross(a,b), 0)) return 2;
    else return 0;
}
int PO(Line a, Line b) { // 正交、平行判定
    return PO(a.p2-a.p1, b.p2-b.p1);
}

istream& operator >>(istream &in, Vector &a) {
    in>>a.x>>a.y;
    return in;
}
istream& operator >>(istream &in, Line &a) {
    in>>a.p1>>a.p2;
    return in;
} // 输入重载

Point project(Point a, Seg b) {
    Vector base=b.p2-b.p1;
    Vector hypo=a-b.p1;
    return b.p1+base*(dot(base, hypo)/ base.norm());
} // 投影

Point ref(Point a, Seg b) {
    Vector base=project(a,b)-a;
    return a+base*2;
} // 映像

int ccw(Vector a, Vector b) {
    if(cross(a,b)>EPS) return 1; // Counter clockwise
    else if(cross(a,b)<-EPS) return -1; // Clockwise
    else if(dot(a,b)<-EPS) return 2; // Online back
    else if(a.norm()<b.norm()) return -2; // Online front
    else return 0; // On segement
} // 判断顺时针逆时针
int ccw(Point p0, Point p1, Point p2) {
    return ccw(p1-p0, p2-p0);
}

bool intersect(Point p1, Point p2, Point p3, Point p4) {
    if( ccw(p1,p2,p3)*ccw(p1,p2,p4) <= 0 &&
        ccw(p3,p4,p1)*ccw(p3,p4,p2) <= 0) return 1;
    return 0;
}
bool intersect(Seg a, Seg b) {
    return intersect(a.p1, a.p2, b.p1, b.p2);
} // 判断线段是否相交

Point crossp(Seg a, Seg b) {
    Vector base=b.p2-b.p1, hypo=a.p1-b.p1, hypo2=a.p2-b.p1;
    double h1=fabs(cross(base,hypo))/base.abs();
    double h2=fabs(cross(base,hypo2))/base.abs();
    double t=h1/(h1+h2);
    return a.p1+(a.p2-a.p1)*t;
}


ostream& operator <<(ostream &out, Vector a) {
    out<<a.x<<' '<<a.y;
    return out;
} // 输出重载

int main() {
    cout.setf(ios::fixed);
    cout<<setprecision(10); // 设置输出精度

    int q;
    cin>>q;
    while(q--) {
        Seg a,b;
        cin>>a>>b;
        cout<<crossp(a,b)<<endl;
    }
    return 0;
}



Measured memory_bytes: 3284
(defun main ()
  (let ((x (read))
	(ans))
    (cond ((and (<= 400 x) (>= 599 x)) (setf ans 8))
	  ((and (<= 600 x) (>= 799 x)) (setf ans 7))
	  ((and (<= 800 x) (>= 999 x)) (setf ans 6))
	  ((and (<= 1000 x) (>= 1199 x)) (setf ans 5))
	  ((and (<= 1200 x) (>= 1399 x)) (setf ans 4))
	  ((and (<= 1400 x) (>= 1599 x)) (setf ans 3))
	  ((and (<= 1600 x) (>= 1799 x)) (setf ans 2))
	  (t (setf ans 1)))
    (format t "~a~%" ans)))
(main)

Measured memory_bytes: 24384
<?php

// define('DEBUG', true);
define('DEBUG', false);

define('MOD', 1000000007);

fscanf(STDIN, "%d", $N);
fscanf(STDIN, "%s", $S1);
fscanf(STDIN, "%s", $S2);

$arS1 = str_split($S1);
$arS2 = str_split($S2);
$ans = 1;

for ($i = 0; $i < $N; $i++) {
    if ($arS1[$i] != $arS2[$i]) {
        $type = "y";
        $i++;
        if ($prev == "") {
            $ans *= 6;
        } else if ($prev == "y") {
            $ans *= 3;
        } else if ($prev == "t") {
            $ans *= 2;
        }
    } else {
        $type = "t";
        if ($prev == "") {
            $ans *= 3;
        } else if ($prev == "y") {
            $ans *= 1;
        } else if ($prev == "t") {
            $ans *= 2;
        }
    }
    $prev = $type;
    $ans %= MOD;
}

echo $ans . PHP_EOL;


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

using namespace std;

int main(){
	int h, w, n;
	cin >> h >> w >> n;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	int t = 1;
	vector<vector<int>> ans(h, vector<int>(w));
	for(int i = 0; i < h; i++){
		if(i % 2 == 0){
			for(int j = 0; j < w; j++){
				if(a[t]){
					ans[i][j] = t;
				}else{
					t++;
					ans[i][j] = t;
				}
				a[t]--;
			}
		}else{
			for(int j = w - 1; j >= 0; j--){
				if(a[t]){
					ans[i][j] = t;
				}else{
					t++;
					ans[i][j] = t;
				}
				a[t]--;
			}
		}
	}
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++)
		{
			cout << ans[i][j];
			if(j < w - 1) cout << " ";
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <cmath>
#define inf 1<<30
#define maxn 1000010
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define ll long long
inline void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
ll a,b,len=0;
int main(){
	read(a);read(b);ll b1=b;
	while(b1){
		len++;
		b1/=10;
	}
	for(ll i=1;i<=len;i++)a*=10;
	ll c=a+b;
	for(ll i=1;i*i<=c;i++){
		if(i*i==c){
			printf("Yes");
			return 0;
		}
	}
	printf("No");
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 1000000000000000000
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;

int main() {
    int N;
    cin >> N;
    int cnt = 0;
    rep(i, N) {
        int a;
        cin >> a;
        if ((i + 1) % 2 == 1 && a % 2 == 1)
            cnt++;
    }

    cout << cnt << endl;
}

Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> W(N);
  int M = 0;
  for(int i = 0; i < N; ++i){
    cin >> W[i];
    M += W[i];
  }
  int s = 0, ans = M;
  for(int i = 0; i < N; ++i){
    s += W[i];
    ans = min(ans,abs(M-2*s));
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    string s;
    cin >> s;
    map<string, int> mp;
    mp["SUN"] = 0;
    mp["MON"] = 1;
    mp["TUE"] = 2;
    mp["WED"] = 3;
    mp["THU"] = 4;
    mp["FRI"] = 5;
    mp["SAT"] = 6;
    int ans;
    ans = 7 - mp[s];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  unsigned long long ary[35] = {0};
  int n; 
  ary[0] = 1; 
  ary[1] = 1;
  ary[2] = 2;
  loop(i,3,35){
    ary[i] = ary[i-1] + ary[i-2] + ary[i-3];
    //  cout<<i<<" "<<ary[i]<<" "<<ary[i]/365<<endl;
  }

 
  while(cin>>n,n){
    cout<<ary[n]/3650+(ary[n]%3650?1:0)<<endl;
  }
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
typedef vector<LL> V;
const LL inf=1e9;
int main(){
    int R,C,r,c;
    cin>>R>>C>>r>>c;
    vector<V> v(R,V(C,0));
    for(int i=0;i<R;i+=r)for(int j=0;j<C;j+=c)v[i][j]=inf-1;
    for(int i=r-1;i<R;i+=r)for(int j=c-1;j<C;j+=c)v[i][j]=-inf;


    LL sum=0;
    REP(i,R)REP(j,C)sum+=v[i][j];
    if(sum<=0){cout<<"No"<<endl;return 0;}
    else{
        cout<<"Yes"<<endl;
        REP(i,R){

            REP(j,C)cout<<v[i][j]<<" ";
            cout<<endl;

        }

    }
    return 0;
}


Measured memory_bytes: 4864
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int a = num / 1000;
        num = num - a * 1000;
        int b = num / 100;
        num = num - b * 100;
        int c = num / 10;
        int d = num % 10;
        int sum = a;
        for(int i = 0; i < 2; i++) {
            if(i == 0) sum += b;
            else sum -= b;
            for(int j = 0; j < 2; j++) {
                int temp1 = sum;
                if(j == 0) sum += c;
                else sum -= c;
                for(int k = 0; k < 2; k++) {
                    int temp2 = sum;
                    if(k == 0) sum += d;
                    else sum -= d;
                    if(sum == 7) {
                        System.out.println(a + toString(i) + b + toString(j) + c + toString(k) + d + "=7");
                        return;
                    }
                    sum = temp2;
                }
                sum = temp1;
            }
            sum = a;
        }
        return;
    }
    private static String toString(int n) {
        if(n == 0) return "+";
        else return "-";
    }
}


Measured memory_bytes: 23764
N, Y = map(int,input().split())

ans = [-1,-1,-1]

for x in range(N+1) :
    for y in range(N+1-x) :
        calc = x*10000 + y*5000 + (N-x-y)*1000        
        if calc == Y :
            ans = [x,y,N-x-y]
            break

print(*ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

struct node {
	ll to, index;
};

int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);
	ll n, x; cin >> n >> x;
	vl a(n); REP(i, n) cin >> a[i];
	vvl mis(n, vl(n));
	REP(i, n) {
		ll prev = i;
		ll next = (prev - 1 + n) % n;
		ll cnt = 1;
		mis[i][0] = a[i];
		while (next != i) {
			mis[i][cnt] = min(mis[i][cnt-1], a[next]);
			prev = next;
			next = (prev - 1 + n) % n;
			cnt++;
		}
	}

	ll ans = TEN(18) + 3;
	REP(i, n) { // 回して見る回数
		ll val = x * i;
		REP(j, n) val += mis[j][i];
		ans = min(ans, val);
	}

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

Measured memory_bytes: 31616
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static int buf[20],len; len=0;
	if(x<0)x=-x,putchar('-');
	for(;x;x/=10)buf[len++]=x%10;
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]+'0');
}
inline void writeln(ll x){write(x); putchar('\n');}
inline void writesp(ll x){write(x); putchar(' ');}
int m,d;
int main()
{
	m=read(); d=read();
	int cnt=0;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=d;j++)
			if((j%10)>1&&(j/10)>1&&(j%10)*(j/10)==i)++cnt;
	writeln(cnt);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;

struct point{
    double x, y;
};

void koch(int n, point p1, point p2){
    if(n == 0) return;
    
    point s, t, u;
    double pai = M_PI * 60.0 / 180.0;
    
    s.x = (p2.x-p1.x)/3.0 + p1.x;
    s.y = (p2.y-p1.y)/3.0 + p1.y;
    t.x = (p2.x-p1.x)*2.0/3.0 + p1.x;
    t.y = (p2.y-p1.y)*2.0/3.0 + p1.y;
    u.x = (t.x - s.x)*cos(pai) - (t.y - s.y)*sin(pai) + s.x;
    u.y = (t.x - s.x)*sin(pai) + (t.y - s.y)*cos(pai) + s.y;
    
    koch(n - 1, p1, s);
    printf("%f %f\n", s.x, s.y);
    koch(n - 1, s, u);
    printf("%f %f\n", u.x, u.y);
    koch(n - 1, u, t);
    printf("%f %f\n", t.x, t.y);
    koch(n - 1, t, p2);
}



int main(){
    int n;
    scanf("%d", &n);
    
    point a, b;
    a.x = 0;
    a.y = 0;
    b.x = 100;
    b.y = 0;
    
    printf("%f %f\n", a.x, a.y);
    koch(n, a, b);
    printf("%f %f\n", b.x, b.y);
    
    return 0;
    
}



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

int main() {
  ll n,k,q;
  cin>>n>>k>>q;
  vector<ll> a(q);
  rep(i,q) cin>>a[i];
  vector<ll> pt(n,k-q);
  rep(i,q){
    pt[a[i]-1]++;
  }
  rep(i,n){
    //cout<<pt[i]<<endl;
    if(pt[i]>0){
      cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl; 
    }
  }
}



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

int main(){
  int i, x[10000], count = 1;
  
  for(i = 0; i < 10000; i++){
    cin >> x[i];
    if(x == 0) break;
  }
  for(i = 0; i < 10000; i++){
    if(x[i] != 0){
      cout << "Case " << count << ": " << x[i] << endl;
      count++;
    }
    else break;
  }
}
  
  

Measured memory_bytes: 1196
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    my_putchar_unlocked(c[i]);
  }
}
int N;
int D[100][2];
int ok[100];
int main(){
  int i;
  rd(N);
  {
    int Lj4PdHRW;
    int KL2GvlyY;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      for(KL2GvlyY=(0);KL2GvlyY<(2);KL2GvlyY++){
        rd(D[Lj4PdHRW][KL2GvlyY]);
      }
    }
  }
  for(i=(0);i<(N);i++){
    if(D[i][0]==D[i][1]){
      ok[i] =1;
    }
    else{
      ok[i] =0;
    }
  }
  for(i=(2);i<(N);i++){
    if(ok[i-2] && ok[i-1] && ok[i]){
      wt_L("Yes");
      wt_L('\n');
      return 0;
    }
  }
  wt_L("No");
  wt_L('\n');
  return 0;
}
// cLay varsion 20200916-1

// --- original code ---
// int N, D[100][2];
// int ok[100];
// {
//   rd(N,D(N,2));
//   rep(i,N) ok[i] = if[D[i][0]==D[i][1], 1, 0];
//   rep(i,2,N) if(ok[i-2] && ok[i-1] && ok[i]) wt("Yes"), return 0;
//   wt("No");
// }


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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define popcnt __builtin_popcount
#define getBit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
// ---------------------------------

void Main() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto &i : a) cin >> i;
  sort(all(a));
  int v = (a.back() + 1) / 2;
  int l = 0, r = n - 1, al = 0;
  while (l <= r) {
    int m = (l + r) / 2;
    if (a[m] <= v) {
      l = m + 1;
      al = m;
    }
    else r = m - 1;
  }
  l = 0, r = n - 1; int ar = 0;
  while (l <= r) {
    int m = (l + r) / 2;
    if (a[m] >= v) {
      r = m - 1;
      ar = m;
    }
    else l = m + 1;
  }
  if (abs(v - a[al]) <= abs(v - a[ar])) {
    cout << a.back() << ' ' << a[al] << '\n';
  }
  else {
    cout << a.back() << ' ' << a[ar] << '\n';
  }
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  cerr << "- ---- -- ----- <3\n";
#endif
  cin.tie(0)->sync_with_stdio(0);
  int T = 1;
  // cin >> T;
  while (T--) Main();
}


Measured memory_bytes: 3964
#include <cstdio>
using namespace std;
int main(){
    int h, m, s;
    while(1){
        scanf("%d %d %d", &h, &m, &s);
        if( h+m+s < 0 ) return 0;
        int left = 7200 - h*3600 - m*60 - s;
        printf("%02d:%02d:%02d\n%02d:%02d:%02d\n",
                left/3600, (left/60)%60, left%60,
                left/1200, (left/20)%60, left*3%60);
    }
    return 0;
}

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

typedef long long ll;

ll N, M;
vector<ll> A;
ll Base, Skip, DSkip;
vector<ll> XSkip, XDSkip;
ll R = 1ll << 60;

int main() {
  cin >> N >> M;
  for (ll i = 0; i < N; ++i) {
    ll a;
    cin >> a;
    --a;
    A.push_back(a);
  }
  for (ll i = 0; i < N - 1; ++i) {
    ll d = A[i + 1] - A[i];
    if (d < 0) d += M;
    Base += d;
    if (A[i] > A[i + 1]) {
      Skip += M - A[i] - 1;
      ++DSkip;
    }
  }
  XSkip.resize(M);
  XDSkip.resize(M);
  for (ll i = 0; i < N - 1; ++i) {
    ll d = A[i + 1] - A[i];
    if (d < 0) d += M;
    XSkip[A[i + 1]] += d - 1 + 1;
  }
  ++XDSkip[A[0]];
  --XDSkip[A[N - 1]];
  for (ll x = 0; x < M; ++x) {
    R = min(R, Base - Skip);
    Skip += DSkip;
    Skip -= XSkip[x];
    DSkip += XDSkip[x];
  }
  cout << R << endl;
  return 0;
}


Measured memory_bytes: 2676
N = int(input())
A = list(map(int,input().split()))
Adic = {}

for i in range(N):
  if str(A[i]) in Adic.keys():
    Adic[str(A[i])] += 1
  else:
    Adic[str(A[i])] = 1
else:
  countDic = {}
  count = 0
  for j in Adic.keys():
    comb = Adic[j] * (Adic[j] - 1) // 2
    count += comb
    countDic[j] = comb
  else:
    for i in A:
      print(count - countDic[str(i)] + ((Adic[str(i)] - 1) * (Adic[str(i)] - 2) // 2))

Measured memory_bytes: 38600
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    cin >> p[i];
    if (i + 1 != p[i]) {
      cnt += 1;
    }
  }
  if (cnt <= 2) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int main(){
    ll n;
    cin>>n;
    string s={};
    while(n){
        n--;
        s.push_back(char(n%26+'a'));
        n/=26;
    }
    reverse(all(s));
    cout<<s<<"\n";
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
int M = 1e9+7;

ll f(int N, int W, vector<int> &v, vector<int> &w, vector<vector<ll> > &dp) {
	if(N < 0 || W <= 0) return 0;
	if(dp[N][W] != -1) return dp[N][W];
	if(W - w[N] >= 0) dp[N][W] = max(f(N - 1, W - w[N], v, w, dp) + v[N], f(N - 1, W, v, w, dp));
	else dp[N][W] = f(N - 1, W, v, w, dp);
	return dp[N][W];
}

 
int main() {
   
    //Fast IO crap
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, W;
    cin >> N >> W;

    vector<int> v(N), w(N);

    for(int i = 0; i < N; i++) cin >> w[i] >> v[i];
	
	vector<vector<ll> > dp(N, vector<ll>(W + 1, -1));

	cout << f(N - 1, W, v, w, dp);
   
    return 0;
}


Measured memory_bytes: 79488
import sys
from itertools import combinations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    L = list(map(int, input().split()))

    res = 0
    for a, b, c in combinations(L, 3):
        if a == b or b == c or c == a:
            continue
        if a + b > c and b + c > a and c + a > b:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9192
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int n,k;
    cin >> n >> k;
    int h[n];
    for(int i=0;i<n;i++){
        cin >> h[i];
    }
    sort(h,h+n);
    long long minh=100000000000;
    for(int i=0;i<n-k+1;i++){
        long long d=h[i+k-1]-h[i];
        minh=min(minh,d);
    }
    cout << minh << endl;
}


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

int main() {
 double W,H,x,y;
 cin >> W >> H >> x >> y;
 cout << W * H / 2 << endl;
 if(x == W / 2 && y == H / 2){
   cout << 1 << endl;
 }
 else{
     cout << 0 << endl;
   }
 
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define in inline
#define cs const 
#define fr first 
#define se second
#define ls (now<<1)
#define rs (now<<1|1)
#define mid ((l+r)>>1)
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define low(i) (i&(-i))
#define par pair<int,int>
#define cn(x) memset(x, 0, sizeof(x))
#define rep(i, x, y) for(int i=x; i<=y; ++i)
#define sep(i, x, y) for(int i=x; i>=y; --i)
#define fore(i, x) for(int i=fir[x]; i; i=nex[i])
cs int G = 3;
cs int ff = 2e5 + 15;
cs int inf = 1e18 + 1;
cs int base = 4;
cs int M = 998244353;
cs int p = 1e18 + 7;

struct Node { int b, s, ban; } q[ff], q2[36];
bool operator < (Node x, Node y) { return x.b < y.b; }

void Add(int &x, int y) { x = ((x + y % M) % M + M) % M; }
void Del(int &x, int y) { x = ((x - y % M) % M + M) % M; }
void Mul(int &x, int y) { x = ((x * y % M) % M + M) % M; }

int x, y;
void init()
{
	cin >> x >> y;
	int nw = x, s = 1;
	while(nw <= y) nw = nw * 2, s ++;
	cout << s - 1;
}
signed main()
{
//	freopen("mentor.in", "r", stdin);
//	freopen("mentor.out", "w", stdout);
	int Ts = 1; 
//	cin >> Ts;
	while(Ts --)
		init();
}


/*
2
2 1
3 2 2 2
1 1
1 2
1
1 0
4 2
10 30 20 30
1 6
2 4
1 7
2 4
2
2 3
3 1
*/

/*
1
22
*/

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define REP(i, m, n) for(int i = m; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define dup(x, y) (((x) + (y)-1) / (y)) //整数型のまま切り上げ演算する
#define PI 3.14159265359
typedef long long LL;
template <class T> inline void chmax(T &a, T b) {
    if(a < b) {
        a = b;
    }
}
template <class T> inline void chmin(T &a, T b) {
    if(a > b) {
        a = b;
    }
}
template <class T> inline T gcd(T x, T y) {
    if(y == 0) {
        return x;
    } else if(x == 0) {
        return y;
    }
    return gcd(y, x % y);
}
template <class T> inline T lcm(T x, T y) { return (x * y) / gcd(x, y); }
template <class T> inline void print_vector(vector<T> vec) {
    for(int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << endl;
}
const LL MOD = 1e9 + 7;
const LL LLINF = 1LL << 60;
const int INF = 1 << 30;

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

    vector<int> X(N);
    rep(i, N) cin >> X[i];

    set<int> meeting_place;
    meeting_place.insert(accumulate(ALL(X), 0) / N);
    meeting_place.insert(dup(accumulate(ALL(X), 0), N));

    int ans = INF;
    for(int P : meeting_place) {
        int tmp = 0;
        rep(i, N) tmp += (X[i] - P) * (X[i] - P);
        chmin(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <memory>
#include <memory.h>
#include <cmath>
#include <fstream>
#include <cmath>
#include <numeric>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <cstdio>
#include <map>
#include <iomanip>
#include <list>
#include <cctype>
#include <algorithm>
#include <complex>
#define USE_MATH_DEFINES
using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<int, PP> PPP;
const int INF = 1 << 29;
const double EPS = 1E-10;

namespace std{
	bool operator < (const xy_t &a, const xy_t &b){
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}

double cross(const xy_t &a, const xy_t &b){
	return imag(conj(a) * b);
}

double dot(const xy_t &a, const xy_t &b){
	return real(conj(a)*b);
}

int ccw(xy_t a, xy_t b, xy_t c){
	b -= a; c -= a;
	if(cross(b, c) > 0) return 1;
	if(cross(b, c) < 0) return -1;
	if(dot(b, c) < 0) return +2;
	if(norm(b) < norm(c) ) return -2;
	return 0;
}

bool intersectSS(const line &s, const line &t){
	return ccw(s.first, s.second, t.first) * ccw(s.first, s.second, t.second) <= 0 &&
		ccw(t.first, t.second, s.first) * ccw(t.first, t.second, s.second) <= 0;
}

xy_t crosspoint(const line &l, const line &m){
	double a = cross(l.second - l.first, m.second - m.first);
	double b = cross(l.second - l.first, l.second - m.first);
	if(abs(a) < EPS && abs(b) < EPS) return m.first;
	if(abs(a) < EPS) assert(false);
	return m.first + b / a * (m.second - m.first);
}


int main(){
	int h, w;
	char field[502][502];
	int upper[600];
	int next[600];
	while(cin >> h >> w && (h || w)){
		fill(&field[0][0], &field[501][501] + 1, '*');
		for(int i = 1; i <= h; i++){
			for(int j = 1; j <= w; j++){
				cin >> field[i][j];
			}
		}
		int ans = 0;
		upper[0] = h + 2;
		fill(next, next + 600, 0);
		for(int i = 1; i <= h; i++){
			for(int j = 1; j <= w; j++){
				if(field[i][j] == '*') upper[j] = h + 2;
				else if(field[i-1][j] == '*'){ 
					upper[j] = i - 1;
				}

				if(upper[j-1] > upper[j]){
					next[j] = j - 1;
				}else if(field[i][j] != '*'){
					int p = j-1;
					while(upper[p] <= upper[j]){
						p = next[p];
					}
					next[j] = p;
				}else{
					next[j] = 0;
				}
				int a = upper[j];
				int b = next[j];
				while(a < i){
					ans = max(ans, (i - a) * (j - b));
					a = upper[b];
					b = next[b];
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1116
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
char a[55][55],b[55][55];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			cin>>b[i][j];
		}
	}
	bool ans=false;
	for(int i=0;i<=n-m;i++){
		for(int j=0;j<=n-m;j++){
			bool ok=true;
			for(int f=0;f<m;f++){
				for(int g=0;g<m;g++){
					if(a[f+i][g+j]!=b[f][g])ok=false;
				}
			}
			if(ok){
				ans=true;
				break;
			}
		}
	}
	cout<<(ans?"Yes":"No")<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int n,l,r,s=0;
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		if(a<l||r<=a)s++;
	}
	cout<<s<<"\n";
	return 0;
} 

Measured memory_bytes: 256
import sys
import os
if sys.platform=="darwin":
   base = os.path.dirname(os.path.abspath(__file__))
   name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
   #print(name)
   sys.stdin = open(name)

h,w = map(int, input().split())
l = [str(input()) for _ in range(h)]

#print(l)
ans = 0
for i in range(h):
   ans = ans + l[i].count(".")

#print(ans)

if ans == (h-1)*(w-1):
   print("Possible")
else:
   print("Impossible")


Measured memory_bytes: 38512
//Abhinav ---IIIT_A
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define f(i,x,n) for(int i=x;i<(int)n;++i)
#define vpii vector<pair<int,int>> 
ld pie=3.141592653589793238462643383279;
int mod=1e9+7;
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};


int dig(int a){
  int r=0;
  while(a!=0){
    int xp=a%10;
    a/=10; if(xp==1) ++r;
  }
  return r;
}

int sp(int a){
  int s=0;
  int ano=a-1;
  while(a!=0){
    s+=a%10;
    a/=10;
  }
  while(ano!=0){
    s+=ano%10;
    ano/=10;
  }
  return s;
}

int fun(int a){
  int r=1;
  f(i,0,10) r*=a;
  return r;
}

void q1(){
  int n,b,q; cin>>n>>b>>q;
  int a[n];  f(i,0,n) a[i]=i/b;
  int curr=-1;
  int load=0;
  while(q--){
    int x; cin>>x;
    if(a[x]!=curr){
      curr=a[x];
      load++;
    }
  }
  cout<<load<<"\n";
}
void q2(){
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    int a[2*n+5];
    f(i,0,2*n) cin>>a[i];
    int o=0,e=0;
    vector<int> odd,even;
    f(i,0,2*n) if(a[i]%2==1) {
      ++o; odd.pb(i+1);
    }
    else {
      ++e; even.pb(i+1);
    }
    vpii vt;
    if(o&1){
      for(int i=0;i<odd.size()-1;i+=2)
        vt.pb({odd[i],odd[i+1]});
      for(int i=0;i<even.size()-1;i+=2)
        vt.pb({even[i],even[i+1]});
    }else{
      if(o>0){
        for(int i=2;i<odd.size();i+=2)
        vt.pb({odd[i],odd[i+1]});
      for(int i=0;i<even.size();i+=2)
        vt.pb({even[i],even[i+1]});
      }else{
          for(int i=2;i<even.size();i+=2)
        vt.pb({even[i],even[i+1]});
      }
    }
    for(auto it : vt) cout<<it.ff<<" "<<it.ss<<"\n";
  }
}
void q3(){
  int t; cin>>t;
  vector<int> xx;
  int pr[100005]={0};
  f(i,2,100005) if(pr[i]==0){
    if(i&1){
      xx.pb(i); for(int j=2*i;j<100005;j+=i) pr[j]=i;
   }
  }
  while(t--){
    int n; cin>>n;
    if(n==1) cout<<"FastestFinger\n";
    else if (n&1) cout<<"Ashishgup\n";
    else{
      int curr=0;
      while(n!=1){
        if(n&1){
          ++curr;
          break;
        }
        int mx=-1;
        for(auto it : xx) if(n%it==0) mx=it;
        if(mx==-1){
          if(n==2){
            break;
          }else{
            ++curr;
            break;
          }
        }else{
          n/=mx;
          curr++;
        }
      }
      if(curr%2==0) cout<<"Ashishgup\n";
      else cout<<"FastestFinger\n";
    }
  }
}
int32_t main(){
#ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n; cin>>n;
  int fre[100005]={0};
  int s=0;
  f(i,0,n){
    int x; cin>>x; fre[x]++;
    s+=x;
  }
  int q; cin>>q;
  while(q--){
    int b,c; cin>>b>>c;
    s-=fre[b]*b;
    s+=fre[b]*c;
    fre[c]+=fre[b];
    fre[b]=0;
    cout<<s<<"\n";
  }
  return 0;
}


Measured memory_bytes: 4404
N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  u, v, w = map(int, input().split())
  edge[u-1].add((v-1, w))
  edge[v-1].add((u-1, w))

dist = [0] * N
stack = [0]
while stack:
  vrt = stack.pop()
  for to, w in edge[vrt].copy():
    stack.append(to)
    dist[to] = dist[vrt] + w
    edge[vrt].discard((to, w))
    edge[to].discard((vrt, w))

for i in range(N):
  print(dist[i] % 2)

Measured memory_bytes: 53664
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var sc *bufio.Scanner

const BufferSize = 1024

func nextInt() int {
	if !sc.Scan() {
		panic(nil)
	}
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

var production bool

func debugf(format string, v ...interface{}) {
	if !production {
		fmt.Printf(format, v...)
	}
}

func min(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res > a[i] {
			res = a[i]
		}
	}
	return res
}

func answer(reader io.Reader, writer io.Writer) {
	sc = bufio.NewScanner(reader)
	buf := make([]byte, BufferSize)
	sc.Buffer(buf, 1e+6)
	sc.Split(bufio.ScanWords)
	n := nextInt()
	s := make([]int, n+1)
	for i := 1; i < n; i++ {
		s[i] = nextInt()
	}
	s[0] = s[1]
	s[n] = s[n-1]

	ans := 0
	for i := 0; i < n; i++ {
		ans += min(s[i], s[i+1])

	}

	_, _ = fmt.Fprintf(writer, "%d", ans)
}

func main() {
	production = true
	answer(os.Stdin, os.Stdout)
}


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

int main()
{
	double a, b, c, d;
	const double pi = 3.141592653589793;

	cin >> a >> b >> c >> d;

	while (a != -1 || b != -1 || c!= -1 || d != -1) {
		double u[3], v[3];

		u[0] = cos(b * pi / 180) * cos(a * pi / 180);
		u[1] = sin(b * pi / 180) * cos(a * pi / 180);
		u[2] = sin(a * pi / 180);

		v[0] = cos(d * pi / 180) * cos(c * pi / 180);
		v[1] = sin(d * pi / 180) * cos(c * pi / 180);
		v[2] = sin(c * pi / 180);

		cout << round(acos(u[0] * v[0] + u[1] * v[1] + u[2] * v[2]) * 6378.1) << endl;
		
		cin >> a >> b >> c >> d;
	}

	return 0;
}



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

int main() {
    int n;
    float m;
    cin >> n >> m;
    vector<int> a(n);
    float sum = 0;
    rep(i,n) {
        cin >> a[i];
        sum+=a[i];
    }

    ll ans = 0;
    rep(i,n) {
        if(a[i]<(sum/(4*m))) continue;
        else ans++;
    }
    if(ans>=m) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> V(N);
    vector<ll> hand(N);
    REP(i, N) cin >> V[i];
    int num = min(N, K);
    ll res = 0;
    for (int j = 0; j <= num; j++){
        for (int i = 0; i <= j; i++){
            int A = i;
            int B = j - i;
            int drop = K - j;
            hand.clear();
            while(A > 0){
                hand.push_back(V[A-1]);
                A--;
            }
            while (B > 0)
            {
                hand.push_back(V[N-B]);
                B--;
            }
            sort(hand.begin(), hand.end());
            REP(i, drop){
                if (hand[i] < 0){
                    hand[i] = 0;
                }
            }
            ll tmp = accumulate(hand.begin(), hand.end(), 0);
            res = max(res, tmp);
        }
    }
    cout << res << endl;
    
    return 0;
}

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

using namespace std;


int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    if(a>b){
        int tem=a;
        a=b;
        b=tem;
    }
    int num[b],k=0;
    for(int i=1;i<=b;i++)
    {
        if(a%i==0&&b%i==0)num[k++]=i;
    }
    cout<<num[k-c]<<endl;
    return 0;
}





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

using namespace std;

long powmod(long base, long exp, long mod){
    base %= mod;
    long result = 1;
    while (exp > 0){
        if(exp & 1){
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

long mod_combination(long N, long A, long M){
    A = min(A, N - A);
    long child = 1;
    for(long k = N; k > (N - A); k--){
        child = (child * k) % M;
    }

    long mother = 1;
    for(long k = 1; k <= A; k++){
        mother = (mother * k) % M;
    }
    long fermat = powmod(mother, M - 2, M);
    return (child * fermat) % M;
}

int main() {
    long N, A, B;
    long M = 1000000000 + 7;
    cin >> N >> A >> B;

    long a, b;
    a = mod_combination(N, A, M);
    b = mod_combination(N, B, M);
    long ans = powmod(2, N, M) - a - b - 1;
    while (ans < 0){
        ans += M;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

S = input()
N = len(S)

dp = [[0] * 13 for i in range(N)]
str_int = '0123456789'
if S[0] in str_int:
    dp[0][int(S[0])] += 1
else:
    for i in range(10):
        dp[0][i] += 1

for i in range(1, N):
    if S[i] in str_int:
        # 前の段
        for j in range(13):
            dp[i][(10 * j + int(S[i])) % 13] += (dp[i - 1][j] % mod)
    else:
        # 前の段
        for j in range(13):
            # 後ろの段
            # ?なら0 ~ 10で回す
            for l in range(10):
                dp[i][(10 * j + l) % 13] += (dp[i - 1][j] % mod)

print(dp[N - 1][5] % mod)

Measured memory_bytes: 99976
def main():
  num = list(map(int,input().split()))
  if num[0]+num[1]>num[0]+num[2]:
    if num[0]+num[2]>num[1]+num[2]:
      print(num[1]+num[2])
    else:
      print(num[0]+num[2])
  else:
    if num[0]+num[1]>num[1]+num[2]:
      print(num[1]+num[2])
    else:
      print(num[0]+num[1])
    
main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  long a, b, ans;
  cin >> a;
  for(int i = 0; i < N - 1; i++) {
    cin >> b;
    a /= __gcd(a,b);
    ans = a * b;
    a = ans;
  }
  cout << a << endl;
  return 0;
}


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

using namespace std;

#define mp make_pair
#define pb push_back
#define llong long long
#define ullong unsigned llong
#define fn fill_n
typedef pair<int, int> P;
int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};

int a, b, c, d;
int A[10000], B[10000], C[10000];
string s, t, r;


int main(){
	cin >> a >> b;
	cout << a + (a>b?-1:0) << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    //Scanner sc=new Scanner(System.in);
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	    int t=1;
	   // t=sc.nextInt();
	    //int t=Integer.parseInt(br.readLine());
	    while(--t>=0){
	      //  int n=sc.nextInt();
	         //     int n=Integer.parseInt(br.readLine());
	         //      int k=sc.nextInt();
	              String s=br.readLine();
	              long sum=0;
	           //  int n=s.length();
	         //     StringTokenizer st=new StringTokenizer(br.readLine());
	         //      int n=Integer.parseInt(st.nextToken());
	          for(int i=0;i<s.length();i++){
	               int  ch=s.charAt(i)-'0';
	              sum=sum+(long)ch;
	          }
	        if(sum%9==0)
	        System.out.println("Yes");
	        else
	        System.out.println("No");
	     
	        
	    }
	    
	}
}

Measured memory_bytes: 36044
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int x, a, b;
    cin >> x >> a >> b;
    if(a - b >= 0)
        cout << "delicious" << endl;
    else if(a + x - b >= 0)
        cout << "safe" << endl;
    else
        cout << "dangerous" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#define ri register int
#define rc register char
#define ll long long int
#define rl register long long int
#define in inline
#define gc getchar
in int read()
{
	ri x=0,p=1;
	rc ch=gc();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
		{
			p=-1;
		}
		ch=gc();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0',ch=gc();
	}
	return x*p;
}
int n,m;
int main()
{
	n=read(),m=read(),printf("%d\n",n*(n-1)/2+m*(m-1)/2);
	return 0;
}

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

int N;
vector<int> a(100010, 0);
bitset<100010> bit;

int main(void){
	
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i) scanf("%d", &a[i]);
	
	int corrent = 1, sum = 0;
	while(corrent != 2){
	    bit[corrent] = true;
	    corrent = a[corrent];
	    ++sum;
	    if(bit[corrent]){
	        printf("-1\n");
	        return 0;
	    }
	}
	printf("%d\n", sum);
	
    return 0;
}


Measured memory_bytes: 640