akhauriyash/Code-Regression huggingface dataset:
use std::io::*;
use std::str::FromStr;

pub 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")
}

pub fn read_n<T: FromStr>(n: usize) -> Vec<T> {
  read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: usize, mut a: Vec<T>) -> Vec<T> {
  match n {
    0 => a,
    _ => {
      a.push(read::<T>());
      read_n_logic(n - 1, a)
    }
  }
}

use std::cmp::{max, min};
use std::collections::BinaryHeap;
use std::collections::HashMap;

fn main() {
  let mut n: i64 = read();
  // let sosuu = vec![0; 100];
  let primes = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47];
  let mut primes_count = vec![0; primes.len()];

  for i in 0..primes.len() {
    // let mut cnt = 0;
    let prime_mum = primes[i];
    let mut a = n;
    while 0 < a {
      a = a / prime_mum;
      primes_count[i] += a;
    }
  }

  let mut ans = 0;

  let mut more_74 = 0;
  let mut more_24 = 0;
  let mut more_14 = 0;
  let mut more_4 = 0;
  let mut more_2 = 0;

  for i in primes_count {
    if 74 <= i {
      more_74 += 1;
    }
    if 24 <= i {
      more_24 += 1;
    }
    if 14 <= i {
      more_14 += 1;
    }
    if 4 <= i {
      more_4 += 1;
    }
    if 2 <= i {
      more_2 += 1;
    }
  }
  println!(
    "{}",
    more_74
      + more_24 * (more_2 - 1)
      + more_14 * (more_4 - 1)
      + ((more_4 * (more_4 - 1)) / 2) * (more_2 - 2)
  );
}


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

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

	vector<int> A(N);

	for (int i = 0; i < N; i++) {
		cin >> A.at(i);
	}

	for (int i = 0; i < N; i++) {
		if (A.at(i) % 2 == 0) {
      if (A.at(i) % 3 == 0 || A.at(i) % 5 == 0 ) {
        continue;
      } else {
        cout << "DENIED" << endl;
        return 0;
      }
		}
	}

	cout << "APPROVED" << endl;
  return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(' ').map(String::toLong).toMutableList()
    val bList = readLine()!!.split(' ').map(String::toLong).toMutableList()
    var total = 0L

    for (i in (n - 1) downTo 0) {
        if (aList[i + 1] >= bList[i]) {
            total += bList[i]
            aList[i + 1] -= bList[i]
            bList[i] = 0
        } else {
            total += aList[i + 1]
            bList[i] -= aList[i + 1]
            aList[i + 1] = 0
        }

        if (aList[i] >= bList[i]) {
            total += bList[i]
            aList[i] -= bList[i]
            bList[i] = 0
        } else {
            total += aList[i]
            bList[i] -= aList[i]
            aList[i] = 0
        }
    }

    println(total)
}

Measured memory_bytes: 84696
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	if(s[2] == s[3] && s[4] == s[5])
		cout << "Yes" << endl;
	else
		cout << "No" << endl; 
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
#define N 510
ll a[N][N];
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    return b?gcd(a%b,b):a;
}
ll gce(ll a,ll b){return a/gcd(a,b)*b;}
int main(){
    vector<ll> p;
    for(ll i=2;p.size()<N*3;i++){
	bool ok=1;for(auto x:p)ok&=i%x>0;
	if(ok)p.push_back(i);
    }
    lol(i,N)lol(j,N){
	if((i+j)%2==0)a[i][j]=p[(i+j)/2]*p[(i-j)/2+2*N];
    }
    lol(i,N)lol(j,N){
	if((i+j)%2==1){
	    ll p=1,dx[]={0,1,0,-1},dy[]={1,0,-1,0};
	    lol(r,4){
		ll xx=j+dx[r],yy=i+dy[r];
		if(xx<0||xx==N||yy<0||yy==N)continue;
		p=gce(p,a[yy][xx]);
	    }
	    a[i][j]=p+1;
	}
    }
    ll maxi=0;
    lol(i,N)lol(j,N)maxi=max(maxi,a[i][j]);
    //cout<<maxi<<endl;
    ll n;cin>>n;
    lol(i,n){
	lol(j,n){if(j)cout<<" ";
	    cout<<a[i+1][j+1];
	}
	cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 5248
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int N = scanner.nextInt();
			int maxValue = 0;
			int maxIndex = 0;
			for (int i = 1; i <= N;i++) {
				int ans = returnEvenCnt(i, 0);
				if (maxValue <= ans) {
					maxIndex = i;
					maxValue = ans;
				}
			}
			System.out.println(maxIndex);
		}
	}

	private static int returnEvenCnt(int n, int evenCnt) {
		if (n % 2 == 1){
			return evenCnt;
		}
		n /= 2;
		evenCnt++;
		return returnEvenCnt(n, evenCnt);
	}
}

Measured memory_bytes: 21844
import sys
from itertools import product
N = int(input())
s = [0 if c == "o" else 1 for c in input()]
ans =[0]*N
for a,b in product([0,1],[0,1]):
    ans[0:2]=[a,b]
    for i in range(2,N):
        ans[i]=(ans[i-2]+ans[i-1]+s[i-1])%2
    x=(ans[N-2]+ans[N-1]+s[N-1])%2
    y=(ans[N-1]+ans[0]+s[0])%2
    if x==ans[0] and y==ans[1]:
        num=['S' if k==0 else'W' for k in ans]
        print(''.join(num))
        sys.exit()
print(-1)

