akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,k;
	cin>>n>>k;
	vl a(n),f(n);
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>f[i];
	sort(all(a));
	sort(rall(f));
	ll ng=-1,ok=LINF,mid;
	while(ng+1<ok){
		mid=(ng+ok)/2;
		ll cnt=0;
		rep(i,n){
			cnt+=max(0ll,(f[i]*a[i]+f[i]-1-mid)/f[i]);
		}
		if(cnt<=k)ok=mid;
		else ng=mid;
	}
	cout<<ok<<endl;
	
}


Measured memory_bytes: 3456
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    S = input().rstrip()

    # すべてを白/黒にするコスト
    ans = min(S.count('.'), S.count('#'))

    white = [0] * (N + 1)

    for i, s in enumerate(S, start=1):
        white[i] += white[i - 1]
        if s == '.':
            white[i] += 1

    for mid, s in enumerate(S):
        # 左をすべて白にする
        left = (mid - white[mid])

        # 右をすべて黒にする
        right = white[N] - white[mid + 1]

        ans = min(ans, left + right)

    print(ans)

sol()

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

// iterator
#define REP(i,from, to) for(unsigned long long int i=from;i<to;i++)
#define REPE(i,from, to) for(unsigned long long int i=from;i<=to;i++)
#define REP_R(i,from, to) for(unsigned long long int i=from;i>to;i--)
#define REPE_R(i,from, to) for(unsigned long long int i=from;i>=to;i--)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define cout2(x, y)      cout << #x << ": " << x << ", " << #y << ": " << y << endl;
#define cout3(x, y, z)   cout << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl;;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

#define coutp(p)         cout << #p << ":" <<  " (" << p.first << ", " << p.second << ")" << endl;

// sort
#define sort_r(x, y)        sort(x, y, greater<unsigned long long int>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;
typedef tuple<lli, lli, lli> tup;
typedef vector<lli> vlli;


const lli MOD = 1000000007;
const lli MAX = 1000001;
lli fac[MAX];       // fac[i]     := iの階乗 % MOD
lli fac_inv[MAX];   // fac_inv[i] := iの階乗の逆元 % MOD (すなわち、fac[i]*fac_inv[i] % MOD == 1)
lli inv[MAX];       // inv[i]     := iの逆元 (すなわち、i*inv[i] % mod == 1)

void init_comb_base() {
    fac[0] = fac[1] = 1;
    fac_inv[0] = fac_inv[1] = 1;
    inv[1] = 1;
    REP(i,2,MAX) {
        fac[i] = i * fac[i-1] % MOD; // n! = n * (n-1)! % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; // ↑の解説参照
        fac_inv[i] = inv[i] * fac_inv[i-1] % MOD; // n! = n * (n-1)! % MOD
    }
}

lli comb(lli n, lli k) {
    if (n<k)
        return 0;
    if (n < 0 || k < 0)
        return 0;

    // nCk = n! / (k! * (n-k)!)
    //     ≡ n! * (k!)^-1 * ((n-k)!)^-1 (mod p)
    return fac[n] * (fac_inv[k] * fac_inv[n-k] % MOD) % MOD;
}

int main() {
    unsigned long long int x,y;
    cin2(x,y);
    // x <= y とする
    if (x > y) {
        swap(x,y);
    }
    if ((x + y) % 3 != 0) {
        cout << 0 << endl;
        return 0;
    }

    lli count = (x+y) / 3;
    // n: 1の方の回数、m: 2の方の回数
    lli n = count*2-x;
    lli m = count-n;
    if (n+m*2 != x || n*2+m != y) {
        cout << 0 << endl;
        return 0;
    }

    // n+mCnを出す
    init_comb_base();
    cout << comb(n+m, n) << endl;
}


Measured memory_bytes: 23680
using static System.Console;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var str = ReadLine().Split().Select(x=>int.Parse(x)).ToArray();
        int sx = str[0], sy = str[1], tx = str[2], ty =str[3];
        var fx = tx - sx;
        var fy = ty - sy;

        mvx(fx);
        mvy(fy);
        mvx(-fx);
        mvy(-fy);

        mvy(-1);
        mvx(++fx);
        mvy(++fy);
        mvx(-1);
        mvy(1);
        mvx(-fx);
        mvy(-fy);
        mvx(1);
    }

    static void mvx(int move)
    {
        if(move > 0)
        {
            for (; move > 0; move--)
            {
                Write("R");
            }
        }else
        {
            move *= -1;
            for (; move > 0; move--)
            {
                Write("L");
            }
        }
    }
    static void mvy(int move)
    {
        if (move > 0)
        {
            for (; move > 0; move--)
            {
                Write("U");
            }
        }
        else
        {
            move *= -1;
            for (; move > 0; move--)
            {
                Write("D");
            }
        }
    }
}

Measured memory_bytes: 2776
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	long long b,bb=0x3f3f3f,a=0;
	for(int i=0;i<n-1;i++){
		scanf("%lld",&b);
		a+=min(b,bb);
		bb=b;
	}
	a+=b;
	cout << a;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <map>
