akhauriyash/Code-Regression huggingface dataset:
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

vector<int> g[100111];
int n;
bool use[100111];
void dfs(int x,int f=0)
{
	int cnt=0;
	for(int i=0;i<(int)g[x].size();i++)
		if(g[x][i]!=f)
		{
			dfs(g[x][i],x);
			cnt+=use[g[x][i]]^1;
		}
	if(cnt>1)
	{
		puts("First");
		exit(0);
	}
	use[x]=cnt;
}
int main()
{
	get1(n);
	if(n%2==1)
	{
		puts("First");
		return 0;
	}
	for(int i=1,u,v;i<n;i++)
	{
		get2(u,v);
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1);
	puts("Second");
	return 0;
}

Measured memory_bytes: 5888
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}
    
let kx = readInts()
let k = kx[0]
let x = kx[1]
let a=500*k-x
if a>=0{
  print("Yes")
}else{
  print("No")
}


Measured memory_bytes: 8284
import sys


class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  # 親を探す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  # x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)


N,M=map(int,input().split())
K=[set() for i in range(M)]
tree=Unionfindtree(N)
for i in range(N):
    L=[int(i)-1 for i in input().split()]
    for m in L[1:]:
        K[m].add(i)
for i in range(M):
    Ki=list(K[i])
    if len(Ki)==0:
        continue
    for h in range(len(Ki)):
        tree.union(Ki[h],Ki[0])
for i in range(N):
    if not tree.connect(0,i):
        print('NO')
        sys.exit()
print('YES')




Measured memory_bytes: 82976
S = list(input())
T = list(input())

ans_list=[]
for s in range(len(S)-len(T)+1):
    ans = 0
    for t in range(len(T)):
        if S[s+t] != T[t]:
            ans += 1
    ans_list.append(ans)
print(min(ans_list))

Measured memory_bytes: 9112
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

a,b,c = I()
if c < a+b:
    print("No")
    sys.exit()

if 2*a*b < c**2 + a**2 + b**2 - 2*c*a-2*b*c:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 10180
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

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

    ll res =  0;
    rep(i, n){
        int x;
        cin >> x;
        res += min(abs(x-k), x)*2;
    }
    cout << res  << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n;
char s[200][200];
int d[200][200]; // d[i][j] = (i~jの最短距離)
bool b[200][200];
int ans;

bool bfs(int start){
    queue<int> q;
    q.push(start);
    d[start][start]=0;

    while(q.size()){
        int now=q.front(); q.pop();
        for(int i=0;i<n;i++){
            if(s[now][i]=='0') continue;
            if(d[start][i]==1e8){
                q.push(i);
                d[start][i]=d[start][now]+1;
                ans=max(ans,d[start][i]);
            }else if(d[start][i]==d[start][now]){
                return false;
            }
        }
    }
    return true;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>s[i][j];
            d[i][j]=1e8;
        }
    }
    for(int i=0;i<n;i++){
        if(!bfs(i)){
            cout<<-1;
            return 0;
        }
    }
    cout<<ans+1;
}

Measured memory_bytes: 512
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	int a=0;
	string s;
	cin >> s;
	for (int i=0;i<s.length()-1;i++) {
		if (s[i]!=s[i+1]) a+=1;
	}
	cout << a;
}

Measured memory_bytes: 512
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)
#define BLACK 1
#define WHITE 0

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

const int max_n = 100000+10;
int N;
vector<pair<int,int>> G[max_n+1];
bool visited[max_n+1];
bool color[max_n+1];

void dfs(int node, bool c) {
    visited[node] = true;
    for(auto u: G[node]) {
        if(visited[u.first])
            continue;

        bool tc = c;
        if(u.second % 2 == 1) {
            tc = !c;
        }
        color[u.first] = tc;
        dfs(u.first, tc);
    }

    return;
}

int main(void) {
    cin>>N;

    for(int i = 1;i < N;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }

    for(int i = 1;i <= N;i++) {
        if(visited[i])
            continue;
        color[i] = BLACK;
        dfs(i, BLACK);
    }

    for(int i = 1;i <= N;i++) {
        cout<<color[i]<<endl;
    }

    return 0;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (int)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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;
    }
}

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

//modでの累乗(繰り返し二乗法)
ll modpow(ll x, ll y, ll m)
{
    if (y == 0)
        return 1;
    ll res = modpow(x, y / 2, m);
    return res * res % m * (y & 1 ? x : 1) % m;
}

//modでの割り算
ll modinv(ll x, ll m) { return modpow(x, m - 2, m); }

//modでの安全な引き算
ll modsub(ll x, ll y, ll m){ return(x + m - y) % m; }

//乗算により二項係数を求める
ll binom(ll n, ll k, ll m)
{
    ll den = 1, num = 1;
    for (int i = 1; i <= k; ++i){
        den *= i;
        num *= (n + 1 - i);
        den %= m;
        num %= m;
    }
    return num * modinv(den,m);
}

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

    ll N, K;
    cin >> N >> K;

    ll mx = 0, mn = 0;
    COMinit();

    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    sort(ALL(A));

    rep(i,N){
        mn += A[i] * COM(N - i - 1, K - 1) % MOD;
        mx += A[N - 1 - i] * COM(N - i - 1, K - 1) % MOD;
    }
    print(modsub(mx,mn,MOD));

    return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> L(N);
    for(int i = 0; i < N; i++)cin >> L[i];
    sort(L.begin(), L.end());
    int s = 0;
    for(int i = 0; i < N - 1; i++)s += L[i];
    if(s > L[N - 1])cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE PartialTypeSignatures #-}
