akhauriyash/Code-Regression huggingface dataset:
n = input()
A = map(int, raw_input().split())
fact = [0]*(n+1)
frev = [0]*(n+1)
MOD = 10**9 + 7
frev[0] = fact[0] = 1

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)

def comb(n, k):
    return (((fact[n] * frev[k]) % MOD) * frev[n-k]) % MOD

left = 0; right = 0
B = [0]*(n+1)
for a in A:
    B[a] += 1
p = B.index(2)
while A[left] != p:
    left += 1
while A[-1-right] != p:
    right += 1
mid = n+1 - left - right
ans = []
for k in xrange(1, n+2):
    res = 0
    if 0 <= k <= n-1:
        res += comb(n-1, k)
    if 0 <= k-1 <= n-1:
        if k-1 <= left+right:
            res += comb(left+right, k-1) + 2*(comb(n-1, k-1) - comb(left+right, k-1))
        else:
            res += 2*comb(n-1, k-1)
    if 0 <= k-2 <= n-1:
        res += comb(n-1, k-2)
    res %= MOD
    ans.append(res)
print "\n".join(map(str, ans))

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

using ll=long long; 

void solve(){
	int n;
	cin>>n;
	string s,t;
	cin>>s>>t;
	for(int i=0; i<s.size(); i++){
		cout<<s[i]<<t[i];
	}	
	cout<<endl;
}

signed main(){
	//while(1)
	solve();
}

Measured memory_bytes: 256
//vec[i]の範囲外エラー表示
#define _GLIBCXX_DEBUG
//includeとusing
#include <bits/stdc++.h>
using namespace std;
//型名省略
using ll = long long;
using st = string;
using vl = vector<long long>;
using vvl = vector<vector<long long>>;
using vc = vector<char>;
using vvc = vector<vector<char>>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using pcc = pair<char, char>;
//定数
const ll INF = 1e9;
const ll MOD = 1e9+7;
const vl dx = {1,0,-1,0,1,0,-1,0};
const vl dy = {0,1,0,-1,0,1,0,-1};
//マクロ
#define rep(i,n) for(ll i = 0; i < (ll) n; i++)
#define rrep(i,n) for(ll i = (ll) n - 1; i >= 0;i--)
#define REP(i,x,n) for(ll i = (ll) x; i < (ll) n; i++)
#define RREP(i,x,n) for(ll i = (ll) n - 1; i >= x; i--)
#define each(i,A) for(ll i: (vl) A)
#define all(A) A.begin(), A.end()
#define Size(A) ll(A.size())
//入力
template<typename T> T input() {T x; cin >> x; return x;}
//正誤判定
void Yes(bool ans){cout << (ans? "Yes" : "No") << endl;}
void YES(bool ans){cout << (ans? "YES" : "NO") << endl;}
//余り切り上げ
ll ceil(ll a,ll b) {return (a + b - 1) / b;}
//最大値・最小値
template <typename T> bool chmax(T &a, const T& b) {if(a < b) {a = b; return true;} return false;}
template <typename T> bool chmin(T &a, const T& b) {if(a > b) {a = b; return true;} return false;}
//最大公約数
ll gcd(ll a,ll b){if(a<b)swap(a,b); if(a%b==0)return b; return gcd(b,a%b);}
//最小公倍数
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
//n乗の余り
ll modPow(ll x,ll n,ll mod){if(n==0)return 1; if(n%2==0)return modPow(x*x,n/2,mod)%mod; return x%mod*modPow(x,n-1,mod)%mod;}


/*--------------------------------------------------------------------------*/

//組み合わせ
const ll MAX = 2100;
vl fac(MAX), finv(MAX), inv(MAX);

void COMinit() {
    fac[0] = 1;
    fac[1] = 1;
    finv[0] = 1;
    finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//main関数
int main() {
    ll s; cin >> s;
    ll ans = 0;

    COMinit();

    REP(i,1,s / 3 + 1){
        ans += COM(s - 2 * i - 1, i - 1);
        ans %= MOD;
    }
    cout << ans << endl;
}



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

typedef long long ll;
using namespace std;

int main()
{
	ll a, b, v, w, t; 
	cin >> a >> v >> b >> w >> t;

	if (a == b)
		cout << "YES\n";
	else if (v < w)
		cout << "NO\n";
	else
		cout << ((abs(a-b) > (v-w) * t) ? "NO\n" : "YES\n");
	return 0;
}

Measured memory_bytes: 3636
arr=[]
for i in range(3):
    arr.append(list(map(int, input().split())))
    arr[i][0]=arr[i][0]-arr[i][1]
    arr[i][1]=arr[i][1]-arr[i][2]
    arr[i][2]=0
if arr[0]==arr[1] and arr[1]==arr[2]:
    print("Yes")
else:
    print("No")


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

using namespace std;
int main(){
	int i,j,k,x,n,d = 0,cnt = 1,ans = 0;
	vector<int> v;
	cin >> n;
	x = n;
	while(x>0){
		x /= 10;
		d++;
	}
	cnt = 9;
	for(j=3;j<=d;j++){
		cnt *= 3;
		for(i=0;i<cnt;i++){
			v.clear();
			x = i;
			bool flag[3];
			flag[0] = false; flag[1] = false; flag[2] = false;
			for(k=0;k<j;k++){
				flag[x%3] = true;
				v.push_back(3 + 2*(x%3));
				x /= 3;
			}
			int res = 0;
			if(flag[0] && flag[1] && flag[2]){
				for(k=0;k<j;k++){
					res *= 10;
					res += v[k];
				}
				if(res<=n) ans++;
			}
		}
	}
	cout << ans << endl;
}
		
		

Measured memory_bytes: 256
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
if N == 1:
    print('Hello World')
else:   
    a, b = [int(sys.stdin.buffer.readline()) for _ in range(2)]
    print(a + b)



Measured memory_bytes: 13828
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[][] ab= new int[n][2];
        for(int i=0;i<n;i++){
            ab[i][0] = Integer.parseInt(sc.next());
            ab[i][1] = Integer.parseInt(sc.next());
        }

        Arrays.sort(ab,new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1]-o2[1];
			}
        });
        int t = 0;
        for(int i=0;i<n;i++){
            t+=ab[i][0];
            if(t>ab[i][1]){
                System.out.print("No");
                System.out.flush();
                return;
            }
        }
        System.out.print("Yes");
        System.out.flush();
        return;
    }
}