Measured memory_bytes: 5660
#include <iostream>
using namespace std;
int n,a,b,c;
int rs[3]={0,0,0};
int rr[3]={0,0,0};
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a>>b>>c;
		rr[0]=a+max(rs[1],rs[2]);
		rr[1]=b+max(rs[0],rs[2]);
		rr[2]=c+max(rs[1],rs[0]);
		rs[0]=rr[0];rs[1]=rr[1];rs[2]=rr[2];
	}
	cout<<max(max(rs[0],rs[1]),rs[2]);

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <cmath>
using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// 0 <= unsigned int <= 4.2e9

int main()
{
    int A, B;
    cin >> A >> B;
    int vAmin = A * 100 / 8 - 1;
    while (static_cast<int>(vAmin * 0.08) != A) {
        ++vAmin;
    }
    int vAmax = vAmin;
    while (static_cast<int>(vAmax * 0.08) == A) {
        ++vAmax;
    }
    --vAmax;

    int vBmin = B * 10 - 1;
    while (static_cast<int>(vBmin * 0.1) != B) {
        ++vBmin;
    }
    int vBmax = vBmin;
    while (static_cast<int>(vBmax * 0.1) == B) {
        ++vBmax;
    }
    --vBmax;
    if ((vAmin > vBmax) || (vBmin > vAmax)) {
        cout << -1 << endl;
        return 0;
    }
    int ans = max(vAmin, vBmin);
    cout << ans << endl;
}


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

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)

#define ll long long
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)

#define xx first
#define yy second
#define mp make_pair
//#define end "\n"
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define pdd pair<double,double>
#define ALL(v) (v).begin(), (v).end()

const ll MOD=998244353;
const ll inf=1e18;

#define MODSET(d) if ((d) >= MOD) d %= MOD;
#define MODNEGSET(d) if ((d) < 0) d = ((d % MOD) + MOD) % MOD;


ll power(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)
            ans=(ans*a);
        n>>=1;
        a=(a*a);
    }
    return ans;
}

ll powerMod(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)
            ans=(ans*a)%MOD;
        n>>=1;
        a=(a*a)%MOD;
    }
    return ans;
}

ll lcm(ll a,ll b){
    return a*(b/__gcd(a,b));
}

ll sumdigit(ll n){
    ll sum=0;
    while(n){
        sum+=n%10;
        n=n/10;
    }
    return sum;
}

ll countSetBit(ll a){
    return __builtin_popcount(a);
}

const long sz=1e5+10;

ll length(ll a){
    ll ans=0;
    while(a){
        ans++;
        a=a/10;
    }
    return ans;
}