#include <deque>
#include <cmath>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>

// short keywords

#define ipow(a,b) (int)pow(a,b)
#define pi(a,b) pair<int,int>(a,b)
#define pis(a,b) pair<int,string>(a,b)
#define pc(c,d) pair<int,pair<int,string>>(c,d)
#define pp(a,b,c) pair<pair<int,int>,int>(pi(a,b),c)
#define ps(a,b,c) pair<string,pair<int,int>>(a,pi(b,c))

// for loops

#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

// short keywords2
typedef long long ll;
typedef set<int>::iterator sit;
typedef vector <int> ::iterator vit;
typedef map<int,int>::iterator mit;
typedef multimap<int,int>::iterator mmit;

class Task
{
public:
    void solve(istream& in,ostream& out)
    {
        ll a,b,c,d;
        in>>a>>b>>c>>d;
        if(a*b<c*d)
        {
            out<<c*d<<endl;
        }
        else
        out<<a*b<<endl;
    }
};


int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	Task solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in,out);
	out.flush();

    return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

pub fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);

// ===

fn main() {
    let (a, b): (i32, i32) = read();
    let mut ans = 0;
    for i in a..b+1 {
        if is_palindrome(i) {
            ans += 1;
        }
    }
    println!("{}", ans);
}

fn is_palindrome(a: i32) -> bool {
    let s = format!("{}", a);
    let rev: String = s.chars().rev().collect();
    s == rev
}


Measured memory_bytes: 4352
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextInt()
    val b = sc.nextInt()
    val c = sc.nextInt()
    val k = sc.nextInt()
    println(problem096b(a, b, c, k))
}

fun problem096b(a: Int, b: Int, c: Int, k: Int): Int {
    val dp = (0..k).map { IntArray(3) }.toMutableList()
    dp[0] = (intArrayOf(a, b, c))
    for (i in 1..k) {
        val abc = dp[i - 1]
        val a = abc[0]
        val b = abc[1]
        val c = abc[2]
        when {
            a >= b && a >= c -> dp[i] = (intArrayOf(a * 2, b, c))
            b >= a && b >= c -> dp[i] = (intArrayOf(a, b * 2, c))
            c >= a && c >= b -> dp[i] = (intArrayOf(a, b, c * 2))
        }
    }
    return dp[k].sum()
}

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


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    

    int n;
    cin>>n;
    int a[1<<n];
    int m = 1<<n;
    multiset<int> rem,st;
    for(int i=0;i<m;i++){
        cin>>a[i];
        rem.insert(a[i]);
    }
    auto k = rem.end();
    k--;
    cerr<<*k<<endl;
    st.insert(*k);
    rem.erase(k);
    // for(auto i:rem) cerr<<i<<endl;
    rem.insert(1e9);
    rem.insert(-1);
    for(int i=0;i<n;i++){
        multiset<int> s = st;
        for(auto j:s){
            auto k = rem.lower_bound(j);
            k--;
            // cerr << j << " " << *k << endl;
            if(*k == -1){
                cout << "No" << endl;
                return 0;
            }
            st.insert(*k);
            // cerr << *k << " ";
            // k++;
            // cerr<<*k<<endl; 
            rem.erase(k);
            // for(auto i:rem) cerr<<i<<endl;
        }
    }
    cout << "Yes" << endl;

    
}

Measured memory_bytes: 19840
#include<bits/stdc++.h>
using namespace std;
int a=0x7f7f7f7f,b=-0x3f3f3f3f,n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a=min(a,x);
        b=max(b,x);
    }
    cout<<b-a<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int N,visited[100010] = {0};
ll dp[100010][2] = {},inf = 1e9+7;
vector<vector<int>> v(100010);

void dfs(int n){
	visited[n] = 1;
	ll b = 1,w = 1;
	for(int i=0;i<v[n].size();i++){
		int s = v[n][i];
		if(visited[s]==0){
			dfs(s);
			b *= dp[s][0];
			b %= inf;
			w *= (dp[s][0]+dp[s][1])%inf;
			w %= inf;
		}
	}
	dp[n][0] = w;
	dp[n][1] = b;
}

int main(){
	cin >> N;
	int a,b;
	for(int i=0;i<N-1;i++){
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=2;i<=N;i++){
		if(v[i].size()==1){
			dp[i][0] = 1;
			dp[i][1] = 1;
		}
	}
	dfs(1);
	if(N==1) cout << 2 << endl;
	else cout << (dp[1][0]+dp[1][1])%inf << endl;
}

Measured memory_bytes: 13184
package main

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