Measured memory_bytes: 74284
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>

using namespace std;

#define MOD 1000000007

int main(){

   int A,B;
   cin>>A>>B;
   
   if(A+B==15) cout<<"+"<<endl;
   else if(A*B==15) cout<<"*"<<endl;
   else cout<<"x"<<endl;
}


Measured memory_bytes: 256
/*THERE'S ALWAYS SOMETHING , NOT THAT YOU WOULD UNDERSTAND . YOU ARE LIKE MY SISTER ,
 EVERYTHING ALWAYS CAME EASY TO HER .
 SHE'S A FIRE BENDING PRODIGY AND EVERY ONE ADORE HER . MY FATHER SAYS
 SHE WAS BORN LUCKY ,HE SAYS I WAS LUCKY TO BE BORN . I DON'T NEED LUCK THOUGH .
 I DON'T WANT IT . I'VE ALWAYS HAD TO STRUGGLE AND FIGHT
 AND THAT'S MADE ME STRONG . IT MADE ME WHO I AM .*/
#include<bits/stdc++.h>
using namespace std;
char grid[1024][1024];  //dp[i] = length of longest path starting at i;
int solve(int n,int m)
{
   long long int dp[n+1][m+1];
   dp[n][m]=1;
   for(int i=n;i>=1;i--)
   {
       for(int j=m;j>=1;j--)
       {
           if(i==n&&j==m)continue;
           if(grid[i][j]=='#')
            dp[i][j]=0;
          else dp[i][j]=(((i==n)?0:dp[i+1][j])+((j==m?0:dp[i][j+1])))%1000000007;
       }
   }
   return dp[1][1];
}
main()
{
    int n,m;
    cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          cin>>grid[i][j];
      }
  }
  cout<<solve(n,m)%1000000007;

}






















































































































/* WHATEVER DOESNT KILL ME ONLY MAKES ME STRONGER .*/


