akhauriyash/Code-Regression huggingface dataset:
// 30/12/19 // 01:26 PM //

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define pb push_back

const int MAXN = 1e5 + 10;

int n, m;
vector<int> grafo[MAXN];
int memo[MAXN];

int solve(int no){
    if(memo[no]!=-1) return memo[no];

    memo[no] = 0;
    for(int adj : grafo[no]){
        memo[no] = max(memo[no], 1 + solve(adj));
    }

    return memo[no];
}

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

    cin >> n >> m;

    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;

        grafo[a].pb(b);
    }

    int resp = 0;
    memset(memo, -1, sizeof(memo));

    for(int i=1; i<=n; i++)
        if(memo[i]==-1)
            resp = max(resp, solve(i));

    cout << resp << endl;

    return 0;
}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
 
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint 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(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
    
    
  int main(){
lint a,b,m;
cin>>a>>b>>m;
lint A[a];
lint B[b];
    rep(i,a)cin>>A[i];
    rep(i,b)cin>>B[i];
    lint ans=INF;
    rep(i,m){
        lint x,y,z;
        cin>>x>>y>>z;
        --x;--y;
         ans=min(ans,A[x]+B[y]-z);
    }
    sort(A,A+a);
    sort(B,B+b);
    ans=min(ans,A[0]+B[0]);
    cout<<ans;
  }
     
  

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int M=4000005;
const int N=2005;

int sum=0,n,a[N];
bitset<M> bit;

int main() 
{
	scanf("%d",&n);
	bit[0]=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		bit|=(bit<<a[i]);
		sum+=a[i];
	}
	for(int i=(sum+1)/2;i<=sum;i++) if(bit[i])
	{
		printf("%d\n",i);
		return 0;
	}
	return 0;
}


Measured memory_bytes: 5296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

bool prime_num(int x) {
    if (x == 1) return false;
    else if (x == 2) return true;
    else if (x % 2 == 0) return false;
    else {
        for (int i = 3; i*i <= x; i += 2) {
            if (x % i == 0) return false;
        }
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    int ans = 0;
    rep(i, 0, n) {
        int x;
        cin >> x;
        if (prime_num(x)) ans ++;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3060
#include "bits/stdc++.h"
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
using namespace std;

#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()



// substr(start, len)

int main(){
  
  int N, P;
  ll cnt = 0;
  cin >> N >> P;

  string S;
  cin >> S;

  vector<int> a(N,0);
  rep(i, 0, N){
    a[i] = ((char)S[i] - '0');
  }

  if(P == 2){
    for(int i = N-1; i >= 0; i--){
      if(a[i]%2 == 0) cnt += i + 1;
    }
  }else if(P == 5){
    for(int i = N-1; i >= 0; i--){
      if(a[i] % 5 == 0) cnt += i + 1;
    }
  }else{
    ll p = 1, b=0;
    vector<ll> m(P,0);
    m[0] = 1;
    for(int i = N-1; i >= 0; i--){
      b = (b + a[i]*p) % P;

      cnt += m[b];
      m[b]++;
      p = p*10%P;
    }
  }

  cout << cnt << endl;


}

Measured memory_bytes: 1412
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def main():
    N = int(input())
    A = [int(c) for c in input().split()]
    num = 0
    for i in range(N):
        num += 1 / A[i]
    print(1/num)


if __name__ == '__main__':
    main()

Measured memory_bytes: 21668
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>

using namespace std;

int main(){

    int mod = 1e9 + 7;

    int N, M;
    cin >> N >> M;
    vector<int> dp(N + 1);
    vector<bool> hole(N + 1, false);

    int a;
    for(int i = 0; i < M; i++){
        cin >> a;
        hole[a] = true;
    }

    dp[0] = 1;
    if(!hole[1]){
        dp[1] = 1;
    }
    else{
        dp[1] = 0;
    }
    for(int i = 2; i <= N; i++){
        if(hole[i]){
            dp[i] = 0;
        }
        else{
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
        }
    }

    cout << dp[N] << endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define bits_count __builtin_popcountll
#define ld long double
#define FOR(i,a,n) for (ll i=(a);i<(n);++i)
#define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define MINUS(a) memset((a),-1,sizeof((a)))
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
#define sz(x) (ll)x.size()
#define pr pair<int,int>



int main()
{
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int x,n;
    cin>>x>>n;

    vector<int>g(n);
    map<int,int>m;
    FOR(i,0,n)
    {
        cin>>g[i];
        m[g[i]]++;
    }
    int p=101,q;
    for(int i=0;i<=101;i++)
    {
        if(m[i]==0)
        {
            if(abs(i-x)<p)
            {
                p=abs(i-x);
                q=i;
            }
        }
    }
    cout<<q<<endl;
    
    
    
}


Measured memory_bytes: 3644
n,m,l = map(int,input().split())
A=[]
B=[]
for i in range(n): 
    A.append(list(map(int,input().split())))
for j in range(m): 
    B.append(list(map(int,input().split())))
for A_r in A:
    print(" ".join(map(str,[sum([x*y for x,y in zip(A_r,[B_r[k] for B_r in B])]) for k in range(l)])))


Measured memory_bytes: 6320
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = b - 1; i >= a; i--)
#define ALL(a) a.begin(), a.end()
#define pii pair<int,int>
#pragma GCC optimize("Ofast")
#define pcnt __builtin_popcount
#define buli(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<class T>bool chmax(T &a, const T &b) {if(a<b){a = b; return 1;} return 0; };
template<class T>bool chmin(T &a, const T &b) {if(a>b){a = b; return 1;} return 0; };
inline void IN(void){return;}
template <typename First, typename... Rest> void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
inline void OUT(void){cout << "\n";return;}
template <typename First, typename... Rest> void OUT(First first, Rest... rest){cout << first << " ";OUT(rest...);return;}
const double EPS = 1e-9;
const int mod = 1e9 + 7;
const int INF = 1e9;
const long long LLINF = 1e18;
long long lcm(ll a, ll b){return a * b / __gcd(a,b);}
struct IoSetup { IoSetup() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
} } iosetup;
template< int mod > struct ModInt {
    int x; ModInt() : x(0) {}
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}
    ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}
    ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}
    ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }return ModInt(u);}
    ModInt pow(int64_t n) const {ModInt ret(1), mul(x); while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x;}
    friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); }
    static int get_mod() { return mod; }
}; using modint = ModInt< mod >;