module Main (main) where

import qualified Data.ByteString.Char8 as C8
import qualified Data.Char as C
import qualified Data.List as L

main :: IO ()
main = do
  [n,m] <- readInts
  readInts >>= output . solve n

solve :: Int -> [Int] -> _
solve n xs
  | s > n = -1
  | otherwise = n-s
  where
    s = sum xs

output :: _ -> IO ()
output = print

-- utils
readInts :: IO [Int]
readInts = L.unfoldr (C8.readInt . C8.dropWhile C.isSpace) <$> C8.getLine

Measured memory_bytes: 4824
#include <bits/stdc++.h>
#define For(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define Fordown(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;

bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}

const int N = 1e5 + 1e3;
int a[N];
int ans = 0;

int main () {
	int n = read();
	For (i, 1, n) {
		int val = read();
		if (val >= 1) ++a[val-1], chkmax(ans, a[val-1]);
		++a[val], chkmax(ans, a[val]);
		++a[val+1], chkmax(ans, a[val+1]);
	}
	printf ("%d\n", ans);
    return 0;
}


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

using namespace std;
using ll =long long;
using db = double;
using vll = vector<long long>;

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; }
#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define leftunique(a) {SORT(a);(a).erase(unique((a).begin(),(a).end()),(a).end());}
//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる
#define debug(x)  cout << #x << " = " << (x) << endl;
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}
const int mod = 1e9 + 7;
const ll INF = 1LL << 60;
//ここから書き始める

int main()
{
	cout <<setprecision(10);
	ll n,k;
	cin >> n>>k;
	ll ans ;
	//k * k-1 * k-1 *...計n個の項がある
	ans = k * pow(k-1,n-1);
	cout << ans << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
h,w = map(int, raw_input().split())
 
area = [0,0,0]
ans = 10**15
if(h%3 == 0 or w%3 == 0):
    ans = 0
else:
    for i in range(1,h/2+1):
        area[0] = i*w
        tmp = w/2
        area[1] = tmp*(h-i)
        area[2] = (w-tmp)*(h-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        tmp = (h-i)/2
        area[1] = tmp*w
        area[2] = (h-i-tmp)*w
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        
    for i in range(1,w/2+1):
        area[0] = i*h
        tmp = h/2
        area[1] = tmp*(w-i)
        area[2] = (h-tmp)*(w-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        tmp = (w-i)/2
        area[1] = tmp*h
        area[2] = (w-i-tmp)*h
        S = max(area)-min(area)
        if(S<ans):
            ans = S
print(ans)

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

int main() {
  int N, M; cin >> N >> M;
  vector<pair<int, int>> stream(M);
  vector<vector<int>> py(N+1);
  for (int i = 0; i < M; i++) {
    int p, y; cin >> p >> y;
    stream.at(i) = make_pair(p, y);
    py.at(p).push_back(y);
  }
  for (int i = 1; i <= N; i++) {
    sort(py.at(i).begin(), py.at(i).end());
  }
  for (auto p : stream) {
    auto index = lower_bound(py.at(p.first).begin(), py.at(p.first).end(), p.second) - py.at(p.first).begin() + 1;
    cout << setfill('0') << right << setw(6) << p.first;
    cout << setfill('0') << right << setw(6) << index << endl;
  }
}


Measured memory_bytes: 7808
#include "bits/stdc++.h"
#ifndef err
#define err(...)(void)0
#endif
using namespace std;
using ll = long long;
using ull = decltype(1ull);
template<class T>int size(T&&a) { return a.size(); }
#define REP(t,a)for(typename make_signed<decltype(a.second)>::type t=a.first,_l##t=a.second;t<_l##t;t++)
#define RREP(t,a)for(typename make_signed<decltype(a.second)>::type t=a.second-1,_l##t=a.first;t>=_l##t;t--)
template<class B>pair<int, B>make_pair(B b) { return{ 0,b }; }
#define rep(t,...)REP(t,make_pair(__VA_ARGS__))
#define rrep(t,...)RREP(t,make_pair(__VA_ARGS__))
#define all(a)begin(a),end(a)
#define rall(a)a.rbegin(),a.rend()
#define var(t, ...) t __VA_ARGS__;in,__VA_ARGS__;

void Calc();
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  cin.exceptions(istream::failbit | istream::badbit);
  cout << fixed << setprecision(15); Calc(); cout.flush(); return 0;
}
template<class A>void amax(A&a, A b) { a = max(a, b); }
template<class A>void amin(A&a, A b) { a = min(a, b); }
template<class A>int comp(A a, A b) { return a < b ? 1 : b < a ? -1 : 0; }
struct Scanner {
  template<class A = string>A Next() { A a; cin >> a; return a; }
  template<class A = int>vector<A>Array(int n) { vector<A>a(n); for (A&i : a) cin >> i; return a; }
  string Line() const { string s; getline(cin, s); return s; }
  template<class A>Scanner&operator,(A&a) { a = Next<A>(); return *this; }
  template<class A>operator A() { return Next<A>(); }
}in;

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


void Calc() {

  string s = in;
  int n = size(s);
  int cnt = 0;

  int l = 0, r = n - 1;

  rep(i, n) {
    if (l >= r)break;
    if (s[l] != s[r]) {
      if (s[l] == 'x') {
        l++;
      }
      else if (s[r] == 'x') {
        r--;
      }
      else {
        cout << (-1) << endl;
        return;
      }
      cnt++;
    }
    else {
      l++, r--;
    }
  }
  cout << (cnt) << endl;
}


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

int main()
{
    int a[4],b[4];
    while(cin>>a[0]>>a[1]>>a[2]>>a[3]>>b[0]>>b[1]>>b[2]>>b[3],!cin.eof()){
        int hit=0,blow=0;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(b[i]==a[j] && i==j){
                    hit++;
                    break;
                }
                if(b[i]==a[j] && i!=j){
                    blow++;
                    break;
                }
            }
        }
        cout<<hit<<' '<<blow<<endl;
    }

    return 0;
}

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