func exec(stdin *Stdin, stdout *Stdout) {
	n := stdin.ReadInt()
	k := stdin.ReadInt()
	a := []int{}
	for i := 0; i < n; i++ {
		a = append(a, stdin.ReadInt()-1)
	}

	s := make([]int, n+1)
	s[0] = 0
	for i := 0; i < n; i++ {
		s[i+1] = (s[i] + a[i]) % k
	}

	ans := 0
	c := map[int]int{}
	for i := 0; i < len(s); i++ {
		ans += get(c, s[i])
		c[s[i]] = get(c, s[i]) + 1
		if i-k+1 >= 0 {
			c[s[i-k+1]] = get(c, s[i-k+1]) - 1
		}
	}

	stdout.Println(ans)
}

func get(d map[int]int, k int) int {
	if v, ok := d[k]; ok {
		return v
	} else {
		d[k] = 0
		return 0
	}
}

func main() {
	stdout := NewStdout()
	defer stdout.Flush()
	exec(NewStdin(bufio.ScanWords), stdout)
}

type Stdin struct {
	stdin *bufio.Scanner
}

func NewStdin(split bufio.SplitFunc) *Stdin {
	s := Stdin{bufio.NewScanner(os.Stdin)}
	s.stdin.Split(split)
	s.stdin.Buffer(make([]byte, bufio.MaxScanTokenSize), int(math.MaxInt32))
	return &s
}

func (s *Stdin) Read() string {
	s.stdin.Scan()
	return s.stdin.Text()
}

func (s *Stdin) ReadInt() int {
	n, _ := strconv.Atoi(s.Read())
	return n
}

func (s *Stdin) ReadFloat64() float64 {
	n, _ := strconv.ParseFloat(s.Read(), 64)
	return n
}

type Stdout struct {
	stdout *bufio.Writer
}

func NewStdout() *Stdout {
	return &Stdout{bufio.NewWriter(os.Stdout)}
}

func (s *Stdout) Flush() {
	s.stdout.Flush()
}

func (s *Stdout) Println(a ...interface{}) {
	fmt.Fprintln(s.stdout, a...)
}


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

using namespace std;

int main()
{
    string str;
    int i=0,j=0,k=0;
    cin>>str;
    
    if(str[0]=='R'){
        i= 1;
    }
    if(str[1]=='R'){
     j = 1;
    }
    if(str[2]=='R'){
         k = 1;
    }
    
    if(i+j+k==3){
        cout<<"3";
    }else if(i+j==2||j+k==2){
        cout<<"2";
    }else if(i+k==2){
        cout<<"1";
    }else if(i==1||j==1||k==1){
        cout<<"1";
    }
    else 
    {
        cout<<"0";
    }
    

    return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a,b) make_pair(a,b)

//RAQ RSQ セグメント木
struct SegmentTree{
private:
	vector<long long> nodes,lazy;
	int n;
public:
	void init(int N){ //初期化する O(N)
		nodes.clear();
		lazy.clear();
		n = 1;
		while(n < N) n *= 2;
		n = 2 * n -1;
		for(int i=0; i<n; i++){
			nodes.push_back(0);
			lazy.push_back(0);
		}
	}
	void eval(int k, int l, int r){ //遅延評価を行う
		if(lazy[k] == 0) return;
		nodes[k] += lazy[k];
		if(r-l > 1){
			lazy[2*k+1] += lazy[k] / 2;
			lazy[2*k+2] += lazy[k] / 2;
		}
		lazy[k] = 0;
	}
	void add(int a, int b, long long x){ //区間に対して値を加算する O(log N)
		add_query(a, b, x, 0, 0, n/2+1);
	}
	void add_query(int a, int b, long long x, int k, int l, int r){
		eval(k, l, r);
		if(r <= a || b <= l) return; //交差する場合
		if(a <= l && r <= b){ //完全に含む場合
			lazy[k] += (r - l) * x;
			eval(k, l, r);
			return;
		}
		add_query(a, b, x, 2*k+1, l, (l+r)/2);
		add_query(a, b, x, 2*k+2, (l+r)/2, r);
		nodes[k] = nodes[2*k+1] + nodes[2*k+2];
	}
	long long sum(int a, int b){ //[a,b)の最小値を求める O(log N)
		return sum_query(a, b, 0, 0, n/2+1);
	}
	long long sum_query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l) return 0; //交差する場合
		eval(k, l, r);
		if(a <= l && r <= b) return nodes[k]; //完全に含む場合
		long long valueL = sum_query(a, b, k*2+1, l, (l+r)/2);
		long long valueR = sum_query(a, b, k*2+2, (l+r)/2, r);
		return valueL + valueR;
	}
};

int main(){
	
	int n,q;
	cin >> n >> q;
	SegmentTree st;
	st.init(n);
	for(int i=0; i<q; i++){
		int t;
		cin >> t;
		if(t == 0){
			int a,b;
			LL x;
			cin >> a >> b >> x;
			a--;
			st.add(a, b, x);
		}
		else{
			int j;
			cin >> j;
			j--;
			cout << st.sum(j, j+1) << endl;
		}
	}

	return 0;
}



Measured memory_bytes: 7168
package main

import "fmt"

