akhauriyash/Code-Regression huggingface dataset:
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;
//const ll MAX_V=114514LL;
//const ll MAX = 500010LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={0,0,1,-1};
vl dy={1,-1,0,0};

//素因数分解O(√n)
map<ll,ll>prime_factor(ll n){
  map<ll,ll>res;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}

const ll MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
//finvが階乗の逆元

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

// 二項係数計算
long long 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;
}

ll modpow(ll a, ll n, ll mod) {
  
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}



int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cout << fixed << setprecision(10);
  /*--------------------------------*/
  ll n;cin>>n;
  map<string,ll>M;
  rep(i,n){
    string s;cin>>s;
    M[s]++;
  }
  cout<<"AC"<<" "<<"x"<<" "<<M["AC"]<<endl;
  cout<<"WA"<<" "<<"x"<<" "<<M["WA"]<<endl;
  cout<<"TLE"<<" "<<"x"<<" "<<M["TLE"]<<endl;
  cout<<"RE"<<" "<<"x"<<" "<<M["RE"]<<endl;
}

Measured memory_bytes: 3676
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] s = new String[n];
        for(int i=0;i<n;i++) s[i] = sc.next();
        int[][] map = new int[n][26];
        for(int i=0;i<n;i++){
            String cur = s[i];
            for(int j=0;j<cur.length();j++){
                map[i][cur.charAt(j)-'a']++;
            }
        }
        int[] res = new int[26];
        for(int i=0;i<26;i++){
            int min = Integer.MAX_VALUE;
            for(int j=0;j<n;j++) min = Math.min(min,map[j][i]);
            res[i]=min;
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<26;i++){
            char cur = (char)(i+'a');
            for(int j=0;j<res[i];j++) sb.append(cur);
        }
        System.out.println(sb.toString());
    }
}



Measured memory_bytes: 24020
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279

#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 1; i <= n; i++)
#define REPR(i, n) for(ll i = n; i >= 1; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
const ld INF = 1e9+123;
#define VEC(type,A,N) vector<type> A(N+10)
#define VECi(type,A,N,i) vector<type> A(N+10,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N+10,vector<type>(M+10))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N+10,vector<type>(M+10,i))
#define ALL(v) v.begin(), v.end()
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
int main(){
    ll N;
    cin>>N;
    
    ll n=N;
    if(N%2==1){
        cout<<0;
        return 0;
    }
    ll cnt=0,t=10,tt=50,ttt=1;
    while(false){
        if(N/t==0)break;
        cnt+=N/t;
        t*=10;
    }
    while(true){
        if(N/tt==0)break;
        cnt+=(N/tt);
        tt*=5;
    }
    //sl(N)
    cout << N/10+cnt;
    
    //cout<<fixed<<setprecision(32)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();

		long ans = 0;
		if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0) {
			ans = 0;
		} else {
			ans = Math.min(Math.min(A * B, B * C), C * A);
		}

		System.out.println(ans);
	}
}


Measured memory_bytes: 9936
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
using namespace std;
int main(){
    
    long long n,k;
    cin>>n>>k;
    long long ans=0;
    ans+=(n/k)*(n/k)*(n/k);
    
    if(k%2==0){
        long long x=n/(k/2)-(n/k);
        ans+=x*x*x;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
ws = [input() for _ in range(n)]

ans = 'Yes'
w = ws[0]
end = w[-1]
w_map = {w:1}
for i in range(1, n):
    w_next = ws[i]
    if not w_next in w_map.keys():
        w_map[w_next] = 1
    else:
        ans = 'No'
        break
    if w_next[0] != end:
        ans = 'No'
        break
    w = w_next
    end = w[-1]
print(ans)


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

using namespace std;

int main() {

	int h, w;
	cin >> h >> w;

	char chars[h][w];
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> chars[i][j];
		}
	}

	int result[h][w];
	// for (int i = 0; i < h; i++) {
	// 	for (int j = 0; j < w; j++) {
	// 		result[i][j] = 0;
	// 	}
	// }
	result[h-1][w-1] = 1;

	for (int i = h-1; i >=0; i--) {
		for (int j = w-1; j>= 0; j--) {
			if (i == h-1 && j == w-1) {
				continue;
			}
			result[i][j] = 0;
			if (i+1 <= h-1 && chars[i+1][j] == '.') {
				result[i][j] += result[i+1][j];
			}
			if (j+1 <= w-1 && chars[i][j+1] == '.') {
				result[i][j] += result[i][j+1];
			}
			result[i][j] %= 1000000007;
		}
	}

	// for (int i = 0; i < h; i++) {
	// 	for (int j = 0; j < w; j++) {
	// 		cout << result[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	cout << result[0][0] << endl;

}

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

long long GCD(long long a, long long b) 
{ 
    if(b==0) 
        return a; 
    return GCD(b, a % b);  
      
}

long long LCM(long long a, long long b)
{
    long long gcd=GCD(a,b);
     return (a*b)/gcd;
}