int main()
{
    fast;
    ll t;
   // cin>>t;
    t=1;
    while(t--){
        ll n;
        
        cin>>n;
        ll a[n],b[n];
        map<ll,ll>mp;
        for(int i=0;i<n;i++){
            cin>>a[i];
            b[i]=a[i];
            mp[a[i]]++;
        }
        sort(a,a+n);
        for(int i=0;i<n;i++){
            if(b[i]==a[n-1]){
                if(mp[a[n-1]]>1)
                    cout<<a[n-1]<<endl;
                else cout<<a[n-2]<<endl;
            }
            else cout<<a[n-1]<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 12160
#include<stdio.h>
#include<string>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include <cmath>
#include <limits>
#include <numeric>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

long long int gcd(ll a,ll b){
    return b != 0 ? gcd(b, a % b) : a;
}
long long int lcm(ll a,ll b){
    ll g=gcd(a,b);
    ll l=a*b/g;
    return l;
}

int main(){
    long long int a,b,c,d;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    long long int l=lcm(c,d);
    long long int lc,ld,lcd;
    lc=b/c-(a-1)/c;
    ld=b/d-(a-1)/d;
    lcd=b/l-(a-1)/l;
    ll ans=lc+ld-lcd;
    printf("%lld\n",b-a+1-ans);
    return 0;
}

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

using namespace std;
int main(){
    string s; cin >> s;
    int i,ans = 0,cnt = 0;
    for(i=0;i<3;i++){
        if(s[i]=='R') cnt++;
        else cnt = 0;
        ans = max(ans,cnt);
    }
    cout << ans << endl;
}

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

int main(){
    int n;
    cin >> n;
    long long int ans = 1LL;
    vector<long long int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++){
        if(a[i] == 0) ans = 0;
    }
    
    if(ans != 0){
        for(int i = 0; i < n; i++){
            if(a[i] <= (long long int)1e18/ans){
                ans *= a[i];
            }else{
                ans = -1;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4036
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      String sn=sc.nextLine();
String[] data={"SUN","MON","TUE","WED","THU","FRI","SAT"};

for(int i=0;i<data.length;i++){
if(sn.equals(data[i])){
System.out.println(7-i);
break;
}
}


	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
    vector<string> a = {"Sunny", "Cloudy", "Rainy"};
    string s;
    cin >> s;
    rep(i,2){
      if(s == a.at(i)) cout << a.at(i+1) << endl;
    }
    if(s== a.at(2)) cout << a.at(0) << endl;
    
  }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

int N,K;
int g[110][110];

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

  cin >> N >> K;
  if (K > (N-1)*(N-2)/2) {
    cout << -1 << endl;
    return 0;
  }
  REP(i,N) {
    for (int j = N-1; j >= 0; j--) if (j != i) g[i][j] = 1;
  }
  int cur = 0;
  REP(i,K) {
    int sum = 0;
    REP(j,N) sum += g[cur][j];
    if (sum == 1) cur++;
    int last = -1;
    for (int j = 0; j < N-1; j++) {
      if (g[cur][j]) {
        g[cur][j] = g[j][cur] = 0;
        break;
      }
    }
  }
  vector<pii> es;
  for (int i = 0; i < N; i++) {
    for (int j = i+1; j < N; j++) {
      if (g[i][j]) es.emplace_back(i+1,j+1);
    }
  }
  cout << es.size() << endl;
  REP(i,es.size()) {
    cout << es[i].first << " " << es[i].second << endl;
  }

  return 0;
}

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



// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    // Failed to predict input format
    string S;
    int Q;
    cin >> S >> Q;
    int reverseFlag = 0;
    for(int i=0;i<Q;i++){
        int T;
        cin >> T;
        if(T==1){
            reverseFlag = 1-reverseFlag;
            continue;
        }
        int F;string C;
        cin >> F >>C;
        F--;
        if(reverseFlag == 1){
            F = 1 -F;
        }
        if(F==0){
            S.insert(0,C);
        }else{
            S += C;
        }
    }
    if(reverseFlag == 1){
        reverse(S.begin(),S.end());
    }
    cout << S << endl;
    return 0;
}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int n;
bool block[5050][5];

void down(int py) {
	for_(y,py,5010) {
		for_(x,0,5) {
			block[y][x] = block[y + 1][x];
			block[y + 1][x] = false;
		}
	}
}

void vanish() {
	for_(y,0,5050) {
		bool van = true;
		
		for_(x,0,5) van &= block[y][x];
		
		if (van) {
			down(y);
			--y;
		}
	}
}

void fall(int dir, int len, int lft) {
	int by = 5010, bx = lft;
	
	while (by > 0) {
		bool end = false;
		
		if (dir) {
			end |= block[by - 1][bx];
		} else {
			for_(x,bx,bx+len) end |= block[by - 1][x];
		}
		
		if (end) break;
		
		--by;
	}
	
	if (dir) {
		for_(y,by,by+len) block[y][bx] = true;
	} else {
		for_(x,bx,bx+len) block[by][x] = true;
	}
}

void play() {
	for_(i,0,n) {
		int a, b, c;
		cin >> a >> b >> c;
		fall(--a, b, --c);
		vanish();
	}
	
	int ans = 0;
	for_(y,0,5050) for_(x,0,5) ans += block[y][x];
	cout << ans << endl;
}

int main() {
	while (cin >> n, n) {
		memset(block, false, sizeof(block));
		play();
	}
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 2020000;
int n,m,k,a[N],b[N],sta[N],top;
int main() {
	read(n);read(m);read(k);
	static char S[N];
	scanf("%s",S+1);rep(i,1,n)a[i]=S[n-i+1]-'0';
	scanf("%s",S+1);rep(i,1,m)b[i]=S[m-i+1]-'0';
	sta[0]=1e9;//sta[]: 01&10 in [pos+1..inf]
	per(i,max(n,m),1)
		if(a[i]&&b[i]){
			int now=k,pos=i;Vi tmp;
			while(now){
				if(!a[pos+1]&&!b[pos+1]){
					int mn=min(now,sta[top]-pos-1);
					a[pos]=b[pos]=0;a[pos+mn]=b[pos+mn]=1;pos+=mn;now-=mn;
				}
				else{
					int mx=0;now--;
					for(int i=pos;;i++){if(a[i])a[i]=0;else{a[i]=1;umax(mx,i);break;}}
					for(int i=pos;;i++){if(b[i])b[i]=0;else{b[i]=1;umax(mx,i);break;}}
					if(a[mx]&&b[mx]){
						rep(i,pos,mx)if(a[i]+b[i]==1)tmp.pb(i);
						while(top&&sta[top]<=mx)top--;
						pos=mx;
					}
					else{
						rep(i,pos,mx)if(a[i]+b[i]==1)tmp.pb(i);
						while(top&&sta[top]<=mx)top--;break;
					}
				}
			}
			per(i,SZ(tmp)-1,0)sta[++top]=tmp[i];
		}
		else if(a[i]||b[i])sta[++top]=i;
	per(i,n+k+2,1)if(a[i]){n=i;break;}
	per(i,m+k+2,1)if(b[i]){m=i;break;}
	per(i,n,1)printf("%d",a[i]);puts("");
	per(i,m,1)printf("%d",b[i]);puts("");
	return 0;
}


Measured memory_bytes: 22656
import std.stdio, std.algorithm, std.string, std.string, std.conv, std.array, std.range, std.math;
int readint() { return readln.chomp.to!int; }
int[] readints() { return readln.split.to!(int[]); }

void main() {
    auto hwd = readints();
    int h = hwd[0], w = hwd[1], d = hwd[2];
    int[] px = new int[h*w+5];
    int[] py = new int[h*w+5];
    foreach(y; 0..h) {
        int[] a = readints();
        foreach(int x, int v; a) {
            px[v] = x;
            py[v] = y;
        }
    }

    int[] ds = new int[h*w+5];
    foreach_reverse(i; 0..h*w-d+1) {
        ds[i] = ds[i+d] + abs(px[i] - px[i+d]) + abs(py[i] - py[i+d]);
    }
    
    int q = readint();
    while(q--) {
        int[] lr = readints();
        writeln(ds[lr[0]] - ds[lr[1]]);
    }
    string _ = readln(); // dbg
}

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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((int)(x).size())
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define ALL(a)  (a).begin(),(a).end()

int main() {
	int a, b;
	cin >> a >> b;
	if (a > b) {
		FOR(i, 1, a) {
			cout << b;
		}
		cout << endl;
	}
	else {
		FOR(i, 1, b) {
			cout << a;
		}
		cout << endl;
	}
	return(0);
}

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

int main(){
	int N;
	int *arr = 0;
	cin >> N;
	arr = new int[N];
	int max = 0, maxp = 0;
	for (int i = 0; i < N; i++){
		int t;
		cin >> t;
		arr[i] = t;
		if (max < t){
			max = t;
			maxp = i;
		}
	}
	int sum = 0;
	for (int i = 0; i < N; i++){
		if (i == maxp){
			continue;
		}
		sum += arr[i];
	}
	if (max < sum){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

	delete arr;
	
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

# +, -, +, -, ...
sum = 0
count = 0
for i in range(n):
    sum += a[i]
    if i % 2 == 0:
        if sum <= 0:
            count += abs(sum) + 1
            sum = 1
    else:
        if sum >= 0:
            count += abs(sum) + 1
            sum = -1

# -, +, -, +, ...
sum2 = 0
count2 = 0
for i in range(n):
    sum2 += a[i]
    if i % 2 == 0:
        if sum2 >= 0:
            count2 += abs(sum2) + 1
            sum2 = -1
    else:
        if sum2 <= 0:
            count2 += abs(sum2) + 1
            sum2 = 1

print(min(count, count2))


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

int main(void) {
    int n,m,sum=0,ans;
    cin>>n;
    int t[150000];
    for(int i=0;i<n;i++) {
        cin>>t[i];
        sum+=t[i];
    }
    cin>>m;
    for(int i=0;i<m;i++) {
        ans=sum;
        int p,x;
        cin>>p>>x;
        if(t[p-1]<=x) {
            ans+=x-t[p-1];
        } else {
            ans-=t[p-1]-x;
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
#define co(a) cout<<a<<endl
#define sz size()
#define bgn begin()
#define en end()
#define pb(a) push_back(a)
#define pop pop_back
#define V vector
#define P pair
#define V2(a,b,c) V<V<int>> a(b,V<int>(c))
#define V2a(a,b,c,d) V<V<int>> a(b,V<int>(c,d))
#define incin(a) int a; cin>>a
//#define min min<int>
//#define max max<int>
template<class T>
 void cou(vector<vector<T>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}
/*template<>
 void cou(vector<vector<char>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}*/
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
 bool prime(int a){
   if(a<2)
     return false;
   else if(a==2)
     return true;
   else if(a%2==0)
     return false;
   double b=sqrt(a);
    for(int i=3;i<=b;i+=2){
      if(a%i==0){
        return false;
      }
    }
   return true;
 }
struct Union{
  vector<int> par;
  Union(int n){
	par= vector<int>(n, -1);
  }
  int find(int x){
    if(par[x]<0)
      return x;
    else
      return par[x]=find(par[x]);
  }
  bool same(int a,int b){
    return find(a)==find(b);
  }
  int Size(int a){
    return -par[find(a)];
  }
  void unite(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b)
      return;
    if(Size(b)>Size(a))
      swap<int>(a,b);
    par[a]+=par[b];
    par[b]=a;
  }
};
int ketas(int a){
  string b=to_string(a);
  int c=0;
  fo(i,keta(a)){
    c+=b[i]-'0';
  }
  return c;
}
/*struct aa{
	vector<int> gt;
  aa(int n){
	gt= vector<int>(n, 1);
  }
	void c(V<int> d,int b){
	if(d[b]==0){
		gt[d[b]-1]++;
		gt[gt.sz-1]++;
	}
	else{
		gt[d[b]-1]++;
		c(d,d[d[b]]-1);
	}
}
void cok(int a){
	cout<<gt[a-1]<<endl;
	fo(i,a-1)
	cout<<gt[i]<<endl;
}
};
*/
signed main(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<(a+1-b)*(a+1-c)<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

string str;
vs ans;

void solve(int i, string s, string used)
{
  if(i == str.size()){
    ans.push_back(s);
    return;
  }
  if(str[i] == 'a'){
    solve(i + 1, s + str[i], used);
    if(used.find(str[i]) == -1) solve(i + 1, s + (char)(str[i] + 1), used + str[i]);
    return;
  }
  if(str[i] != 'z' && used.find(str[i]) == -1){
    solve(i + 1, s + (char)(str[i] + 1), used + str[i]);
  }
  if(s.find(str[i]) != -1){
    solve(i + 1, s + str[i], used);
  }

  return;
}

int main(void) {

    while(cin >> str, str != "#"){

        solve(0,"","");

        sort(all(ans));
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        cout << ans.size() << endl;
        if(ans.size() <= 10){
            rep(i,ans.size()){
                cout << ans[i] << endl;
            }
        }else{
            rep(i,5){
                cout << ans[i] << endl;
            }
            rep(i,5){
                cout << ans[ans.size() - 5 + i] << endl;
            }
        }
        ans.clear();
    }
}



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

int main ()
{
    int n,w;
    cin>>n>>w;
    vector<int> city(n,0);
    
    for (int i=0;i<2*w;i++)
    {
        int k;
        cin>>k;
        city.at(k-1)+=1;
    }

    for(int i=0;i<n;i++)
    {
        cout<<city.at(i)<<endl;
    }
}


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

#define FILE
#define fr first
#define se second

using namespace std;

const long long N = 2e5 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

long long h;
int main()
{
    #ifdef FILEs
        freopen("input.txt", "r", stdin);
        /// freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);

    cin >> h;
    long long x = 1;
    long long res = x;
    while(x * 2 <= h){
        x *= 2;
        res += x;
    }
    cout << res << "\n";
}



Measured memory_bytes: 256
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=2000+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
	return c;
}

int n,k,dp[N][N];

int main() {
	n=read(),k=read();
	dp[0][n+1]=1;
	for (int i=1;i<k;++i) {
		int s=dp[i-1][n-i+2];
		for (int j=n-i+1;j>=2;--j)
			s=(s+dp[i-1][j])%mod,dp[i][j]=s;
	}
	int ans=0;
	for (int i=2;i<=n-k+2;++i) ans=(ans+dp[k-1][i])%mod;
	if (n!=k) ans=1ll*ans*qpow(2,n-k-1)%mod;
	printf("%d\n",ans);
	return 0;
}

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

#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define mod 1000000007
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0);
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(ll x=j;x<n;x++)
#define repr(x,j,n)for(ll x=j;x>n;x--)
typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;
const int N=2e6+7;

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
    if(b&1)
    r=(r*a)%m;
    b=b/2;
    a=(a*a)%m;
    }
    return r%m;
}
int main()
{
    int w,s;
    cin>>s>>w;
    if(w>=s)cout<<"unsafe";
    else cout<<"safe";
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}

Measured memory_bytes: 3632
main :: IO()
main = do
    [w,a,b] <- map read . words <$> getLine
    print $ getsolve w a b

getsolve :: Int -> Int -> Int -> Int
getsolve w a b
    | br < al			= al - br
    | ar < bl			= bl - ar
    | otherwise			= 0
    where al = a
          ar = a + w
          bl = b
          br = b + w





Measured memory_bytes: 508
#[allow(unused_imports)]
use std::cmp;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::vec::Vec;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{d: usize,}
    println!(
        "{}",
        if d == 25 {
            "Christmas"
        } else if d == 24 {
            "Christmas Eve"
        } else if d == 23 {
            "Christmas Eve Eve"
        } else if d == 22 {
            "Christmas Eve Eve Eve"
        } else {
            ""
        }
    )
}


Measured memory_bytes: 4352
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      int total=sc.nextInt();
      int totalleg=sc.nextInt();
      if(totalleg>=2*total&&totalleg<=4*total&&totalleg%2==0){
         System.out.println("Yes");
      }else{
         System.out.println("No");
      }  
   }
}
      
      


Measured memory_bytes: 35776
def main():
    n, k = map(int, input().split())
    if k == 0:
        print(n * n)
        return
    ans = 0
    for i in range(k + 1, n + 1):
        p, q = divmod(n, i)
        ans += p * (i - k) + max(q - k + 1, 0)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
//
//  main.cpp
//  ABC136E
#include <iostream>
#include <vector>
#include <set>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;int main(int argc, const char * argv[]) {
    ll n,k;
    cin>>n>>k;
    vector<int>a(n);
    ll sum=0; // 操作後も合計は変わらないことを利用する
    rep(i,n){
        cin>>a.at(i);
        sum+=a.at(i);
    }
    set<ll> candidates; // 合計から、最大公約数の候補を列挙するset　重複なし
    for(int i=1;i*i<=sum;i++){
        if(sum%i==0){
            candidates.insert(i);
            candidates.insert(sum/i);
        }
    }
    ll ans=1;
    for(ll x : candidates){
        ll need;
        vector<ll>r(n);
        rep(i,n) r.at(i)=a.at(i)%x;
        sort(r.begin(),r.end());
        ll tot=0;
        rep(i,n) tot+=r.at(i);
        ll right=tot/x;
        ll left=n-right;
        need=0;
        rep(i,left){
            need+=r.at(i);
        }
        if(need<=k) ans=max(ans,x);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3244
#include<bits/stdc++.h>
using namespace std;
int a,zs,s;
int main()
{
    cin>>a;
    zs=a%10,s=(a-a%100)/100;
    if(zs==s)
	cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<cmath>

using namespace std;
int k(int N){
  if(N > 0){
    return k(N - 1) * N;
  }
  else{
    return 1;
  }
}

double res = 0;
double dist(int x1, int y1, int x2, int y2){
  return sqrt((double)(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double av(int *x, int *y, int N){
  for(int i = 0; i < N; i++){
    for(int j = i + 1; j < N; j++){
      res += dist(x[i], y[i], x[j], y[j]) * k(N - 1) * 2;
    }
  }
}

int main(){
  int N, x[10], y[10];
  scanf("%d", &N);
  for(int i = 0; i < N; i++){
    scanf("%d%d", &x[i], &y[i]);
  }
  av(x, y, N);
  printf("%lf\n", res / k(N));
  return 0;
}



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

const ll MAXN = 200000;

ll N, flag=0, tmp=0, mid=0;
vector<ll> A(MAXN, 0);

signed main(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> A[i];
    ll ng = -1;
    ll ok = 1000000001;
    while(1){
        //ll ngnum = ng*2;
        //ll oknum = ok*2;
        //cout << "ng : " << ng << " ok : " << ok << endl;
        //ll mid = (ng+ok)/2;
        //ll tmp = (ng+ok)/2;
        mid = (ng+ok)/2;
        tmp = (ng+ok)/2;
        for(int i=0;i<N-1;i++) {
            tmp=A[i]-tmp;
        }
        if(tmp+mid==A[N-1]) break;
        else if(tmp+mid>A[N-1]) {
            ok = mid;
        }
        else {
            ng = mid;
        }
        //cout << " mid : " << mid << " tmp : " << tmp << " A : " << A[N-1] << endl;
        //cout << endl;
    }
    tmp = mid;
    for(int i=0;i<N;i++) {
        if(i) cout << " ";
        cout << 2*tmp;
        tmp=A[i]-tmp;
    }
    return 0;
}

Measured memory_bytes: 2816
import qualified Data.ByteString.Char8 as B
import Data.Maybe
main = putStrLn.solve.map(fst.fromJust.B.readInt).B.words=<<B.getLine
solve (a:b:_) = if or [x`mod`3==0 |x<-[a,b,a+b]] then "Possible" else "Impossible"

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

int main(){
	long long hoge,hoge2;
	cin>>hoge>>hoge2;
	bitset<32> a(hoge),b(hoge2);
	cout<<(a&b)<<endl<<(a|b)<<endl<<(a^b)<<endl;
	return 0;
}



Measured memory_bytes: 3152
#!/usr/bin/env python3
import sys
from itertools import chain

def solve(X: int, N: int, p: "List[int]"):
    p = set(p)
    for d in range(0, 100):
        x = X - d
        if x not in p:
            return x
        x = X + d
        if x not in p:
            return x

def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    # X, N, p = map(int, line.split())
    X = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(X, N, p)
    print(answer)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9212
/*
ID: computerbox --> Huseyn Hajiyev
LANG: C++
TASK: target_mode_on
*/
#include <bits/stdc++.h>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define _CRT_SECURE_NO_WARNINGS
//#include <boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;
#define FAST_READ ios_base::sync_with_stdio(0);
#define in freopen("input.txt", "r", stdin);
#define out freopen("output.txt", "w", stdout);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define COUT(n, a) cout<< fixed << setprecision(a) << n<<endl
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
#define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
#define MAXN 2000
//cin.ignore (7777, '\n');

using namespace std;

#define debug(args...)(Debugger()) , args
class Debugger
{
  public:
  Debugger(const std::string& _separator=", ") :
  first(true),separator(_separator){}
  template<typename ObjectType>
  Debugger& operator,(const ObjectType& v)
  {
        if(!first)cerr<<separator;
        cerr<<v;
        first=false;
        return *this;
  }
  ~Debugger() {cerr<<endl;}      
  private:
    bool first;
    string separator;
};
 
template <typename T1, typename T2>
inline ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p)
{
   return os<<"("<<p.first<<", "<<p.second<<")";
}
template<typename T>
inline ostream &operator<<(ostream & os,const vector<T>& v)
{
    bool first=true;
    os<<"[";
    for(unsigned ll i=0;i<v.size();i++)
    {
        if(!first)os<<", ";
        os<<v[i];
        first=false;
    }
        return os<<"]";
}
template<typename T>
inline ostream &operator<<(ostream & os,const set<T>&v)
{
    bool first=true;
    os<<"[";
    for(typename set<T>::const_iterator ii=v.begin();ii!=v.end();++ii)
    {
        if(!first)os<<", ";
        os<<*ii;
        first=false;
    }
    return os<<"]";
}
template<typename T1, typename T2>
inline ostream &operator<<(ostream & os,const map<T1, T2>&v)
{
        bool first=true;
        os<<"[";
        for(typename map<T1,T2>::const_iterator ii=v.begin(); ii!=v.end();++ii)
        {
            if(!first)os<<", ";
            os<<*ii;
            first=false;
        }
        return os<<"]";
}
ll a,b,c;
vector<ll>massiv;

int main(){
FAST_READ;
//cin.tie(0);
cin>>a>>b>>c;
massiv.pb(a);
massiv.pb(b);
massiv.pb(c);
sort(all(massiv));
cout<<(massiv[2]*10+massiv[1])+massiv[0]<<endl;








return 0;
} 


Measured memory_bytes: 764
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;


namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Anser(new ConsoleInput(Console.In, ' '));
        }

        public void Anser(ConsoleInput Input)
        {
            // 解答
            var InputData = Input.ReadIntArray(2);

            if(InputData[1] % InputData[0] == 0)
            {
                Console.WriteLine(InputData.Sum());
            }
            else
                Console.WriteLine(Math.Abs(InputData[0] - InputData[1]));
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader Stream;
        private char Separator = ' ';
        private Queue<string> InputStream;

        public ConsoleInput(System.IO.TextReader Stream, char Separator = ' ')
        {
            this.Separator = Separator;
            this.Stream = Stream;
            InputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if (InputStream.Count != 0)
                {
                    return InputStream.Dequeue();
                }

                string[] splitStrs = Stream.ReadLine().Split(Separator);

                for (int i = 0; i < splitStrs.Length; ++i)
                {
                    InputStream.Enqueue(splitStrs[i]);
                }

                return InputStream.Dequeue();
            }
        }

        public string ReadLine { get { return Stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}

        public string[] ReadStrArray(long N) 
        { 
            var inputStrArray = new string[N];
            for (long i = 0; i < N; ++i)
            {
                inputStrArray[i] = Read;
            } 
            
            return inputStrArray;
        }

        public int[] ReadIntArray(long N) 
        { 
            var inputIntArray = new int[N];
            for (long i = 0; i < N; ++i)
            {
                inputIntArray[i] = ReadInt;
            }
           
            return inputIntArray;
        }

        public long[] ReadLongArray(long N) 
        { 
            var inputLongArray = new long[N];
            for (long i = 0; i < N; ++i)
            {
                inputLongArray[i] = ReadLong;
            }
            
            return inputLongArray;
        }
    }
}

Measured memory_bytes: 13396
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long i64;
const int MOD = 924844033;
const int MAXN = 200000 + 10;

int N;
int A[MAXN * 4], B[MAXN * 4], rev[MAXN * 4];
int fact[MAXN], inv[MAXN], siz[MAXN];

vector <int> Adj[MAXN];

template <class T>
inline T modularExp(T base, T exp)
{
	T ret(1);

	while(exp)
	{
		if(exp & 1)
			ret = 1LL * ret * base % MOD ;
		base = 1LL * base * base % MOD ;
		exp = exp >> 1;
	}

	return ret;
}

namespace NumberTheoryTransformation
{

const int PrimitiveRoot = 5;

inline int Get_wn(int i)
{
	return modularExp(PrimitiveRoot, (MOD - 1) / (i << 1));
}

void NTT(int * coef, int n, int f)
{
	for(int i = 0; i < n; i++)
		if(i < rev[i])
			swap(coef[i], coef[rev[i]]);

	for(int i = 1; i < n; i = i << 1)
	{
		int x, y, wn = Get_wn(i);

		for(int j = 0; j < n; j = j + i * 2)
			for(int k = 0, w = 1; k < i; k++, w = 1LL * w * wn % MOD)
				x = coef[j + k], y = 1LL * coef[j + k + i] * w % MOD,
				coef[j + k] = (x + y) % MOD, coef[j + k + i] = (x - y) % MOD;
	}

	if(f == 1)		// Inverted?
		return;
	reverse(coef + 1, coef + n);
	int inverse = modularExp(n, MOD - 2);
	for(int i = 0; i < n; i++)
		coef[i] = 1LL * coef[i] * inverse % MOD;
}

void convolution(int n)
{
	NTT(A, n, 1), NTT(B, n, 1);
	for(int i = 0; i < n; i++)
		A[i] = 1LL * A[i] * B[i] % MOD;
	NTT(A, n, -1);
}

}

void prepare()
{
	fact[0] = 1;
	for(int i = 1; i < MAXN; i++)
		fact[i] = 1LL * fact[i-1] * i % MOD;

	inv[MAXN - 1] = modularExp(fact[MAXN-1], MOD - 2);
	for(int i = MAXN - 1; i > 0; i--)
		inv[i-1] = 1LL * inv[i] * i % MOD;
}

void DFS(int cur)
{
	siz[cur] = 1;

	for(int to : Adj[cur])
	{
		if(siz[to])
			continue;
		DFS(to);

		siz[cur] += siz[to];
		A[siz[to]] --, A[N - siz[to]]--;
	}
}

int main()
{
	int s, l = 0;
	prepare();

	scanf("%d", &N), A[N] = N;

	for(int i = 1; i < N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		Adj[u].push_back(v), Adj[v].push_back(u);
	}

	DFS(1);

	for(int i = 1; i <= N; i++)
		A[i] = 1LL * A[i] * fact[i] % MOD;
	for(int i = 0; i <= N; i++)
		B[i] = inv[N - i];

	for(s = 1; s <= N * 2; s = s * 2)
		l++;
	for(int i = 0; i < s; i++)
		rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (l - 1)));

	NumberTheoryTransformation::convolution(s);
	for(int i = 1; i <= N; i++)
		printf("%lld\n", 1LL * (A[N + i] + MOD) * inv[i] % MOD);
}


Measured memory_bytes: 32768
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#define INF 1e9
#define MAX_N 301

using namespace std;

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

int N;
ll A[MAX_N][MAX_N];

ll check() {
    ll res = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            bool flag = false;
            for (int k = 0; k < N; ++k) {
                if (i == j || j == k || k == i) continue;
                if (A[i][j] > A[i][k] + A[k][j]) {
                    return -1;
                } else if (A[i][j] == A[i][k] + A[k][j]) {
                    flag = true;
                }
            }
            if (flag) {
                res += A[i][j];
            }
        }
    }
    return res;
}


