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

using namespace std;
using ll = long long;

int main(){
	ios_base::sync_with_stdio(false);
	int n, a, b;
	cin >> n >> a >> b;
	vector<int> x(n);
	for(int i = 0; i < n; ++i){ cin >> x[i]; }
	ll answer = 0;
	for(int i = 1; i < n; ++i){
		const ll d = x[i] - x[i - 1];
		answer += min<ll>(a * d, b);
	}
	cout << answer << endl;
	return 0;
}



Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		BigDecimal n = BigDecimal.valueOf(100);
		BigDecimal a = BigDecimal.valueOf(Long.parseLong(sc.next()));
		BigDecimal b = BigDecimal.valueOf(1.01);
		int count = 0;
		while (n.compareTo(a) < 0) {
			n = n.multiply(b);
			n = n.setScale(0, BigDecimal.ROUND_FLOOR);
			count++;
		}
		System.out.println(count);

	}

	static class FastScanner {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public FastScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			tokenizer = null;
		}

		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public String nextLine() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					return reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}

			return tokenizer.nextToken("\n");
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
	}
}

Measured memory_bytes: 33920
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;

int main(){
    ll n, y;
    cin >> n >> y;
    ll ans = 0;
    for(ll i = 0; i < n + 1; i++){
        for(ll j = 0; j < n - i + 1; j++){
            ll k = n - i - j;
            if((i * 10000) + (j * 5000) + (k * 1000) == y){
                cout << i << ' ' << j << ' ' << k << endl;
                return 0;
            }
        }
    }

    cout << "-1 -1 -1" << endl;
}
  

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

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

        cout << a+b << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <string>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int finishTime(VEC(int)& times)
{
    int time = 0;
    FOR(i, 0, times.size()) {
        int order = time;
        while (order % 10 != 0)
            order++;
        time = order + times[i];
    }

    return time;
}

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    VEC(int) times(5);
    READVEC(times);
    sort(ALL(times));

    int ret = 10000000;
    do {
        ret = min(ret, finishTime(times));
    } while (next_permutation(ALL(times)));

    cout << ret << endl;
    return 0;
};


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int
	var s string
	fmt.Scan(&n)
	fmt.Scan(&s)
	// 文字列を一文字ずつ扱う
	if s[:n/2] == s[n/2:] {
		fmt.Println("Yes")
		return
	} 
	fmt.Println("No")
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
// typedef long double ldouble;

using Graph = vector<vector<int>>;

// int ctoi(const char c){
//   if('0' <= c && c <= '9') return (c-'0');
//   return -1;
// }

// int gcd(int a, int b){
//   int ma = max(a,b);
//   int mi = min(a,b);
//   if(mi == 0) return ma;

//   return gcd(mi, ma%mi);
// }

// llong POW(llong a, llong b){
//   if(b == 0) return 1;
//   else{
//     if(b%2 == 0) return POW(a * a % MOD, b / 2) % MOD;
//     else return a * POW(a * a % MOD, b / 2) % MOD;
//   }
// }

int main(){
  int N;
  cin >> N;
  if(N < 1000) cout << "ABC" << endl;
  else cout << "ABD" << endl;
}

Measured memory_bytes: 256
def triangle?(a, b, c)
  a <= b + c && b <= c + a && c <= a + b
end

def valid?(a, b, c)
  triangle?(a, b, c) || triangle?(a + 1, b, c)
end

def calc(rear, front, west, east, north, south, best)
  path = ''
  loop do
    a = rear + front
    b = west + east
    c = north + south

    return path if a + b + c == 0

    if east > 0 && valid?(b - 1, c, a)
      rear, front, west, east = east - 1, west, rear, front
      y = 'E'
    elsif north > 0 && valid?(c - 1, a, b)
      rear, front, north, south = north - 1, south, front, rear
      y = 'N'
    elsif south > 0 && valid?(c - 1, a, b)
      rear, front, north, south = south - 1, north, rear, front
      y = 'S'
    elsif west > 0 && valid?(b - 1, c, a)
      rear, front, west, east = west - 1, east, front, rear
      y = 'W'
    else
      throw 'error'
    end
    
    if best
      x = best[path.size]
      return best if x < y
      best = nil if x > y
    end
    path << y  
  end
end

def find(target)
  best = nil
  target.permutation(6).to_a.uniq.each do |rear, front, west, east, north, south|
    a = rear + front
    b = west + east
    c = north + south
    if valid?(a, b, c)
      best = calc(rear, front, west, east, north, south, best)
    end
  end
  best
end

loop do
  target = STDIN.gets.split.map!(&:to_i)
  break if target.max == 0
  p, q = STDIN.gets.split.map!(&:to_i)
  result = find(target)
  puts result ? result[p-1...q] : 'impossible'
end

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

using namespace std;