int main()
{
    long long i, j, k, n, m, t, x, y, s=0, c=0, l;
    cin >> n >> m;
    if(n==m)
        cout << "Yes\n";
    else
    {
        cout << "No\n";
    }
    
}


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

using namespace std;

string str[65];
map<string, unsigned long long int> ans[101];

int init() {
  char c[4] = {'A', 'C', 'G', 'T'};
  int index=0;
  for (int i=0; i<4; i++)
    for (int j=0; j<4; j++)
      for (int k=0; k<4; k++) {
          str[index++] = string() + c[i] + c[j] + c[k];
        }
    return 0;
}

int main () {
  int N;
  unsigned long long int MOD = 1000000007LL;
  char c[4] = {'A', 'C', 'G', 'T'};
  cin >> N;

  init();
  for (int i=0; i<64; i++) {
    if (str[i] != "AGC" && str[i] != "GAC" && str[i] != "ACG") {
      ans[3][str[i]] = 1;
    } else
      ans[3][str[i]] = 0;
  }

  for (int i=4; i<=N; i++) {
    for (int j=0; j<4; j++) {
      for (int k=0; k<64; k++) {
        string check_str = str[k].substr(1) + c[j];
        if (check_str != "AGC" && check_str != "GAC" && check_str != "ACG"
            && !(str[k].find("AG") == 0 && c[j]=='C') && !(str[k].find("A") == 0 && check_str.substr(1) == "GC")) {
          ans[i][str[k].substr(1)+c[j]] += ans[i-1][str[k]];
          ans[i][str[k].substr(1)+c[j]] %= MOD;
        }
      }
    }
  }

  unsigned long long int A = 0;
  for (auto i=ans[N].begin(); i!=ans[N].end(); i++) {
    A = (A + i->second) % MOD;
  }
  cout << A << endl;

  return 0;
}

Measured memory_bytes: 896
<?php
$k = trim(fgets(STDIN));
fscanf(STDIN,"%d %d",$a,$b);
$i = 0;
while (@$num < 1000) {
    $num = $k * ++$i;
    if ($num >= $a and $num <= $b) {
        echo "OK".PHP_EOL;
        exit;
    }
}
echo "NG".PHP_EOL;

Measured memory_bytes: 16036
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
#define INF 1000000001
#define INFL 1000000000000000001
#define M 1000000007
int main(void){
	int n;
	bool ok=true;
	cin>>n;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		if(a%2==0&&a%3!=0&&a%5!=0)ok=false;
	}
	if(ok)printf("APPROVED\n");
	else printf("DENIED\n");
}


Measured memory_bytes: 256
//const config = { stdin: 'tmp', newline: '\r\n' }; // win
const config = { stdin: '/dev/stdin', newline: '\n' }; // linux

line = require('fs').readFileSync(config.stdin, 'ascii').trim()
	.split(config.newline);
line.shift();
res = line.reduce(function (prev, cur) {
	ary = cur.split(' ');
	if (ary[0] > ary[1]) prev[0] += 3;
	else if (ary[0] !== ary[1]) prev[1] += 3;
	else { prev[0]++; prev[1]++; }
	return prev;
}, [0, 0]);
console.log(res.join(' '));

Measured memory_bytes: 15796
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

ans = 0
if n <= k
  ans = 1
elsif n <= (k * 2) - 1
  ans = 2
else
  ans = ((n - 1) + (k - 2)) / (k - 1)
end
puts ans


Measured memory_bytes: 8708
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std; 

#define is_uruu leapyear
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(a);i>(b);--i)
    