Measured memory_bytes: 12412
#include<bits/stdc++.h>
using namespace std;
int d[10]= {0};
bool ok(int x)
{
    int o;
    while(x)
    {
        o=x%10;
        if(d[o])
            return false;
        x/=10;
    }
    return true;
}
int main()
{
    int n,k,x;
    scanf("%d%d",&n,&k);
    for(int i=0; i<k; i++)
    {
        scanf("%d",&x);
        d[x]=1;
    }
    for(int i=n;; i++)
    {
        if(ok(i))
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
string s,t;
  cin>>s>>t;
  int m=s.size();
  int n=t.size();
  // string dp[m+1][n+1];
	int lcs[m+1][n+1];

  for(int i=0;i<=m;i++)
  {
    for(int j=0;j<=n;j++){
      if(i==0||j==0)
      {
     //   dp[i][j]="";
       	lcs[i][j]=0;
      }
      else if(s[i-1]==t[j-1])
      {
      //  dp[i][j]=dp[i-1][j-1]+s[i-1];
       	lcs[i][j]=lcs[i-1][j-1]+1;
      }
      else{
        if(lcs[i-1][j]>lcs[i][j-1])
        {
       //   dp[i][j]=dp[i-1][j];
          lcs[i][j]=lcs[i-1][j];
        }
        else
        {
        //   dp[i][j]=dp[i][j-1];
           lcs[i][j]=lcs[i][j-1];
        }
      }
    }
  }
  string result="";
  int i=m,j=n;
  while(i>=0 && j>=0){
    if(lcs[i][j]==lcs[i-1][j])
      i--;
    else if(lcs[i][j]==lcs[i][j-1])
      j--;
    else
    {
      result=s[i-1]+result;
      i--;
      j--;
    }
  }
    cout<<result<<endl;

}


Measured memory_bytes: 35456
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define DEBUG2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl
typedef long long ll;
class Solver{
    public:
    static const int MAXN=1e5+10;
    int n,l,q;
    int dp[MAXN][40];
    int x[MAXN];
    void solve(){
        ios::sync_with_stdio(false);
        cin>>n;
        for(int u=1;u<=n;u++)cin>>x[u];
        cin>>l;
        for(int u=1;u<=n;u++){
            int lb=u,rb=n,lstp=-1;
            while(lb<=rb){
                int mid=(lb+rb)>>1;
                if(x[mid]<=x[u]+l){
                    lb=mid+1;
                    lstp=mid;
                }
                else rb=mid-1;
            }
            assert(lstp!=-1);
            dp[u][0]=lstp;
        }
        for(int t=1;t<=30;t++){
            for(int u=1;u<=n;u++){
                dp[u][t]=dp[dp[u][t-1]][t-1];
            }
        }
        cin>>q;
        while(q--){
            ll ans=0;
            int a,b;
            cin>>a>>b;
            if(a>b)swap(a,b);
            for(int t=30;t>=0;t--){
                if(dp[a][t]<b){
                    ans+=((1ll)<<t);
                    a=dp[a][t];
                }
            }
            cout<<ans+1<<"\n";
        }
    }
};
int main()
{
    // freopen("in.txt","r",stdin);
    (new Solver())->solve();
}

Measured memory_bytes: 16896
N = int(input())

s = [None] * N
for i in range(N):
    s[i] = input()

sx = {x: s.count(x) for x in set(s)}

M = int(input())
t = [None] * M
for i in range(M):
    t[i] = input()

tx = {x: t.count(x) for x in set(t)}

mx = 0
for sk in sx.keys():
    td = tx[sk] if sk in tx else 0
    mx = max(mx, (sx[sk] - td))

print(mx)

Measured memory_bytes: 3064
n = int(input())
s = [input() for nesya in range(n)]
a,w,t,r = 0,0,0,0
for b in s:
  if b == 'AC':
    a += 1
  elif b == 'WA':
    w += 1
  elif b == 'TLE':
    t += 1
  else:
    r += 1
print('AC x '+str(a))
print('WA x '+str(w))
print('TLE x '+str(t))
print('RE x '+str(r))

Measured memory_bytes: 16328
#include<bits/stdc++.h>
#include <iterator>
#include <iostream>
#include <numeric>
#include <math.h>
#define ll long long
#define ull long
#define mpa make_pair
#define pb push_back
#define ff first
#define pii pair<ll,ll>
#define dd long long
#define trace(x) cerr << #x << " : " << x << endl
#define ss second
#define boost ios_base::sync_with_stdio(0)
#define forp(i,a,b) for(ll i=a;i<=b;i++)
#define rep(i,n)    for(ll i=0;i<n;++i)
#define ren(i,n)    for(ll i=n-1;i>=0;i--)
#define forn(i,a,b) for(ll i=a;i>=b;i--)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end();
#define sc(x) scanf("%lld",&x)
#define clr(x,val) memset(x,val,sizeof(x))
#define pr(x) printf("%lld\n",x) 
#define gc getchar
#define pdd pair<dd,dd>
#define prec(x) cout<<fixed<<setprecision(x)
#define fre freopen("input.txt","r",stdin),freopen("output.txt","w",stdout)
using namespace std;
char a[300005];
ll is_pow_2(ll n){
   ll x=n&(n-1);
   return x>0;	
}
int main(){
   
   ll a,b,c,d;
   cin>>a>>b>>c>>d;
   cout<<max(a*c,max(a*d,max(b*d,b*c)));
   
}
    
   
   

  
   
 

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

#define fio                         \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);                    \
  cout.tie(NULL);
#define ll long long
#define ull unsigned long long
#define ld long double
#define endl "\n"
#define ff first
#define ss second
#define pi pair<ll, ll>
#define PI 3.141592653589793238462643383279502884L
#define mp make_pair
#define pb push_back
#define fall(i, a, b) for (int i = a; i < b; i++)
#define sz(x) (ll) x.size()
#define all(x) x.begin(), x.end()
#define ed cout << "ed";
#define time_passed 1.0 * clock() / CLOCKS_PER_SEC
ll MOD = 1e9 + 7;
ll MOD1 = 1e9 + 123;
ll MOD2 = 1e9 + 321;

int main()
{
    fio;
    ll t, a, n, q, k, i, l, m, c, u, f, j, p, r, x, y, s, b, d;
    cin>>n;
    vector<int>v(n, 0);map<int, int>mp;
    for (i=0;i<n;i++)
        cin>>v[i], mp[v[i]]++;
    if (n%2==0)f=1;
    else f=0;
    c=0;if(mp[0]>1)c=1;
    for (i=0;i<n;i++)
        if (v[i]%2!=f && mp[v[i]]>2 )
        {
            c=1;break;        
         }
    if (c==1)cout<<0<<endl;
    else {
        n/=2;
        f=1;
        while (n--) {
            f=(f*2)%MOD;
   
        }
        cout<<f<<endl;
    }
    return 0;
}


Measured memory_bytes: 6528
# coding: utf-8
from collections import defaultdict


def main():
    N = int(input())
    dic = defaultdict(int)
    max_p = 0

    for i in range(N):
        dic[input()] += 1

    d = dict(dic)
    l = []

    for key, value in d.items():
        l.append([key, value])
        if max_p < value: max_p = value
    
    l.sort(key=lambda x: (-x[1], x[0]), reverse=False)

    for i, j in l:
        if j == max_p:
            print(i)
        else:
            break


if __name__ == "__main__":
    main()


Measured memory_bytes: 75892
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = n; i >= n; i--)