int main() {
    string n; cin >> n;
    for (int i = 0; i < 3; i++) {
        if (n[i] == '1') n[i] = '9';
        else n[i] = '1';
    }
    cout << n << endl;
    return 0;
}


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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	int_fast64_t l0 = 2ll, l1 = 1ll, l2;

	if (N == 1) { cout << l1;  return 0; }
	else if (N == 0) { cout << l1;  return 0; }
	
	for (int i = 2; i <= N; ++i) {
		l2 = l1 + l0;
		l0 = l1;
		l1 = l2;
	}
	cout << l2;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i = 0; i < n; i++) cin >> h[i];
  int ans = 0;
  while(true){
    int idx = 0;
    for(int i = 0; i < n; i++){
      if(h[idx] < h[i]) idx = i;
    }
    if(h[idx] == 0) break;
    for(int i = idx+1; i < n; i++){
      if(h[i] != h[idx]) break;
      h[i]--;
    }
    h[idx]--;
    ans++;
  }
  cout  << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
	int y,x;
	cin >> y >> x;
	string s[y];
	for (int i = 0; i < y; ++i)
	{
		cin >> s[i];
	}
	for (int i = 0; i < x + 2; ++i)
	{
		cout << "#";
	}
	cout << endl;
	for (int i = 0; i < y; ++i)
	{
		cout << "#" << s[i] << "#" << endl;
	}
		for (int i = 0; i < x + 2; ++i)
	{
		cout << "#";
	}
	cout << endl;

}

Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_variables)]

fn main() {
    let N: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let A: Vec<usize> = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    };
    let B: Vec<i64> = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    };
    let C: Vec<i64> = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    };

    let (ans, _) = (0..N).fold((0, N), |(res, prev), i|
        if A[i] == prev + 1 { (res + B[A[i] - 1] + C[A[i] - 2], A[i]) }
        else { (res + B[A[i] - 1], A[i]) }
    );

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
using namespace std;

int main()
{
    string W, W_;
    int m,h;
    cin>> W;
    while(W!="-"){
        cin >> m;
        
        for(int i = 0; i <m; i++){
            cin >> h;
            W = W.substr(h,W.length()+1)+ W.substr(0,h);
            // cout << W << endl;
        }
        cout << W << "\n";
        cin>> W;
    }
    return 0;
}


Measured memory_bytes: 3148
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        while(true)
        {
        int n = sc.nextInt();

        if(n==0) break;

        int score[] = new int[n];
        for(int i=0; i<n; i++) score[i] = sc.nextInt();

        double mean = 0;
        double bunnsann = 0;
        double ans;

        //mean
        for (int i = 0; i < n; i++) mean += (double) score[i];
        mean /= n;

        //bunnsann
        for (int i = 0; i < n; i++) bunnsann += Math.pow((double) (score[i] - mean), 2.0);
        bunnsann /= n;

        //ans
        ans = Math.sqrt(bunnsann);

        System.out.printf("%.8f\n",ans);
        }
        sc.close();
    }
}


Measured memory_bytes: 31632
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl; cout << "       ";
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}

int main(){
	int N;
	cin >> N;
	vector<ll> A(N);
	int num_minus = 0;
	for(int i=0; i<N; i++){
		ll a;
		cin >> a;
		if(a<0){
			num_minus++;
			a *= -1;
		}
		A[i] = a;
	}
	
	sort(A.rbegin(), A.rend());
	ll ans = 0;
	for(int i=0; i<N; i++) ans += A[i];
	if(num_minus % 2 ==1) ans -= 2*A.back();
	cout << ans << endl;
	
	return 0;
}



Measured memory_bytes: 4052
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define REPR(i,n) for(ll i=n-1;i>=0;i--)

typedef long long ll;
#define INF 1e18