func readMatrix(n int, m int) *[][]int {
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, m)
		for j := 0; j < m; j++ {
			fmt.Scan(&a[i][j])
		}
	}
	return &a
}

func main() {
	var n, m, l int
	fmt.Scan(&n, &m, &l)

	a := *readMatrix(n, m)
	b := *readMatrix(m, l)
	// fmt.Println(a, b)

	got := make([][]int, n)
	for i := 0; i < n; i++ {
		got[i] = make([]int, l)
		for j := 0; j < l; j++ {
			for k := 0; k < m; k++ {
				got[i][j] += a[i][k] * b[k][j]
			}
			if j > 0 {
				fmt.Print(" ")
			}
			fmt.Print(got[i][j])
			if j >= l-1 {
				fmt.Println()
			}
		}
	}
}




Measured memory_bytes: 2560
#!/usr/bin/env python3]
import sys
sys.setrecursionlimit(2000)

N = int(input())
syogen = []
for i in range(N):
    N_a = int(input())
    syogen_a = []
    for _ in range(N_a):
        x, y = input().split()
        syogen_a.append([int(x) - 1, int(y)])
    syogen.append(syogen_a)


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in range(N):
        if s in syojikitati:
            d[s] = 1
        else:
            d[s] = 0

    for s in syojikitati:
        d[s] = 1
        for x, y in syogen[s]:
            if d[x] != y:
                return False
    return True


max_syojiki = 0

for i in range(2 ** N):
    d = {}
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)


Measured memory_bytes: 9128
from collections import defaultdict
import math
import sys
input = sys.stdin.readline


def select_num(a, b, mod=1000000007):
    sum = pow(2, a, mod) + pow(2, b, mod) - 1
    return sum % mod


def dict_count(d, a, b):
    this = a / b
    pair = b / a
    if not d.get(this, False):
        d[this] = {"num": 0, "pair": pair}
    d[this]["num"] += 1


def main():
    MOD = 1000000007
    n = int(input())

    d = defaultdict(lambda: [0] * 2)
    zero = 0
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 or b == 0:
            if a == b == 0:
                n -= 1
                zero += 1
            elif a == 0:
                d[0][True] += 1
            elif b == 0:
                d[0][False] += 1

        else:
            gcd = math.gcd(a, b)
            a //= gcd
            b //= gcd

            if b < 0:
                a, b = -a, -b

            rot = False
            if a < 0:
                b, a = -a, b
                rot = True
            d[(a, b)][rot] += 1

    ans = 1
    for k, v in d.items():
        ans *= select_num(v[0], v[1], MOD)
        ans %= MOD

    ans += zero - 1
    ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 60720
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    int n, k;
    cin >> n >> k;
    ll a[n];
    rep(i,n)cin >> a[i];
    vector<ll> plus, minus;
    rep(i,n){
        if(a[i] > 0)plus.push_back(a[i]);
        else minus.push_back(a[i]);
    }
    n = plus.size();
    int m = minus.size();
    sort(plus.begin(), plus.end(), greater<ll>());
    sort(minus.begin(), minus.end());

    ll ans = 1;
    ll MOD = 1e9+7;

    if(n == 0){
        if(k % 2 == 0){
            rep(i,k){
                ans *= abs(minus[i]);
                ans %= MOD;
            }
        }else{
            rep(i,k){
                ans *= abs(minus[m-1-i]);
                ans %= MOD;
            }
            ans = MOD - ans;
        }
    }

    else if(k == n+m){
        rep(i,n){
            ans *= plus[i];
            ans %= MOD;
        }
        rep(i,m){
            ans *= MOD + minus[i];
            ans %= MOD;
        }
    }

    else{ // 最初にn,m,kをすべて偶数にしてしまう.
        if(k % 2 == 0){
            if(n % 2 == 1){
                plus.erase(plus.begin() + n - 1);
                n--;
            }
            if(m % 2 == 1){
                minus.erase(minus.begin() + m - 1);
                m--;
            }
        }else{
            ans *= plus[0];
            plus.erase(plus.begin());
            n--;
            k--;
            if(n % 2 == 1){
                plus.erase(plus.begin() + n - 1);
                n--;
            }
            if(m % 2 == 1){
                minus.erase(minus.begin() + m - 1);
                m--;
            }
        }
        vector<ll> v;
        rep(i,n/2){
            v.push_back(plus[i*2] * plus[i*2+1]);
        }
        rep(i,m/2){
            v.push_back(minus[i*2] * minus[i*2+1]);
        }
        sort(v.begin(), v.end(), greater<ll>());
        rep(i,k/2){
            ans *= v[i] % MOD;
            ans %= MOD;
        }
    }

    ans %= MOD;
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 8240
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
  x = 0; char c = getchar(); int f = 0;
  for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
  if (f) x = -x;
}