#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))

#define endl "\n"
#define pb push_back
#define rtn return
#define elif else if

#define INF 2000000000	//int型は2 * 10^9ぐらいまで
#define MOD 1000000007
 
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

typedef long long ll;
typedef unsigned long long ull;

template <typename T>
inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T>
inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T>
inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T>
inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T>
inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

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

	string s, t;
	cin >> s >> t;

	bool ans = false;
	for(unsigned i = 0;i < s.size();i++){
		if(s == t){
			ans = true;
			break;
		}
		char c = s.back();
		s.pop_back();
		reverse(ALL(s));
		s.pb(c);
		reverse(ALL(s));
	}
	if(ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	rtn 0;
}

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

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define DEBUG 0
#define LIM 1000000007

int main(){


	lli H,W;
	lli h,w;
	cin>>H>>W>>h>>w;

	cout<<(H-h)*(W-w)<<endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int n;
	scanf("%d",&n);
	int a[n+1];
	a[0] = 0;
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
	}
	int max = -1,max_number = 1,second_max = -10, second_max_number = 1;
	max=a[1];
	for(int i=1; i<=n; i++){
		if(a[i] > max){
			max = a[i];
			max_number = i;
		}
	}
	
	if(max_number == 1){
		second_max = a[2];
		second_max_number = 2;
	}
	else{
		second_max = a[1];
		second_max_number = 1;
	}
	for(int i=1; i<=n; i++){
		if((a[i] > second_max) && (i != max_number)){
			second_max = a[i];
			second_max_number = i;
		}
	}
	
	for(int i=1; i<=n; i++){
		if(i != max_number) printf("%d\n",max);
		else printf("%d\n",second_max);
	}
	
	return 0;
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
ll gcd(ll x, ll y){
  if(y==0) return x;
  else return gcd(y, x%y);
}
ll lcm(ll x,ll y){
  ll g=gcd(x,y);
  return x/g*y;
}
ll a[55],b[55];
ll f(int n, ll x){
  if(!x) return 0;
  if(!n) return 1;
  if(x<a[n-1]+2) return f(n-1,x-1);
  return b[n-1]+1+f(n-1,x-2-a[n-1]);
}
          
  
int main() {
  int N; 
  cin >> N;
  ll X;
  cin >> X;
  a[0] = 1, b[0] = 1;
  rep(i,N){
    a[i+1]=a[i]*2+3;
    b[i+1]=b[i]*2+1;
  }
  ll ans=f(N,X);
  cout << ans << endl;
}
  



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

int main()
{
	int n,m;
	cin >> n >> m;
	ll k;
	cin >> k;
	vector<ll> a(n),b(m),asum(n+1),bsum(m+1);
	for(int i = 0;i<n;i++)
	{
		cin >> a[i];
		asum[i+1] = a[i]+asum[i];
	}

	for(int i = 0;i<m;i++)
	{
		cin >> b[i];
		bsum[i+1] = b[i]+bsum[i];
	}

	ll ans  = 0;
	for(int i = 0;i<n+1;i++)
	{
		ll now = i;
		if(asum[i]>k)continue;
		ll kk = k - asum[i];
		now += upper_bound(bsum.begin(),bsum.end(),k-asum[i])-bsum.begin();
		now --;
		

		ans = max(ans,now);
		//cout << i << ' ' << now << endl;
	}
	cout << ans<<endl;
}


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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	int v = 0, a, b, c, A, B, C; cin >> a >> b >> c;
	while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0 && v < 1000) {
		v++;
		A = (b + c) / 2;
		B = (a + c) / 2;
		C = (a + b) / 2;
		a = A, b = B, c = C;
	}
	cout << (v < 1000 ? v : -1) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
#define lc (now<<1)
#define rc (now<<1|1)
using namespace std;
const int N=1e5+100;
int n,Q,r; 
ll tag[N<<2],mx[N<<2];
void add(int now,int l,int r,int x,int y,int v)
{
	if (x<=l&&r<=y)
	{
		tag[now]+=v; 
		mx[now]+=v; 
		return;
	}
	int mid=l+r>>1;
	if (x<=mid) add(lc,l,mid,x,y,v);
	if (y>mid) add(rc,mid+1,r,x,y,v);
	mx[now]=max(mx[lc],mx[rc])+tag[now];
}
int main(){
	scanf("%d%d",&n,&Q);
	r=1;
	while (Q--)
	{
		int x,y,w; 
		scanf("%d%d%d",&x,&y,&w);
		while (r<y) 
			add(1,1,n,++r,n,1);
		add(1,1,n,x,y,w);
		printf("%lld\n",mx[1]);
	}
	return 0;
}


Measured memory_bytes: 7320
def con2(n):
    return n*(n-1)//2

n = int(input())
a = list(map(int, input().split()))
s = [0] * (n+1)
dic = {0:1}
for i in range(1, n+1):
    s[i] = s[i-1] + a[i-1]
    if not s[i] in dic:
        dic[s[i]] = 1
    else:
        dic[s[i]] += 1