int main(){
	ll n; cin>>n;
	ll sum=0;
	FOR(i,1,n+1){
		if(i%3!=0 && i%5!=0){
			sum+=i;
		}
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 3636
#include<stdio.h>
#include<string.h>

int main(){
	
	char kartuA[105];
	char kartuB[105];
	char kartuC[105];
	
	strcpy(kartuA, "");
	strcpy(kartuB, "");
	strcpy(kartuC, "");
	
	scanf("%s", kartuA);
	scanf("%s", kartuB);
	scanf("%s", kartuC);
	
	int lenA = strlen(kartuA);
	int lenB = strlen(kartuB);
	int lenC = strlen(kartuC);
	
	int A[105];
	int B[105];
	int C[105];
	
	for(int i = 0; i<lenA; i++){
		if(kartuA[i] == 'a'){
			A[i] = 1;
		} 
		else if(kartuA[i] == 'b'){
			A[i] = 2;
		}
		else if(kartuA[i] == 'c'){
			A[i] = 3;
		}
	}
	
	for(int i = 0; i<lenB; i++){
		if(kartuB[i] == 'a'){
			B[i] = 1;
		} 
		else if(kartuB[i] == 'b'){
			B[i] = 2;
		}
		else if(kartuB[i] == 'c'){
			B[i] = 3;
		}
	}
	
	for(int i = 0; i<lenC; i++){
		if(kartuC[i] == 'a'){
			C[i] = 1;
		} 
		else if(kartuC[i] == 'b'){
			C[i] = 2;
		}
		else if(kartuC[i] == 'c'){
			C[i] = 3;
		}
	}
	
	
//	for(int i = 0; i<lenA; i++){
//		printf("%d", A[i]);
//	}
//	puts("");
//	
//	for(int i = 0; i<lenB; i++){
//		printf("%d", B[i]);
//	}
//	puts("");
//	
//	for(int i = 0; i<lenC; i++){
//		printf("%d", C[i]);
//	}
//	puts("");
	
	int idxA = 0;
	int idxB = 0;
	int idxC = 0;
	int first = 1;
	int nextPlayer = 1;
	
	int winA = 0;
	int winB = 0;
	int winC = 0;
	
	while(winA == 0 && winB == 0 && winC == 0){
//		if(idxA >= lenA && nextPlayer == 1){
//			winA = 1;
//			break;
//		}
//		else if(idxB >= lenB && nextPlayer == 2){
//			winB = 1;
//			break;
//		}
//		else if(idxC >= lenC && nextPlayer == 3){
//			winC = 1;
//			break;
//		}
		if(nextPlayer == 1){
			if(idxA >= lenA){
				winA = 1;
				break;
			}
			else{
//				puts(" lol A");
				nextPlayer = A[idxA];
				idxA++;
			}
		}
		else if(nextPlayer == 2){
			if(idxB >= lenB){
				winB = 1;
				break;
			}
			else{
//				puts(" lol B");
				nextPlayer = B[idxB];
				idxB++;
			}
		}
		else if(nextPlayer == 3){
			if(idxC >= lenC){
				winC = 1;
				break;
			}
			else{
//				puts(" lol ");
				nextPlayer = C[idxC];
				idxC++;
			}
		}
	}
	
	if(winA == 1){
		puts("A");
	}
	else if(winB == 1){
		puts("B");
	}
	else if(winC == 1){
		puts("C");
	}
	
	return 0;
}

Measured memory_bytes: 128
while 1:
    n = int(input())
    if n == 0:
        break

    data = []
    for _ in range(n):
        s, p, q, r = map(int, input().split())
        data.append([s, p, q, r])

    P, Q, R, C = map(int, input().split())

    flag = False
    for d in data:
        cal = d[1] * 4 + d[2] * 9 + d[3] * 4
        if d[1] <= P and d[2] <= Q and d[3] <= R and cal <= C:
            flag = True
            print(d[0])

    if not flag:
        print("NA")


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

#define N 200005

int n, s, l, x, y, ans;
vector <int> v[N];
bool u[N];

void dfs(int q){
    u[q] = 1;
    if (l > ans) ans = l, s = q;
    for (auto it: v[q])
        if (!u[it]) l++, dfs(it), l--;
}

int main(){
    cin >> n;
    for (int i=1; i<n; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    for (int i=1; i<=n; i++) u[i] = 0;
    dfs(s);
    cout << ((ans + 2) % 3 ? "First" : "Second");
    return 0;
}


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

s = input()
t = input()
answer = 0
for start_i in range(len(s)-len(t)+1):
  compared_s = s[start_i:]
  index = 0
  matched_count = 0
  for t_s in t:
    if t_s == compared_s[index]:
      matched_count += 1
    index += 1
  if answer < matched_count:
    answer = matched_count

print(len(t)-answer)

Measured memory_bytes: 9128
/*Bismillahir Rahmanir Rahim.*/
#include <stdio.h>
#include<string.h>
int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a<=(b*c))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(abs(a - b) <= d && abs(b - c) <= d) {
    cout << "Yes" << endl;
  } else if(abs(a - c) <= d) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

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

int main() {
  int N;
  int div;
  int sum;
  int T = 100000000;
  cin >> N;
  div = N;
  for (int i = 0; i < 9; i++) {
    sum += (div / T);
    div = (div % T);
    T /= 10;
    //cout << T << endl;
  }
  if(N % sum == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

int main(){
  int n,k,q,i,j,a;
  cin >> n >> k >> q;
  ll p[n];
  for(i=1;i<=n;i++){
    p[i]=k-q;
  }
  for(i=1;i<=q;i++){
    cin >> a;
    p[a]=p[a]+1;
  }
  for(i=1;i<=n;i++){
    if(p[i]>0)cout<<"Yes";
    else cout<< "No";
    cout <<"\n";
  }
  return 0;
}

Measured memory_bytes: 1408
#line 1 "SCC.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/graph/SCC.hpp"

#include <cassert>
#include <iostream>
#include <vector>

#ifndef STRONGLY_CONNECTED_COMPONENTS
#define STRONGLY_CONNECTED_COMPONENTS

class StronglyConnectedComponents {
public:
  StronglyConnectedComponents(const std::vector<std::vector<int>> &g) {
    int n = g.size();
    std::vector<std::vector<int>> rg(n);
    for (int i = 0; i < n; i++) {
      for (const auto &v : g[i]) {
        rg[v].push_back(i);
      }
    }
    int now_id = 0;
    std::vector<int> id(n);
    std::vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
      now_id = dfs(i, now_id, id, visited, g);
    }

    int comp_id = 0;
    visited.assign(n, false);
    components_id.resize(n);
    for (int i = n - 1; i >= 0; i--) {
      rdfs(id[i], comp_id, visited, rg);
      comp_id++;
    }
  }

  int get(int i) const {
    assert(0 <= i && i < static_cast<int>(components_id.size()));
    return components_id[i];
  }

private:
  int dfs(int cur, int now_id, std::vector<int> &id, std::vector<bool> &visited,
          const std::vector<std::vector<int>> &g) {
    if (visited[cur])
      return now_id;
    visited[cur] = true;
    for (const auto &v : g[cur]) {
      now_id = dfs(v, now_id, id, visited, g);
    }
    id[now_id] = cur;
    now_id++;
    return now_id;
  }

  void rdfs(int cur, int comp_id, std::vector<bool> &visited, const std::vector<std::vector<int>> &g) {
    if (visited[cur])
      return;
    visited[cur] = true;
    components_id[cur] = comp_id;
    for (const auto v : g[cur]) {
      rdfs(v, comp_id, visited, g);
    }
  }

  std::vector<int> components_id;
};

using SCC = StronglyConnectedComponents;

#endif
#line 5 "SCC.test.cpp"

int main() {
  int v, e;
  std::cin >> v >> e;
  std::vector<std::vector<int>> g(v);
  for (int i = 0; i < e; i++) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
  }

  SCC scc(g);

  int q;
  std::cin >> q;
  for (int i = 0; i < q; i++) {
    int u, v;
    std::cin >> u >> v;
    std::cout << (scc.get(u) == scc.get(v)) << std::endl;
  }
}



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

void SME(int *a);

int main(){
    int a[3];
    for(int i=0;i<3;i++){
        cin>>a[i];
    }
    SME(a);
    return 0;
}

void SME(int *a){
    int Max,Mid,Min;
    Max=0;Min=100000;
    for(int i=0;i<3;i++){
        if(a[i]>Max){
            Max=a[i];
        }
        if(a[i]<Min){
            Min=a[i];
        }
    }

    int j=0; int k=0;

    for(int i=0;i<3;i++){
        if(Max==a[i]){
            j=j+1;
        }
        if(Min==a[i]){
            k=k+1;
        }
    }
    if(j==2){
        Mid=Max;
    }
    else if(k==2){
        Mid=Min;
    }
    else{for(int i=0;i<3;i++){
        if(Min<a[i] && a[i]<Max){
            Mid=a[i];
        }}
    }

    cout<<Min<<" "<<Mid<<" "<<Max<<endl;
}




Measured memory_bytes: 3100
from sys import stdin
#, setrecursionlimit, stdout
#setrecursionlimit(1000000)
#from collections import deque
#from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
def ii(): return int(stdin.readline())
def fi(): return float(stdin.readline())
def mi(): return map(int, stdin.readline().split())
def fmi(): return map(float, stdin.readline().split())
def li(): return list(mi())
def si(): return stdin.readline().rstrip()
def lsi(): return list(si())
#mod=1000000007
res=['Yes', 'No']
############# CODE STARTS HERE #############


test_case=1
while test_case:
    test_case-=1


    cnt=[0]*100005
    n=ii()
    a=li()
    for i in a:
        cnt[i]+=1
    s=sum(a)
    for _ in range(ii()):
        x, y=mi()
        s+=(y-x)*cnt[x]
        print(s)
        cnt[y]+=cnt[x]
        cnt[x]=0

Measured memory_bytes: 84388
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<climits>
#include<stack>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<sstream>
using namespace std;
 
const int LOOP_TIMES = 1000;
const double EPS = 1e-6;
int L, N;
 
double Evaluate(int *r){
    double val = r[0] + r[N-1];
    for(int i = 0; i < N - 1; i++){
        int a = abs( r[i] - r[i+1] ), c = r[i] + r[i+1];
        val += sqrt(c*c - a*a);
    }
    return val;
}
 
bool IsChange(int cnt){
    return cnt < rand()%LOOP_TIMES + 1;
}
 
double Solve(int *r){
    double score = Evaluate(r), mi = score;
    for(int cnt = 0; cnt < LOOP_TIMES; cnt++){
        int *a = r + rand()%N, *b = r + rand()%N;
        swap(*a, *b);
 
        double next_score = Evaluate(r);
        if( score >= next_score && !IsChange(cnt) ) swap(*a, *b);
        else score = next_score;
         
        mi = min(mi, score);
    }
    return mi;
}
 
int main(){
    while(cin >> L){
        N = 0;
        int r[12];
        string S;
        getline(cin, S);
        stringstream SS(S);
        while( !SS.eof() ){
            SS >> r[N++];
        }
 
        double ans;
        if(N == 1) ans = r[0]*2;
        else ans = Solve(r);
 
        if(L - ans + EPS > 0) puts("OK");
        else puts("NA");
    }
    return 0;
}

Measured memory_bytes: 1212
#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 2e3 + 5;
const int maxm = 4e6 + 5;
int n , a[maxn];
bitset<maxm> dp[2];

int main(){
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    cin >> n;
    int sum = 0;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i];
        sum += a[i];
    }
    dp[0][0] = 1;
    sum = sum / 2 + sum % 2;
    for(int i = 1 ; i <= n ; ++i){
        dp[i & 1] = dp[!(i & 1)] | (dp[!(i & 1)] << a[i]);
    }
    for( ;  ;++sum )if(dp[n & 1][sum])return cout << sum , 0;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;
int N, M;

int main()
{
    cin >> N >> M;
    vector<long long> a[3];
    rep(i, N)
    {
        rep(j, 3)
        {
            ll tmp;
            cin >> tmp;
            a[j].emplace_back(tmp);
        }
    }
    ll maxv = 0;
    for (int bit = 0; bit < (1 << 3); ++bit) {
        vector<ll> b;
        rep(i, N)
        {
            ll tmp = 0;
            rep(j, 3)
            {
                if (bit & (1 << j)) {
                    tmp += a[j][i];
                } else {
                    tmp -= a[j][i];
                }
            }
            b.emplace_back(tmp);
        }
        sort(b.begin(), b.end());
        reverse(b.begin(), b.end());
        ll sum = 0;
        for (int i = 0; i < M; ++i) {
            sum += b[i];
        }
        maxv = max(maxv, sum);
    }
    cout << maxv << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int r,g,b;
  cin>>r>>g>>b;
  if((10 * g + b) % 4 == 0) {
    cout << "YES" << endl;
  } else {
    cout <<"NO"<<endl;
  }

  return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
    return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
    auto inner = make_vec_nd(init, rest...);
    return vector<decltype(inner)>(size, inner);
}

int main() {
    ll N;
    cin >> N;
    vector<ll> ais;
    vector<ll> sum_ais;
    sum_ais.push_back(0);
    for (ll i = 0; i < N; i++) {
        ll ai;
        cin >> ai;
        ais.push_back(ai);
        sum_ais.push_back(sum_ais.back() + ai);
    }
    auto dp = make_vec_nd(numeric_limits<ll>::max(), N, N+1);
    for (ll len = 1; len <= N; len++) {
        for (ll start = 0; start + len <= N; start++) {
            ll end = start + len;
            if (len == 1) {
                dp[start][end] = 0;
            } else if (len == 2) {
                dp[start][end] = sum_ais[end] - sum_ais[start];
            } else {
                for (ll start2 = start + 1; start2 < end; start2++) {
                    dp[start][end] = min(dp[start][end], dp[start][start2] + dp[start2][end] + sum_ais[end] - sum_ais[start]);
                }
            }
        }
    }
    cout << dp[0][N] << endl;
}


Measured memory_bytes: 1536
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        String s = a + String.valueOf(b);
        int val = Integer.valueOf(s);
        for (int i = 0; i < 1000; i++) {
            if (i * i == val) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
// rep(i, 1, 5) --> {1,2,3,4}
// rep(i, 5, 1) --> {4,3,2,1}
// rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    ll x, t;
    cin >> x >> t;
    cout << max(0LL, x-t);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

ll A[1010], B[1010], C[1010];
int main()
{
	int X, Y, Z, K;
	cin >> X >> Y >> Z >> K;
	for (int i = 0; i < X; i++) cin >> A[i];
	for (int i = 0; i < Y; i++) cin >> B[i];
	for (int i = 0; i < Z; i++) cin >> C[i];
	sort(A, A + X, greater<ll>());
	sort(B, B + Y, greater<ll>());
	sort(C, C + Z, greater<ll>());
	vector<ll> V;
	for (int i = 0; i < X; i++) {
		for (int j = 0; j < Y; j++) {
			V.push_back(A[i] + B[j]);
		}
	}
	sort(V.begin(), V.end(), greater<ll>());
	vector<ll> ans;
	for (int i = 0; i < min((int)V.size(), K); i++) {
		for (int j = 0; j < Z; j++) {
			ans.push_back(V[i] + C[j]);
		}
	}
	sort(ans.begin(), ans.end(), greater<ll>());
	for (int i = 0; i < K; i++) {
		cout << ans[i] << endl;
	}
}


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

int main()
{
    int n;
    cin >> n;
    set<string> st;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        st.insert(s);
    }
    cout << st.size() << endl;
    return 0;
}

Measured memory_bytes: 19064
#include<stdio.h>


main(){
  int s[100000];
  int t[50000];
  int n,q;
  int count=0;
  int i,j;
  int left,mid,right;
  
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%d",&s[i]);
  }
  
  scanf("%d",&q);
  for(i=0; i<q; i++){
    scanf("%d",&t[i]);
  }
  
  for(i=0; i<q; i++){
    right = n;
    left = 0;
    while(left <= right) {
      mid = (left + right) / 2; 
      if (s[mid] == t[i]) {
	count++;
	break;
      } else if (s[mid] < t[i]) {
	left = mid + 1; 
        } else {
	right = mid - 1; 
      }
    }
    
  }

  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 1184
H, W, K = gets.split.map(&:to_i)
Cs = readlines.map{_1.strip.split('')}

require 'matrix'
cs = Matrix.rows(Cs.map{_1.map{|c| c == '#' ? 1 : 0}})
ans = 0
(0 ... 2**W).each do |w|
  cv = Matrix.column_vector(("%0#{W}b" % w).split('').map(&:to_i))
  (0 ... 2**H).each do |h|
    rv = Matrix.row_vector(("%0#{H}b" % h).split('').map(&:to_i))
    ans += 1 if (rv*cs*cv)[0, 0] == K
  end
end
puts ans

Measured memory_bytes: 15152
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
A = INT()
B = INT()

if A > B:
	print("GREATER")
elif A < B:
	print("LESS")
else:
	print("EQUAL")


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

typedef long long ll;
typedef unsigned long long ull;

int main()
{
    ll X;
    cin >> X;
    ll deposit = 100;
    ll res = 0;
    while(X > deposit){
        deposit = (ll)(1.01 * deposit);
        res++;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

char sir[110];

int main()
{
    //freopen("file.in","r",stdin);
    //freopen("file.out","w",stdout);
    scanf("%s",sir+1);
    int l=strlen(sir+1),sol=1e9;
    for(char i='a';i<='z';i++)
    {
        sir[l+1]=i;
        int c=0,r=0;
        for(int j=1;j<=l+1;j++)
            if(sir[j]==i) {r=max(r,c);c=0;}
            else c++;
        sol=min(sol,r);
    }
    printf("%d",sol);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

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 (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::vector<ll> a(3*N); rep(i, 3*N) std::cin >> a[i];

  std::vector<ll> b(3*N);
  std::priority_queue<ll, std::vector<ll>, std::greater<>> q;
  ll Sum = 0;
  rep(i,3*N) {
    if ( sz(q) != N ) {
      q.push(a[i]);
      Sum += a[i];
    }
    else {
      ll t = q.top();
      if ( t < a[i] ) {
        q.pop();
        q.push(a[i]);
        Sum -= t;
        Sum += a[i];
      }
    }
    b[i] = Sum;
  }

  Sum = 0;
  std::vector<ll> c(3*N);
  std::priority_queue<ll, std::vector<ll>, std::less<>> p;
  rep(i,3*N) {
    if ( sz(p) != N ) {
      p.push(a[3*N-i-1]);
      Sum += a[3*N-i-1];
    }
    else {
      ll t = p.top();
      if ( t > a[3*N-i-1] ) {
        p.pop();
        p.push(a[3*N-i-1]);
        Sum -= t;
        Sum += a[3*N-i-1];
      }
    }
    c[3*N-i-1] = Sum;
  }

  ll ans = -1e15;
  for(ll i=N-1; i<2*N; i++) ans = std::max(ans, b[i]-c[i+1]);
  std::cout << ans << std::endl;
  return 0;
}


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

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define pb push_back
#define mp make_pair
#define INF 999999999
#define MOD 1000000007
#define sp ' '
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()

//typedef
typedef long long ll;
typedef pair<int, int> pint;
typedef map<int, int> mint;
typedef vector<int> vint;
typedef vector<char> vch;
typedef vector<long long> vll;
typedef vector<string> vstr;


int mod(int a, int b){return (a%b+b)%b;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll a, ll b){ll ans=1; rep(i, b){ans=ans*a%MOD;} return ans;}

template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T>
void dpp(T n){cerr << n << endl;}

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int ddx[8] = {1,0,-1,0,1,-1,-1,1};
const int ddy[8] = {0,1,0,-1,1,1,-1,-1};




template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str();
}


vector<string> split(const string &str, char sep)
{
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.pb(buffer);
    }
    return v;
}




int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b;
    cin >> a >> b;

    ppp(a*b-a-b+1);








    return 0;
}


Measured memory_bytes: 896
n=int(input())
k=int(input())
x=map(int,input().split())

ans=0

for i in x:
  #Aロボットの移動距離は2xi
  #Bロボットの移動距離は2(k-xi)
  #AとBの最小値をansに足していく
  ans += min(i*2, abs(i-k)*2)

print(ans)

Measured memory_bytes: 2940
in1=gets.chomp.split(" ").map(&:to_i)
n=in1[0]
l=in1[1]
array=[]

num=0
for i in 0...n do
array.push(l+i)
end
 min=array[0].abs
 index=0
for i in 0...n do
 if array[i].abs<min
  min=array[i].abs
  index=i
 end
end
array.delete_at(index)
for i in 0...n-1 do
 num=num+array[i]
end
puts num


Measured memory_bytes: 1916
import re
class c(int):
    def __add__(self,n):
        return c(int(self)+int(n))
    def __sub__(self,n):
        return c(int(self)-int(n))
    def __mul__(self,n):
        return c(int(self)*int(n))
    def __truediv__(self,n):
        return c(int(int(self)/int(n)))
  
for _ in range(int(input())):
    print(eval(re.sub(r'(\d+)',r'c(\1)',input()[:-1])))

Measured memory_bytes: 7884
#include <bits/stdc++.h>
#include <string>
#include<vector>
using namespace std;
typedef long long ll;
int main(){
    int x; cin >> x;
    int res = 9;
    if(x>=1800 && x<=1999) res = 1;
    else if(x>=1600 && x<=1799) res = 2;
    else if(x>=1400 && x<=1599) res = 3;
    else if(x>=1200 && x<=1399) res = 4;
    else if(x>=1000 && x<=1199) res = 5;
    else if(x>=800 && x<=999) res = 6;
    else if(x>=600 && x<=799) res = 7;
    else if(x>=400 && x<=599) res = 8;
    cout << res << endl;
    return 0;
}

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

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

	int n;
	cin >> n;
	set<int> s;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		s.insert(x);
	}
	if (int(s.size()) == n) {
		cout << "YES" << '\n';
	} else {
		cout << "NO" << '\n';
	}

	return 0;
}