namespace {
  const int mo = 1e9 + 7;
  inline int add(int x, int y) {
    if ((x += y) >= mo) x -= mo;
    return x;
  }
  inline int mul(int x, int y) {
    return 1LL * x * y % mo;
  }
  inline int power(int a, int k) {
    int ans = 1;
    for (; k; k >>= 1, a = mul(a, a))
      if (k & 1) ans = mul(ans, a);
    return ans;
  }
}
const int N = 3333;
int n, q, a[N], f[N][N];

int main(void) {
  read(n); read(q);
  rep (i, n) read(a[i]);
  rep (i, n) rep (j, n) f[i][j] = a[i] > a[j];
  int inv2 = power(2, mo - 2);
  rep (i, q) {
    int x, y; read(x); read(y);
    rep (j, n) if (j != x && j != y) {
      f[j][x] = f[j][y] = mul(inv2, add(f[j][x], f[j][y]));
      f[x][j] = f[y][j] = mul(inv2, add(f[x][j], f[y][j]));
    }
    f[x][y] = f[y][x] = mul(inv2, add(f[x][y], f[y][x]));
  }
  int ans = 0;
  rep (i, n) rep (j, n) if (i < j) ans = add(ans, f[i][j]);
  cout << mul(ans, power(2, q)) << "\n";
}


Measured memory_bytes: 41216
Module Module1

    Sub Main()
        'let'
        Dim N As Long = CLng(Console.ReadLine())
        'var'
        Dim d(N - 1), cnt, pre As Long

        For i As Long = 0 To N - 1
            d(i) = CLng(Console.ReadLine())
        Next

        Array.Sort(d)

        For i As Long = 0 To N - 1
            If i <> 0 AndAlso d(i - 1) < d(i) Then
                cnt += 1
            End If

            pre = d(i)
        Next

        Console.WriteLine(cnt + 1)
    End Sub

End Module


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

ll N;
ll A, B, C;
ll L[1001];

ll dfs(ll cur, ll a, ll b, ll c) {
	if (cur == N) {
		if (a > 0 && b > 0 && c > 0) {
			return abs(a - A) + abs(b - B) + abs(c - C) - 10 * 3;
		}
		else {
			return INF;
		}

	}
	ll no_use = dfs(cur + 1, a, b, c);
	ll a_use = dfs(cur + 1, a + L[cur], b, c) + 10;
	ll b_use = dfs(cur + 1, a, b + L[cur], c) + 10;
	ll c_use = dfs(cur + 1, a, b, c + L[cur]) + 10;
	return min(no_use, min(min(a_use, b_use), c_use));
}

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

	cin >> N;
	cin >> A >> B >> C;

	rep(i, N) cin >> L[i];
	
	ll ans = dfs(0, 0, 0, 0);

	cout << ans << "\n";

	return 0;
}

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

using namespace std;

struct I{I(){ios::sync_with_stdio(false);cin.tie(0);}}init;

struct edge{
    int flow,to,rev;
};

typedef vector<edge> E;
typedef vector<E> Graph;
typedef vector<int> VI;
typedef vector<VI> VV;
void addedge(Graph &g,int s,int t,int f,int rf){
    int n=g[s].size();
    int m=g[t].size();
    g[s].push_back(edge{f,t,m});
    g[t].push_back(edge{rf,s,n});
}
VI bfs(Graph &G,int s){
    int N=G.size();
    queue<int> que;
    VI dist(N,-1);
    dist[s]=0;
    que.push(s);
    for(;!que.empty();que.pop()){
        auto v=que.front();
        for(auto &e:G[v])
            if(e.flow>0&&dist[e.to]==-1){
                dist[e.to]=dist[v]+1;
                que.push(e.to);
            }
    }
    return dist;
}

int maxflow(Graph& G,int s,int t){
    int res=0;
    int N=G.size();
    while(true){
        auto dist=bfs(G,s);
        if(dist[t]<0)break;
        vector<size_t> iter(N,0);
        std::function<int(int,int)> dfs=[&](int v,int f){
            if(v==s)return f;
            for(auto &i=iter[v];i<G[v].size();i++){
                edge &e=G[v][i];
                edge &re=G[e.to][e.rev];
                if(re.flow>0&&dist[v]>dist[e.to]){
                    int d=dfs(e.to,min(f,re.flow));
                    if(d>0){e.flow+=d;re.flow-=d;return d;}
                }
            }
            return 0;
        };
        int f;
        while((f=dfs(t,114514))>0)res+=f;
      
    }
    return res;
}

