akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_variables)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::cmp::{max, min, Ordering};

struct Input {
    data: Vec<String>,
}

impl Input {
    pub fn new() -> Input {
        Input{data: Vec::new()}
    }

    fn read(&mut self) {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        self.data = line.split_whitespace().rev().map(|s| s.parse::<String>().unwrap()).collect::<Vec<_>>();
    }

    pub fn pop(&mut self) -> String {
        if self.data.len() == 0 {
            self.read();
        }
        return self.data.pop().unwrap();
    }

    pub fn get<T: core::str::FromStr>(&mut self) -> T {
        return self.pop().parse::<T>().ok().unwrap();
    }
}

impl<T: core::str::FromStr> std::ops::Shr<&mut T> for Input {
    type Output = Input;

    fn shr(mut self, rhs: &mut T) -> Input {
        *rhs = self.get();
        return self;
    }
}

fn main() {
    let mut cin = Input::new();

    let (N, M) = (cin.get::<i32>(), cin.get::<usize>());

    let mut A = vec![0; M];

    for i in 0..M {
        cin = cin >> &mut A[i];
    }
    let mut S = 0;
    for a in A {
        S += a;
    }

    let ans = max(-1, N - S);
    println!("{}", ans);
}


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

/*
int main(){
    int a, b, c;
    cin >> a >> b;
    c = b - a + 1;
    for (int i = 0; i <= c; i++){
        a += i;
    }
    cout << a - b << endl;
}
*/

int main(){
    int a,b; cin >> a >> b;
    int num = b-a;
    int sum = 0;
    for(int i =0; i<b-a; ++i){
        sum += 1+i;
    }
    cout << sum-b <<  endl;
}

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

int main() {
	int n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];
	ll ans = 0;
	rep(i, 60) {
		ll x = 0;
		rep(j, n) if (a[j] >> i & 1) x++;
		ll tmp = x * (n - x) % mod;
		rep(j, i) {
			tmp *= 2;
			tmp %= mod;
		}
		ans += tmp;
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}


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

#ifdef LOCAL
#define debug(var) cerr << #var << " = " << var;
#else
#define debug(var)
#endif

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

void solve() {
	int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
	printf("%d", max(a*b, c*d));
}

int main() {
	init();
	int t = 1; //scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

ll INF = (1ll << 32);
double EPS = 1e-4;

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

  vvi c(10, vi(10));
  for (ll i = 0; i < 10; i++) {
    for (ll j = 0; j < 10; j++) {
      cin >> c[i][j];
    }
  }

  vvi A(H, vi(W));
  for (ll i = 0; i < H; i++) {
    for (ll j = 0; j < W; j++) {
      cin >> A[i][j];
      if (A[i][j] == -1) {
        A[i][j] = 1;
      }
    }
  }

  vi m(10, INF);
  m[1] = 0;

  for (ll i = 0; i < 10; i++) {
    for (ll j = 0; j < 10; j++) {
      for (ll k = 0; k < 10; k++) {
        m[j] = min(m[j], m[k] + c[j][k]);
      }
    }
  }

  ll ans = 0;
  for (ll i = 0; i < H; i++) {
    for (ll j = 0; j < W; j++) {
      ans += m[A[i][j]];
    }
  }

  cout << ans << endl;
}



Measured memory_bytes: 512
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int N;      cin >> N;
    vector<int> a(N);
    for(int i = 0 ; i < N ; ++i)
        cin >> a[i];
    for(int i = 0 ; i < N ; ++i){
        for(int j = i - 1; j >= 0 ; --j)
            if(a[j + 1] < a[j])     swap(a[j + 1], a[j]);
            else    break;
        for(int i = 0 ; i < N - 1; ++i)
            cout << a[i] << ' ';
        cout << a[N - 1] << endl;
    }
}


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