typedef int INT;
#define int long long

namespace Stdin
{
    int read()
    {
        int sum = 0;
        char c = getchar(), f = c;
        while(c < '0' || c > '9') f = c, c = getchar();
        while(c >= '0' && c <= '9') sum = sum * 10 + c - '0', c = getchar();
        if(f == '-') sum *= -1;
        return sum;
    }
    char GetOnce(char s, char e)
    {
        char c = getchar();
        while(c < s || c > e) c = getchar();
        return c;
    }
}

namespace STD
{
    const int N = 100000 + 10;
    int n, m;
    int tot, sum, mrk;
    int C[N], S[4];
    int head[N], used[N], cnt;
    struct edge { int to, va, nxt; } e[N << 1];
    int ans;
    
    void Add(int x, int y)
    {
        e[++cnt] = (edge) { y,  1, head[x] }; head[x] = cnt;
        e[++cnt] = (edge) { x, -1, head[y] }; head[y] = cnt;
    }

    int Cal(int x) { x %= 3; if(x == 0) return 3; return x; }

    void DFS(int u)
    {
        tot++;
        S[C[u]]++;
        used[u] = 1;
        for(int i = head[u]; i; i = e[i].nxt)
        {
            sum++;
            int v = e[i].to;
            int w = e[i].va;
            if(used[v] == 0) C[v] = Cal(C[u] + w), DFS(v);
            if(C[v] == 0 || C[v] == Cal(C[u] + w)) continue;
            mrk = 1;
        }
    }
}

using namespace Stdin;
using namespace STD;

void MAIN()
{
    n = read(), m = read();
    for(int i = 1; i <= m; i++)
    {
        int x = read();
        int y = read();
        Add(x, y);
    }
    for(int i = 1; i <= n; i++)
    {
        if(used[i]) continue;
        memset(S, 0, sizeof(S));
        mrk = tot = sum = 0;
        C[i] = 1;
        DFS(i);
        if(mrk) ans += tot * tot;
        else if(S[1] == 0 || S[2] == 0 || S[3] == 0) ans += sum / 2;
        else ans += S[1] * S[2] + S[1] * S[3] + S[2] * S[3];
    }
    printf("%lld\n", ans);
}

INT main()
{
    #ifndef ONLINE_JUDGE
        // freopen("INPUT", "r", stdin);
        // freopen("OUTPUT", "w", stdout);
        // long _begin_time = clock();
    #endif
    
    MAIN();
    
    #ifndef ONLINE_JUDGE
        // long _end_time = clock();
        // printf("time = %ld ms", _end_time - _begin_time);
    #endif
    
    return 0;
}

Measured memory_bytes: 11904
#include <algorithm>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<string>
#define rep(i,n) for(int i=0; i<(int)n; i++)//n回繰り返す
using namespace std;
using ll = long long;
using P = pair<int, int>;

int N;
void dfs(string s ,char mx){
    if (s.size() == N) {
        cout << s << endl;
        return;
    }
    for (char c = 'a'; c <= mx + 1; c++){
        string t = s;
        t += c;
        dfs(t,max(mx,c));
      }
  }

int main() {
    cin >> N;
    string s;
    s.push_back('a');
    dfs(s,'a');
    return 0;

}


    
    

    
    
    
    

















Measured memory_bytes: 1536
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

if a < b:
  if a + t * v >= b + t * w:
    print("YES")
  else:
    print("NO")
else:
  if a - t * v <= b - t * w:
    print("YES")
  else:
    print("NO")