int main(){
    for(int N,M,S,T;cin>>N>>M>>S>>T,N+M+S+T;){
        S--;T--;
        VV edge(N,VI(N,0));
        Graph G(N);
        for(int i=0;i<M;i++){
            int a,b;cin>>a>>b;
            edge[a-1][b-1]++;
        }
        for(int a=0;a<N;a++)
            for(int b=a+1;b<N;b++)
                if(edge[a][b]>0||edge[b][a]>0)
                    addedge(G,a,b,edge[a][b],edge[b][a]);
        int flow=maxflow(G,S,T);
        int add=0;
        int cnt=0;
        queue<int> que;
        VI color(N,-1);
        que.push(S);
        color[S]=0;
        while(que.size()){
            int v=que.front();que.pop();
            for(auto &e:G[v]){
                if(e.flow>0&&color[e.to]==-1){
                    color[e.to]=color[v];
                    que.push(e.to);
                }
            }
        }
        que.push(T);
        color[T]=1;
        while(que.size()){
            int v=que.front();que.pop();
            for(auto &e:G[v]){
                auto &re=G[e.to][e.rev];
                if(re.flow>0&&color[e.to]==-1){
                    color[e.to]=color[v];
                    que.push(e.to);
                }
            }
        }
        for(int a=0;a<N;a++)
            for(int b=0;b<N;b++)
                if(color[a]==1&&color[b]==0&&edge[a][b]>0)
                    cnt+=edge[a][b],add=1;
        cout<<flow+add<<" "<<cnt<<endl;
    }
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  bool ans=false;
  for(int i=0;i<N;i++){
    char c;
    cin >> c;
    if(c=='Y')ans=true;
  }
  if(ans)cout << "Four";
  else cout << "Three";
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
 
int main(){
    string n;
    cin>>n;
    long sum = 0;

    for(char a : n){
        sum += int(a - '0');
    }

    if(sum%9 == 0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

    return 0;
}

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

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
 
typedef long long ll;
using namespace std;
 
int main(){
  char s[13];
  cin >> s;

  rep(i,0,strlen(s)){
    if(i == 5 || i == 13){
      printf(" ");
    }
    else printf("%c",s[i]);
  }
  printf("\n");
  
  return 0;
}

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

using namespace std;

int main() {
    string S;
    string ac = "AC";
    cin >> S;
    if (S.find(ac) == string::npos)
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) (bit>>(i)) & 1
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(i, n) a[idx][i] = v[i]; idx++; PER = a;} while(next_permutation(ALL(v)));} while(0); // int fact(), VVI PERを宣言しておく
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using LD = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
using VD = vector<double>;
const LL INF = 1e18;
const LL MOD = 1e9 + 7;

template<class T> inline bool chmin(T &a, T b){if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){if (a < b) {a = b; return true;} return false;}

void END(){cout << 1 << endl; exit(0);}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s, t, u;
  int a, b;
  cin >> s >> t >> a >> b >> u;
  if (s == u) a--;
  else b--;
  cout << a << " " << b;

  return 0;
}


Measured memory_bytes: 256
import numpy as np

n,k = map(int, input().split())
p = np.array(list(map(int, input().split())))

exp = (p + 1) / 2
max_sum_exp = sum(exp[0:k])
sum_exp = max_sum_exp
for i in range(n-k):
    sum_exp = sum_exp + exp[k+i] - exp[i]
    max_sum_exp = max(sum_exp, max_sum_exp)

print(max_sum_exp)

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

int main(){
  int x, n; cin >> x >> n;
  int a[n];
  int m,M;
  m = 101, M = 0;
  for(int i = 0; i < n; ++i) {
    cin >> a[i];
    if(a[i] > M) M = a[i];
    if(a[i] < m) m = a[i];
  }
  int ex = 1000;
  int answer;
  for(int i = m-1; i <= M+1; ++i){
    bool judge = true;
     if(fabs(i - x) < ex){
       for(int j = 0; j < n; ++j){
         if(i == a[j]) {
           judge = false;
           break; 
         }
       }
       if(judge) {
         ex = fabs(i-x);
         answer = i;

       } 
     }
  }
  if(n == 0) answer = x;
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 3640
import bisect,collections,copy,heapq,itertools,math,string
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
 
s = input()
ans = math.inf
for x in s:
    t = s.split(x)
    tmp = 0
    for i in range(len(t)):
        tmp = max(tmp, len(t[i]))
    ans = min(ans, tmp)
print(ans)

Measured memory_bytes: 9876
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%I64d",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
#define INF                         (int)1e9
#define EPS                         1e-9
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
#define forall(i,a,b)               for(int i=a;i<b;i++)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define MOD                         1000000007
typedef long long ll;
/*For you see , each day i love you
 more.Today more than yesterday
  less than tomorrow.*/
using namespace std;

int main()
{
	int n,k;
	cin>>n>>k;
	vector<int> vec;
	for(int i = 0;i<n;i++)
	{
		int x;s(x);
		vec.push_back(x);
	}
	
	int start = 1 , end = 1000000000;
	
	while(start <= end)
	{
		int mid = (start + end)/2;
		
		ll val = 0;
		
		for(int i = 0;i<n;i++)
		{
			if(vec[i] % mid == 0)
				val+=(vec[i]/mid - 1);
			else
				val = val + (int)floor(1.0*vec[i] / mid);	
		}
		
		if(val > k)
		{
			start = mid + 1;
		}
		else
		{
			end = mid-1;
		}
	}
	
	cout<<end+1<<endl;
	
	return 0;
}

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

#define int long long

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)
#define rrep(i, s) rep(i, s, >= 0, --)