int main(int argc, char const *argv[]) {
  int h, w;
  cin >> h >> w;
  vector<string> a(h);
  for (size_t i = 0; i < h; i++) cin >> a[i];
  vector<vector<int>> dist(h, vector<int>(w, -1));
  queue<pair<int, int>> que;
  int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
  int ans = 0;

  for (size_t i = 0; i < h; i++) {
    for (size_t j = 0; j < w; j++) {
      if (a[i][j] == '#') {
        dist[i][j] = 0;
        que.push(make_pair(i, j));
      }
    }
  }

  while (!que.empty()) {
    auto p = que.front();
    que.pop();
    for (size_t k = 0; k < 4; k++) {
      int x = p.first + dx[k];
      int y = p.second + dy[k];
      if (0 <= x && x < h && 0 <= y && y < w) {
        if (dist[x][y] == -1) {
          dist[x][y] = dist[p.first][p.second] + 1;
          que.push(make_pair(x, y));
        }
      }
    }
  }

  for (size_t i = 0; i < h; i++)
    for (size_t j = 0; j < w; j++) ans = max(ans, dist[i][j]);

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

Measured memory_bytes: 13456
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    da = [[None]*n for _ in range(64)]
    for i in range(n):
        da[0][i] = a[i]-1
    for i in range(1, 64):
        for j in range(n):
            da[i][j] = da[i-1][da[i-1][j]]
    ans = 0
    for i in range(64):
        p = k&1
        if p == 1:
            ans = da[i][ans]
        k//= 2
    print(ans+1)

if __name__ == "__main__":
    main()


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

using namespace std;
int N;
int MAX,MIN = 1000000;
int a[100001];
int c_MAX,c_MIN;
int main() {
  cin >> N;

  for(int i = 0; i < N; i++) {
    cin >> a[i];
    MAX = max(MAX,a[i]);
    MIN = min(MIN,a[i]);
  }
  //cout <<MAX<<MIN<<endl;

  if(MAX - MIN > 1) {
    cout <<"No"<<endl;
    return 0;
  }

  if(MAX == MIN) {
    if(MAX == N-1 || MAX <= N / 2) {
      cout << "Yes" <<endl;
      return 0;
    }
  }

  for(int i = 0; i < N; i++) {
    if(a[i] == MAX) c_MAX++;
    if(a[i] == MIN) c_MIN++;
  }
  
  if(c_MAX >= 2 * (MAX - c_MIN) && MAX > c_MIN) {
    cout <<"Yes"<<endl;
    return 0;
  }
 
  cout <<"No"<<endl;
}


Measured memory_bytes: 768
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const int INF = 1001001001;

int main()
{
	int n;
	while(scanf("%d", &n), n){
		int bld[2][100];
		rep(i, 2) rep(j, n)
			scanf("%d", &bld[i][j]);
		
		bool visited[200] = {false};
		int ans = -1;
		queue<pii> Q;
		Q.push(pii(0, 0));
		Q.push(pii(n, 0));
		while(!Q.empty()){
			pii data = Q.front();
			Q.pop();
			int id = data.first / n;
			int pos = data.first % n;
			while(pos+1<n && bld[id][pos]==1 && bld[id][pos+1]==1)
				++pos;
			while(bld[id][pos] == 2)
				--pos;
			
			if(visited[id*n+pos])
				continue;
			visited[id*n+pos] = true;
			if(pos == n-1){
				ans = data.second;
				break;
			}
			rep(i, 3){
				int next = pos + i;
				if(next >= n)
					break;
				Q.push(pii((!id)*n+next, data.second+1));
			}
		}
		if(ans == -1)
			puts("NA");
		else
			printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1064
n=gets.to_i

sam1=Array.new(n)
sam2=Array.new(n)
sam1=gets.split.map!(&:to_i)
sam2=gets.split.map!(&:to_i)
#数列をint型に変更

kot1=1#sam1
kot2=1#sam2
kazu1=n
kazu2=n
for i in 0..n-2
  ans1=1
  for j in 1..kazu1
    ans1=ans1*j
  end#ans1=nの階上
  kot1+=ans1/kazu1*(sam1[i]-1)#ans1にnの階上を入力　２の階上で終了にする
  kazu1-=1
  for k in 0..n-1
    if sam1[k]>sam1[i]
      sam1[k]=sam1[k]-1#大きい数を1小さくする
    end
  end
end
for i in 0..n-2
  ans2=1
  for j in 1..kazu2
    ans2=ans2*j
  end#ans1=nの階上
  kot2+=ans2/kazu2*(sam2[i]-1)#ans1にnの階上を入力　２の階上で終了にする
  kazu2-=1
  for k in 0..n-1
    if sam2[k]>sam2[i]
      sam2[k]-=1#大きい数を1小さくする
    end
  end
end
puts (kot1-kot2).abs


Measured memory_bytes: 14244
#include<bits/stdc++.h>
using namespace std;
#define mx 100010
int a[mx],p[mx],k,koko[mx];

void sieve()
{
    a[1]=1;
    for(int i=2; i<sqrt(mx); i++)
    {
        if(!a[i])
        {
            p[k++]=i;
            for(int j=i*i; j<mx; j=j+i)
            {
                a[j]=1;
            }
        }
    }
}

int main()
{
    sieve();
    for(int i=2;i<mx;i++)
    {
        if(!a[i] && !a[(i+1)/2]) koko[i]=koko[i-1]+1;
        else koko[i]=koko[i-1];
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        printf("%d\n",koko[r]-koko[l-1]);
    }
}


Measured memory_bytes: 1408
def c_1d_reversi():
    # 端の同じ色の石は1個の石を置けばひっくり返せる
    # 連続した石をひとまとめにしたとき，何個の石があるかが解
    from itertools import groupby
    return len(list(groupby(input()))) - 1

print(c_1d_reversi())

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

int main(){
    using namespace std;
    unsigned long k, q;
    cin >> k >> q;
    vector<unsigned long> d(k);
    for(auto& i : d)cin >> i;
    const auto& query = [&](unsigned long n, unsigned long x, unsigned long m) -> unsigned long {
        unsigned long S{x + n}, c{n + k - 1};
        for(const auto& i : d)S += c-- / k * ((i + m - 1) % m);
        return n - S / m + x / m;
    };
    for(unsigned long i{0}, n, x, m; i < q; ++i){
        cin >> n >> x >> m;
        cout << query(n - 1, x, m) << endl;
    }
    return 0;
}

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

int main() {
	// your code goes here
     int h1,s1,h2,s2;
     cin>>h1>>s1>>h2>>s2;
     while(h1>0 && h2>0)
     {
     	h2=h2-s1;
     	if(h2<=0)
     	{
     		cout<<"Yes";
     		return 0;
     	}
     	h1=h1-s2;
     	if(h1<=0)
     	{
     		cout<<"No";
     		return 0;
     	}
     
     }
	return 0;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<algorithm>
#include<utility>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int main(){
	int n; ll k;
	scanf("%d %lld", &n, &k);
	P p[100000];
	for(int i = 0; i < n; i++) scanf("%d %d", &p[i].first, &p[i].second);
	sort(p, p + n);
	ll c = 0;
	for(int i = 0; i < n; i++){
		c += p[i].second;
		if(c >= k){ printf("%d\n", p[i].first); break; }
	}
	return 0;
}

Measured memory_bytes: 896
h, w = map(int, input().split(" "))
a = [input() for _ in range(h)]

h_remove_count = 0
while "."*w in a:
	a.remove("."*w)
	h_remove_count += 1

a = ["".join(h_line) for h_line in zip(*a)]
while "."*(h-h_remove_count) in a:
	a.remove("."*(h-h_remove_count))

for line in zip(*a):
	print("".join(line))

Measured memory_bytes: 3064
#include <cmath>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define REP(i,n) for(int i = 0; i < n; i++)

int main(void)
{
    int N, M, X;
    cin >> N >> M >> X;
    int A[M];
    for(int i = 0; i < M; i++) cin >> A[i];

    int cp = 0;
    for(int i = X; i < N + 1; i++){
        for(int j = 0; j < M; j++){
            if(i == A[j]){
                cp++;
            }
        } 
    }

    int cm = 0;
    for(int i = X; i > -1; i--){
        for(int j = 0; j < M; j++){
            if(i == A[j]){
                cm++;
            }
        } 
    }

    cout << min(cp, cm) << endl;

    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    int n;
    ll k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    rep(i,n) a[i]--;

    vector<int> town;
    set<int> st;
    town.push_back(0);
    st.insert(0);
    int i = 0;
    while(true){
        k--;
        if (k == 0){
            cout << a[i]+1 << endl;
            return 0;
        }
        if (st.find(a[i]) == st.end()){
            town.push_back(a[i]);
            st.insert(a[i]);
            i = a[i];
            continue;
        }else{
            vector<int> loop;
            rep(j,town.size()){
                if (a[i] == town[j]) {
                    for(int k = j; k < town.size(); k++) loop.push_back(town[k]);
                    break;
                }
            }
            k %= loop.size();
            cout << loop[k] + 1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 12264
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let s: String = read();

    println!("{}", s.chars().filter(|&c| c == '1').count());
}


Measured memory_bytes: 2100
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

class PartParsistentUnionFind{
    typedef pair<int,int> pii;
private:
    vector<int> par;
    vector<int> time;
    vector<vector<pii>> size;
    int now;
public:
    PartParsistentUnionFind(){}
    PartParsistentUnionFind(int N){init(N);}
    void init(int N){
        par.clear(); time.clear(); size.clear();
        par.assign(N,0);
        time.resize(N,INT_MAX);
        size.assign(N,vector<pii>(1,{0,1}));
        now = 0;
    }
    int find(int x,int T = INT_MAX){
        if(T == INT_MAX) T = now;
        if(time[x] > T) return x;
        else return find(par[x],T);
    }
    bool unite(int x,int y){
        now++;
        x = find(x,now); y = find(y,now);
        if(x == y) return false;
        if(par[x] < par[y]) swap(x,y);
        par[x] += par[y];
        par[y] = x;
        time[y] = now;
        size[x].push_back({now,par[x]});
        return true;
    }
    int Getnow(){ return now; }
    bool same(int x,int y,int T = INT_MAX){
        if(T == INT_MAX) T = now;
        return find(x,T) == find(y,T);
    }
};

void solve2(){
    int n,q; cin >> n >> q;
    PartParsistentUnionFind PPUF(n);
    vector<pair<int,pii>> query;
    while(q--){
        int com; cin >> com;
        int x,y; cin >> x >> y;
        if(com == 0){
            PPUF.unite(x, y);
        }else{
            query.push_back({PPUF.Getnow(),{x,y}});
        }
    }
    for(auto q:query){
        cout << PPUF.same(q.second.first,q.second.second,q.first) << endl;
    }
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    //   solve1();
    solve2();
    return 0;
}



Measured memory_bytes: 4508
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
template<class Read>void in(Read &x){
    x=0;
    int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        f|=(ch=='-');
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x=f?-x:x;
    return;
}
int n,sum=1,ans,a[200005];
int main(){
    in(n);
    for(int i=1;i<=n;i++)in(a[i]);
    for(int i=1;i<=n;i++)if(a[i]==sum)sum++,ans++;
    printf("%d\n",ans==0?-1:n-ans);
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{

while(1)
{
int n,num,j=0;
string sig="0000000",str;
cin>>n;
if(n==-1)break;
for(int k=0;k<n;k++)
{
cin>>num;
string ans="";

if(num==0)str="0111111";
else if(num==1)str="0000110";
else if(num==2)str="1011011";
else if(num==3)str="1001111";
else if(num==4)str="1100110";
else if(num==5)str="1101101";
else if(num==6)str="1111101";
else if(num==7)str="0100111";
else if(num==8)str="1111111";
else str="1101111";
for(int i=0;i<7;i++)
{
if(sig.at(i)!=str.at(i))ans+='1';
else ans+='0';
}
sig=str;
cout<<ans<<endl;
}
}
return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int q;
int main(){
	cin>>q;
	rep(w,q){
		ll a,b,c,d;
		cin>>a>>b>>c>>d;
		ll k = (a+b)/(min(a,b)+1);
		ll lb=-1LL,ub=a+1;
		while(ub-lb > 1){
			ll mid = (lb+ub)/2;
			ll bb = max(0ll,(mid-1)/k);
			ll zana = a-mid,zanb = b-bb;
			if(zanb <= (zana+1)*k){
				lb = mid;
			}
			else{
				ub = mid;
			}
		}
		bool ok = 0;
		for(ll x=min(a,lb+334LL);x>=max(0LL,lb-334LL);x--){
			ll acnt = x;
			ll bcnt = max(0ll,(x-1)/k);
			ll sum = acnt+bcnt;
			acnt += (a+b-sum)/(k+1);
			bcnt += (a+b-sum)-((a+b-sum)/(k+1));
			if(acnt != a || bcnt != b) continue;
			for(ll i=c;i<=d;i++){
				if(i<=sum){
					if(i%(k+1) == 0) printf("B");
					else printf("A");
				}
				else{
					ll j = a+b+1-i;
					if(j%(k+1) == 0) printf("A");
					else printf("B");
				}
			}
			ok = 1;
			puts("");
			break;
		}
		assert(ok);
	}
}

Measured memory_bytes: 384
// =================================
//   author: memset0
//   date: 2018.12.26 08:23:54
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define rep(i, l, r) for (register int i = l; i <= r; i++)
namespace ringo {
typedef long long ll;
typedef unsigned long long ull;
template <class T> inline void read(T &x) {
	x = 0; register char c = getchar(); register bool f = 0;
	while (!isdigit(c)) f ^= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
	if (f) x = -x;
}
template <class T> inline void print(T x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar('0' + x % 10);
}
template <class T> inline void maxd(T &a, T b) { if (b > a) a = b; }
template <class T> inline void mind(T &a, T b) { if (b < a) a = b; }
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline T abs(const T &a) { if (a < 0) return -a; return a; }

const int N = 1e2 + 10;
int n, m, p, k, ans, sum, a[N];

void main() {
	read(n);
	for (int i = 1; i <= n; i++) read(a[i]), sum += a[i];
	read(m);
	for (int i = 1; i <= m; i++) {
		read(p), read(k);
		print(sum - a[p] + k, '\n');
	}
}

} signed main() { return ringo::main(), 0; }

Measured memory_bytes: 256
def bi(x,n):
    o = [0]*n
    c = 0
    while x > 0:
        o[c] = x % 2
        c += 1
        x //= 2
    return o

N,M = map(int,input().split(" "))
s = [0]*M
for i in range(M):
    s[i] = list(map(int,input().split(" ")))[1:]
p = list(map(int,input().split(" ")))

c = 0
for j in range(2**N):
    o = bi(j,N)
    a = True
    for i in range(M):
        a = a and sum([o[x-1] for x in s[i]])%2 == p[i]
    c += a

print(c)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
int N;
vector<int> V;
int dp[100005][5];
int fun(int K,int x)
{
    int y,i,flag;
    if(x==0)
        y=1;
    if(x==1)
        y=0;
    flag=0;
    for(i=0;i<N;i++)
    {
        if(V[i]<=K)
        {
            if(dp[(K-V[i])][y]==-1)
            dp[(K-V[i])][y]=fun((K-V[i]),y);
            if(dp[(K-V[i])][y]==x)
            flag=1;
        }
        else
        break;
    }
    if(flag==0)
        dp[K][x]=y;
    else
    {
        dp[K][x]=x;
    }
    return dp[K][x];
}
int main()
{
    int K,i,x,j;
    cin>>N>>K;
    for(i=0;i<N;i++)
    {
        cin>>x;
        V.pb(x);
    }
    for(i=0;i<100005;i++)
    {
        for(j=0;j<5;j++)
            dp[i][j]=-1;
    }
    dp[K][0]=fun(K,0);
    if(dp[K][0]==0)
        cout<<"First";
    else if(dp[K][0]==1)
        cout<<"Second";
    return 0;
}

Measured memory_bytes: 9984
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <stdio.h>

using namespace std;

#define fo(i,n) for(int i=0; i<(int)n; i++)
#define rep(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#define mp(a,b) make_pair(a,b)
#define pb(x) push_back(x)
#define pii pair<int,int>

#define vll vector<long long>
#define vvll vector< vll >

int N,M,A,B,C,T;

int s[55];

vvll mul(vvll a, vvll b) {
	vvll c = vvll(N,vll(N,0)); 
	
	for (int i=0; i<N; i++) for (int j=0; j<N; j++) {
		long long sum = 0;
		for (int k=0; k<N; k++) {
			sum += a[i][k]*b[k][j]%M;
			sum %= M;
		}
		c[i][j] = sum;
	}
	return c;
}

vvll mpow(vvll a, int e) {
	if (e==1) return a;
	
	vvll c = vvll(N,vll(N,0)); 
	for (int i=0; i<N; i++) {
		c[i][i] = 1;
	}
	
	if (e==0) return c;
	
	c = mpow(a,e>>1);
	c = mul(c,c);
	if (e%2==0) return c;
	return mul(a,c);
}
	

int main() {

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

	while (cin>>N>>M>>A>>B>>C>>T && N!=0) {
		for (int i=0; i<N; i++) cin>>s[i];
		
		vvll trans = vvll(N,vll(N,0));
		
		for (int i=0; i<N; i++) {
			trans[i][i] = B;
			if (i>0) trans[i][i-1] = A;
			if (i<N-1) trans[i][i+1] = C;
		}
		
		trans = mpow(trans,T);
		
		for (int i=0; i<N; i++) {
			long long sum = 0;
			for (int k=0; k<N; k++) {
				sum += (s[k]*trans[i][k])%M;
				sum %= M;
			}
			cout<<sum;
			if (i!=N-1) cout<<" ";
		}
		
		cout<<endl;
	}
	
    return 0;

}

Measured memory_bytes: 2556
using System;
using System.Collections.Generic;

class Program {
    static Graph G;

    public struct Graph {
        public HashSet<int>[] points;

        public Graph (int n) {
            points = new HashSet<int>[n];
            for (int i = 0; i < n; i++) {
                points[i] = new HashSet<int> ();
            }
        }

        public void AddLine (int a, int b) {
            points[a].Add (b);
            points[b].Add (a);
        }

        public void AddDirectionalLine (int a, int b) {
            points[a].Add (b);
        }
    }

    static void Main (string[] args) {
        int N = int.Parse (Console.ReadLine ());
        string[] input1 = Console.ReadLine ().Split (' ');
        G = new Graph (N);

        for (int i = 0; i < N - 1; i++) {
            G.AddDirectionalLine (int.Parse (input1[i]) - 1, i + 1);
        }

        for (int i = 0; i < N; i++) {
            Console.WriteLine (G.points[i].Count);
        }
    }
}

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

using namespace std;

int main(){
	double m,sum=0.0,b,c=0.0;int n;
	cin>>n>>m;
	int a[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	b=sum/(4.0*m);
	for(int i=1;i<=n;i++){
		if(a[i]>=b)c++;
	}
	if(c>=m){
		cout<<"Yes";
	}
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int a[200000],b[200000];
int main(){
	int n;cin>>n;
	rep(i,n+1){
		scanf("%d",&a[i]);
	}
	rep(i,n){
		scanf("%d",&b[i]);
	}
	ll sum=0;
	rep(i,n){
		if(a[i]){
			int c=min(b[i],a[i]);
			sum+=c;
			b[i]-=c;
			a[i]-=c;
		}
		if(a[i+1]){
			int c=min(b[i],a[i+1]);
			sum+=c;
			b[i]-=c;
			a[i+1]-=c;
		}
	}
	cout<<sum<<endl;
}

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
    int d, t, s;

    cin >> d >> t >> s;

    if (d / s < t)
    {
        cout << "Yes" << endl;
    }
    else if (d / s == t && d % s == 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

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

using namespace std;

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

	int n;
	cin>>n;
	int h[n];
	for(int i = 0; i < n; i++) cin>>h[i];

	int dp[n];
	dp[n-1] = 0;
	dp[n-2] = abs(h[n-2] - h[n-1]);

	for(int i = n - 3; i >= 0; i--) {
		dp[i] = min(dp[i+1] + abs(h[i]-h[i+1]), dp[i+2]+ abs(h[i]-h[i+2]));
	}

	cout<<dp[0];
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,h,m;
    cin>>a;
    h=a/3600;
    a-=h*3600;
    m=a/60;
    a-=m*60;
    cout<<h<<":"<<m<<":"<<a<<endl;
}



Measured memory_bytes: 3088
#include<stdio.h>
int main(void){
    int a,b,d,r;
    double f;
    scanf("%d %d",&a,&b);
    d=a/b;
    r=a%b;
    f=(double)a/(double)b;
    printf("%d %d %f\n",d,r,f);
    return 0;
}


Measured memory_bytes: 2108
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 1000000007

using namespace std;
typedef pair<llint, llint> P;

llint n;
llint a[100005], b[100005], c[100005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= n; i++) cin >> c[i];
	sort(a+1, a+n+1);
	sort(c+1, c+n+1);
	
	llint ans = 0;
	for(int i = 1; i <= n; i++){
		llint p = lower_bound(a+1, a+n+1, b[i]) - a;
		llint mul = p-1;
		p = upper_bound(c+1, c+n+1, b[i]) - c;
		mul *= n-(p-1);
		ans += mul;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 2688
#include<stdio.h>

int main(){
    int S,h,m,s;
    scanf("%d", &S);
    h = S / 3600;
    m = (S - h * 3600) / 60;
    s = S % 60;
    printf("%d:%d:%d\n",h,m,s);
    return 0;
}




Measured memory_bytes: 2132
import java.util.*;

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

        int T = sc.nextInt();

        for (int t = 0; t < T; t++) {
            long A = sc.nextLong();
            long B = sc.nextLong();
            long C = sc.nextLong();
            long D = sc.nextLong();

            if (B > A) {
                System.out.println("No");
                continue;
            }

            if (B > D) {
                System.out.println("No");
                continue;
            }

            if (C >= B) {
                System.out.println("Yes");
                continue;
            }

            long g = gcd(B, D);

            if (B - g + (A % g) > C) {
                System.out.println("No");
            } else {
                System.out.println("Yes");
            }

        }
    }

    private static long gcd(long a, long b) {
        long c = a % b;
        if (c == 0) return b;
        return gcd(b, c);
    }
}

Measured memory_bytes: 25064
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll a,b,d;
    char c,e;
    cin>>a>>c>>b;
    if(c=='+')
    d=a+b;
    else
    d=a-b;
    cout<<d;
    return 0;
}

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

#define int long long

signed main() {
    int A, B, C, D;
    string S;
    cin >> S;
    A = S[0] - '0', B = S[1] - '0', C = S[2] - '0', D = S[3] - '0';
    if (A + B + C + D == 7) {
        cout << A << "+" << B << "+" << C << "+" << D << "=7" << endl;
    } else if (A - B + C + D == 7) {
        cout << A << "-" << B << "+" << C << "+" << D << "=7" << endl;
    } else if (A + B - C + D == 7) {
        cout << A << "+" << B << "-" << C << "+" << D << "=7" << endl;
    } else if (A - B - C + D == 7) {
        cout << A << "-" << B << "-" << C << "+" << D << "=7" << endl;
    } else if (A + B + C - D == 7) {
        cout << A << "+" << B << "+" << C << "-" << D << "=7" << endl;
    } else if (A - B + C - D == 7) {
        cout << A << "-" << B << "+" << C << "-" << D << "=7" << endl;
    } else if (A + B - C - D == 7) {
        cout << A << "+" << B << "-" << C << "-" << D << "=7" << endl;
    } else if (A - B - C - D == 7) {
        cout << A << "-" << B << "-" << C << "-" << D << "=7" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int lo;
lo a,b,c;


int main(){
    cin >> a >> b >> c;
    if(a + b >= c){
        cout << "No";
        return 0;
    }
    if((b * a * 4) < (c - b - a) * (c - b - a)) {
        cout << "Yes";
    }
    else cout << "No";

}

//g++ code.cpp -o code.exe
// code.exe

Measured memory_bytes: 256
N, M = map(int, input().split())
a1, a2 = 2, M
a = {}
while (a1 - 1) ** 2 <= a2 or a1 == a2:
    if a2 % a1 == 0:
        a2 //= a1
        if a1 in a:
            a[a1] += 1
        else:
            a[a1] = 1
    else:
        a1 += 1
p = 1
if a2 != 1:
    a[a2] = 1
for v in a.values():
    tmp = 1
    for i in range(v):
        tmp = tmp * (v + N - 1 - i) // (i + 1)
    p *= tmp
print(p % (10 ** 9 + 7))

Measured memory_bytes: 3064
import java.util.*;
import static java.lang.System.*;
import java.io.*;
import java.math.*;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int h = sc.nextInt();
		int n = sc.nextInt();
		long dam = 0;
		for (int i = 0; i < n; i++)
			dam += sc.nextLong();
		if (dam >= h)
			out.print("Yes");
		else
			out.print("No");

		out.close();
	}

static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}
}

Measured memory_bytes: 22736
n = int(input())
s = [input() for i in range(n)]
m = int(input())
t = [input() for i in range(m)]
from collections import Counter
cnt_s = Counter(s)
cnt_t = Counter(t)
money = 0
for i in set(s):
    temp = cnt_s[i] - cnt_t[i]
    if money < temp:money = temp
print(money)

Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int main(){
   int n,k;
   string s;
   cin >> n >> k;
   int ans=k;
   for (int i=0;i < n-1;i++) ans*=k-1;
   cout << ans <<endl;
   return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);

		int P = sc.nextInt();
		int Q = sc.nextInt();
		int R = sc.nextInt();
		int min = 200;

		if (min >= P + Q) {
			min = P + Q;
		}

		if (min >= P + R) {
			min = P + R;
		}

		if (min >= Q + R) {
			min = Q + R;
		}

		System.out.print(min);
	}
}


Measured memory_bytes: 21844
// パナソニックプログラミングコンテスト2020 B.cpp

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;

int main()
{
	mp::cpp_int h,//縦
		w,//横
		temp;
	cin >> h >> w;
	if (h == 1 || w == 1) {
		cout << 1 << endl;
	}
	else {
		if (w % 2 == 0) {
			cout << w / 2 * h << endl;
		}
		else {
			if (h % 2 == 0) {
				cout << h / 2 * w << endl;
			}
			else {
				temp = (w + 1) / 2;
				cout << temp + h / 2 * w << endl;
			}
		}
	}
}

Measured memory_bytes: 256
//

fun main() {
    msolutions2020a()
}

fun msolutions2020a() {
    val n = readLine()!!.toInt()
    val ans = when (n) {
        in 1800..1999 -> 1
        in 1600..1799 -> 2
        in 1400..1599 -> 3
        in 1200..1399 -> 4
        in 1000..1199 -> 5
        in 800..999 -> 6
        in 600..799 -> 7
        else -> 8
    }
    println(ans)
}


Measured memory_bytes: 34416
MOD = 10**9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n, m, k = map(int, input().split())
print((((n+m)*n*m*(m*n-1))//6)*comb(n*m-2, k-2)%MOD)

Measured memory_bytes: 18804
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
int ruiseki[200000];
int next_go[200000];
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> tmp_a;
	REP(i, n) {
		int c;
		cin >> c;
		tmp_a.push_back(make_pair(0, -c));
	}
	REP(i, n) {
		int c;
		cin >> tmp_a[i].first;
	}
	sort(tmp_a.begin(), tmp_a.end());
	vector<pair<int, int>> a;
	vector<int> b;
	REP(q, tmp_a.size()) {
		a.push_back(make_pair(-tmp_a[q].second, q));
		b.push_back(tmp_a[q].first);
	}
	vector<pair<int, int>> base_a = a;
	sort(a.begin(), a.end());
	int ok = 0;
	REP(q, a.size()) {
		if (a[q].first > b[q]) {
			ok = 2;
		}
	}
	if (ok == 0) {
		for (int i = 1; i < a.size(); ++i) {
			ruiseki[i] += ruiseki[i - 1];
			if (a[i].first > b[i - 1]) {
				ruiseki[i]++;
			}
		}
		for (int i = 0; i < a.size(); ++i) {
			if (a[i].second <= i) {
				if (a[i].first <= b[a[i].second]) {
					ok = 1;
				}
			}
			else {
				int hoge = ruiseki[a[i].second] - ruiseki[i];
				if (hoge == 0) {
					ok = 1;
				}
			}
		}
		REP(i, a.size()) {
			next_go[a[i].second] = i;
		}
		int cnt = 0;
		int now = 0;
		while (cnt == 0 || now != 0) {
			cnt++;
			now = next_go[now];
		}
		if (cnt != a.size()) {
			ok = 1;
		}
	}
	string ans[2] = { "No","Yes" };
	cout << ans[ok%2] << endl;
}


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

#define ll long long
#define ull unsigned long long

using namespace std;

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

	ll sum = 0;
	for (int ii = 1; ii <= N; ++ii){
		if ( ((ii % 3) != 0) && ((ii % 5) != 0) ){
			sum += ii;
		}
	}

	cout << sum << endl;

	return 0;
}


Measured memory_bytes: 3632
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            flag = False
            for i in [-1, 0, 1]:
                for j in [-1, 0, 1]:
                    if not i+j in [-1, 1]:
                        continue
                    if 0 <= h+i < H and 0 <= w+j < W:
                        if S[h+i][w+j] == '#':
                            flag = True
            if not flag:
                print('No')
                exit()
print('Yes')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N,M;
	cin>>N>>M;
	int sum=0;
	vector<int> V(M);
	for(int i=0;i<M;i++)
	{
		cin>>V[i];
		sum+=V[i];
	}
	if(sum>N)
	{
		cout<<-1;
	}
	else
	cout<<N-sum;
	
	
	return 0;}


Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<time.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
int main(){
	vector<bool>in(31);
	rep(i,28){
		int a;
		cin>>a;
		in[a]=true;
	}
	loop(i,1,31)if(!in[i])cout<<i<<endl;
}

Measured memory_bytes: 1192
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));

function main(){
  var n = next();
  var ans = n * (n+1) * (n+2) / 6;
  for(var i = 1; i < n; i++){
    var u = next(), v = next();
    if(u > v){var temp = u; u = v; v = temp;}
    ans -= u * (n-v+1);
  }
  return ans;
}

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

#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rep(i, a, b) for (long i = (a); i <= (b); ++i)
#define per(i, a, b) for (long i = (a); i >= (b); --i)

using namespace std;

using I = int;
using L = long;
using F = float;
using S = string;
using SS = stringstream;
using C = char;
using LL = long long;
using VI = vector<int>;
using VL = vector<long>;
using VF = vector<float>;
using VS = vector<string>;
using VVI = vector<vector<int>>;
using VVL = vector<vector<long>>;
using PLL = pair<long, long>;
using PLF = pair<long, float>;
using PLS = pair<long, string>;
using PSL = pair<string, long>;
using PSF = pair<string, float>;
using PSS = pair<string, string>;
using MLL = map<long, long>;
using MLF = map<long, float>;
using MLS = map<long, string>;
using MSL = map<string, long>;
using MSF = map<string, float>;
using MSS = map<string, string>;

const long kMax2 = 109;
const long kMax3 = 1009;
const long kMax4 = 10009;
const long kMax5 = 100009;
const long kMax6 = 1000009;
const long kInfI = 0x3F3F3F3F;
const float kInfF = 1e15;

template <class T>
void PrintVector(const vector<T> & v) {
  for (const auto & e: v) {
    cout << e << endl;
  }
}

template <class T>
void PrintVector(const vector<T> & v, I n) {
  rep(i, 0, n - 1) {
    cout << v[i] << endl;
  }
}

int main(int argc, char const *argv[]) {
  I n, a;
  I ans;

  cin >> n >> a;
  ans = n % 500;
  if (ans <= a) cout << "Yes\n";
  else cout << "No\n";

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int INT_INF = 1e9;
const ll MOD = 1e9 + 7;
const int INT_MOD=1e9+7;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 0; i <= n; i++)
#define rrep(i,n) for(int i=n;i>0;i--)
#define RREP(i,n) for(int i=n;i>=0;i--)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
ll dp[103][100005]={};
ll total[100003];
signed main(){
    int n,k;
    cin>>n>>k;
    int a[n+1]={};
    for(int i=1;i<n+1;i++) cin>>a[i];
    dp[0][0]=1;
    for(int i=1;i<n+1;i++){
        total[0]=0;
        for(int j=1;j<=k+1;j++) total[j]=(total[j-1]+dp[i-1][j-1])%MOD;
        rep(j,k+1) dp[i][j]=(total[j+1]-total[max(0,j-a[i])]+MOD)%MOD;
    }
    cout<<dp[n][k]<<endl;
    return 0;
}

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

#include "bits/stdc++.h"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/rope"

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define f first
#define s second

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

struct custom_hash 
{
    static uint64_t splitmix64(uint64_t x) 
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const 
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

vector<vector<int>> adj;
vector<bool> vis;
ll x, y;
void dfs(int s)
{
    if(s <= 1e5) x++;
    else y++;
    F0R(i, sz(adj[s]))
    {
        if(!vis[adj[s][i]])
        {
            vis[adj[s][i]] = true;
            dfs(adj[s][i]);
        }
    }
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    adj.assign(2e5 + 1, vector<int>());
    F0R(i, n)
    {
        int r, c;
        cin >> r >> c;
        adj[r].pb(1e5 + c);
        adj[1e5 + c].pb(r);
    }
    vis.assign(2e5 + 1, false);
    ll res = 0;
    FOR(i, 1, sz(adj))
    {
        if(!vis[i])
        {
            vis[i] = true;
            x = 0; y = 0;
            dfs(i);
            res += x * y;
        }
    }
    cout << res - n;

    return 0;
}

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

using namespace std;

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

    constexpr int MOD = 1'000'000'007;
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    int res = 1;
    map<int, int> cnt;
    cnt[-1] = 3;
    for (int i = 0; i < N; ++i) {
        int mul = cnt[A[i] - 1] - cnt[A[i]];
        res = (1LL * res * mul) % MOD;
        ++cnt[A[i]];
    }
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 5376
# def insertionsort(A,n,g):
#     global cnt
#     for i in range(g,n):
#         v = A[i]
#         j = i - g
#         while j >= 0 and A[j] > v:
#             A[j+g] = A[j]
#             j = j - g
#             cnt += 1
#         A[j+g] = v

def insertionsort(A,n,g):
    global cnt
    for i in range(g,n):
        right = i
        left = i - g
        while left >= 0 and A[left] > A[right]:
            A[right],A[left] = A[left],A[right]
            right = left
            left -= g
            cnt += 1

def shellsort(A,n):
    G = [1]
    x = 0
    while G[x]*3 + 1 <= n:
        G.append(G[x]*3 + 1)
        x += 1

    G = G[::-1]
    for i in range(len(G)):
        insertionsort(A,n,G[i])

    return A,G,cnt


if __name__ == '__main__':
    import math
    n = int(input())
    A = []
    cnt = 0
    for i in range(n):
        x = int(input())
        A.append(x)
    ans,G,cnt = shellsort(A,n)

    #answer
    print(len(G))
    for i in range(len(G)):
        if i == len(G) - 1:
            print(G[i])
        else:
            print(G[i],end = " ")
    print(cnt)
    for i in range(n):
        print(ans[i])



Measured memory_bytes: 45588
def main():
    a,b,k=map(int,input().split())
    ans = [a+i if a+i<=b else a for i in range(k) ]
    ans += [b-k+i+1if a<=b-k+i+1else b for i in range(k)]
    ans = sorted(set(ans))
    print("\n".join(map(str,ans)))
if __name__=="__main__":
    main()

Measured memory_bytes: 3064
R = lambda type_ = "int": list(map(eval(type_), input().split(' ')))

N, H = R()
a, b = 0, []
while N:
    a_, b_ = R()
    b.append(b_)
    a = max(a, a_)
    N -= 1

b.sort()
i = len(b) - 1
while i >= 0 and H > 0 and b[i] >= a:
    H -= b[i]
    i -= 1
    
if i < 0 and H > 0:
    print(len(b) + (H - 1) // a + 1)
elif H <= 0:
    print(len(b) - i - 1)
elif a > b[i]:
    print(len(b) - i - 1 + (H - 1) // a + 1)


Measured memory_bytes: 7512