int main(){
    iosetup;
    int N, K; IN(N, K);
    vector<int> H(N);
    rep(i, 0, N) cin >> H[i];
    sort(ALL(H), greater<int>());
    ll sum = 0;
    rep(i, 0, N){
        if(i < K) continue;
        sum += H[i];
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define mod 1000000007
#define MAX 20000000009
using namespace std;

vector<int> arr(200005,0);

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++){
        int val;
        cin >> val;
        arr[val-1]++;
    }
    for(int i = 0; i < n; i++){
        cout << arr[i] << endl;
    }
}



Measured memory_bytes: 3904
N,M = map(int,input().split())
H = list(map(int,input().strip().split()))
xy=[map(int, input().split()) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

list=[0]*N
for i in range(M):
    if H[x[i]-1]<H[y[i]-1]:
        list[x[i]-1]+=1

    elif  H[x[i]-1]==H[y[i]-1]:
        list[x[i]-1]+=1
        list[y[i]-1]+=1
    else:
        list[y[i]-1]+=1
count=0
for i in range(N):
    if list[i]==0:
        count+=1

print(count)


Measured memory_bytes: 66908
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < n; ++i)
#define FOR(i, b, n) for (ll i = b; i <= n; ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

vector<ll> mem(2001, -1);
ll f(ll S) {
  if (S < 3)
    return 0;
  if (S == 3)
    return 1;
  if (mem[S] >= 0)
    return mem[S];
  mem[S] = (f(S - 3) + f(S - 1)) % MOD;
  return mem[S];
}
void solve(ll S) {
  cout << f(S) << endl;
}

int main(){
  // int 3E4  long 2E9  ll 9E18
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll S;
  cin >> S;

  solve(S);

  return 0;
}


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