ans = 0
#print(s)
#print(dic)
for key in dic:
    if dic[key] == 1:
        continue
    else:
        ans += con2(dic[key])

print(ans)


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll N; cin >> N;
  ll a[N]; rep(i,N) cin >> a[i];

  ll sp = 0, np = 0;
  rep(i,N) {
    np += a[i];
    if (i%2==0) {
      if (np<=0) { sp += 1-np; np = 1; }
    }
    else {
      if (np>=0) { sp += np+1; np = -1; }
    }
  }

  ll sm = 0, nm = 0;
  rep(i,N) {
    nm += a[i];
    if (i%2==1) {
      if (nm<=0) { sm += 1-nm; nm = 1; }
    }
    else {
      if (nm>=0) { sm += nm+1; nm = -1; }
    }
  }

  ll result = min(sp, sm);
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 4388
N = int(input())
count = 0
p = list(map(int,input().split()))
for i in range(1,len(p)-1):
  if (p[i-1] < p[i] and p[i] < p[i+1]) or (p[i-1] > p[i] and p[i] > p[i+1]):
    count += 1
print(count)

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

#ifdef _PRINTDEBUG
  #include "lib/printdebug.hpp"
#else
  #define printdebug(...) 1
#endif
#define MOD_1_000_000_007 (1000000007)
#define IINF (1<<28)
#define LINF (1LL<<60)
#define rep(i, n)      REP(i, 0, (n))
#define repc(i, n)     REPC(i, 0, (n))
#define REP(i, n, m)   for (int i = (int)(n); i <  (int)(m); i++)
#define REPC(i, n, m)  for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
#define yesno(cond)       YESNO((cond), "Yes", "No")
#define YESNO(cond, a, b) cout << ((cond) ? (a) : (b)) << "\n"

namespace solver {
  using namespace std;
  typedef long long ll;

  string s;

  void init() {
    cin >> s;
  }

  void solve() {
    s += '$';
    string t;
    rep(i, s.size()) {
      if(s[i] == 'B' && s[i+1] == 'C') t += 'D', i += 1;
      else t += s[i];
    }
    ll a = 0, ans = 0;
    rep(i, t.size()) {
      if(t[i] == 'A') a++;
      else if(t[i] == 'D') ans += a;
      else a = 0;
    }
    cout << ans << "\n";
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  solver::init();
  solver::solve();
  return 0;
}

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);	
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll ,ll> 			pll;
typedef pair<ld,ld> 			pld;
typedef unordered_map<ll,ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5+7;
const ll 	MAX7 	= 	1e+7+7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9+7;

vll adj[MAXN];ll visit[MAXN]={};
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1};
int dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};

// <------------- Declare Variables Here ------------> //

ll T=1;
ll n,x;
string s;

// <------------- Implement Functions Here ----------> //



// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n;
	vll a(n+1);
	vll vis(n+1,0);
	//vis[1] = 1;
	for(ll i=1;i<=n;i++) cin >> a[i];
	ll cou = 0;
	ll ss = 1;
	while(vis[ss] == 0) {
		vis[ss] = 1;
		if(ss == 2) {
			cout<<cou;return;
		}
		cou++;
		ss = a[ss];
	}
	cout<<-1;
}

int main() {
	fastio;randomINT;
	//cin>>t;
	while(T--) {
		MAIN();
	}
	return 0;
}


Measured memory_bytes: 239256
//ITP1_10_A
#include <stdio.h>
#include <math.h>

int main(){

	double x1,y1,x2,y2;
	scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	
	
	printf("%f",sqrt(pow(x1-x2,2)+pow(y1-y2,2)));
	
	return 0;

}

Measured memory_bytes: 652
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

int main() {
    ll n, k; cin >> n >> k;
    vector<ll> tel(n), path = {1};
    set<ll> seen = {1};
    ll loop;
    rep(i, n) cin >> tel[i];
    rep(i, n) {
        ll add = tel[*(path.end()-1) - 1];
        if(seen.count(add)) {
            loop = add;
            break;
        }
        seen.insert(add);
        path.push_back(add);
    }
    assert(loop != NULL);
    if(k < path.size()) {
        cout << path[k] << endl;
        return 0;
    }
    rep(i, path.size()) if(path[i] == loop) cout << path[(k - i) % (path.size() - i) + i] << endl;
}


Measured memory_bytes: 15488
/* ****revpro**** */
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl	   '\n'
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)    
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mii	    map<ll,ll>
using namespace std;

#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define N  100005
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;  
#define ordered_set tree<double, null_type,less<double>, rb_tree_tag,tree_order_statistics_node_update> 
void solve()
{
	ll a,b;
	cin>>a>>b;
	cout<<a*b<<endl;
}	
signed main()
{
	
		/***********************************/
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    mt19937_64 generator (seed);
    /***********************************/
 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
		
	}
	TIME
	return 0;
}

Measured memory_bytes: 3800
a, b = map(int, input().split())

if a == b:
    print(a)
    exit()