Measured memory_bytes: 9600
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;
typedef long long ll;

void calc(int n,int m,int h,int k){
    //int n,m,h,k;
    int a,b,s[1000],num[1000],sum=0,ans,numb[1000]={0};
    vector<pair<int,int> > vec,in;
    
    // scanf("%d%d%d%d",&n,&m,&h,&k);
    
    for(int i=0;i<n;i++){
        scanf("%d",&s[i]);
        num[i]=i;
    }
    
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        in.push_back(make_pair(b,a));
    }
    
    sort(in.begin(),in.end());
    
    for(int i=0;i<m;i++){
        swap(num[in[i].second-1],num[in[i].second]);
        vec.push_back(make_pair(num[in[i].second-1],num[in[i].second]));
    }
    
    for(int i=0;i<n;i++){
        if(num[i]<k){
            sum+=s[i];
        }
        numb[num[i]]=i;
    }
    ans=sum;
    
    for(int i=0;i<m;i++){
        if((vec[i].first<k)^(vec[i].second<k)){
            if(vec[i].first<k)
                ans=min(ans,sum-s[numb[vec[i].first]]+s[numb[vec[i].second]]);
            else
                ans=min(ans,sum-s[numb[vec[i].second]]+s[numb[vec[i].first]]);
        }
        
    }
    
    printf("%d\n",ans);
    
    return;
}