int main() {
    cin >> N;
    ll sum = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> A[i][j];
            sum += A[i][j];
        }
    }
    
    ll res = check();
    if (res == -1) {
        cout << -1 << endl;
    } else {
        cout << (sum - res) / 2 << endl;
    }
    
    return 0;
}


Measured memory_bytes: 896
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include<math.h>
#include<bitset>
#include<iomanip>
#include<queue>
using namespace std;

int main() {
	int A, P; cin >> A >> P;
	cout << (3 * A + P) / 2 << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mod 1000000007
// #define mod 998244353
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll power[401][401], presum[401][401];
	for (int i = 1; i <= 400; i++)
	{
		power[i][0] = 1;
		for (int j = 1; j <= 400; j++)
		{
			power[i][j] = (power[i][j - 1] * i) % mod;
		}
	}
	for (int j = 0; j <= 400; j++)
	{
		presum[0][j] = j;
	}
	for (int i = 1; i <= 400; i++)
	{
		presum[i][0] = 0;
		for (int j = 1; j <= 400; j++)
		{
			presum[i][j] = (presum[i][j - 1] + power[j][i]) % mod;
		}
	}
	int n, c;
	cin >> n >> c;
	int a[n + 1], b[n + 1];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i + 1];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> b[i + 1];
	}
	ll dp[n + 1][c + 1];
	for (int j = 0; j <= c; j++)
	{
		dp[0][j] = (j == 0);
	}
	for (int i = 0; i < n; i++)
	{
		for (int t = 0; t <= c; t++)
		{
			ll ans = 0;
			for (int r = 0; r <= t; r++)
			{

				ans += (presum[r][b[i + 1]] - presum[r][a[i + 1] - 1]) * dp[i][t - r];
				ans %= mod;
			}
			ans += mod;
			ans %= mod;
			dp[i + 1][t] = ans;
		}
	}
	cout << dp[n][c] << endl;
	return 0;
}