cnt = b - a + 1
cnt -= (a % 2 == 1) + (b % 2 == 0)
a, b = a * (a % 2 == 1), b * (b % 2 == 0)
print((cnt // 2 % 2) ^ a ^ b)


Measured memory_bytes: 61928
#include<stdio.h>
#include <iostream>
#include <string>
#include <math.h>
using namespace std;


int zero_to_ten(int a){
    if(a == 0){
        return 10;
    }else{
        return a;
    }
}

int main( void )
{
    int A, B, C, D, E;
	cin >> A >> B >> C >> D >> E;

    int tmpA, tmpB, tmpC, tmpD, tmpE;
    tmpA = A % 10;
    tmpB = B % 10;
    tmpC = C % 10;
    tmpD = D % 10;
    tmpE = E % 10;
    tmpA = zero_to_ten(tmpA);
    tmpB = zero_to_ten(tmpB);
    tmpC = zero_to_ten(tmpC);
    tmpD = zero_to_ten(tmpD);
    tmpE = zero_to_ten(tmpE);

    int tmpmin = min(min(min(min(tmpA, tmpB), tmpC), tmpD), tmpE);

    A = (A+9)/10*10;
    B = (B+9)/10*10;
    C = (C+9)/10*10;
    D = (D+9)/10*10;
    E = (E+9)/10*10;

    cout << A + B + C + D + E + tmpmin - 10<< "\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int H,W,n,sx,sy;
char s[N],t[N];
int nw,mx;
int main(){
	//freopen("a.in","r",stdin);
	scanf("%d%d%d%d%d%s%s",&H,&W,&n,&sx,&sy,s+1,t+1);bool flg=1;
	nw=sy;mx=H+1;for(int i=1;i<=n;i++){if(s[i]=='L')nw--;mx=min(mx,nw);if(t[i]=='R'&&nw<W)nw++;}if(mx<1)flg=0;
	nw=sy;mx=0;for(int i=1;i<=n;i++){if(s[i]=='R')nw++;mx=max(mx,nw);if(t[i]=='L'&&nw>1)nw--;}if(mx>W)flg=0;
	nw=sx;mx=W+1;for(int i=1;i<=n;i++){if(s[i]=='U')nw--;mx=min(mx,nw);if(t[i]=='D'&&nw<H)nw++;}if(mx<1)flg=0;
	nw=sx;mx=0;for(int i=1;i<=n;i++){if(s[i]=='D')nw++;mx=max(mx,nw);if(t[i]=='U'&&nw>1)nw--;}if(mx>H)flg=0;
	if(!flg)puts("NO");else puts("YES");
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	static int n;
	static int[] A;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Main eSearch = new Main();
		n = in.nextInt();
		A = new int[n];
		for(int i = 0;i<n;i++){
			A[i] = in.nextInt();
		}
		int q = in.nextInt();
		int[] m = new int[q];
		for(int j=0;j<q;j++){
			m[j] = in.nextInt();
			if(eSearch.solve(0, m[j]))
				System.out.println("yes");
			else 
				System.out.println("no");
		}
	}
	public boolean solve(int i,int m){
		if(m==0) return true;
		if(i>=n) return false;
		
		boolean res = solve(i+1,m)||solve(i+1,m-A[i]);
		return res;
	}
}

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define MAXX 100005
#define INF INT_MAX

#define PI   3.14159265358979323846264338327950

#define PB push_back
#define PF push_front
#define F first
#define S second

#define fixx(n) fixed << setprecision(n)

#define ll 	 long long 

#define mod  1000000007



int main()
{
	FAST;
	int n, a, b;
	cin >> n >> a >> b;
	a *= n;
	cout << min(a, b);
	return 0;
	
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
long long int fact(long long int n)
{
    if(n==1 || n==0)
        return 1;
    else
        return ((n%M)*(fact(n-1)%M))%M;

}
int div(int n)
{  int c=0;
    for(int i=1;i<sqrt(n);i++)
    {
        if(n%i==0)
        {
          c++;
        }
    }
    c=c*2;
    if(pow(sqrt(n),2)==(sqrt(n)*sqrt(n)))
        c++;
    return  c;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   long long int n;
   cin>>n;
   long long int l[n+1];
   l[0]=2;
   l[1]=1;
   for(long long int i=2;i<=n;i++)
   l[i]=l[i-1]+l[i-2];
  cout<<l[n];


 return 0;
}








Measured memory_bytes: 3704
#include <bits/stdc++.h>
using namespace std;
#define int long long
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr array<int, 4> dx = {1, 0, -1, 0};
constexpr array<int, 4> dy = {0, 1, 0, -1};

template <class T>
void sortIndex(const vector<T> &vec, vector<int> &idx)
{
    idx.resize(vec.size());
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&vec](int l, int r) { return vec[l] < vec[r]; });
}

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

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

    vector<int> idx(n);
    sortIndex(a, idx);

    for (int i = 0; i < n; i++)
    {
        cout << idx[i]+1 << (i < n - 1 ? " " : "");
    }
    cout << endl;
}


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