int main(){
    int n,m,h,k;
    
    while(1){
        scanf("%d%d%d%d",&n,&m,&h,&k);
        
        if(n==0) break;
        
        calc(n,m,h,k);
    }
}

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

namespace AtCoder_Project_CSharp
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();

            if (s.Length == 1) { Console.WriteLine(s); return; }

            var k = int.Parse(Console.ReadLine());

            var alphabets = Enumerable.Range('a', 26).ToArray();

            var kouhos = new List<string>(5);

            foreach (var alphabet in alphabets)
            {
                bool is_good = false;
                for (int i = 0; i < s.Length; i++)
                {
                    char c = s[i];
                    if (alphabet == c)
                    {
                        kouhos.Add(s.Substring(i));
                    }

                }

            }

            kouhos.Sort();
            

            var kouhos2 = new HashSet<string>();

            foreach (var kouho in kouhos)
            {
                for (int i = 0; i < kouho.Length; i++)
                {
                    string str = kouho.Substring(0, i + 1);
                    if (!kouhos2.Contains(str))
                    {
                        kouhos2.Add(str);
                        if (kouhos2.Count == k)
                        {
                            Console.WriteLine(str);
                            return;
                        }
                    }
                }
            }

            return;
        }
    }
}


Measured memory_bytes: 49484
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "{ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "}";

    return os;
}