Measured memory_bytes: 9188
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

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

    int N, A, B, C, D;
    string S;
    cin >> N >> A >> B >> C >> D >> S;
    A--; B--; C--; D--;
    bool answer = true;

    for (int i = A; i < C; i++)
        if (S[i] == '#' && S[i + 1] == '#')
            answer = false;

    for (int i = B; i < D; i++)
        if (S[i] == '#' && S[i + 1] == '#')
            answer = false;

    if (C > D) {
        bool has_three = false;

        for (int i = B; i <= D; i++)
            if (S[i - 1] == '.' && S[i] == '.' && S[i + 1] == '.')
                has_three = true;

        if (!has_three)
            answer = false;
    }

    cout << (answer ? "Yes" : "No") << '\n';
}


Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define debug(x) cout << #x << '=' << x << '\n'
const long long MOD=1e9+7;
//const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?"": " ");
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    cout << '(' << p.first << ',' << p.second << ')';
    return os;
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<string> S(N); cin >> S;
    vector<int> sum(N),Min(N,0);
    for (int i=0;i<N;++i){
        int cnt=0;
        for (int j=0;j<S[i].size();++j){
            if (S[i][j]=='(') ++cnt;
            else --cnt;
            chmin(Min[i],cnt);
        }
        sum[i]=cnt;
    }
    int Sum=0;
    for (int i=0;i<N;++i) Sum+=sum[i];
    if (Sum!=0){cout << "No" << '\n'; return 0;}
    vector<pair<int,int>> v1,v2;
    Sum=0;
    for (int i=0;i<N;++i){
        if (Min[i]>=0) Sum+=sum[i];
        else if (sum[i]>=0) v1.emplace_back(Min[i],sum[i]);
        else v2.emplace_back(Min[i]-sum[i],Min[i]);
    }
    sort(all(v1)); reverse(all(v1)); sort(all(v2));
    for (auto p:v1){
        if (Sum+p.first<0){cout << "No" << '\n'; return 0;}
        Sum+=p.second;
    }
    for (auto p:v2){
        int M=p.second,s=M-p.first;
        if (Sum+M<0){cout << "No" << '\n'; return 0;}
        Sum+=s;
    }
    cout << "Yes" << '\n';
}

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

queue<pair<int,int> > qu;
vector<int> v[111];
int root;
int b;
int d[111];
pair<int, int> pa;
int g;

void wide(int num){

  memset(d,-1,sizeof(d));
  d[num] = 0;
  qu.push(make_pair(num,d[1]));

  while(!qu.empty()){

    pa = qu.front();
    qu.pop();
    int id = pa.first;

    for(int i = 0; i < (int)v[id].size(); i++){
      if(d[v[id][i]] == -1){
	d[v[id][i]] = pa.second + 1;
	qu.push(make_pair(v[id][i],d[v[id][i]]));
      }
    }
  }
  for(int i = 1; i <= g; i++){
    cout << i << " " << d[i] << endl;
  }

}

int main(){

 
  cin >> g;
  int n;
  for(int i = 0; i < g; i++){
    cin >> n >> b;
    for(int j = 0; j < b; j++){
      cin >> root;
      v[n].push_back(root);
    }
  }

  wide(1);

}

Measured memory_bytes: 1228
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

int n;

bool check(vector<int> a) {
	rep(i, a.size()) {
		if (a[i] != i + 1)return false;
	}
	return true;
}

int solve(vector<int> a) {
	int cnt = 0;

	while (1) {
		if (check(a))return cnt;
		int a_size = a.size();
		rep(i, a.size()) a[i]--;
		vector<int> na;
		rep(i, a.size()) {
			if (a[i])na.push_back(a[i]);
		}
 		a = na;
		a.push_back(a_size);
		cnt++;
		
		if (cnt > 10000) return -1;	
	}
}