int main() {
	long int N, T;
	cin >> N >> T;
	long int time = 0;
	vector<long int> vec (N);
	for(long int i = 0;i < N;i++){
		cin >> vec.at(i);
	}
	
	long int comp = 0;
	long int left = 0;
	for(long int i = 0;comp < N;i++){
		if(vec.at(comp) == i){
			comp++;
			left = T;
		}
		if(left > 0){
			left--;
			time++;
		}
	}
	time += left;
	cout << time << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){for(ll i=0;i<v.size();++i) x<<v[i]<<" ";return x;}
template <typename X> ostream& operator << (ostream& x,const set<X>& v){for(auto it:v) x<<it<<" ";return x;}
template <typename X, typename Y> ostream& operator << (ostream& x, const pair<X,Y>& v) {x<<v.ff<<" "<<v.ss;return x;}
template <typename T, typename S> ostream& operator << (ostream& os, const map<T, S>& v) { for (auto it : v) os << it.first << "=>" << it.second << endl; return os; }
struct pair_hash {inline std::size_t operator()(const std::pair<ll, ll> & v) const {return v.first*31+v.second;}};
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define fr first
#define sc second
#define prnt(m) for(auto it = m.begin() ; it != m.end() ; ++it){cout<<*it<<endl;}
#define tra(it,m) for(auto it=m.begin();it!=m.end();++it)
#define DBG(x) cout<<"# # #     "<<x<<'\n';
#define fri(i,s,n) for(long long i=s;i<n;i++)
#define mod 1000000007LL
#define mod2 998244353
#define vct2 vector<vector<ll>>
#define vct vector<ll>
#define pll pair<ll,ll>
#define rz(n) resize(n)
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define arrin(a,n) for(ll i = 0; i < n ; i++){cin>>a[i];}
#define arrout(a,n) for(ll i = 0;i < n; i++){cout<<a[i]<<" ";}
#define ex(s) cout<<s<<endl,exit(0);
#define infy 2e18
#define five 100005;
#define six 1000005;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
//___________________________________________________________________________________________________________________________________________________________
bool f(string s)
{
       string ss = s;
       reverse(all(ss));
       return ss == s;
}
int main(){
       string s;
       cin>>s;
       
       if(!f(s)){
              cout<<"No"<<endl;
              return 0;
       }
       int n = s.size();
       string s1;
       fri(i,0,n/2){s1.pb(s[i]);}
       if(!f(s1)){
              cout<<"No"<<endl;
              return 0;
       }
       reverse(all(s));
       s1.clear();

       fri(i,0,n/2){s1.pb(s[i]);}
       if(!f(s1)){
              cout<<"No"<<endl;
              return 0;
       }
       cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
use io::*;

fn main() {
    let con = read_string();
    let mut sc = Scanner::new(&con);

    let s: Vec<char> = sc.next::<String>().chars().collect();
    let k: i64 = sc.next();
    let k = k - 1;

    let mut ones = 0;
    for i in 0..s.len() {
        if s[i] == '1' {
            ones += 1;
        } else {
            break;
        }
    }

    let ans = if k < ones { '1' } else { s[ones as usize] };

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

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define vll vector<ll>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb  push_back
#define ppb pop_back
#define mp  make_pair
int main(){
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	// #endif
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	ll num;
	cin>>num;
	ll ans=0;
	ans=1000*(num/500);
	num=num-500*(num/500);
	ans+=5*(num/5);
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  long long S;
  scanf("%lld", &S);
  for (int i = 0; i < K; ++i)
    cout << S << " \n"[i == N - 1];
  for (int i = K; i < N; ++i)
    if (S == 1)
      cout << S + 1 << " \n"[i == N - 1];
    else
      cout << S - 1 << " \n"[i == N - 1];

  return 0;
}


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

int main() {
  int n; cin >> n;
  pair<LL, LL> p[n];
  for (int i = 0; i < n; i ++) cin >> p[i].second >> p[i].first;

  sort(p, p + n);
  LL sum = 0;
  string ans = "Yes";
  for (int i = 0; i < n; i ++) {
    sum += p[i].second;
    if (sum > p[i].first) {
      ans = "No";
      break;
    }
  }
  cout << ans << endl;
}

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

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007; //998244353;

template<class _T> static void get(_T& a) {
	std::cin >> a;
}
template<class _T> static void get(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void get(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}
template <class _T> static _T tp_abs(_T a) {
	if (a < (_T)0) {
		a *= (_T)-1;
	}
	return a;
}

static void exec();

int main()
{
	exec();
	fflush(stdout);
	return 0;
}

static void exec()
{
	int K;
	get(K);

	std::vector<int> ai(K);
	for (int i = 0; i < K; i++) {
		get(ai[i]);
	}

	if (ai[K - 1] != 2) {
		printf("-1\n");
		return;
	}

	LLONG min = 2, max = 2;
	for(int i = K - 1; i >= 0; i--) {
		LLONG tmp = ai[i];
		bool ok = false;

		LLONG div = min / ai[i];
		if (min % ai[i]) {
			div++;
		}

		if (div * ai[i] > max) {
			printf("-1\n");
			return;
		}

		min = (min / ai[i] + ((min % ai[i]) ? 1 : 0)) * ai[i];
		max = (max / ai[i]) * ai[i] + ai[i] - 1;
	}
	printf("%lld %lld\n", min, max);
}


Measured memory_bytes: 3772
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    S=input()
    N=len(S)
    
    ans=int(S)
    import itertools
    for r in range(N-1):
        for ite in itertools.combinations(range(1,N), r+1):
            a=[0]+list(ite)+[N]

            for i in range(len(a)-1):
                b=int(S[a[i]:a[i+1]])
                ans+=b
                
                
    print(ans)

main()


Measured memory_bytes: 39280
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }


const ll mod = 1000000007;
const int N = 2000010;
ll fact[N], invf[N];

ll add(ll x, ll y){
    return (x+y)%mod;
}

ll mul(ll x, ll y){
    return (x%mod)*(y%mod)%mod;
}

ll powll(ll x, ll y){
    x %= mod;
    ll res = 1LL;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}

ll divll(ll x, ll y){
    x %= mod;
    return (x * powll(y,mod-2)) % mod;
}

ll nPr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(fact[n], invf[n-r]);
}

ll nCr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(mul(fact[n], invf[r]), invf[n-r]);
}