ll pow_mod(ll a, ll p) {
    ll res = 1;
    while(p) {
        if (p & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        p >>= 1;
    }

    return res;
}


ll mod_inv(ll a, ll m) {
    ll b = m, u = 0, v = 1;
    while(a) {
        ll t = b / a;
        swap(b -= t * a, a);
        swap(u -= t * v, v);
    }

    return (u % m + m) % m;
}

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

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#ifdef LOCAL
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

typedef pair<ll, vi> Data;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int X, Y, Z, K;
    cin >> X >> Y >> Z >> K;

    ll A[X], B[Y], C[Z];
    REP(i, X) cin >> A[i];
    REP(i, Y) cin >> B[i];
    REP(i, Z) cin >> C[i];

    sort(A, A + X, greater<ll>());
    sort(B, B + Y, greater<ll>());
    sort(C, C + Z, greater<ll>());

    priority_queue<Data, vector<Data>, less<Data>> q;
    q.push(Data(A[0] + B[0] + C[0], vi({0, 0, 0})));
    set<vi> s;

    int cnt = 0;
    while (cnt < K) {
        Data d = q.top(); q.pop();
        int ca = d.se[0], cb = d.se[1], cc = d.se[2];
        if (s.count(d.se)) continue;
        s.insert(d.se);
        ++cnt;

        cout << d.fi << endl;

        if (ca < X - 1) q.push(Data(A[ca + 1] + B[cb] + C[cc], vi({ca + 1, cb, cc})));

        if (cb < Y - 1) q.push(Data(A[ca] + B[cb + 1] + C[cc], vi({ca, cb + 1, cc})));

        if (cc < Z - 1) q.push(Data(A[ca] + B[cb] + C[cc + 1], vi({ca, cb, cc + 1})));
    }

}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
const int MAXN=1E5+10;
int arr[MAXN];
int d(int i,int j){
    return i>j?i-j:j-i;
}
int main(){ jizz
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    int sum=0;
    for(int i=0;i<=n;i++){
        sum+=d(arr[i],arr[i+1]);
    }
    for(int i=1;i<=n;i++){
        cout<<sum-d(arr[i-1],arr[i])-d(arr[i],arr[i+1])+d(arr[i-1],arr[i+1])<<"\n";
    }
    return 0;
}


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