int main() {
	int c0=0, c1=0, c2=0, n, a[100001];
	cin >> n;
	FOR(i, 0, n) cin >> a[i];
	
	FOR(i, 0, n){
		switch (a[i] % 4){
			case 0:
			c2++;
			break;
			
			case 2:
			c1++;
			break;
			
			case 1:
			case 3:
			c0++;
			break;
		}
	}
	if(c1 == 0){
		if(c0 <= c2 + 1) cout << "Yes" << endl;
		else cout << "No" << endl;
		return 0;
	}
	if(c0 <= c2) cout << "Yes" << endl;
		else cout << "No" << endl;
		return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int main()
{
    int n,m,i,a[10001],sum = 0;
    scanf("%d%d",&n,&m);
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    double vote = (double)sum/(4*m);
    int cnt = 0;
    for(i=0; i<n; i++)
        if(a[i]>=vote)cnt++;
    if(cnt>=m) printf("Yes\n");
    else if(cnt<m)printf("No\n");

    return 0;
}


Measured memory_bytes: 128
K, N = map(int,input().split())
A = list(map(int,input().split()))
A_edi = A
ans = []
for i in range(N-1):
    A_edi.append(A[i]+K)
for k in range(len(A)-N+1):
    ans.append(A[k+N-1]-A[k])
print(min(ans))



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

using namespace std;

long long dp[55][55][2555];
long long a[55];

int main(){
	int n, A;
	scanf("%d %d", &n, &A);
	for (int i = 0; i < n; i++){
		scanf("%lld", a + i);
	}
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			for (int k = 0; k < 2501; k++){
				if (dp[i][j][k]){
					dp[i + 1][j + 1][k + a[i]] += dp[i][j][k];
					dp[i + 1][j][k] += dp[i][j][k];
				}
			}
		}
	}
	long long ans = 0;
	for (int i = 1; i <= n; i++){
		ans += dp[n][i][i * A];
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 55552
#include<iostream>
using namespace std;
int n,a[100005];
int main()
{
	cin>>n;
	int x;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		a[x]=i;
	}
	for(int i=1;i<=n;i++)
	cout<<a[i]<<" ";
	return 0; 
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;
  cin>>n;
  ll s=0;
  ll c=0;
  ll g;
  for(ll i=1;i<=n;i++){
   for(ll j=1;j<=n;j++){
    for(ll k=1;k<=n;k++){
        g=__gcd(j,k);
        s+=__gcd(i,g);
    }
   }
  }
  cout<<s<<endl;
}


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main()
{
    int N, M;
    cin >> N >> M;
    if(M == 0){
        if(N == 1){
            cout << 0 << endl;
            return 0;
        }
        else{
            cout << pow(10, N-1) << endl;
            return 0;
        }
    }
    vector<int> S(M);
    vector<int> C(M);

    REP(i, M){
        cin >> S[i] >> C[i];
    }

    REP(i, M){
        if(S[i] == 1){
            if(C[i] == 0){
                if(N != 1){
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
    }

    for(int i=0; i<M-1; i++){
        for(int j=i+1; j<M; j++){
            if(S[i] == S[j]){
                if(C[i] != C[j]){
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
    }
    vector<bool> check(N,false);
    int ans = 0;
    for(int i=0; i<M; i++){
        if(check[S[i]-1] == false){
            ans += pow(10,(N-S[i])) * C[i];
            check[S[i]-1] = true; 
        }
    }

    if(check[0] == false){
        ans += pow(10, N-1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int
main(int argc, char *argv[])
{
    char s1[51];
    char s2[51];
   
    scanf("%s",s1);
    scanf("%s",s2);
    
       
    for(int i=0;i<strlen(s1)-1;i++){
        printf("%c%c",s1[i],s2[i]);
    }
    if(strlen(s1)==strlen(s2)){
        printf("%c%c",s1[strlen(s1)-1],s2[strlen(s2)-1]);
    }
    else{
        printf("%c",s1[strlen(s1)-1]);
    }
    printf("\n");
        return 0;
}


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

int ex(char x){
  return int(x-'0');
}

int main(){
  string S;cin >> S;
  int N = S.size()-1;
  int A = ex(S[0]);
  vector<int> B(N);
  for(int i=0;i<N;i++){
    B[i]=ex(S[i+1]);
  }
  for(int bit=0;bit<(1<<N);bit++){
    vector<char> op(N,'-');
    int sum = A;
    for(int i=0;i<N;i++){
      if(bit&(1<<i)){
        op[i] = '+';
        sum += 2*B[i];
      }
      sum -= B[i];
    }
    if(sum==7){
      cout << A;
      for(int i=0;i<N;i++){
        cout << op[i] << B[i];
      }
      cout << "=7" << endl;
      return 0;
    }
  }
  cout << "impossible" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <climits>
#include <sstream>
#include <array>
#include <tuple>
#include <set>
#include <iterator>
#include <cstdio>
#include <string>
#include <stack>
#include <valarray>
#include <utility>
#include <iomanip>
#include <list>
#include <numeric>
#include <regex>
#include <map>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll          long long
#define PI          3.1415926535
#define pb          push_back
#define ins         insert
#define INF         LLONG_MAX
#define mk          make_pair
#define lb(v,x)     lower_bound(all(v),x)
#define ub(v,x)     upper_bound(all(v),x)
#define ff          first
#define ss          second
#define rev         reverse
#define uset        unordered_set
#define umap        unordered_map
#define endl        "\n"
#define max3(x,y,z)  max(x,max(y,z))
#define min3(x,y,z)  min(x,min(y,z))
#define sz(a)       (ll)a.size()
#define double      long double
#define minpq       priority_queue <ll,vector<ll>,greater<ll> > 
#define fill(x,y)   memset(x,y,sizeof(x))
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define MOD         1000000007 //1e9+7
#define bp(n)       __builtin_popcountll(n)
#define mxt(a)      *(max_element(a.begin(),a.end()))
#define mnt(a)      *(min_element(a.begin(),a.end())
#define unique_sort(c) (sort(all(c)), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define rep(i, a, b) for(ll i = (a); i<= (b); ++i)
#define trav(a, x) 	 for(auto &a : x)
#define re(i,n)      for(ll i = 0; i < n; ++i) 
const ll N = 4e5 + 7;
typedef pair<ll,ll>   pii;
typedef vector<pii>   vpii;
typedef vector<ll>    vll;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
ll power(ll x,ll y){ll res=1;x=x;while(y>0){if(y&1)res=(res*x);y=y>>1;x=(x*x);}return res;}
template<typename T> T gcd(T a,T b){ if(a==0) return b; return gcd(b%a,a); }
template<typename T> T powm(T a,T b, ll m){T cnt=1; while(b>0){ if(b%2==1) cnt=(cnt*a)%m; b/=2; a=(a*a)%m; }return cnt%m;}
ll ncr(ll n,ll r){ll res=1;if(r>n)return 0;if(r>n-r)r=n-r;for(ll i=0;i<r;i++){res*=(n-i);res/=(i+1);}return res;}
ll sqr(ll x) { return x * x;}
// always use 1ll*ans to avoid signed integer overflow; 
void prec(){

}
ll n,k,x,i,j,pos;
vll ad[N];
vll v,repeat;
bool vis[N];
void dfs(ll x){
	vis[x]=true;
	v.pb(x);
	for(auto it: ad[x]){
		if(!vis[it]) dfs(it);
	}
}
void solve(){
	cin>>n>>k;
	rep(i,1,n){
		cin>>x;
		ad[i].pb(x);
	}
	dfs(1);
	//trav(a,v) cout<<a<<" ";
	ll last=ad[v.back()][0];
	for(int i=0; i<sz(v); ++i)
		if(v[i]==last) pos=i;
	for(int i=pos; i<sz(v); ++i){
		repeat.pb(v[i]);
	}
	if(k<=sz(v)-1) cout<<v[k]<<endl;
	else{
		k-=pos;
		cout<<repeat[k%sz(repeat)]<<endl;
	}
}

int main()
{
    ios;
    int tc=1;
    //cin>>tc;
    prec();
    while(tc--)
    	solve();
    return 0; 
}


Measured memory_bytes: 34608
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,i,j,a[105],ans[100005],cnt;
bool cmp(int a,int b)
{
	return a%2<b%2;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d",a+i);
		if(a[i]&1)
			++j;
	}
	if(j>2)
	{
		printf("Impossible");
		return 0;
	}
	sort(a+1,a+1+m,cmp);
	if(m==1)
	{
		if(a[1]==1)
			ans[++cnt]=1;
		else
		{
			ans[++cnt]=1;
			ans[++cnt]=a[1]-1;
		}
	}
	else
	{
		if(a[m-1]&1)
			swap(a[1],a[m-1]);
		if(a[1]&1)
			ans[++cnt]=a[1]+1;
		else
		{
			ans[++cnt]=1;
			ans[++cnt]=a[1];
		}
		for(i=2;i<m;++i)
			ans[++cnt]=a[i];
		if(a[m]!=1)
			ans[++cnt]=a[m]-1;
	}
	for(i=1;i<=m;++i)
		printf("%d ",a[i]);
	puts("");
	printf("%d\n",cnt);
	for(i=1;i<=cnt;++i)
		printf("%d ",ans[i]);
	return 0;
}


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

int main(){
	int N,M;
	cin>>N>>M;
	vector<int> cnt(N,1);
	vector<bool> flag(N,false);
	flag[0]=true;
	
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		cnt[a]--;
		cnt[b]++;
		if(flag[a])flag[b]=true;
		if(cnt[a]==0)flag[a]=false;
	}
	
	int ans = 0;
	for(int i=0;i<N;i++){
		if(flag[i])ans++;
	}
	
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,count=0,m;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>m;
    for(int j=2;j*j<=m;j++)
      if(m%j==0){
	count++;
	break;
      }
  }
  cout<<n-count<<endl;
  return 0;
}

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

int main(){
    int x;
    cin>>x;
    if (x<1200)
    {
        /* code */
        cout<<"ABC"<<endl;
    }
    else
    {
        cout<<"ARC"<<endl;
    }
    
    
    
    }


Measured memory_bytes: 256
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
M = mod = 10**9 +7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]


def dfs(root):
    global ans,g
    if ans[root]:return 

    temp = 0
    for j in g[root]:dfs(j)
    if len(g[root]):temp = max(ans[j] for j in g[root])
    ans[root] = 1 + temp

n,m = li()
g = defaultdict(set)
for i in range(m):
    a,b = li()
    g[a].add(b)

ans = [0]*(n + 1)

for j in range(1,n + 1):
    if not ans[j]:dfs(j)

print(max(ans) - 1)

Measured memory_bytes: 80036
import itertools
N=input()
ans=0
l=itertools.product(range(2),repeat=len(N)-1)
for i in l:
	tmp=''
	for j in range(len(i)):
		if i[j]==0:
			tmp+=N[j]
		else:
			tmp+=N[j]+'+'
	tmp+=N[-1]
	ans+=eval(tmp)
print(ans)


Measured memory_bytes: 39024
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main()
{
    string s;
    cin >> s;
    int freq[27] = {0};
    for(int i = 0; i < s.size(); i++)
        freq[s[i] - 'a']++;
    for(int i = 0; i < s.size(); i++)
    {
        if(freq[s[i] - 'a'] % 2)
            return cout << "No", 0;
    }
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
 
int main() {
  int k, s;
  cin >> k >> s;
  ll cnt = 0;
  rep(x,k+1) {
    rep(y,k+1) {
      int z = s-x-y;
      if (z>=0 && z<=k) cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3576
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

ll modpow(ll a,ll n,ll mod){
  ll res=1;
  while(n){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

int main(){
  ll N,K;
  cin>>N>>K;
  VL X(K+1);
  ll mod=1e9+7;
  rep(i,K) X[i+1]=modpow(K/(i+1),N,mod);
  rep(i,K) rep(j,K/(K-i)-1) (X[K-i]+=mod-X[(K-i)*(j+2)])%=mod;
  ll ans=0;
  rep(i,K) (ans+=X[i+1]*(i+1)%mod)%=mod;
  cout<<ans<<endl;
}

Measured memory_bytes: 3992
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N = 6;
    int i;
    int a[N];
    int count =0;
    for(i=0;i<N;i++)
    {
        cin >> a[i];
    }
    
    
        if(a[4]-a[0] > a[5])
        {
            count =1;
        }
    
    
    if(count ==0)
    {
        cout << "Yay!"<<endl;
    }
    else
    {
        cout << ":("<<endl;
    }
    return 0;
    
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;

typedef pair<int, int> P;

int main() {
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    int xmax = X;
    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        xmax = max(temp, xmax);
    }
    int ymin = Y;
    for (int i = 0; i < M; i++) {
        int temp;
        cin >> temp;
        ymin = min(temp, ymin);
    }
    cout << (xmax < ymin ? "No War" : "War") << endl;
    return 0;
}

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

//#define USING_LONG_LONG
#ifdef USING_LONG_LONG
    #define int long long
    const int INF=1001001001001001001ll;
#else
    const int INF=1001001001;
#endif

#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define RREP(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define clr(a) memset((a),0,sizeof(a))
#define CLR(a) memset((a),-1,sizeof(a))
#define each(i,v) for(__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define minv(a,b) (a)=min((a),(b))
#define maxv(a,b) (a)=max((a),(b))
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef vector<string>vs;
typedef pair<int,int>pii;
#define fi first
#define se second

const int SQ=400;
int N,Q;
struct latte{
    vi v;
    int s;
    latte(){v.clear();s=0;}
};

vector<latte>li;

signed main(){
    scanf("%d%d",&N,&Q);
    latte now;
    rep(i,N){
        now.v.pb(0);
        if(i%SQ==SQ-1){li.pb(now);now=latte();}
    }
    if(now.v.size())li.pb(now);

    while(Q--){
        int type,x,y;scanf("%d%d%d",&type,&x,&y);
        if(type==0){
            x--;
            int cur=0;
            rep(i,li.size()){
                if(x<cur+li[i].v.size()){
                    li[i].v[x-cur]+=y;
                    li[i].s+=y;
                    break;
                }
                cur+=li[i].v.size();
            }
        }
        else{
            x--;y--;
            int ret=0,cur=0;
            rep(i,li.size()){
                if(x<=cur&&cur+li[i].v.size()<=y+1)ret+=li[i].s;
                else if(!(y<cur||cur+li[i].v.size()<x+1)){
                    rep(j,li[i].v.size()){
                        if(x<=cur+j&&cur+j<=y)ret+=li[i].v[j];
                    }
                }
                cur+=li[i].v.size();
            }
            printf("%d\n",ret);
        }
    }
    return 0;
}

Measured memory_bytes: 1540
import bisect

a, b, q = map(int, input().split())
INF = 10 ** 11
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
x = [int(input()) for _ in range(q)]
s = [-INF] + s + [INF]
t = [-INF] + t + [INF]

ans = []
for xi in x:
    s_idx = bisect.bisect_left(s, xi)
    t_idx = bisect.bisect_left(t, xi)
    yi = []
    for j in range(2):
        sj = s[s_idx - j]
        for k in range(2):
            tk = t[t_idx - k]
            d = min(abs(xi - sj), abs(xi - tk)) + abs(sj - tk)
            yi.append(d)
    ans.append(min(yi))
for ansi in ans:
    print(ansi)


Measured memory_bytes: 21528
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include "iomanip"
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
#include <cassert>
#include <stack>

using namespace std;




void print(vector<int> &b) {
    for (auto i : b) {
        cout << i << " ";
    }
}


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

    int a,b ,c;
    cin >> a>> b >> c;
    cout << max(c - (a - b), 0);

    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n,s=0;
    cin>>n;
    vector<ll> a(n),b(n),c(n-1);
    for(ll i=0;i<n;i++) cin>>a[i];
    for(ll i=0;i<n;i++){
        cin>>b[i];
        s+=b[i];
    }
    for(ll i=0;i<n-1;i++) cin>>c[i];
    for(ll i=0;i<n-1;i++){
        if(a[i+1]==a[i]+1) s+=c[a[i]-1];
    }
    cout<<s<<endl;
    return 0;
}

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

enum Answer {
    Good,
    Bad,
}
fn main() {
    let s: String = read();
    let mut temp: u8 = 100; 
    let mut answer: Answer = Answer::Good;
    for i in s.as_bytes().iter() {
        if temp == *i {
            answer = Answer::Bad;
            break;
        } else {
            temp = *i;
        }
    }
    match answer {
        Answer::Good => { println!("{}", "Good"); }
        Answer::Bad  => { println!("{}", "Bad"); }
    }
}

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


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

int main(){
	int money = 100000;
	int n;

	cin >> n;
	for(int i=0 ; i<n ; i++){
		money *= 1.05;
		if(money%1000 != 0){
			money += 1000 - (money%1000);
		}
	}
	cout << money << endl;
} 

Measured memory_bytes: 0
let rec pow_mod x y m =
  if y = 0 then 1
  else let z = pow_mod (x*x mod m) (y / 2) m in if y mod 2 = 1 then x*z mod m else z

let prime_p n =
  if n == 2 then true
  else if n < 2 || n mod 2 = 0 then false
  else if pow_mod 2 (n - 1) n = 1 then true
  else false

let () =
  let n = read_int () in
  let rec read i cnt =
    if i >= n then cnt
    else read (i + 1) (cnt + (if prime_p (read_int ()) then 1 else 0))
  in
  Printf.printf "%d\n" (read 0 0)

Measured memory_bytes: 2892
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>

using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> l(n);
    for (int i=0; i<n; i++) {
        cin>>l[i];
    }
    sort(l.begin(), l.end());
    int sum=0;
    for (int j=0; j<k; j++) {
        sum += l[l.size()-1-j];
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main() {
  const int n = 3;
  int a[3];
  std::cin >> a[0] >> a[1] >> a[2];

  for(int i = 0; i < n; ++i) {
    for(int j = i; j < n; ++j) {
      if(a[j] < a[i]) {
       int tmp = a[i];
       a[i] = a[j];
       a[j] = tmp;
      }
    }
  }

  std::cout << a[0] << " " << a[1] << " " << a[2] << std::endl;

  return 0;
}

Measured memory_bytes: 3064
while true do
  n = gets.to_i
  break if n == 0

  field = Array.new(21, 0).map{ Array.new(21, 0) }
  gems = []
  n.times do
    gems << gets.split.map(&:to_i)
  end

  bot = [10, 10]
  field[bot[0]][bot[1]] = 1
  gets.to_i.times do
    dir, dis = gets.split
    dis = dis.to_i

    if dir == "N"
      (1..dis).each{ |i| field[bot[0]][bot[1]+i] = 1 }
      bot = [bot[0], bot[1]+dis]
    elsif dir == "E"
      (1..dis).each{ |i| field[bot[0]+i][bot[1]] = 1 }
      bot = [bot[0]+dis, bot[1]]
    elsif dir == "S"
      (1..dis).each{ |i| field[bot[0]][bot[1]-i] = 1 }
      bot = [bot[0], bot[1]-dis]
    elsif dir == "W"
      (1..dis).each{ |i| field[bot[0]-i][bot[1]] = 1 }
      bot = [bot[0]-dis, bot[1]]
    end
  end

  count = 0
  gems.each do |gem|
    x, y = gem
    if field[x][y] == 1
      count += 1
    else
      break
    end
  end

  puts count == n ? "Yes" : "No"
end

Measured memory_bytes: 6128
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int x[60];;
long long dp[60][60][2600];
int main()
{
    int n, a;
    scanf("%d%d", &n, &a);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &x[i]);
    for(int i = 0; i <= n; ++i)
        dp[i][0][0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= i; ++j)
        {
            for(int k = 0; k <= 2500; ++k)
            {
                if(k - x[i] >= 0)
                    dp[i][j][k] += dp[i - 1][j - 1][k - x[i]];
                dp[i][j][k] += dp[i - 1][j][k];
            }
        }
    }
    long long ans = 0;
    for(int i = 1; i <= n; ++i)
        ans += dp[n][i][a * i];
    printf("%lld\n", ans);
    return 0;
}
/*
3 8
8 8 9
 
4 8
7 9 8 9
 
8 5
3 6 2 8 7 6 5 9
 
33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
 
*/

Measured memory_bytes: 61696
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  int a,b,c;
  cin>>a>>b>>c;
  int g=a;
  bool ok=false;
  rep(i,0,1000){
     a%=b;
    if(a==c)ok=true;
    a+=g;
   // cout<<a<<endl;
  }
  if(ok)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}

Measured memory_bytes: 3604
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class AGC002
{
    static void Main(string[] args) {
        var spl = Console.ReadLine().Split();
        long a = long.Parse(spl[0]);
        long b = long.Parse(spl[1]);
        if (a > 0 && b > 0) {
            Console.WriteLine("Positive");
        } else if (a < 0 && b < 0) {
            if (a % 2 == 0 && b % 2 == 0) Console.WriteLine("Negative");
            else if (a % 2 == -1 && b % 2 == -1) Console.WriteLine("Negative");
            else Console.WriteLine("Positive");
        } else {
            Console.WriteLine("Zero");
        }
    }
}


Measured memory_bytes: 2776
N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
weights = list()
values = list()
for _ in range(N):
    v, w = map(int, input().split())
    values.append(v)
    weights.append(w)

for i in range(N):
    for w in range(W+1):
        if w >= weights[i]: 
            dp[i+1][w] = max(dp[i][w-weights[i]] + values[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])


Measured memory_bytes: 41892
def gets_nums
  gets.split(' ').map(&:to_i)
end
until (n_m = gets_nums) == [0, 0]
  puts n_m[0].times
    .map { gets_nums }
    .transpose
    .map {|a| a.reduce(:+) }
    .each.with_index(1)
    .sort_by {|sum, i| [-sum, i] }
    .map {|_, i| i }
    .join(' ')
end

Measured memory_bytes: 7616
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(string, S, T);
  int sl = S.length();
  int tl = T.length();
  vector<string> v;
  rep(i, 0, sl - tl + 1) {
    bool ok = true;
    rep(j, 0, tl) {
      if (S[i + j] != T[j] && S[i + j] != '?') {
        ok = false;
        break;
      }
    }
    if (ok) {
      v.push_back(S.substr(0, i) + T + S.substr(i + tl, sl - i - tl));
    }
  }
  if (v.size()) {
    sort(all(v));
    replace(all(v[0]), '?', 'a');
    print(v[0]);
  } else {
    print("UNRESTORABLE");
  }
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  	int N, L;
    cin >> N >> L;


    int sum = 0;
    for(int i=0;i<N;i++) sum += L+i;

    int ans = 1000;
    int candi;

    for(int i=0;i<N;i++){
      if(abs(L+i)<ans){
        candi = i;
        ans = abs(L+i);
      }
    }

    cout << sum - L - candi <<endl;

    
  	return 0;
}


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

std::string replaceOtherStr(std::string &replacedStr, std::string from, std::string to) {
    const unsigned int pos = replacedStr.find(from);
    const int len = from.length();
 
    if (pos == std::string::npos || from.empty()) {
        return replacedStr;
    }
 
    return replacedStr.replace(pos, len, to);
}

int main() {
    string s;
    
 
   cin >> s;
  
  
std::string target = ",";     // 検索文字列
std::string replacement = " "; // 置換文字列
if (!target.empty()) {
  std::string::size_type pos = 0;
  while ((pos = s.find(target, pos)) != std::string::npos) {
    s.replace(pos, target.length(), replacement);
    pos += replacement.length();
  }
}
   
  
   cout << s << endl;
   
  
  return 0;
}

Measured memory_bytes: 256
import string
import collections

N = int(input())
S = [input() for _ in range(N)]
max_str = collections.Counter(S[0])
for i in range(N-1):
  tmp = collections.Counter(S[i+1])
  #print(tmp)
  for k, v in max_str.items():
    if k in tmp:
      max_str[k] = min(v, tmp[k])
    else:
      max_str[k] = 0
#print(max_str)
ans = ""
for k, v in sorted(max_str.items()):
  ans += k * v
print(ans)


Measured memory_bytes: 3772
import bisect
import math

n, d, a = map(int, input().split())
xh = []

for _ in range(n):
    x, h = map(int, input().split())
    xh.append((x, h))
xh.sort(key=lambda x: x[0])
xs = [x[0] for x in xh]

ranges = []
for x in xs:
    ranges.append(bisect.bisect_right(xs, x + 2 * d))


# N: 処理する区間の長さ
N = n
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


for i, (x, h) in enumerate(xh):
    update(i, i + 1, h)

ans = 0
for i in range(n):
    v = query(i, i + 1)
    if v > 0:
        t = math.ceil(v / a)
        ans += t
        update(i, ranges[i], -t * a)
print(ans)


Measured memory_bytes: 125384
#include<iostream>
#include<cmath> 
using namespace std;
#define ll long long
#define N 500005
#define Mod 1000000007
ll ksm(ll x,ll y){
    ll ans=1ll;
    while(y){
        if(y&1){
            ans=(ll)((ll)ans*x%Mod);
        }
        y>>=1ll;
        x=(ll)((ll)x*x%Mod);
    }
    return ans;
}
ll fact[N]={1ll};
ll inv(ll a)
{
	return ksm(a,Mod-2);
}
ll C(ll a,ll b)
{
	return fact[b]*inv(fact[a])%Mod*inv(fact[b-a])%Mod;
}
inline ll A(ll a,ll b)
{
	return fact[b]*inv(fact[b-a])%Mod;
}
int main()
{
	for(int i=1;i<=500001;++i) 
		fact[i]=(fact[i-1]*i)%Mod;
	ll n,m;
	cin>>n>>m;
	ll sum=A(n,m);
	for(int i=1;i<=n;++i)
		if(i&1) sum=((sum-C(i,n)*A(n-i,m-i)%Mod)+Mod)%Mod;
		else sum=(sum+C(i,n)*A(n-i,m-i)%Mod)%Mod;
	cout<<sum*A(n,m)%Mod<<endl;
	return 0;
} 

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

long sum(long n){
	return n*(n+1)/2;
}

int main(){
	int n;
	scanf("%d", &n);
	long ans = sum(n) - sum(n/3)*3 - sum(n/5)*5 + sum(n/15)*15;
	printf("%ld\n", ans);
}

Measured memory_bytes: 3784
#include "bits/stdc++.h"
#define hhh cerr<<"hhh"<<endl
#define see(x) cerr<<(#x)<<'='<<(x)<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 3e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;



int main() {
    string l; cin>>l;
    if(l.find('7')!=l.npos) printf("Yes\n");
    else printf("No\n");
}

Measured memory_bytes: 3620
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def my_round(a,dig=0):
    p = 10 ** dig
    return (a * p * 2 + 1) // 2 / p

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    n = int(input())
    h = int(input())
    w = int(input())
    _h = n - h + 1
    _w = n - w + 1
    print(_h * _w)
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 38508
#include<bits/stdc++.h>
#include<string>
#include<cmath>

using namespace std;

#define ll long long int
#define loop(i, n) for (int i = 0; i < n; i++)
#define loops(i, s, n) for (int i = s; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define MOD 1000000007
#define PI 3.141592653589793

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

    double a,b,h,m;
    cin>>a>>b>>h>>m;

    double ang = abs((60*h - 11*m)/2);
    double angle = min(ang, 360 - ang);
    angle = angle *(PI/180);
    double ans = a*a + b*b - (2 * a * b * cos(angle));
    cout<<fixed<<setprecision(12)<<sqrt(ans);
}

Measured memory_bytes: 4276
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}

macro_rules! put {
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

#[derive(Clone)]
enum State {
    AfterA,
    AfterB,
}

struct StateMachine {
    active_a: usize,
    total: usize,
    state: State,
}

impl StateMachine {
    fn new() -> Self {
        StateMachine {
            active_a: 0, total: 0, state: State::AfterA
        }
    }

    fn feed(&mut self, x: char) {
        let state = self.state.clone();
        match (state, x) {
            (State::AfterA, 'B') => {
                self.state = State::AfterB;
            }
            (State::AfterA, 'A') => {
                self.active_a += 1;
            }
            (State::AfterA, 'C') => {
                self.active_a = 0;
            }
            (State::AfterB, 'A') => {
                self.active_a = 1;
                self.state = State::AfterA;
            }
            (State::AfterB, 'B') => {
                self.active_a = 0;
            }
            (State::AfterB, 'C') => {
                self.total += self.active_a;
                self.state = State::AfterA;
            }
            _ => unreachable!()
        }
    }
}


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

    let mut sm = StateMachine::new();

    for x in sc.cin::<String>().chars() {
        sm.feed(x);
    }

    put!(sm.total);
}


use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
}

Measured memory_bytes: 4352
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush
from decimal import Decimal

def solve():
    a, b = input().split()

    print(int(Decimal(a) * Decimal(b)))


if __name__ == '__main__':
    solve()


Measured memory_bytes: 10076
#include<stdio.h>

#define inf 10000
#define NIL -1
#define WHITE 1
#define BLACK 2
#define N 101

int color[N],G,w[N][N],d[N],pi[N];

void prim(void);
int main(){
  int i,j,cost=0;
  scanf("%d",&G);
  for(i=0;i<G;i++){
    for(j=0;j<G;j++){
      scanf("%d",&w[i][j]);
    }
  }
  prim();
  for(i=1;i<G;i++){
    cost += d[i];
  // printf("%d\n",d[i]);
  }
  printf("%d\n",cost);
  return 0;
}

void prim(){
  int u,v,i,mincost;
  for(u=0;u<G;u++){
    d[u] = inf;
    pi[u] = NIL;
    color[u] = WHITE;
  }
  d[0] = 0;
  while(1){
    mincost = inf;
    for(i=0;i<G;i++){
      if(color[i] != BLACK && d[i] < mincost){
        mincost = d[i];
        u=i;
      }
    }
    if(mincost == inf){
      break;
    }
    color[u] = BLACK;
    for(v=0;v<G;v++){
      if(color[v] != BLACK && w[u][v] < d[v] && w[u][v]>=0){
        pi[v] = u;
        d[v] = w[u][v];
      }
    }
  }
}



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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rp(i,n)
    cin >> a.at(i);
    sort(a.begin(),a.end());
    bool answer=false;
    rp(i,n-1){
        if(a.at(i)==a.at(i+1)){
            answer=true;
            break;
        }
    }
    if(answer) puts("NO");
    else puts("YES");
    return 0;
}

Measured memory_bytes: 1024