void init_f(){
    fact[0] = 1;
    FOR(i,1,N-1){
        fact[i] = (fact[i-1] * i) % mod;
    }
    invf[N-1] = divll(1, fact[N-1]);
    FORR(i,N-1,1){
        invf[i-1] = (invf[i] * i) % mod;
    }
}


int main(void){
    int k;
    string s;
    cin >> k >> s;
    init_f();
    int n = s.length();

    ll ans = 0;
    REP(x,k+1){
        ll tmp = (powll(25, x) * nCr(n + x - 1, n - 1)) % mod;
        tmp = tmp * powll(26, k - x);
        ans = (ans + tmp) % mod;
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll A, V; cin >> A >> V;
  ll B, W; cin >> B >> W;
  ll T; cin >> T;

  ll tpa = A + V*T, tpb = B + W*T;
  ll tma = A - V*T, tmb = B - W*T;
  string result = (A<=B&&tpa>=tpb)||(A>=B&&tma<=tmb) ? "YES" : "NO";
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
#include<functional>
using namespace std;

int MOD = 1e9 + 7;

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

int main() {
	int n, a;
	cin >> n >> a;
	int MAX = a;
	vector<int> x(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		MAX = max(MAX, x[i]);
		x[i] -= a;
	}

	vector<vector<ll>> dp(60, vector<ll>(5010, 0));
	dp[0][n * MAX] = 1;

	for (int i = 1; i <= n; i++) {
		for (int k = 0; k <= 5005; k++) {
			dp[i][k] = dp[i - 1][k];
			if (k - x[i - 1] >= 0 && k - x[i - 1] <= 2 * n * MAX) dp[i][k] += dp[i - 1][k - x[i - 1]];
		}
	}
	cout << dp[n][n*MAX] - 1 << endl;
}

Measured memory_bytes: 2688
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define X 1000000007
using namespace std;
int n,c[30];char s[N+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
	RI i,f=1;for(scanf("%d%s",&n,s+1),i=1;i<=n;++i) f=1LL*(QP(c[s[i]&31]+1,X-2)+1)*f%X,++c[s[i]&31];
	return printf("%d\n",f-1),0;
}

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

int main(void){
    int n,k;
    cin>>n>>k;
    vector<int> d(k),list(n,0);
    vector<vector<int>> a(k,vector<int>(100));

    for(int i=0;i<k;i++){
        cin>>d[i];
        for(int j=0;j<d[i];j++){
            cin>>a[i][j];
            list[a[i][j]-1]=1;
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        if(list[i]==0)cnt++;
    }

    cout<<cnt<<endl;;

    return 0;
}

Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
void print() {
    cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail) != 0)
        cout << " ";
    print(forward<Tail>(tail)...);
}
template <class T>
void print(vector<T> &vec) {
    for (auto &a : vec) {
        cout << a;
        if (&a != &vec.back())
            cout << " ";
    }
    cout << endl;
}
template <class T>
void print(vector<vector<T>> &df) {
    for (auto &vec : df) {
        print(vec);
    }
}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define xrep(i, a, b) for (int i = int(a); i < int(b); ++i)
using ll = long long;
const int INF = 1001001001;
const int BIG = 100010;


int dp[BIG];

int main() {
    int N;
    cin >> N;
    vector<int> H(N);
    rep(i, N) cin >> H[i];
    rep(i, BIG) dp[i] = INF;

    dp[0] = 0;
    xrep(i, 1, N) {
        chmin(dp[i], dp[i-1] + abs(H[i]-H[i-1]));
        if(i>=2) {
            chmin(dp[i], dp[i-2] + abs(H[i]-H[i-2]));
        }
    }
    print(dp[N-1]);

    return 0;
}

Measured memory_bytes: 4028
#include<bits/stdc++.h>
#define ll long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 2e5+5;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
int main()
{
    fastio();
    string s;
    cin>>s;
    int l = s.size();
    if(s[l-1]=='3') cout<<"bon"<<endl;
    else if(s[l-1]=='0' ||s[l-1]=='1'||s[l-1]=='6'||s[l-1]=='8') cout<<"pon"<<endl;
    else cout<<"hon"<<endl;
    return 0;
}


Measured memory_bytes: 3640