int main() {
    int H, W;
    while (true) {
        cin >> H >> W;
        if (H == 0 && W == 0) break;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cout << '#';
            }
            cout << endl;
        }
        cout << endl;
    }
}

Measured memory_bytes: 1152
n = int(input())
data = []
for i in range(n):
    x, y, h = map(int, input().split())
    data.append([x,y,h])
data.sort(reverse=True, key = lambda x:x[2])
for Cx in range(0,101):
    for Cy in range(0,101):
        height = data[0][2] + abs(Cx - data[0][0]) + abs(Cy - data[0][1])
        for i in range(1,n):
            if data[i][2] != max(height - abs(Cx - data[i][0]) - abs(Cy - data[i][1]), 0):
                break
            if i == n - 1:
                print("{} {} {}".format(Cx,Cy,height))
                exit()


Measured memory_bytes: 3064
#include <stdio.h>

int main(void)
{
  int W, H, x, y, r;

  scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

  if ( 0 <= (x - r) && 0 <= (y - r) &&  W >= (x + r) && H >= (y + r))
  {
    printf("Yes\n");
  } else printf("No\n");
  

  return 0;
}


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


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

	vector<int> past(n), future(n);
	for(auto& e : past) {
		cin >> e;
	}
	for(auto& e : future) {
		cin >> e;
	}

	sort(future.begin(), future.end());
	int max_win = 0;
	{
		vector<int> sorted_past = past;
		sort(sorted_past.begin(), sorted_past.end());
		int j = 0;
		for(int i=0;i<n;i++) {
			while (j < n && sorted_past[i] >= future[j]) j++;
			if (j < n) {
				max_win++;
				j++;
			}
		}
	}

	set<pair<int, int>> s;
	for(int i=0;i<n;i++) {
		s.insert(make_pair(past[i], i));
	}
	vector<int> ans(n, -1);

	int fix_win = 0;
	for(int i=0;i<n;i++) {
		auto check = [&](int t) {
			int k = 0;
			int wins = future[t] > past[i] ? 1 : 0;
			for (auto& p : s) {
				if (p.second == i) continue;
				while (k < future.size() && (k == t || future[k] <= p.first)) k++;
				if (k < future.size()) {
					wins++;
					k++;
				}
			}
			return fix_win + wins == max_win;
		};

		int win_border = upper_bound(future.begin(), future.end(), past[i]) - future.begin();

		if(win_border < future.size() && check(win_border)){
			// win this trick
			int l = win_border, r = future.size();
			while (r - l > 1) {
				int mid = (l + r) / 2;
				if (check(mid)) {
					l = mid;
				} else {
					r = mid;
				}
			}

			ans[i] = future[l];
			fix_win++;
			future.erase(future.begin() + l);
		} else {
			// lose this trick
			int l = 0, r = win_border;
			while (r - l > 1) {
				int mid = (l + r) / 2;
				if (check(mid)) {
					l = mid;
				} else {
					r = mid;
				}
			}

			ans[i] = future[l];
			future.erase(future.begin() + l);
		}
		s.erase(make_pair(past[i], i));
	}

	cout << ans[0];
	for(int i=1;i<n;i++) {
		cout << " " << ans[i];
	}
	cout << endl;

	return 0;
}