#define all(c) begin(c), end(c)
template<typename T>bool maxup(T& a, const T&& b) { if (a < b) { a = b; return true; }; }
template<typename T>bool maxup(T& a, const T& b) { if (a < b) { a = b; return true; }; }
template<typename T>bool minup(T& a, const T&& b) { if (a > b) { a = b; return true; }; }
template<typename T>bool minup(T& a, const T& b) { if (a > b) { a = b; return true; }; }

#define X first
#define Y second

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

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

	int N; cin >> N;
	string s; cin >> s;
	V hs;
	bool ansed = false;
	REP3(a, 2) REP3(b, 2) if (!ansed) {
		hs.clear();
		hs.resize(N);
		hs[0] = a;
		hs[1] = b;
		rep(i, 1, N - 1) {
			int val;
			if (hs[i]) {
				val = s[i] == 'o' ? hs[i - 1] : !hs[i - 1];
			} else {
				val = s[i] == 'x' ? hs[i - 1] : !hs[i - 1];
			}
			hs[i + 1] = val;
		}
		bool ok = true;
		if (hs[0] && ((s[0] == 'o') != (hs[N - 1] == hs[1]))) ok = false;
		if (!hs[0] && ((s[0] == 'o') == (hs[N - 1] == hs[1]))) ok = false;
		if (hs[N - 1] && ((s[N - 1] == 'o') != (hs[N - 2] == hs[0]))) ok = false;
		if (!hs[N - 1] && ((s[N - 1] == 'o') == (hs[N - 2] == hs[0]))) ok = false;
		if (ok) {
			rep(i, N) cout << (hs[i] ? 'S' : 'W');
			cout << endl;
			ansed = true;
		}
	}
	if (!ansed) cout << -1 << endl;

	system("pause");
}

Measured memory_bytes: 1608
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;

int bitnum(int n){
    int ret = 0;
    while(n > 0){
        ret += (n & 1); n >>= 1;
    }
    return ret;
}

signed main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    int MIN = 1e16;
    for(int mask = 0; mask < (1 << n); mask++){
        if(bitnum(mask) < k) continue;
        int last = -1;
        int tmp = 0;
        int fin = 0;
         for(int j = 0; j < n; j++){
            if(mask & (1 << j)){
                fin = j;
            }
         }
        for(int j = 0; j < n; j++){
            if(mask & (1 << j)){
                if(last == -1) last = a[j];
                else{
                    tmp += max(last - a[j] + 1, (int)0);
                    last = a[j] +  max(last - a[j] + 1, (int)0);
                }
            }else{
                last = max(last, a[j]);
            }
        }
        MIN = min(MIN, tmp);
    }
    cout << MIN << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
//LLONG_MIN
ll MOD = 1e9+7;

ll f(ll n){
	if(n==1)return 1;
	return n*f(n-1)%MOD;
}

int main(void){
	ll N,M,ans;
	cin>>N>>M;
	if(abs(N-M)>1){
		ans=0;
	}else{
		if(N==M){
			ans = f(N)*f(M)*2%MOD;
		}else{
			ans = f(N)*f(M)%MOD;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h> 
using namespace std; 
#define ll long long int
#define fi first
#define se second
#define pb push_back
#define mod 998244353
#define rep(i,a,b) for (int i=(a);i<(b);i++)
#define repn(i,a,b) for (int i=(a);i>=(b);i--)
#define repq(i,a,b) for (int i=(a);i<(b);i++)
#define pa pair<int,int>
#define be begin()
#define en end()
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll modInverse(ll a, ll m) 
{ ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0; while (a > 1){ ll q = a / m; ll t = m; m = a % m, a = t; t = y; y = x - q * y; x = t; } 
    if (x < 0) x += m0; return x; 
}
ll power(ll x, ll y, ll p)  
{  
    ll res = 1;x = x % p;if (x == 0)return 0;while (y > 0)  
    {if (y & 1) res = (res*x) % p;  y = y>>1; x = (x*x) % p;}
    return res;

}
bool sortinrev(const pair<int,int>&a,const pair<int,int>&b){if(a.fi==b.fi)return b.se>a.se;return a.fi>b.fi;}
void run(vector<ll>v){for(int i=0;i<v.size();i++)cout<<v[i]<<" ";cout<<endl;}
void solve()
{
    ll n;
    cin>>n;
    ll a[n],sum=0;ll freq[100001];
    memset(freq,0,sizeof(freq));
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        freq[a[i]]++;
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int x,y;
        cin>>x>>y;
        freq[y]+=freq[x];
        sum+=(freq[x]*(y-x));
        freq[x]=0;
        cout<<sum<<endl;

    }




}

int main() 
{ 
    


    solve();

        
    
    
    return 0; 
} 

Measured memory_bytes: 5160
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    string s;
    cin >> s;
    int n = s.size();
    if (n & 1) {
        cout << "No\n";
    }   
    else {
        string ans = "Yes";
        for (int i = 0; i < n; ++i) {
            if (i & 1) {
                if (s[i] != 'i')
                    ans = "No";
            }
            else {
                if (s[i] != 'h')
                    ans = "No";
            }
        }   
        cout << ans << endl;
    }   

}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define N 2305
#define LL long long
const LL mo = 1e9+7;
LL C[N][N];
void Init() {
	C[0][0] = 1;
	for(int i=1; i<=2000; i++) {
		for(int j=1; j<i; j++) C[i][j] = (C[i-1][j-1]+C[i-1][j])%mo;
		C[i][i] = C[i][0] = 1;
	}
	return ;
}
int main() {
	Init();
	int n,k;
	scanf("%d%d",&n,&k);
	int B = k,R = n-k;
	for(int i=1; i<=k; i++) printf("%lld\n",C[B-1][i-1]*C[R+1][i]%mo);
	return 0;
}

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

const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint dp[5000][5000];

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

  mint cur = 2;
  rep(i, m) {
    dp[0][i] = cur;
    cur *= 2;
  }
  cur = 2;
  rep(i, n) {
    dp[i][0] = cur;
    cur *= 2;
  }

  for (int i=1; i<n; i++) {
    for (int j=1; j<m; j++) {
      dp[i][j] = dp[i][j-1] * 2 + (dp[i-1][j] - dp[i-1][j-1]) * (j + 2);
    }
  }

  cout << dp[n-1][m-1].x << endl;

  return 0;
}