int main()
{
	while (cin >> n, n) {
		vector<int> b(n);

		rep(i, n)cin >> b[i];

		int ans = solve(b);
		if (ans != -1)cout << ans << endl;
		else cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3160
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
using namespace std;
using ll = long long;
using vi = vector<int>;

int main() {
  string S, T;
  cin >> S >> T;
  int mx = 0;
  rep(i, S.size() - T.size() + 1) {
    int cnt = 0;
    rep(j, T.size()) {
      if (S[i + j] == T[j]) cnt++;
    }
    mx = max(mx, cnt);
  }
  cout << T.size() - mx << endl;
  return 0;
}


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

int main(void){
    int r, d, x;
    cin >> r >> d >> x;

    int ans = x;
    rep(i, 10){
        ans = r * ans - d;
        cout << ans << endl;
    }
}


Measured memory_bytes: 384
#include <stdio.h>

int main(void){
  
  int A;
  int B;
  
  scanf("%d",&A);
  scanf("%d",&B);
  
  if(B % A == 0){
    printf("%d",A + B);
  }
  else{
    printf("%d",B - A);
  }
  
  return 0;
}

Measured memory_bytes: 128
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecVec = vector<Vec>;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fs first
#define sc second
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;}
template <typename T>
void co(const T n){cout << n << endl;}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void coVec(const Vec &v){for(ll i : v) cosp(i); cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;

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

int main(void){
	ll a, b;
	cin >> a >> b;
	co(a/gcd(a, b)*b);

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using llong = long long;

int main(){
  llong n;
  cin >> n;
  vector<llong> a(n);

  for(llong i=0;i<n;++i){
    cin >> a[i];
    a[i] -= i+1;
  }
  sort(a.begin(),a.end());
  llong middle = a[n/2];
  llong sadness = 0;
  for(auto v:a){
    sadness += abs(v-middle);
  }
  cout << sadness << endl;
  return 0;
}


Measured memory_bytes: 1792
'''
Author : Shubhanshu Jain;
'''

import math
import random;
from collections import defaultdict 
mod =1000000007
r1 = lambda : int(input());
rm = lambda : map(int,input().split());
rms = lambda : map(str,input().split());
rls = lambda : list(rm())

def solve():
    ls = rls();
    print(ls.index(0)+1)
        
        





def def_value(): 
	return "nan"
	
solve();



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

#define all(x) (x).begin(), (x).end()
#define itn int
#define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end())

using namespace std;

inline int nxt() {
	int x;
	scanf("%d", &x);
	return x;
}

int main() {
	int n = nxt();
	vector<itn> a(n);
	for (int i = 0; i < n; ++i) {
		a[i] = nxt();
	}
	map<int, int> M;
	int ans = 0;
	for (int x : a) {
		M[x] += 1;
	}
	make_unique(a);
	reverse(all(a));
	for (int x : a) {
		if ((x & (x - 1)) == 0) {
			ans += M[x] / 2;
		} else {
			int t = 1 << (32 - __builtin_clz(x));
			int z = min(M[x], M[t - x]);
			ans += z;
			M[t - x] -= z;
		}
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 19712
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner s=new Scanner(System.in);
		HashMap<String,Integer> h=new HashMap<String,Integer>();
		String n[]=new String[1000];
		int index=0;
		while(s.hasNext()){
			String b=s.next();
			if(h.containsKey(b)){
				int c=h.get(b).intValue();
				h.put(b,Integer.valueOf(c+1));
			}else{
				h.put(b,Integer.valueOf(1));
				n[index++]=b;
			}
		}
		int max=0;
		String maxs="";
		int test=0;
		String tests="";
		for(int i=0;i<index;i++){
			if(n[i].length()>max){
				max=n[i].length();
				maxs=n[i];
			}
			if(h.get(n[i]).intValue()>test){
				test=h.get(n[i]).intValue();
				tests=n[i];
			}
		}
		System.out.println(tests+" "+maxs);
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> s(n),l(n),p(n);
    rep(i,n) cin>>s[i]>>l[i]>>p[i];
    int m;
    cin>>m;
    bool flag=true;
    vector<int> ans;
    vector<vector<int> > dp(400,vector<int>(400));
    rep(j,400)rep(k,400) dp[j][k]=-1;
    dp[0][0]=0;
    rep(x,n)FOR(k,s[x],l[x]+1)rep(j,400){
      if(j>=k && dp[x+1][j-k]>=0){
        dp[x+1][j]=max({dp[x+1][j],dp[x][j],dp[x+1][j-k]+p[x]});
            //cout<<k<<' '<<j<<' '<<dp[x+1][j]<<endl;
      }else{
        dp[x+1][j]=max(dp[x+1][j],dp[x][j]);
      }
    }/*
      rep(x,n+1){
        rep(j,w+1){
          cout<<dp[x][j]<<' ';
        }
        cout<<endl;
      }*/
    rep(i,m){
      int w;
      cin>>w;
      if(!flag) continue;
      if(dp[n][w]==-1) flag=false;
      else ans.push_back(dp[n][w]);
    }
    if(flag){
      for(auto itr:ans) cout<<itr<<endl;
    }
    else cout<<-1<<endl;
}


Measured memory_bytes: 3676
#include<stdio.h>
int prime(int n)
{
	if (n < 2)
		return 0;
	if (n == 2)
		return 1;
	int i;
	for (i = 2; i * i <= n; i++)
		if (n % i == 0)
			return 0;
	return 1;
}
int main()
{
	int x;
	scanf("%d", &x);
	for (;; x++)
	{
		if (prime(x) > 0)
		{
			printf("%d\n", x);
			return 0;
		}
	}
}

Measured memory_bytes: 128
n=int(input())
l=list(map(int,input().split()))
n1=-1
n2=-1
n3=-1
ans=1
mod=1000000007
b=True
for i in range(n):
  num=l[i]
  if num==n1+1 and num==n2+1 and num==n3+1:
    ans=(ans*3)%mod
    n1+=1
  elif num==n1+1 and num==n2+1:
    ans=(ans*2)%mod
    n1+=1
  elif num==n2+1 and num==n3+1:
    ans=(ans*2)%mod
    n2+=1
  else:
    if num==n1+1:
      n1+=1
    elif num==n2+1:
      n2+=1
    elif num==n3+1:
      n3+=1
    else:
      b=False
      break
if b:    
  print(ans%mod)
else:
  print(0)

Measured memory_bytes: 14056
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor, gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10
    U = list()
    L = list()
    N = II()
    for i in range(N):
        a,b = LMIIS()
        U.append(b)
        L.append(a)
    U.sort()
    L.sort()
    if N % 2 == 1:
        upper = U[(1+N)//2-1]
        lower = L[(1+N)//2-1]
        print(int(upper-lower)+1)
    else:
        upper = (U[N//2-1]+U[N//2])
        lower = (L[N//2-1]+L[N//2])
        print(upper-lower+1)
    
    
        




    
main()

Measured memory_bytes: 97136
def main():
    a,b,c = map(int,input().split())
    k=int(input())
    while(k>0):
        if(a>=b):
            b *= 2
        elif(b>=c):
            c *= 2
        k -= 1
        if(a < b and b < c):
            print("Yes")
            return

    print("No")
    return

if __name__=="__main__":
    main()

Measured memory_bytes: 9172
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <cmath>
using namespace std;

int main(int argc, const char * argv[]) {
  string s;
  vector<char> ans;
  cin >> s;
  for(int i = 0; i < s.size();i++){
    if(s.at(i) != 'B'){
      ans.push_back(s.at(i));
    }else{
      if(ans.size() != 0){
        ans.pop_back();
      }
    }
  }
  for(int i = 0; i < ans.size();i++){
    cout << ans.at(i);
  }
  cout  << endl;
  return 0;
}


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

using namespace std;

int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	int sum1=abs(b-a)+abs(c-b),sum2=abs(c-a)+abs(b-c),sum3=abs(a-b)+abs(c-a),sum4=abs(a-c)+abs(b-a),sum5=abs(a-c)+abs(b-a),sum6=abs(b-c)+abs(b-a);
	cout<<min(min(sum5,sum6),min(min(sum1,sum2),min(sum3,sum4)))<<endl;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/dp/tasks/dp_b

import * as fs from "fs";

const split = (str: string): string[] =>
  str.split(" ").map((v: string) => v.trim());
const split_number = (str: string): number[] =>
  split(str).map((v: string) => +v);

export function main(input: string) {
  const lines = input.split("\n");
  const [n] = split_number(lines[0]);

  // Playの初期化
  let play: number[][] = [];
  for (let i = 0; i < n; i++) {
    play[i] = split_number(lines[i + 1]);
  }

  // DP値の初期化
  let dp: number[][] = [];
  for (let i = 0; i < n + 1; i++) {
    dp[i] = [0, 0, 0];
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < 3; j++) {
      for (let k = 0; k < 3; k++) {
        if (j != k) {
          dp[i + 1][k] = Math.max(dp[i + 1][k], dp[i][j] + play[i][k]);
        }
      }
    }
  }

  return Math.max(...dp[n]);
}

if (!process.env.LOCAL_DEBUG) {
  console.log(main(fs.readFileSync("/dev/stdin", "utf8")));
}


Measured memory_bytes: 55984
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define num 1000000007
//#define num 998244353
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define up(a,b) (((a)%(b)==0)?((a)/(b)):((a)/(b))+1)
#define inarr(i,a,n,A) for(ll i=a;i<n;i++) { cin>>A[i]; }
#define vll vector<long long>
#define pii pair <int,int>
#define pll pair<long long, long long>
#define vpii vector< pair <int,int>>
#define vpll vector< pair<long long, long long>>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) (a>b)?(a>c)?a:c:(b>c)?b:c
#define min3(a,b,c) (a<b)?(a<c)?a:c:(b<c)?b:c
#define avg(a,b) ((a)+(b))/2
#define pb push_back
#define pob pop_back
#define mp make_pair
#define sf int flag=0     //Remember semicolon
#define assmin(a,b) if(b<=a) { a=b; }
#define assmax(a,b) if(b>=a) { a=b; }
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
typedef long long ll;

ll mymod(ll a, ll b)
{
	return (a%b + b)%b;
}
 
 
ll mod_exp(ll a, ll b, ll c)
{
	ll res=1;
	a=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			res=(res*a)%c;
		}
		b/=2;
		a=(a*a)%c;
	}
	return res;
}
ll gcd(ll a, ll b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b, a%b);
}
bool prime[3001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    prime[1]=false;
    for (int p=2; p*p<=3000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=3000; i += p) 
                prime[i] = false; 
        } 
    } 
}
ll powe[20];
void power()
{
	powe[0]=1;
	REP(i,1,20)
	{
		powe[i]=(powe[i-1]*10)%num;
        if(powe[i]<0)
        powe[i]+=num;
	}
}
struct node
{
	vll adj;
    ll dist;
};

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,x,y;
    cin>>n>>x>>y;
    node N[n+1];
    REP(i,1,n)
    {
        N[i].adj.push_back(i+1);
        N[i+1].adj.push_back(i);
    }
    N[x].adj.push_back(y);
    N[y].adj.push_back(x);
    map<ll,ll> m;
    REP(i,1,n+1)
    {
        bool vis[n+1];
        queue<ll> q;
        memset(vis, false, sizeof(vis));
        q.push(i);
        N[i].dist=0;
        vis[i]=true;
        while(!q.empty())
        {

            ll f=q.front();
            q.pop();
            for(auto x: N[f].adj)
            {
                if(!vis[x])
                {
                    N[x].dist = N[f].dist + 1;
                    m[N[x].dist]++;
                    vis[x]=true;
                    q.push(x);
                }
            }
        }
    }
    REP(i,1,n)
    {
        cout<<m[i]/2<<endl;
    }
	return 0;
}




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

int main(){
  int n;
  cin >> n;
  vector<int> p(n);
  int cnt = 0;
  for(int i = 0;i < n;i++)cin >> p[i];
  for(int i = 0;i < n;i++){
    if(p[i] == i+1);
    else{
      cnt++;
    }
  }
  if(cnt > 2)cout << "NO" << endl;
  else cout << "YES" << endl;
  cin >> n; 
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> digs;

int find_g(int x) {
	for (int j=0; j<int(digs.size()); j++)
			if (digs[j] > x) return digs[j];
	return -1;
}

int find_ge(int x) {
	for (int j=0; j<int(digs.size()); j++)
			if (digs[j] >= x) return digs[j];
	return -1;
}

int main() {
	for (int i=0; i<10; i++)
		digs.push_back(i);

	int n, k; cin>>n>>k;
	while (k--) {
		int d; cin>>d;
		digs.erase(remove(digs.begin(), digs.end(), d), digs.end());
	}

	int num[8], t = 0;
	do {
		num[t++] = n % 10;
		n /= 10;
	} while (n);

	int ans[8];
	for (int i=t-1; i>=0; i--) {
		int g = find_ge(num[i]), idx = i;

		if (g == -1) {
			for (int j=i+1; j<t; j++) {
				g = find_g(num[j]);
				if (g != -1) {
					idx = j;
					break;
				}
			}

			if (g == -1) {
				idx = t++;
				num[idx] = -1;
				g = digs[0] ? digs[0] : digs[1];
			}
		}

		ans[idx] = g;
		if (g > num[idx]) {
			for (int j=idx-1; j>=0; j--)
				ans[j] = digs[0];
			break;
		}
	}

	for (int i=t-1; i>=0; i--)
		cout << ans[i];
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = [[] for i in range(a)]
for i in range(b):
    x,y = map(int,input().split(" "))
    br[x-1].append(y-1)
    br[y-1].append(x-1)
ans = 0
for i in range(a):
    count = 0
    for r in br[i]:
        if ar[r] >= ar[i]:
            count += 1
    if count == 0:
        ans += 1
print(ans)

Measured memory_bytes: 29484
#include<bits/stdc++.h> 
using namespace std;
  
int main() 
{  
    char str1[11] ;
    char str2[12] ;
    cin>>str1>>str2;
    int result1 = strncmp(str2, str1, strlen(str1)); 
   
    if(result1 == 0)          
        printf("Yes\n");     
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 3628
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		S = S.replaceAll("-","");
		if(S.equals(""))System.out.println("-4");
		if(S.equals("+"))System.out.println("-2");
		if(S.equals("++"))System.out.println("0");
		if(S.equals("+++"))System.out.println("2");
		if(S.equals("++++"))System.out.println("4");
	}
}

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


using namespace std;

int main(){
	int N=0,K=0;cin>>N>>K;
	vector<int> array(N);
	
	for(int i=0;i<N;i++)
	    cin>>array[i];
	    
	vector<int> winner(K+1);
	for(int i=0;i<=K;i++)
	    if(winner[i]==0)
	        for(int j=0;j<N && i+array.at(j)<=K;j++) winner[i+array.at(j)] = 1;
	if(winner[K]==1) cout << "First";
	else cout << "Second";
	
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

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


int main(){
    ll n, k;
    cin >> n >> k;
    mint ans(0);
    
    for (ll i=k; i<=n+1; i++) {
        ll l = i*(i-1)/2;
        ll r = (2*n-i+1)*i/2;
        ans += (r-l+1);
    }
    
    
    
    cout << ans.x << endl;
    return 0;
}


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

int main(void)
{
    char a,b;

    cin>>a>>b;
    int c,d;
    c=0?a=='H':'D';
    d=1?b=='H':'D';
    int ans=a^b;
    cout <<(ans==0?'H':'D')<<endl;

    return 0;
}


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

int payment(vector<int> p){
	  return 10*p[0] + 50*p[1] + 100*p[2] + 500*p[3];
}
vector<int> charge(int m){
	  vector<int> ans(4);
	  ans[3] = m/500; m -= (m/500)*500;
	  ans[2] = m/100; m -= (m/100)*100;
	  ans[1] = m/50;  m -= (m/50)*50;
	  ans[0] = m/10;
	  return ans;
}

bool judge(vector<int>& f, vector<int>& ch ){
	  for(int i=0; i<4; i++)
			if( f[i] == 1 and ch[i] > 0)
				  return false;
	  return true;
}

int main(){
	  int N;  cin >> N;
	  while(1){
   
			vector<int> c(4);
			int sum=0;;
			for(int i=0; i<4; i++){
				  cin >> c[i];
				  sum += c[i];
			}
			vector<int> f(4,0);
			int mini = 1e+9;
			vector<int> pay(4);
			vector<int> ans(4);
			for(pay[0]=0; pay[0]<=c[0]; pay[0]++){
				  if(pay[0]>0) f[0] = 1;
				  for( pay[1]=0; pay[1]<=c[1]; pay[1]++){
						if(pay[1]>0) f[1] = 1;
						for(pay[2]=0; pay[2]<=c[2]; pay[2]++){
							  if(pay[2]>0) f[2] = 1;
							  for(pay[3]=0; pay[3]<=c[3]; pay[3]++){
									if(pay[3]>0) f[3] = 1;

									int m_pay = payment(pay);
									int n_pay = accumulate(pay.begin(), pay.end(), 0);
													  
									if( m_pay >= N ){
										  vector<int> ch = charge( m_pay - N );
										  int n_charge = accumulate(ch.begin(), ch.end(), 0);
										  if(mini > sum - n_pay + n_charge){
												if( judge(f,ch) ){
													  ans = pay;
													  mini = sum - n_pay + n_charge;
												}
										  }
									}
									f[3] = 0;
							  }
							  f[2] = 0;
						}
						f[1] = 0;
				  }
				  f[0] = 0;
			}
			
				  
			for(int i=0; i<4; i++){
				  if(ans[i] > 0){
						if(i==0)
							  cout << 10 << " " << ans[i] << endl;
						if(i==1)
							  cout << 50 << " " << ans[i] << endl;
						if(i==2)
							  cout << 100 << " " << ans[i] << endl;
						if(i==3)
							  cout << 500 << " " << ans[i] << endl;

				  }
			}
			cin >> N; if(!N) break;
			cout << endl;
	  }
	  
	  
}

Measured memory_bytes: 1216
# N = input()
NArray = []
operator = []
operand = []
for x in raw_input().split():
  if  x == '+':
    a1 = operand[len(operand)-1]
    operand.pop()
    a2 = operand[len(operand)-1]
    operand.pop()
    operand.append(a2 + a1)
  elif  x == '-':
    a1 = operand[len(operand)-1]
    operand.pop()
    a2 = operand[len(operand)-1]
    operand.pop()
    operand.append(a2 - a1)
  elif  x == '*':
    a1 = operand[len(operand)-1]
    operand.pop()
    a2 = operand[len(operand)-1]
    operand.pop()
    operand.append(a2 * a1)
  else:
    operand.append(int(x))

print operand[0]
  

Measured memory_bytes: 6296
#include <stdio.h>

int main(void) {
  int n, k, x, y;
  int sum = 0;

  scanf("%d", &n);
  scanf("%d", &k);
  scanf("%d", &x);
  scanf("%d", &y);

  if(n <= k) {
    sum = n * x;
    printf("%d\n", sum);
  }
  else {
    sum = k * x + (n - k) * y;
    printf("%d\n", sum);
  }

  return 0;
}

Measured memory_bytes: 128
using System;

namespace AOJ.Volume5
{
    public class MaximumSum
    {
        public static int Main()
        {
            while (true)
            {
                var input = Console.ReadLine().Split(' ');
                int n = int.Parse(input[0]);
                int k = int.Parse(input[1]);
                if (n == 0 && k == 0) { break; }

                // ??\??????????????´??°????¶?????????????
                var sum = new long[n + 1];
                sum[0] = 0;
                for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + long.Parse(Console.ReadLine()); }

                // ?????§????????¢???
                // i??????(i >= 1)??????i+k-1???????????§???k????????´??°?????????
                // sum[i+k-1] - sum[i-1]
                long answer = long.MinValue;
                for(int i = 1; i <= n - k + 1; i++)
                {
                    answer = Math.Max(answer, sum[i + k - 1] - sum[i - 1]);
                }
                Console.WriteLine(answer);
            }
            return 0;
        }
    }
}

Measured memory_bytes: 10400
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
using namespace std;

int main()
{
	int N;
	cin >> N;
	vector<unsigned long long> count(5);
	string s = "MARCH";
	for (auto i = 0; i < N; ++i)
	{
		string S;
		cin >> S;
		for (auto j = 0; j < 5; ++j)
		{
			if (S[0] == s[j])
			{
				++count[j];
				break;
			}
		}
	}

	auto result = 0ull;
	for (auto i = 0; i < 3; ++i)
	{
		for (auto j = i + 1; j < 4; ++j)
		{
			for (auto k = j + 1; k < 5; ++k)
			{
				result += count[i] * count[j] * count[k];
			}
		}
	}

	cout << result << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,k;cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    int dp[n];
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++){
        int x=a[i];dp[i]=INT_MAX;
        for(int j=i-1;j>=0&&j+k>=i;j--){
            dp[i]=min(dp[i],abs(x-a[j])+dp[j]);
        }
    }
    cout<<dp[n-1];
}


Measured memory_bytes: 4372
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
int main(){
  long long int n,ans=1;
  cin>>n;
  bool flag=true;
  vector<int> v(n);
  rep(i,n) cin>>v[i];
  sort(v.begin(),v.end());
  rep(i,n){
    if(n%2==0){
      if(v[i]!=(i/2)*2+1){
        flag=false;
        break;
      }
    }else{
      if(v[i]!=((i+1)/2)*2){
        flag=false;
      }
    }
  }
  long long int count=n/2;
  count%=1000000007;
  rep(i,count){
    ans*=2;
    ans%=1000000007;
  }
  if(flag){
    cout<<ans<<endl;
  }else{
    cout<<0<<endl;
  }
}


Measured memory_bytes: 640
X = int(input())
s = [0] * (X + 1)
for i in range(1, 1001):
    for j in range(2, 1001):
        n = i**j
        if n > X: break
        s[n] += 1
for i in range(X, 0, -1):
    if s[i]:
        print(i)
        exit()


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

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  ll n;
  cin >> n;
  ll ans = 1LL<<60;
  for (ll i = 1; i*i <= n; ++i) {
    if (n % i != 0) continue;
    ll res = i + n/i - 2;
    ans = min(ans,res);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256