Measured memory_bytes: 4096
n=int(input())
a=[]
for i in range(2):
  a.append(list(map(int,input().split())))
ans=0
for i in range(n):
  tmp=0
  tmp+=sum(a[0][0:i+1])
  tmp+=sum(a[1][i:])
  ans=max(ans,tmp)
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define CEIL(a,b) (((a) + ((b)-1)) / (b))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP_ll(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VREP_int(v) for(std::vector<int>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;


int main(int argc, const char * argv[]) {
	int N;
	cin >> N ;

	vector<int> unit;
	unit.push_back(1);
	int d = 6;
	while(d <= N){
		unit.push_back(d);
		d*=6;
	}
	d = 9;
	while(d <= N){
		unit.push_back(d);
		d*=9;
	}

	int dp[N+1];

	dp[0]=0;
	FOR(i,1,N){
		dp[i] = 1000000;
		VREP_int(unit){
			if(i-*itr>=0){
				dp[i] = min(dp[i],dp[i-*itr]+1);
			}
		}
	}
	println(dp[N]);


	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int q=1e9+7;
typedef long long giant;
typedef pair<giant,giant> Pair;
typedef pair<int,int> Data;
namespace num {
	const int maxn=91;
	giant F[maxn];
	vector<Pair> a[maxn];
	void init() {
		F[0]=F[1]=1;
		for (int i=2;i<maxn;++i) F[i]=F[i-1]+F[i-2];
		assert(F[maxn-1]>2e18);
		a[1].emplace_back(1,2);
		a[1].emplace_back(1,3);
		for (int i=2;i+2<maxn;++i) {
			for (const Pair &pr:a[i-1]) {
				Pair nw(pr.second,pr.first+pr.second);
				giant lim=F[i-1]+F[i+2];
				for (;nw.second<lim;nw.second+=nw.first) a[i].push_back(nw);
			}
		}
	}
	int __initer__=(init(),0);
}
int T,ans;
giant A,B,cnt;
Data work() {
	scanf("%lld%lld",&A,&B);
	if (A>B) swap(A,B);
	ans=1;
	for (int i=1;num::F[i]<=A && num::F[i+1]<=B;++i) ans=i;
	if (ans==1) return Data(1,A%q*B%q);
	cnt=0;
	for (const Pair &pr:num::a[ans-1]) {
		if (pr.second<=A) cnt=(cnt+(B-pr.first)/pr.second)%q;
		if (pr.second<=B) cnt=(cnt+(A-pr.first)/pr.second)%q;
	}
	return Data(ans,cnt);
}
int main() {
	for (scanf("%d",&T);T--;) {
		Data ans(work());
		printf("%lld %lld\n",ans.first,ans.second);
	}
	return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define out(a) cout << a << endl
using namespace std;
typedef long long ll;

int gcd2(int a, int b){
    if (a%b==0){
        return b;
    } else {
        return gcd2(b, a%b);
    }
}
int gcd3(int a, int b, int c){
    if (a%c==0 && b%c==0){
        return c;
    } else if (a%c==0) {
        return gcd2(c, b);
    } else if (b%c==0) {
        return gcd2(c, a);
    } else {
        if (a%c < b%c) return gcd3(c, b%c, a%c);
        else return gcd3(c, a%c, b%c);
    }
}

int main() {
    int K;
    ll count=0;
    cin >> K;
    FOR(a, 1, K+1){
    FOR(b, 1, K+1){
    FOR(c, 1, K+1){
        count += gcd3(a,b,c);
    }
    }
    }
    out(count);
}




Measured memory_bytes: 3596
#define INT_MAX 2147483647
#include<bits/stdc++.h>
using namespace std;

const int MAX_N=10000000;
 
int n;
int dat[MAX_N*2-1];
 
void init(){
    int i=n;
    n=1;

	while (n<i)n*=2;
	
	fill(dat,dat+n*2,INT_MAX);
}
 
void update(int i,int x){
	i+=n-1;
	dat[i]=x;
	while(i>0){
		i=(i-1)/2;
		dat[i]=min(dat[i*2+1],dat[i*2+2]);
	}
}
 
int query(int a,int b,int k,int l,int r){
	if(r<a||b<l)return INT_MAX;
	if(a<=l&&r<=b) return dat[k];
	else{
		int vl=query(a,b,k*2+1,l,(l+r)/2);
		int vr=query(a,b,k*2+2,(l+r)/2+1,r);
	    return min(vl,vr);
	}
}

int main(){
    int q,a,b,c;
    cin>>n>>q;
    
    init();
    
    while(q--){
        cin>>a>>b>>c;
        if(a)cout<<query(b,c,0,0,n-1)<<endl;
        else update(b,c);
        
        /*for(int i=0;i<n*2;i++){
            cout<<dat[i]<<" ";
        }
        cout<<endl;*/
    }
    
}

Measured memory_bytes: 4128