/*
*/


Measured memory_bytes: 198988
#include <bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(false);cin.tie(0);
#define setnow clock_t tStart=clock();
#define time (double)(clock() - tStart)/CLOCKS_PER_SEC;
#define setin(x) ifstream cin(x);
#define setout(x) ofstream cout(x);
typedef long long ll;
typedef long long int lli;
typedef pair < int, int> dbl;
const int maxInt = 1e9*2;
const lli maxLong = 1e18*2;

int main(){
           int n;
           cin >> n;
           int x = n * 800;
           int y = n / 15 * 200;
           cout << x-y<<endl;
}


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


int main(){
    
    int N;cin>>N;
    char s[110],t[110];
    rep(i,0,N){
            cin>>s[i];
    }
    rep(i,0,N){
            cin>>t[i];
    }
    int k=0;
    bool f;
    rep(i,0,N+1){
        f=true;
        rep(j,0,i){
            if(s[N-i+j]!=t[j])f=false;
        }
        if(f)k=i;
    }
    cout<<2*N-k<<endl;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long n;
void solve()
{
    long long ans=0,tmp=0;
    while(n--)
    {
        long long x;
        cin>>x;
        if (!tmp) {tmp=x;ans++;}
        else if (x>=tmp) {tmp=x;ans++;}
    }
    cout<<ans<<endl;
}
int main()
{
    while(cin>>n)
        solve();
    return 0;
}

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

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

    string s;
    cin>>s;
    if(s[s.size()-1]=='s')s+="es";
    else s+='s';
    cout<<s<<"\n";
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef bool boolean;

int X, n, q;
int *rs;
boolean down = true;

typedef class Data {
	public:
		int L, R;
		int low;

		Data() {	}

		void pass(int t, boolean down) {
			if (down) {
				L -= t, R -= t;
				if (L < 0)
					low += -L, L = 0, low = min(low, X);
				if (R < 0)
					R = 0;
			} else {
				L += t, R += t;
				if (R > X)
					R = X;
				if (L > X)
					low = X, L = X;
			}
		}

		int getVal(int v) {
			if (v < low)
				return L;
			if (v > low + R - L)
				return R;
			return L + v - low;
		}
}Data;

Data d;
inline void solve() {
	scanf("%d", &X);
	scanf("%d", &n);
	rs = new int[(n + 1)];
	for (int i = 1; i <= n; i++)
		scanf("%d", rs + i);
	scanf("%d", &q);
	
	int cur = 0, pr = 1, tc, tv;
	d.L = 0, d.R = X, d.low = 0;
	
	while (q--) {
		scanf("%d%d", &tc, &tv);
		while (pr <= n && rs[pr] <= tc) {
			d.pass(rs[pr] - cur, down);
			down = !down, cur = rs[pr], pr++;
		}
		d.pass(tc - cur, down), cur = tc;
		printf("%d\n", d.getVal(tv));
	}
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(a) cout << #a << ": " << a << endl
#define sz(a) int(a.size())
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define fast cin.tie(0); ios::sync_with_stdio(false)
int32_t main(){ fast;
	ll a, b; cin>>a>>b;
	ll ans = 0;
	while(a<=b){
		a *= 2;
		ans++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/diverta2019/tasks/diverta2019_a

#include "algorithm"
#include "functional"
#include "iostream"
#include "numeric"
#include "queue"
#include "set"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

void solve() {
  ll N, K;
  cin >> N >> K;

  ll res = N - K + 1;
  cout << res << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 256