int main(void)
{
    int n; scanf("%d", &n);
    std::vector<unsigned int> a(n);
    for( int i = 0 ; i < n ; ++i )
    {
       scanf("%d ",&a[i]);
    }

    int count = 0;
    unsigned int max = 65535;
    while(max--)
    {
        bool is_end = false;
        for(int i=0;i<n;++i) 
        {
            if(a[i] & 1 == 1) {
                is_end = true;
                break;
            }
            a[i] = a[i] >> 1;
        }
        if(is_end) break;
        ++count;
    }
   
   std::cout << count << std::endl;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 1010;
#define int long long
inline int read()
{
	register int x = 0 , f = 0; register char c = getchar();
	while(c < '0' || c > '9') f |= c == '-' , c = getchar();
	while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
	return f ? -x : x;
}
int n;
int x[N] , y[N] , len[50];
inline int Abs(int x) { return x < 0 ? -x : x; }
signed main()
{
	n = read();
	for(int i = 1 ; i <= n ; ++i) x[i] = read() , y[i] = read();
	int tmp = Abs(x[1] + y[1]) & 1;
	for(int i = 2 ; i <= n ; ++i) if((Abs(x[i] + y[i]) & 1) != tmp) { puts("-1"); return 0; }
	cout << (32 - tmp) << '\n'; // (0 , 0)是偶数;
	int tot = 0; len[tot = 1] = 1; cout << 1 << ' ';
	if(tmp)
		for(int i = 1 ; i <= 30 ; ++i) len[++tot] = 1 << i , cout << len[tot] << ' ';
	else
		for(int i = 0 ; i <= 30 ; ++i) len[++tot] = 1 << i , cout << len[tot] << ' ';
	cout << '\n';
	char ans[32];
	for(int i = 1 ; i <= n ; ++i)
	{
		int nowx = 0 , nowy = 0;
		for(int j = tot ; j >= 1 ; --j)
		{
			int dx = Abs(nowx - x[i]) , dy = Abs(nowy - y[i]);
			if(dx > dy)
			{
				if(nowx < x[i]) nowx += len[j] , ans[j] = 'R'; else nowx -= len[j] , ans[j] = 'L';
			}
			else
			{
				if(nowy < y[i]) nowy += len[j] , ans[j] = 'U'; else nowy -= len[j] , ans[j] = 'D';
			}
		}
		for(int j = 1 ; j <= tot ; ++j) putchar(ans[j]); cout << '\n';
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
typedef long long int ll;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;

int N;
pair<int, int> a[101];
pair<int, int> b[101];
int ans = 0;

int main() {
	cin >> N;
	rep(i, 0, N)cin >> a[i].second >> a[i].first;
	rep(i, 0, N)cin >> b[i].first >> b[i].second;

	sort(a, a + N);
	sort(b, b + N);

	vector<int> h;
	rep(i, 0, N)h.push_back(0);

	rep(i, 0, N) {
		int max = 0;
		int hantei = -1;
		rep(j, 0, N) {
			if (b[i].first > a[j].second && b[i].second > a[j].first && h[j] == 0) {
				if (max <= a[j].first) {
					max = a[j].first;
					hantei = j;
				}
			}
		}
		if (hantei >= 0) {
			h[hantei] = 1;
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <ll> V;
bool cmp(ll A,ll B){
    return A>B;
}
int main() {
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++){
        ll x;
        cin>>x;
        V.push_back(x);
    }
    sort(V.begin(),V.end(),cmp);
    n-=2;
    ll ans=V[0];
    ll have=n/2,rest=n%2;
    for(ll i=1;i<=have;i++){
        ans+=V[i]*2;
    }
    if(rest){
        ans+=V[have+1];
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 5296
test,submit=map(int,input().split())
ac_wa_map={}
ac=0
wa=0
wa_counter=[0]*test
for i in range(submit):
    test_no,acwa=input().split()
    if test_no not in ac_wa_map:
        ac_wa_map[test_no]=acwa
        if acwa=="AC":
            ac+=1
        elif acwa=="WA":
            wa_counter[int(test_no)-1]+=1
    elif acwa=="AC" and ac_wa_map[test_no]=="WA":
        ac+=1
        ac_wa_map[test_no]=acwa
        wa+=wa_counter[int(test_no)-1]
    elif acwa=="WA" and ac_wa_map[test_no]=="WA":
        wa_counter[int(test_no)-1]+=1
    

print(ac,wa)
        

Measured memory_bytes: 22748
#include <stdio.h>
 
int main(void) 
{
  int a, b, tmp, GCM;
 
  scanf("%d %d", &a, &b);
 
  /* ユークリッドの互除法 */
 
  if (b > a) {
    tmp = a;
    a   = b;
    b   = tmp;
  }
 
  while (b != 0) {
    tmp = b;
    b   = a % b;
    a   = tmp;
  }
 
  GCM = a;
 
  printf("%d\n", GCM);
 
  return 0;
}



Measured memory_bytes: 2752
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScanner in = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        B solver = new B();
        solver.solve(1, in, out);
        out.close();
    }

    static class B {
        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            int N = in.nextInt();
            String S = in.next();
            String T = in.next();

            StringBuilder sb = new StringBuilder(N * 2);
            for (int i = 0; i < N; i++) {
                sb.append(S.charAt(i)).append(T.charAt(i));
            }
            out.println(sb.toString());
        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 20820
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB emplace_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("[DEBUG] ");W(__VA_ARGS__);}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1<<18;
int A[SIZE],B[SIZE];
void solve() {
    int N,K;
    R(N,K);
    FOR(i,1,N){
        R(A[i]);
    }
    REP(cs,K){
        bool ch=0;
        MS0(B);
        FOR(i,1,N){
            B[max(1,i-A[i])]++;
            B[min(N,i+A[i])+1]--;
        }
        FOR(i,1,N)B[i]+=B[i-1];
        FOR(i,1,N){
            if(A[i]!=B[i]){
                A[i]=B[i];
                ch=1;
            }
        }
        if(!ch)break;
    }
    W(VI(B+1,B+N+1));
}
int main(){
#define MULTITEST 0
#if MULTITEST    
    CASET{
        solve();
    }
#else
    solve();
#endif
    return 0;
}


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

using namespace std;
#define llu unsigned long long
#define ll long long
#define p pair<int,int>
#define M 1000000007
//sieve can be used here!
bool isPrime(int n){
	if(n==1)return false;//1 is not prime
	for(int i=2;i*i<=n;i++){
		if(n%i==0)return false;
	}
	return true;
}
bool myComp(p a,p b){
	if(a.first==b.first) return a.second<b.second;
	return a.first>b.first;
}
int row[]={-1,0,1,0};
int col[]={0,-1,0,1};
ll squareRoot(ll x){
	ll low=0;
	ll high=x;
	while(low<=high){
		ll mid= low+(high-low)/2;
		if((mid*mid)>x)high=mid-1;
		else if(mid*mid<x)low=mid+1;
		else return mid;
	}
	return low;
}
void dfs(char par,int r,int c,vector<vector<char>>& arr,vector<vector<bool>>& visited){
	int n=arr.size();
	int m=arr[0].size();
	visited[r][c]=true;
	arr[r][c]=par;
	for(int i=0;i<4;i++){
		int newRow=r+row[i];
		int newCol=c+col[i];
		if(newRow>=0&&newRow<n&&newCol>=0&&newCol<m&&!visited[newRow][newCol]&&arr[newRow][newCol]!='-'){
			if(par=='B') dfs('W',newRow,newCol,arr,visited);
			else dfs('B',newRow,newCol,arr,visited);
		}
	}
}
llu sumDigit(llu x){
	llu ans=0;
	while(x>0){
		ans+=x%10;
		x/=10;
	}
	return ans;
}
llu func(llu a,llu b){
	if(sumDigit(a)==b)return 0;
	llu ans=0;
	llu temp=1;
	while(sumDigit(a)>b){
		int currDigit=((a/temp)%10);
		llu curr=((10-(currDigit))%10)*temp;
		ans+=curr;
		a+=curr;
		temp*=10;
	}
	return ans;
}
int helper(string&temp,string&t){
	int count=0;
	for(int i=0;i<t.length();i++){
		if(temp[i]!=t[i])count++;
	}
	return count;
}
int func(string& s,string &t){
	int i=0;
	int j=t.length()-1;
	int ans=INT_MAX;
	while(j<s.length()){
		string temp=s.substr(i,j-i+1);
		ans=min(ans,helper(temp,t));
		i++;
		j++;
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin>>s;
	string t;
	cin>>t;
	cout<<func(s,t);
	return 0;
}



Measured memory_bytes: 3624
n, a, b, c, d = gets.chomp.split(' ').map(&:to_i)
s = gets.chomp

a_road = s[(a-1)..(c-1)]
b_road = s[(b-1)..(d-1)]

if c > d
  road = s[(b-2)..d]
  unless road.include?('...')
    puts 'No'
    exit
  end
end

if a_road.include?('##') || b_road.include?('##')
  puts 'No'
else
  puts 'Yes'
end


Measured memory_bytes: 2428
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

vector<pll> uft;

ll parent(ll a){
    if(uft[a].F==a){return a;}
    return uft[a].F=parent(uft[a].F);
}

void merge(ll a,ll b){
    if(parent(a)==parent(b)){return;}
    if(uft[parent(a)].S<uft[parent(b)].S){swap(a,b);}
    uft[parent(a)].S+=uft[parent(b)].S;
    uft[parent(b)].F=parent(a);
}

typedef pair<ll,pll> P;


int main(){
    ll n,m;
    while(cin>>n>>m,n){
    uft.resize(n);
    for(int i=0;i<n;i++){uft[i]={i,1};}
    vector<pll> h(n);
    for(int i=0;i<n;i++){cin>>h[i].F; h[i].S=i;}
    sort(h.begin(),h.end());
    vector<ll> R(n);
    for(int i=0;i<n;i++){R[h[i].S]=i;}
    vector<vector<pll>> edge(n);
    for(int i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        a=R[a-1];
        b=R[b-1];
        if(a>b){swap(a,b);}
        edge[a].push_back({b,c});
    }
    ll H=h.back().F;
    ll mi=E;
    for(ll i=n-1;i>=0;){
        ll t=i;
        H=h[i].F;
        while(t>=0 && h[t].F==H){
            for(auto &e:edge[t]){
                merge(t,e.F);
            }
            t--;
        }
        //cout<<i<<" "<<uft[parent(n-1)].S<<endl;
        if(uft[parent(n-1)].S!=n-t-1){mi=H;}
        i=t;
    }
    priority_queue<P,vector<P>,greater<P>> Q;
    ll ans=0;
    for(int i=0;i<n;i++){uft[i]={i,1};}
    ll i=n-1;
    while(i>=0 && h[i].F>=mi){
        for(auto &e:edge[i]){
            Q.push({e.S,{e.F,i}});
        }
        i--;
    }
    for(;i>=0;){
        mi=h[i].F;
        while(i>=0 && h[i].F>=mi){
            for(auto &e:edge[i]){
                Q.push({e.S,{e.F,i}});
            }
            i--;
        }
        while(!Q.empty()){
            P e=Q.top(); Q.pop();
            if(parent(e.S.F)!=parent(e.S.S)){ans+=e.F; merge(e.S.F,e.S.S);}
        }
    }
    cout<<ans<<endl;
    }
    
    
    return 0;
}



Measured memory_bytes: 4712
#include <iostream>
#include <map>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

int N, K, A[3], score[100009][3];
int V[100009], dp[100009][3];

long long solve(vector<int> a) {
	for (int i = 0; i <= a.size(); i++) {
		dp[i][0] = -(1 << 30); dp[i][1] = -(1 << 30); dp[i][2] = -(1 << 30);
	}
	dp[0][0] = score[a[0]][0];
	dp[0][1] = score[a[0]][1];
	dp[0][2] = score[a[0]][2];
	for (int i = 1; i < a.size(); i++) {
		for (int j = 0; j < 3; j++) {
			if (dp[i - 1][j] < 0) continue;
			for (int k = 0; k < 3; k++) {
				if (j == k) continue;
				dp[i][k] = max(dp[i][k], dp[i - 1][j] + score[a[i]][k]);
			}
		}
	}

	return max({ dp[a.size() - 1][0], dp[a.size() - 1][1], dp[a.size() - 1][2] });
}

int main() {
	cin >> N >> K;
	cin >> A[0] >> A[1] >> A[2];
	for (int i = 0; i < N; i++) {
		char c; cin >> c;
		if (c == 'r') V[i] = 2;
		if (c == 's') V[i] = 0;
		if (c == 'p') V[i] = 1;
		score[i][V[i]] = A[V[i]];
	}

	long long ret = 0;
	for (int i = 0; i < K; i++) {
		vector<int> VV;
		for (int j = i; j < N; j += K) VV.push_back(j);
		ret += solve(VV);
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 3832
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    A.sort()
    B.sort()
    C.sort()
    
    A_cand = [0 for i in range(N)]
    B_cand = [0 for i in range(N)]
    
    skip_loop = 0
    for i in range(N):
        cnt = skip_loop
        for j in range(N-skip_loop):
            if B[N-i-1] < C[N-skip_loop-j-1]:
                cnt += 1
            else:
                break
        B_cand[N-i-1] = cnt
        skip_loop = cnt
    
    skip_loop = 0
    ans = 0
    pre_loop_ans = 0
    for i in range(N):
        cnt = skip_loop
        ans += pre_loop_ans
        for j in range(N-skip_loop):
            if A[N-i-1] < B[N-skip_loop-j-1]:
                ans += B_cand[N-skip_loop-j-1]
                pre_loop_ans += B_cand[N-skip_loop-j-1]
                cnt += 1
            else:
                break
        A_cand[N-i-1] = cnt
        skip_loop = cnt
    print(ans)
    

solve()

Measured memory_bytes: 23328
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int LEN=80,MAXLEN=25600;

int n,m;
int a[LEN+1][LEN+1],b[LEN+5][LEN+5];
bool dp[LEN+1][LEN+1][MAXLEN+5];

signed main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)  cin>>a[i][j];
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)  cin>>b[i][j];
	}
	for (int i=1;i<=m;i++)  dp[0][i][0]=1;
	for (int i=1;i<=n;i++)  dp[i][0][0]=1;
	
	dp[1][1][abs(a[1][1]-b[1][1])]=1;
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (i==1&&j==1)  continue;
			
			int now=a[i][j]-b[i][j];
			if (i!=1)
			{
				for (int k=0;k<=MAXLEN;k++)
				{
					if (dp[i-1][j][k]==1)
					{
						dp[i][j][abs(k+now)]=1;
						dp[i][j][abs(k-now)]=1;
					}
				}	
			}
			if (j!=1)
			{
				for (int k=0;k<=MAXLEN;k++)
				{
					if (dp[i][j-1][k]==1)
					{
						dp[i][j][abs(k+now)]=1;
						dp[i][j][abs(k-now)]=1;
					}
				}
			}
		}
	}
	for (int i=0;i<=MAXLEN;i++)
	{
		if (dp[n][m][i])  return cout<<i<<endl,0;
	}
}

Measured memory_bytes: 162688
#include "iostream"
#include "math.h"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
using namespace std;

int main() {
	int n;
	string str;
	cin >> n >> str;
	int cnt = 0;
	for (int i = 0; i < n-1; i++) {
		if (str[i] == str[i + 1]) {
			cnt++;
		}
	}
	cout << n - cnt << endl;
}

Measured memory_bytes: 512
from collections import deque

def main():
    N = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a = deque(a)
    ans = 0
    for i in range(N):
        a.pop()
        ans += a.pop()
        a.popleft()
    print(ans)

if __name__ == "__main__":
    main()


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

#define PI 3.14159265359
#define MODULO 1000000007

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int s,w;
	cin >> s >> w;
	s>w? cout << "safe" : cout << "unsafe";
}

Measured memory_bytes: 3648
import numpy as np
LARGE = 10 ** 9 + 7
N = int(input())
A = np.array(input().split(), dtype=np.int64)

shift = 0
total = 0
while A.any():
    bits = np.count_nonzero(A & 1)
    total += (bits * (N - bits)) << shift
    A >>= 1
    shift += 1

print(total % LARGE)


Measured memory_bytes: 62776
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int X,Y,legs;
    cin>>X>>Y;
    for(int i =0;i<=X;i++){
        legs = i*4 + (X-i)*2;
        if(legs == Y){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
#include <queue>
#include <climits>
#include<cmath>
#include <sstream>
#include <iomanip>

int main()
{
    int64_t a,b;
    std::cin>> a;

    std::vector< int64_t> c( a );

    for( int i = 0; i < a; i++ )
    {
        std::cin>> c[i];
    }

    int64_t d,e;
    d = c.front();
    e = c.back();

    int64_t r,l;
    r = 1;
    l = 1;
    //for( int i = 1; i < a; i++ )
    while( 1 )
    {
        if( r + l == c.size() )
        {
            break;
        }
        
        if( d < e )
        {
            d += c[r];
            r += 1;
        }
        else
        {
            e += c[c.size()-l-1];
            l += 1;
        }        
    }

    std::cout<< abs( d - e );
}


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

const int INF = 1e9+7;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)


int main() {
	int n,m;
	cin >> n >> m;
	if(n < m){
		rep(i, m) cout << n;
		cout << endl;
	}else{
		rep(i, n) cout << m;
		cout << endl;
	}

}


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

int main(){
	ll N, A, B, ans = 0;
	cin >> N >> A >> B;
	vector<ll> X(N);
	for (int i = 0;i < N;i++) {
		cin >> X[i];
	}
	for (int i = 1;i < N;i++) {
		ans += min((X[i] - X[i - 1])*A, B);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	p := make([]int, n)
	for i, _ := range p {
		fmt.Scan(&p[i])
	}
	sort.Ints(p)

	ans := 0
	for i := 0; i < k; i++ {
		ans += p[i]
	}
	fmt.Println(ans)

}

Measured memory_bytes: 1888
using System;
class revkuku{
  public static void Main(){
    int num = int.Parse(Console.ReadLine());
    bool flag = false;
    for(int i=1; i<=9 && !flag; i++){
      for(int j=i; j<=9; j++){
        if(i*j == num){
          flag = true;
          break;
        }
      }
    }
    if(flag){
      Console.WriteLine("Yes");
    }
    else{
      Console.WriteLine("No");
    }
  }
}


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

int main(void)
{
    int h, w;
    cin >> h >> w;
    vector<vector<bool>> s(h+2);
    s[0] = vector<bool>(w+2, false);
    s[h+1] = vector<bool>(w+2, false);
    for (int i = 1; i < h+1; i++) {
        s[i] = vector<bool>(w+2, true);
        string row;
        cin >> row;
        for (int j = 1; j < w+1; j++) {
            // '.' -> true
            // '#' -> false
            if (row[j-1] == '#') {
                s[i][j] = false;
            }
        }
        s[i][0] = false;
        s[i][w+1] = false;
    }

    vector<vector<vector<int>>> g(h+2, vector<vector<int>>(w+2, vector<int>(2, 0)));
    int maxg = 0;
    for (int i = 1; i < h+1; i++) {
        for (int j = 1; j < w+1; j++) {
            if (s[i][j] == false) continue;

            // 横方向に探索
            if (s[i-1][j] == true) {
                g[i][j][0] = g[i-1][j][0];
            } else {
                for (int k = i+1; s[k][j] == true; k++) g[i][j][0]++;
            }

            // 縦方向に探索
            if (s[i][j-1] == true) {
                g[i][j][1] = g[i][j-1][1];
            } else {
                for (int k = j+1; s[i][k] == true; k++) g[i][j][1]++;
            }

            maxg = max(maxg, g[i][j][0] + g[i][j][1] + 1);
        }
    }
    // for (int i = 0; i < h+2; i++) {
    //     for (int j = 0; j < w+2; j++) {
    //         cout << (s[i][j] ? (g[i][j][0] + g[i][j][1] + 1) : 0);
    //     }
    //     cout << endl;
    // }

    cout << maxg << endl;

    return 0;
}



Measured memory_bytes: 220288
#include<bits/stdc++.h>
using namespace std;
#define iso ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
#define clr(x) memset((x), 0, sizeof(x))
#define mod 998244353
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll ,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_tree;*/
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b)
{
    return (a.second < b.second);
}
ll modularExponentiation(ll x,ll n)
{
    ll result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%mod;
        x=(x*x)%mod;
        n=n/2;
    }
    return result;
}
ll modInverse(ll A)
{
    return modularExponentiation(A,mod-2);
}
ll arr[200005],ans[200005];

int main()
{
    iso;
    int i,n;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>arr[i];
    ans[0]=0;
    ans[1]=abs(arr[1]-arr[0]);
    for(i=2;i<n;i++)
    {
        ans[i]=min(ans[i-2]+abs(arr[i]-arr[i-2]),ans[i-1]+abs(arr[i]-arr[i-1]));
    }
    cout<<ans[n-1];

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <iomanip>
#include <typeinfo>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <set>
#include <numeric>
using namespace std;


typedef long long       ll;
typedef struct edge_ { ll to; ll cost; } edge;
typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef vector<double>  vd;
typedef vector<bool>    vb;
typedef vector<string>  vs;
typedef vector<char>    vc;
typedef vector<edge>    ve;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;
typedef vector<vll>		vvll;
typedef vector<vi>		vvi;
typedef vector<ve>      vve;
typedef vector<vc>		vvc;

#define repr(itr, bgn, end) for (ll itr = (ll)bgn; itr < (ll)end; ++itr)
#define rep(itr, end) repr(itr, 0, end)
#define reprrev(itr, bgn, end) for (ll itr = (ll)end - 1; itr >= (ll)bgn; --i)
#define reprev(itr, end) reprrev(itr, 0, end)
#define all(container) container.begin(), container.end()
#define sortall(container) sort(all(container))
#define yn(cond) cond ? (cout << "Yes" << endl) : (cout << "No" << endl)
#define YN(cond) cond ? (cout << "YES" << endl) : (cout << "NO" << endl)

// 定数
#define LLONG_MAX numeric_limits<ll>::max()
#define INT_MAX numeric_limits<int>::max()
constexpr double PI = 3.14159265358979323846;
constexpr ll INF = 1 << 15;
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-7;

// よく使うもの
constexpr int dy[4] = { 0, 1, 0, -1 };
constexpr int dx[4] = { 1, 0, -1, 0 };


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}

// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
	for (T& x : vec) os << x << " ";
	return os;
}

// pair出力
template<typename S, typename T>
ostream& operator << (ostream& os, pair<S, T>& p) {
	os << p.first << " " << p.second;
	return os;
}


template <typename argType>
argType GCD(argType a, argType b) {
	return a % b == 0 ? b : GCD(b, a % b);
}


int main()
{
	int N, X;
	cin >> N >> X;
	vi x(N);
	cin >> x;

	int mindis = INT_MAX;
	for (int xx : x) {
		if (abs(xx - X) < mindis)
			mindis = abs(xx - X);
	}

	int ans = mindis;
	for (int i = 0; i < N; i++) {
		ans = GCD(ans, abs(x[i] - X));
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


C = [0] * (2 * N - 1)
D = [0] * N
for i in range(2 * N - 1):
    C[i] = A[i % N] ^ A[(i + 1) % N]
    D[i % N] = B[i % N] ^ B[(i + 1) % N]

class KMP:

    def __init__(self, W):
        self.W = W
        self.L = len(W)
        self.T = self._build(W)

    def _build(self, W):
        T = [0] * self.L
        T[0] = -1
        T[1] = 0
        i = 2
        j = 0

        while i < self.L:
            if W[i - 1] == W[j]:
                T[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = T[j]
            else:
                T[i] = 0
                i += 1

        return T

    def search(self, S):
        m = 0
        i = 0
        L = len(S)
        while m + i < L:
            # print(m, i)
            if self.W[i] == S[m + i]:
                i += 1
                if i == self.L:
                    i -= 1
                    ret = m
                    m = m + i - self.T[i]
                    i = self.T[i]
                    yield ret
            else:
                m = m + i - self.T[i]
                if i > 0:
                    i = self.T[i]

# def ok(x, i):
#     for j in range(N):
#         if A[(j + i) % N] ^ B[j] != x:
#             return False
#     return True
#
#
# for i in range(N):
#     x = A[i] ^ B[0]
#     if ok(x, i):
#         print(i, x)

kmp = KMP(D)
for x in kmp.search(C):
    xor = A[x] ^ B[0]
    print(x, xor)

Measured memory_bytes: 43656
while True:
    money=int(input())
    if money==0:
        break
    n=1000-money
    a=n//500
    b=(n%500)//100
    c=(n%500%100)//50
    d=(n%500%100%50)//10
    e=(n%500%100%50%10)//5
    f=(n%500%100%50%10%5)//1
    print(a+b+c+d+e+f)
    



Measured memory_bytes: 5584
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define rep(i,l,r) for(rint i=l;i<=r;i++)
#define per(i,l,r) for(rint i=l;i>=r;i--)
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define fir first
#define sec second
#define mset(s,t) memset(s,t,sizeof(s))
template<typename T1,typename T2>void ckmin(T1 &a,T2 b){if(a>b)a=b;}
template<typename T1,typename T2>void ckmax(T1 &a,T2 b){if(a<b)a=b;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
int read(){
  int x=0,f=0;
  char ch=getchar();
  while(!isdigit(ch))f|=ch=='-',ch=getchar();
  while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
  return f?-x:x;
}
#define int long long
const int N=500005;
const int mod=998244353;
int l[N],r[N];
int dp[N],n,k;
int sum[N];
signed main(){
  n=read(),k=read();
  for(int i=1;i<=k;i++){
    l[i]=read(),r[i]=read();
    if(l[i]>r[i])swap(l[i],r[i]);
  }
  dp[1]=1,sum[1]=1;
  for(int i=2;i<=n;i++){
    for(int j=1;j<=k;j++){
      int L=i-r[j],R=i-l[j];
      if(R<=0)continue;
      if(L<=0){
        dp[i]=(dp[i]+sum[R])%mod;
      }else{
        dp[i]=(dp[i]+sum[R]-sum[L-1])%mod;
      }
    }
    //printf("dp[%d]=%d\n",i,dp[i]);
    sum[i]=(sum[i-1]+dp[i])%mod;
  }
  printf("%lld\n",(dp[n]%mod+mod)%mod);
  return 0;
}


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

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

const ll MOD = 1000 * 1000 *1000 + 7 ;
inline void chadd(ll &a, const ll b) { a = (a + b) % MOD;}
inline ll add(const ll a, const ll b){ return (a + b) %  MOD;}
inline void chsub(ll &a, const ll b) { a = (a - b + MOD) % MOD;}
inline ll sub(const ll a, const ll b){ return (a - b + MOD) % MOD; }
inline void chmul(ll &a, const ll b) { a = (a * b) %  MOD;}
inline ll mul(const ll a, const ll b){ return (a * b) %  MOD;}

template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }

const int MAXSIZE = 1024;
ll dp[MAXSIZE][MAXSIZE];

int main() {
  int H, W; cin>>H>>W;
  vector<string> a(H);
  REP(h,H) cin>>a[h];
  dp[0][0] = 1;
  REP(h,H) REP(w,W) {
    if(a[h][w] == '#') continue;
    if(h-1 >= 0) chadd(dp[h][w], dp[h-1][w]);
    if(w-1 >= 0) chadd(dp[h][w], dp[h][w-1]);
    //    cout << h << w << ":" << dp[h][w] << endl;
  }

  cout << dp[H-1][W-1] << endl;
  return 0;
}


Measured memory_bytes: 9472
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

#define N 600000
#define NIL -1

//array
int key[N];
int parent[N];
int leftc[N];
int rightc[N];
//root
int root=NIL;

//function insert
void insert(int z){
  int x,y;
  
  y=NIL;
  x=root;

  while(x!=NIL){
    y=x;
    if(key[z]<key[x]) x=leftc[x];
    else x=rightc[x];
  }  
  
  parent[z]=y;

  if(y==NIL) root=z;
    
  else if(key[z]<key[y]) leftc[y]=z;

  else rightc[y]=z;
  
  
}

//function search
int find(int now,int data){
  if(now==NIL ||data==key[now]) return now;
  
  if(data<key[now]) return find(leftc[now],data);
  else return find(rightc[now],data);
}

//function minimum
int treeminimum(int x){
  while(leftc[x]!=NIL){
    x=leftc[x];
  }
  return x;
}

//function successor
int treesuccessor(int x){
  int y; 
  if(rightc[x]!=NIL) return treeminimum(rightc[x]);
  y=parent[x];
  while(y!=NIL &&x==rightc[x]){
    x=y;
    y=parent[y];
  }
  return y;
}


//function delete
void treedelete(int z){
  int x,y;
  if(leftc[z]==NIL ||rightc[z]==NIL) y=z;
  else y=treesuccessor(z);

  if(leftc[y]!=NIL) x=leftc[y];
  else x=rightc[y];

  if(x!=NIL) parent[x]=parent[y];
  if(parent[y]==NIL) root=x;
  else if(y==leftc[parent[y]]) leftc[parent[y]]=x;
  else rightc[parent[y]]=x;

  if(y!=z) key[z]=key[y];

}

//print
void inorderprint(int now){
  if(now!=NIL){
    inorderprint(leftc[now]);
    printf(" %d",key[now]);
    inorderprint(rightc[now]);
  }
}

void preorderprint(int now){
  if(now!=NIL){
    printf(" %d",key[now]);
    preorderprint(leftc[now]);
    preorderprint(rightc[now]);
  }
}



int main(){

  int n,i,j,data;
  int z=0;
  int del;
  char str[10];
  //initialize array
  for(i=0;i<N;i++){
    parent[i]=NIL;
    key[i]=NIL;
    rightc[i]=NIL;
    leftc[i]=NIL;
  }
  //load n
  scanf("%d",&n);
  //load commnad and key
  for(i=0;i<n;i++){
    scanf("%s",str);
    if(strcmp(str,"insert")==0) {
      scanf("%d",&data);
      key[z]=data;
      insert(z);
      z++;
    }
    else if(strcmp(str,"find")==0){
      scanf("%d",&data);
      if(find(root,data)!=NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(strcmp(str,"delete")==0){
      scanf("%d",&data);
      del=find(root,data);
      treedelete(del);
    }
    else if(strcmp(str,"print")==0){
      inorderprint(root);
      cout <<endl;
      preorderprint(root);
      cout <<endl;
    }
  }

  return 0;
}

Measured memory_bytes: 10000
def main():
    """
    1 <= N <= 10^4
    1 <= ai <= 10^9
    """
    N = int(input())
    A = map(int, input().split())

    ans = f(N, A)
    print(ans)


def f(N, A):
    """
    以下の操作をできるだけ多くの回数繰り返す

    1 ≤ i ≤ N を満たす全ての i に対して,
    どちらかを行う.  
        ai の値を 2で割る
        aiの値を 3倍する
    ただし,
        全ての i に対して 3倍することはできず
        操作後の aiの値は整数でなければならない


    2の倍数でなければ2で割れない
    2で割って奇数になった場合、その後は3倍にしかできない
    操作後の数値上限はないので、1つでも2で割れれば良い
    """
    ans = sum(p(a) for a in A)

    return ans


def p(a):
    ans = 0
    while a > 0:
        if a % 2 == 0:
            ans += 1
            a //= 2
        else:
            break
    return ans


if __name__ == '__main__':
    main()


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#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 P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    map<int, int> mp;
    rep(i, 5) {
        int x;
        cin >> x;
        mp[x]++;
    }
    
    int ans = 0;
    rep(i, 5) {
        if (mp[i+1]==0) ans = i+1;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
from bisect import bisect_left,bisect_right

n=int(input())
l=sorted(list(map(int,input().split())))
cnt=0
for i in range(n):
    lim=False
    for j in range(i+1,n):
        MIN=abs(l[i]-l[j])
        MAX=l[i]+l[j]
        min_idx=max(bisect_right(l,MIN),j+1)
        if not lim:
            max_idx=bisect_left(l,MAX)
            if max_idx==n:lim=True
        res=max_idx-min_idx
        if min_idx<=i<=max_idx:res-=1
        if min_idx<=j<=max_idx:res-=1
        cnt+=max(res,0)
print(cnt)

Measured memory_bytes: 50136
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <unordered_map>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
constexpr long long MOD = 1e9 + 7;
constexpr long long MAX = 1000000;

//long long MOD = 998244353;
constexpr ll INF = 1e17;
constexpr double PI = 3.141592653589793;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }


template<typename T>
T gcd(T a, T b) {
    T c = 1;
    while (c != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}



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

    ll a, b;
    cin >> a >> b;
    cout << lcm(a, b) << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

int A[1000000];
int G[1000000/2];
int cnt;

void print(int A[], int n) {
  for (int i=0; i<n; i++) {
    printf("%d\n", A[i]);
  }
}

void insertionSort(int A[], int n, int g) {
  for (int i=g; i<n; i++) {
    int v = A[i];
    int j = i-g;
    while (j >= 0 && A[j] > v) {
      A[j+g] = A[j];
      j = j-g;
      cnt++;
    }
    A[j+g] = v;
  }
}

void shellSort(int A[], int n) {
  int m = 0;
  G[0] = 1;
  while (G[m] <= n) {
    G[m+1] = 3*G[m]+1;
    m++;
  }
  printf("%d\n", m);
  for (int i=m-1; i>=0; i--) {
    printf("%d", G[i]);
    if (i > 0) putchar(' ');
  }
  putchar('\n');
  cnt = 0;
  for (int i=m-1; i>=0; i--) insertionSort(A, n, G[i]);
  printf("%d\n", cnt);
}

int main() {
  int N;
  scanf("%d", &N);
  for (int i=0; i<N; i++) scanf("%d", &A[i]);
  shellSort(A, N);
  print(A, N);
  return 0;
}

Measured memory_bytes: 6564