Measured memory_bytes: 3268
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  deque<char> d;
  for(int i=0;i<s.size();i++)
    d.push_back(s.at(i));
  int q;
  cin>>q;
  int r=0;
  for(int i=0;i<q;i++){
    int t;
    cin>>t;
    if(t==1)
      r=!r;
    if(t==2){
      int f;
      char c;
      cin>>f>>c;
      if(f==1^r)
        d.push_front(c);
      else
        d.push_back(c);
    }
  }
  if(r){
    while(!d.empty()){
      cout<<d.back();
      d.pop_back();
    }
  }else{
    while(!d.empty()){
      cout<<d.front();
      d.pop_front();
    }
  }
  cout<<endl;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main()

{
long long int m[1000000];

long long int sum =0,q;
int x,i,p,z,o;
scanf("%d %d",&x,&o);

for(i=0;i<x;i++)
{
scanf("%lld",&m[i]);

sum=sum+m[i];

}


q=1000000;
for(i=0;i<x;i++)
{
if(m[i]<q)
{
q=m[i];
}
}

if(o==sum)
{
printf("%d",x);
}
else if(o!=sum)
{
p=o-sum;

z=p/q;

printf("%d",z+x);
}

return 0;
}  

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

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

    int st = s.find('A'), fi = s.rfind('Z');

    cout << fi - st + 1 << endl;
    return 0;
}


Measured memory_bytes: 3704
#include <iostream>
#include <fstream>

using namespace std;

int main()
{
		//freopen("in.txt","r",stdin);
		int n;
		cin>>n;
		if(n%1000==0)
			cout<<0;
		else
			cout<<(n/1000+1)*1000-n;

	return 0;
}

Measured memory_bytes: 3676
#include<stdio.h>


int main(){
	int value[101]={0};
	int v,i;
	int max=0;

	for(i=0;i<101;i++){
		value[i]=0;
	}
	while(~scanf("%d",&v)){
		value[v]++;
	}
	for(i=0;i<101;i++){
		if(max<value[i]){
			max=value[i];
		}
	}
	for(i=0;i<101;i++){
		if(max==value[i]){
			printf("%d\n",i);
		}
	}

	return 0;
}

Measured memory_bytes: 596