akhauriyash/Code-Regression huggingface dataset:
#include<iostream>  
#include<algorithm>  
#include<ctime>  
#include<cstdio>  
#include<cmath>  
#include<cstring>  
#include<string>  
#include<vector>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
#include<list>  
#include<numeric>  
using namespace std;  
#define LL long long  
#define ULL unsigned long long  
#define INF 0x3f3f3f3f  
#define mm(a,b) memset(a,b,sizeof(a))  
#define PP puts("*********************");  
template<class T> T f_abs(T a){ return a > 0 ? a : -a; }  
template<class T> T gcd(T a, T b){ return b ? gcd(b, a%b) : a; }  
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}  
// 0x3f3f3f3f3f3f3f3f  
//0x3f3f3f3f  
  
const int MAXN = 200050, SIZE = 26;  
struct SAM {  
    int len[MAXN], link[MAXN], next[MAXN][SIZE];  
    int total, last;  
    inline int newNode(int L) {  
        len[++total] = L; link[total] = 0;  
        for(int i = 0; i < SIZE; ++i) next[total][i] = 0;  
        return total;  
    }  
    inline void Add(int c) {  
        int i, p = last, cur = newNode(len[last] + 1);  
        for(; p && !next[p][c]; p = link[p]) next[p][c] = cur;  
        if(!p) link[cur] = 1;//令其指向初始状态  
        else {  
            int q = next[p][c];  
            if(len[q] == len[p] + 1) link[cur] = q;  
            else {//>  
                int clone = newNode(len[p] + 1);  
                for(i = 0; i < SIZE; ++i) next[clone][i] = next[q][i];  
                link[clone] = link[q];  
                link[q] = link[cur] = clone;  
                for(; p && next[p][c] == q; p = link[p]) next[p][c] = clone;  
            }  
        }  
        last = cur;  
    }  
    void Init () {//根节点是1  
        total = 0;  
        last = newNode(0);  
    }  
}sam;  
char str[MAXN];  
int num[MAXN],idx[MAXN];  
int dp[MAXN];  
void solve(int k){  
    int now=1,L=0;  
    while(k){  
        for(int j=0;j<SIZE;j++){  
            if(sam.next[now][j]==0)  
                continue;  
            int x=sam.next[now][j];  
            if(k>dp[x])  
                k-=dp[x];  
            else{  
                str[L++]='a'+j;  
                now=x;  
                k--;  
                break;  
            }  
        }  
    }  
    str[L]='\0';  
    puts(str);  
}  
int main(){  
  
    int Q,k;  
    scanf("%s",str);  
        sam.Init();  
        for(int i=0;str[i]!='\0';i++)  
            sam.Add(str[i]-'a');  
        for(int i=1;i<=sam.total;i++)  
            num[i]=0;  
        for(int i=1;i<=sam.total;i++)  
            num[sam.len[i]]++;  
        for(int i=1;i<=sam.total;i++)  
            num[i]+=num[i-1];  
        for(int i=1;i<=sam.total;i++)  
            idx[num[sam.len[i]]--]=i;  
  
        for(int i=sam.total;i>=1;i--){  
            int now=idx[i];  
            dp[now]=1;  
            for(int j=0;j<SIZE;j++)  
                dp[now]+=dp[sam.next[now][j]];  
        }  
        
     
            scanf("%d",&k);  
            solve(k);  
        
    return 0;  
}  

Measured memory_bytes: 4480
#include <stdio.h>
int main(){
	int n, m;
	int a, b;
	int l=0, r;
	scanf("%d %d", &n, &m);
	r = n;
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		if (l < a)
			l = a;
		if (r > b)
			r = b;
	}
	if (l > r) {
		l = 1;
		r = 0;
	}
	l--;
	printf("%d\n", r - l);
	return 0;
}

Measured memory_bytes: 1716
#include <bits/stdc++.h>
using namespace std;
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }
const int INF = 0x3fffffff;

vector<int> dist(const vector<vector<int>>& g, int s){
  vector<int> d(g.size(), INF);
  queue<int> q;
  d[s] = 0;
  q.push(s);
  while(q.size()){
    int at = q.front();
    q.pop();
    for(int i : g[at]) if(chmin(d[i], d[at] + 1)) q.push(i);
  }
  return d;
}
int main(){
  int n, u, v;
  cin >> n >> u >> v;
  u--; v--;
  vector<vector<int>> g(n);
  for(int i = 0; i < n - 1; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<int> d_taka = dist(g, u), d_aoki = dist(g, v);
  int ans = 0;
  for(int i = 0; i < n; i++) if(d_taka[i] < d_aoki[i]) chmax(ans, d_aoki[i] - 1);
  cout << ans << endl;
}

Measured memory_bytes: 6656
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <algorithm>
#include <queue>
#include <iterator>
#include <functional>
#include <numeric>
#include <cmath>
#include <stack>
#include <limits>
#include <ctime>

using namespace std;

#define ll long long
#define f0(i,n)for(ll i=0;i<n;i++)
#define f0r(i,n)for(ll i=n-1;i>=0;i--)
#define fc(i,c,n,s)for(ll i=c;i<=n;i+=s)
#define fcr(i,c,n,s)for(ll i=n;i>=c;i-=s)
#define sc(n) static_cast<ll>(n)
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef list<ll> LST;
typedef vector<ll> VEC;
typedef map<ll, ll> MAP;

int main() {
	IO;
#ifdef _DEBUG
	ifstream cin("In.txt");
#endif
	ll n,m,x,total=0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x;
		total += x;
	}
	cout << (total>=n ? "Yes":"No") << endl;
	return 0;
}

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

struct edge {
  int to, cost;
};

int N;
vector<edge> G[101010];
int d[101010];

void dfs(int n, int pre) {
  for (auto x : G[n]) {
    if (x.to != pre) {
      d[x.to] = d[n] + x.cost;
      dfs(x.to, n);
    }
  }
}

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

  dfs(0, -1);

  for (int i = 0; i < N; i++) {
    if (d[i] % 2 == 0) {
      cout << 0 << endl;
    } else {
      cout << 1 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 +7;
typedef long long ll;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    int n = read();
    if(n >= 400 && n <= 599) printf("8");
    else if(n >= 600 && n <= 799) printf("7");
    else if(n >= 800 && n <= 999) printf("6");
    else if(n >= 1000 && n <= 1199) printf("5");
    else if(n >= 1200 && n <= 1399) printf("4");
    else if(n >= 1400 && n <= 1599) printf("3");
    else if(n >= 1600 && n <= 1799) printf("2");
    else printf("1");
    printf("\n");
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int con = 0;
  for (int i = 1; i < n; ++i) 
    if (s[i - 1] == s[i]) con++;

  int ans = s.length() - con;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using P = pair<int,int>;
const long long inf = 1000000001; // const 書き換え禁止
const double PI = 3.14159265358979323846; //M_PI はライブラリ

int main(void){
    char b;
    cin >> b;
    if(b == 'A'){
        cout << "T" << endl;
    }else if(b=='T'){
        cout << "A" << endl;
    }else if(b=='G'){
        cout << "C" << endl;
    }else if(b=='C'){
        cout << "G" << endl;
    }
}

Measured memory_bytes: 3516
import sys
import collections

N = int(input())

def factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return collections.Counter(a).items()

list = factorize(N)
ans = 0
tmp = [0,1,3,6,10,15,21,28,36,45,55,66,78,91]
for k,v in list:
    for j in range(len(tmp)):
        if v < tmp[j]:
            ans += j - 1
            break

print(ans)

Measured memory_bytes: 65984
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
LL A, B, C, D;
map<LL, LL> memo;
LL solve(LL N) {
    if (N == 0) return 0;
    if (N == 1) return D;
    if (memo.count(N)) return memo[N];
    LL l2 = (N/2)*2;
    LL r2 = ((N+1)/2)*2;
    LL l3 = (N/3)*3;
    LL r3 = ((N+2)/3)*3;
    LL l5 = (N/5)*5;
    LL r5 = ((N+4)/5)*5;
 
    LL res = 1e18;
    if (N < res/D) res = N*D;
    res = min(res, llabs(l2-N)*D + A + solve(l2/2));
    res = min(res, llabs(r2-N)*D + A + solve(r2/2));
 
    res = min(res, llabs(l3-N)*D + B + solve(l3/3));
    res = min(res, llabs(r3-N)*D + B + solve(r3/3));
 
    res = min(res, llabs(l5-N)*D + C + solve(l5/5));
    res = min(res, llabs(r5-N)*D + C + solve(r5/5));
 
    memo[N] = res;
 
    return res;
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        memo.clear();
        LL N;
        cin >> N;
        cin >> A >> B >> C >> D;
        cout << solve(N) << "\n";
    }
}

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

using namespace std;

#define IoFast ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long int
#define float long double
#define foor(i, a, b) for ( int (i) = (a); (i)<(b); (i)++ )
#define foor2(i, a, b) for( int (i) = (a); (i)>(b); (i)-- )
#define foorl(i, a, b) for ( ll (i) = (a); (i)<(b); (i)++ )
#define foorl2(i, a, b) for( ll (i) = (a); (i)>(b); (i)-- )
#define mp make_pair
#define f1 first
#define f2 second
#define pb push_back
#define pii pair<int,int>
#define vpii vector <pii>
#define vi vector<int>
#define sz(a) (int) a.size( )
#define fillArr(n, a) foor(i, 0, n) cin >> a[i];
#define print(a) cout << #a << endl;
#define umax(a,b) a = max ( a, b )
#define umin(a,b) a = min ( a, b )
#define all(k) k.begin ( ), k.end( )
#define rall(k) k.rbegin ( ), k.rend( )
#define clean(k) memset( k, 0, sizeof(k) )
#define endl '\n'


int main(){
	IoFast;
	ll a,b,c;
	cin >> a >> b >> c;
	ll ans1 = INT_MAX , ans2 = INT_MAX,ans3 = INT_MAX;
	//if (a % 2 != 0){i
		ans1 = abs((a / 2) - ((a+1)/2))  * b * c ;
	//}
	//if (c % 2 != 0){
		ans2 = abs( ((c / 2)) - (((c+1)/2))) * b * a ;
	//}
	//if (b % 2 != 0){
		ans3 = abs( ((b / 2)) - (((b+1)/2))) * c * a ;
	//}
	cout << min({ans1,ans2,ans3}) << endl;
}



Measured memory_bytes: 256
#include <stdio.h>


int main () {
	int a,b;
	int tampung = 1;
	scanf("%d", &a);
	scanf("%d", &b);
	
	for ( int i = 0 ; i < a; i++) {
		if (tampung <= b) {
			tampung *= 2;
		} else {
			tampung += b;
		}
	}
	printf ("%d\n", tampung);
	return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MAX 2000005
#define MOD 1000000007
#define MOD2 998244353
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define vi vector<ll>
#define vp vector<pii>
#define all(v) v.begin(),v.end()
#define sz(x) (ll)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(ll i=a;i<b;++i)
#define ROF(i,a,b) for(ll i=a;i>=b;--i)
#define trace(x) cerr<<#x<<": "<<x<<'\n';
typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

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

const int N = 100005;

ll dp[N][3];
vector<int>g[N];
bool vis[N][3];

void bfs(int s){
    FOR(i,0,N){
        FOR(j,0,3){
            dp[i][j]=MOD;
        }
    }
    dp[s][0]=0;
    vis[s][0]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        FOR(i,0,3){
            if(!vis[u][i]){
                continue;
            }
            for(int v:g[u]){
                if(vis[v][(i+1)%3]){
                    continue;
                }
                dp[v][(i+1)%3]=dp[u][i]+1;
                vis[v][(i+1)%3]=1;
                q.push(v);
            }
        }
    }
}

int main(){
    IOS
    int n,m;
    cin>>n>>m;
    FOR(i,0,m){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
    }
    int s,t;
    cin>>s>>t;
    bfs(s);
    if(vis[t][0]){
        cout<<dp[t][0]/3;
    }
    else{
        cout<<-1;
    }

    cerr<<"Time: "<<1.0/CLOCKS_PER_SEC<<" ms"<<endl;
    return 0;
}

Measured memory_bytes: 8320
#include <iostream> 
#include <bits/stdc++.h>
#include <vector> 
#include <algorithm> 
#include <string>
#include <cmath>
#include <iomanip> 
#include<climits> 
#include <utility>   
#include <set>
#include <numeric> 
#include <iterator>
#include <map> 
using namespace std; 
#define ll long long int
//#define M 1000000007
//typedef pair<ll,ll> p; 
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
   int n;
   cin>>n;
   ll sum=0;
   for(int i=1;i<=n;i++)
   {
       if(i%3!=0 && i%5!=0)
       {
           sum+=i;
       }
   }
   cout<<sum<<endl;
}


Measured memory_bytes: 3640
#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<typeinfo>
#include<functional>
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<vector<ll>> edge;
vector<ll> dp;
vector<ll> fi;

ll Time=0;

void dfs(ll where){
    Time++;
    dp[where]=Time;
    for(int i=0;i<edge[where].size();i++){
        const ll &to=edge[where][i];
        if(dp[to]!=-1){continue;}
        dfs(to);
    }
    Time++;
    fi[where]=Time;
}

int main(){
    ll n;
    cin>>n;
    edge.resize(n);
    dp.resize(n,-1);
    fi.resize(n,-1);
    for(int i=0;i<n;i++){
        ll u,k;
        cin>>u>>k;
        u--;
        for(int t=0;t<k;t++){
            ll v;
            cin>>v;
            v--;
            edge[u].push_back(v);
        }
    }
    for(int i=0;i<n;i++){
        if(dp[i]==-1){dfs(i);}
    }
    for(int i=0;i<n;i++){
        cout<<i+1<<" "<<dp[i]<<" "<<fi[i]<<endl;
    }
    
    
    
    return 0;
}



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

int main() {
  int64_t A,B;
  cin>>A>>B;
  while(A!=0&&B!=0){
    if(A>B){
      A=A%B;
    }
    else{
      B=B%A;
    }
  }
  int64_t Z=1,X=max(A,B);
  for(int64_t i=2;i<1000000;i++){
    if(X%i==0){
      Z++;
      while(X%i==0){
        X/=i;
      }
    }
  }
  if(X>1){
    Z++;
  }
  cout<<Z<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    int n, o, h, t;
    string s;
    cin >> n;
     
    while(n--){
        o = h = t = 0;
        while(o < 3){
            cin >> s;
            if(s == "HIT"){
                if(h == 3){
                    t++;
                } else {
                    h++;
                }
            } else if(s == "HOMERUN"){
                t = t + h + 1;
                h = 0;
            } else {
                o++;
            }
        }
        cout << t << endl;
    }
     
    return 0;
}

Measured memory_bytes: 1208
using System;
using static System.Console;
using static System.Math;
using System.Text;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        long[] n = ReadLine().Split().Select(a => long.Parse(a)).ToArray();
        long d = n[2] - n[1] - n[0];
        if(0 < d && 4 * n[0] * n[1] < d * d)
        {
            WriteLine($"Yes");
        }
        else
        {
            WriteLine($"No");
        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stdio.h>
#include <string.h>

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

using namespace std;

int main()
{
    int k, n;
    cin >> k >> n;
    vector<int> A;
    A.assign(n, 0);
    int temp;
    rep(i, n)
    {
        cin >> temp;
        A[i] = temp;
    }
    int dist = A[0] + k - A[n - 1];
    rep(i, n - 1)
    {
        dist = max(dist, A[i + 1] - A[i]);
    }
    cout << k-dist << endl;
    return 0;
}

Measured memory_bytes: 1024
n,m = map(int,input().split())
ac = 0
wa = 0
p = []
s = []
flag = 0
ind_lists = [0]*(n)
for i in range(m):
    P,S = map(str,input().split())
    p.append(int(P))
    s.append(S)
mita = set()
for i in range(m):
    if p[i] in mita:
        pass
    elif s[i] == "AC":
        mita.add(p[i])
        ind_lists[p[i] - 1] = (i+1)
o_set = set()
for i in range(len(ind_lists)):
    if ind_lists[i]-1 < 0:
        o_set.add(i+1)
mita = set()
for i in range(m):
    if p[i] in o_set or p[i] in mita:
        pass
    elif s[i] == "AC":
        ac += 1
        mita.add(p[i])
    else:
        wa += 1

print(ac,wa)
    
    



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


#define fast_IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using lli = long long int;
using ll = long long ;
using ld=long double;
using d= double;

bool isPrime(ll n){if(n<2)return false;for(ll i=2;i*i<=n;++i){if(n%i==0){return false;}}return true;}

ll lcm(ll x,ll y){
    return (x*y)/(__gcd(x,y));
}

int a[11][11]; 

signed main(){
    fast_IO;
    int t=1;
    //cin>>t;
    while(t--){
         int n;
         int d;
         cin>>n>>d;
         
         for(int i=0;i<n;i++){
             for(int j=0;j<d;j++){
                 cin>>a[i][j];
             }
         }
         ll ans=0;
         for(int i=0;i<n;i++){
             for(int j=i+1;j<n;j++){
                 int sum=0;
                 for(int k=0;k<d;k++){
                     sum+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
                 }
                 ld x=sqrt(sum);
                 int temp=x;
                 bool p=(temp*temp)==sum;
                 ans+=p;
             }
         }
         cout<<ans<<endl;
    }   
    return 0;
}


Measured memory_bytes: 3660
def main():
    n, m = list(map(int, input().split()))
    coins = list(map(int, input().split()))

    dp = [float('inf')] * 50001
    dp[0] = 0

    for i in range(m):
        for j in range(n+1):
            if j + coins[i] > n:
                break
            else:
                dp[j + coins[i]] = min(dp[j + coins[i]], dp[j] + 1)

    print(dp[n])
main()



Measured memory_bytes: 7528
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい
// https://github.com/atcoder/live_library
// cppdbg: test.exeのterminalに標準入力を打てる

#define ALL(x) x.begin(),x.end()
#define get_tp(t,i) get<i>(t)
#define len(x) (ll)(x.size())
#define ub(a,x) (upper_bound(ALL(a),x)-a.begin())
#define lb(a,x) (lower_bound(ALL(a),x)-a.begin())
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<ll, vector<ll>, greater<ll> > gpq; //逆順priority_queue
typedef priority_queue<ll> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

int main(){
    int a,b,c;cin>>a>>b>>c;
    cout<<((a+b>=c)?"Yes":"No")<<endl;
}

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

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> divs;
    for(int i=1; i*i<=N; i++) if(N%i == 0){
        divs.push_back(i);
        if(i < N/i) divs.push_back(N/i);
    }
    sort(divs.begin(), divs.end());
    int sz = divs.size();

    vector<int64_t> num(sz);
    int64_t ans = 0;
    for(int i=0; i<sz; i++){
        int d = divs[i];
        int64_t res = power_mod(K, (d+1)/2);
        add(num[i], res);
        add(ans, num[i] * (d%2 ? d : d/2));
        for(int j=i+1; j<sz; j++) if(divs[j] % divs[i] == 0) add(num[j], MOD - num[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

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

    vec<int> a(N);
    rep(i, N) {
        cin >> a[i];
        --a[i];
    }
    int now = a[0];
    int count = 1;
    rep(i, N+1) {
        if(now == 1) {
            cout << count << endl;
            return 0;
        }
        now = a[now];
        ++count;
    }
    cout << -1 << endl;
}


Measured memory_bytes: 3784
#include<bits/stdc++.h>
using namespace std;
 
#define int             long long
#define ld              long double
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define pii             pair<int, int>
#define mk(arr,n,type)  type *arr=new type[n];
#define vi              vector<int>
#define si              set<int>
#define usi             unordered_set<int>
#define mii             map<int, int>
#define umii            unordered_map<int, int>
#define pqmax           priority_queue<int>
#define pqmin           priority_queue<int, vi, greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define trailzrobits(x) __builtin_ctzll(x)
#define leadzrobits(x)  __builtin_clzll(x)
#define paritybits(x)   __builtin_parityll(x)
#define gcd             __gcd
#define lcm(x, y)       (x * y) / gcd(x, y)
#define mod             1000000007
#define endl            '\n'
#define PI              3.14159265358979323846
#define inf             1e9 + 1
#define sp(x,y)         fixed<<setprecision(y)<<x

void __print(int x) {cout<<x;}
void __print(float x){cout<<x;}
void __print(double x){cout<<x;}
void __print(ld x) {cout<<x;}
void __print(char x){cout <<'\''<<x<<'\'';}
void __print(const char *x){cout <<'\"' <<x<<'\"';}
void __print(const string &x) {cout<<'\"'<<x<<'\"';}
void __print(bool x) {cout<<(x?"true":"false");}
template<typename T,typename V>     void __print(const pair<T,V> &x) {cout<<'{';__print(x.first);cout<<',';__print(x.second);cout<<'}';}
template<typename T>                void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}void _print() {cout << "]\n";}
template <typename T,typename... V> void _print(T t, V... v) {__print(t);if(sizeof...(v))cout<<", ";_print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout<<"["<<#x<<"]=[";_print(x)
#else 
#define dbg(x...)
#endif

int power(int x, int y, int p = mod){
    int res = 1;
    x %= p;
    while(y > 0){
        if(y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res; 
}

int inv(int x, int p = mod){
    return power(x, p - 2) % p;
}

const int N = 1e6 + 6;
 
struct item{
    int wt, val;
};
int32_t main(){

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int t = 1;
    // cin >> t;
    while(t--){
       
        int n, W; cin>>n>>W; 
        vector<item> a(n+1);
        for(int i=1; i<=n; i++)
            cin>>a[i].wt>>a[i].val;
        
        int maxVal = n * 1000;
        int dp[n+1][maxVal+1];

        for(int v=0; v<=maxVal; v++)
            dp[1][v] = inf;
        dp[1][0] = 0;
        dp[1][a[1].val] = a[1].wt;

        for(int i=2; i<=n; i++){
            for(int v=0; v<=maxVal; v++){
                dp[i][v] = dp[i-1][v];
                if(v >= a[i].val)
                    dp[i][v] = min(dp[i][v], a[i].wt + dp[i-1][v-a[i].val]);
            }
        }

        int ans = 0;
        for(int v=0; v<=maxVal; v++){
            if(dp[n][v] <= W)
                ans = v;
        }
        cout<<ans;
    }

    return 0;

}

Measured memory_bytes: 78336
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, start, end) for(int i = start; i < (int)(end); ++i)

int main(){
    string s, t;
    cin >> s >> t;
    cout << t + s << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;

string wzo = "CODEFESTIVAL2016";
char sl[nax];

int main() {
	scanf("%s", sl);
	int ans = 0;
	for(int i = 0; i < 16; ++i) ans += sl[i] != wzo[i];
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 764
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Main main=new Main();
		main.run();
	}

	void run() {
		
		Scanner sc=new Scanner(System.in);
		
		int N=sc.nextInt();
		int W=sc.nextInt();
		
		int[] value=new int[N];
		int[] weight=new int[N];
		
		for(int i=0;i<N;i++) {
			value[i]=sc.nextInt();
			weight[i]=sc.nextInt();
		}
		
		//dp[i][w]=i番目までのアイテムと重さwのリュックを使った時の価値の最大値
		//dp[0][0]=0;
		
		int[][] dp= new int[N+1][W+1];//0オリジンだから、要素の数はN+1,W+1
		
		//N=3 0,1,2,3
		
		
		//アイテムを一つも使わなければ、価値は0
		for(int w=0;w<W+1;w++) {
			dp[0][w]=0;
		}
		
		
		for(int i=0;i<N;i++) {
			
			for(int w=0;w<W+1;w++) {
				
				//そもそも入る余地があるのかどうか
				if(w>=weight[i]) {
					dp[i+1][w]=Math.max(dp[i][w-weight[i]]+value[i],dp[i][w]);
				}else {
					dp[i+1][w]=dp[i][w];
				}
				
			}
			
		}
		
		System.out.println(dp[N][W]);
		
		sc.close();
		
		
	}
}






Measured memory_bytes: 31104
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD 998244353
template<class T>inline bool chmax(T& a,T b){if (a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T& a,T b){if (a>b){a=b;return 1;}return 0;}
const long long INF = 1LL << 60;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
//四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct edge{//グラフに使うヤツ
    ll from,to,cost;
};

typedef vector<vector<edge> > G;
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

int main() {
    ll n;
    cin >> n;
    ll a[n];
    for (ll i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a,a+n);
    vector<ll> x;
    for (ll i=n-1;i>=1;i--){
        if (a[i]==a[i-1]){
            x.push_back(a[i]);
            i--;
        }
    }
    if (x.size()<2){
        cout << 0 << endl;
        return 0;
    }
    cout << x[0]*x[1] << endl;
    return 0;
}

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

using pii = pair<int, int>;
using ll  = long long;
#define rep(i, j) for (int i = 0; i < (int)(j); i++)
#define repeat(i, j, k) for (int i = (j); i < (int)(k); i++)
#define all(v) v.begin(), v.end()
#define debug(x) cerr << #x << " : " << x << endl

template <class T>
bool set_min(T &a, const T &b) {
    return a > b ? a = b, true : false;
}

template <class T>
bool set_max(T &a, const T &b) {
    return a < b ? a = b, true : false;
}
// vector
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &a : v) is >> a;
    return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (const T &t : v) os << "\t" << t;
    return os << endl;
}
// pair
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &v) {
    return os << "<" << v.first << ", " << v.second << ">";
}

const int INF = 1 << 30;
const ll INFL = 1LL << 60;

int main() {
    int N, M, X;
    cin >> N >> M >> X;
    vector<int> C(N);
    vector<vector<int>> A(N, vector<int>(M));
    rep(i, N) {
        cin >> C[i];
        rep(j, M) cin >> A[i][j];
    }
    ll ans = INFL;
    for (int bit = 0; bit < (1 << 12); bit++) {
        ll sum = 0;
        vector<int> cnt(M);
        rep(i, N) if (bit & (1 << i)) {
            sum += C[i];
            rep(j, M) cnt[j] += A[i][j];
        }
        bool ok = true;
        rep(i, M) ok &= cnt[i] >= X;
        if (ok) set_min(ans, sum);
    }
    cout << (ans == INFL ? -1 : ans) << endl;
    return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;
#define long long ll

int main() {
	int n, k;
	cin >> n >> k;
	int cp[26] = {};
	unordered_set<string> blet;
	for (int i = 0; i < n; ++i) {
		string a;
		cin >> a;
		blet.insert(a);
	}
	for (auto a : blet)
		cp[a[0] - 'A']++;
	int q = 0;
	k--;
	while (true) {
		sort(cp, cp + 26);
		if (!cp[25 - k])
			break;
		q++;
		for (int i = 25; i >= 25 - k; --i)
			cp[i]--;
	}
	cout << q << '\n';
	return 0;
}

Measured memory_bytes: 1408
#import<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
LL a,b,c,i,j,k,m,n,s,x,y,p[100005],q[100005],r[300018];
int C(LL x,LL y){return x>y;}
main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>x>>y>>a>>b>>c;
	for(;i<a;i++)cin>>p[i];
	for(i=0;i<b;i++)cin>>q[i];
	for(i=0;i<c;i++)cin>>r[i];
	sort(p,p+a,C);
	sort(q,q+b,C);
	for(i=0;i<x;)r[c++]=p[i++];
	for(i=0;i<y;)r[c++]=q[i++];
	sort(r,r+c,C);
	for(i=0;i<x+y;i++)s+=r[i];
	cout<<s;
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const ll mod = 1000000007;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	int n; cin>>n;
	vector<int> cnt(60, 0);
	for(int i = 0; i < n; i++){
		ll x; cin>>x;
		for(int k = 0; k < 60; k++){
			if((x>>k)&1)cnt[k]++;
		}
	}
	ll ans = 0;
	for(int k = 0; k < 60; k++){
		ll tmp = (1LL<<k)%mod;
		(tmp *= cnt[k]) %= mod;
		(tmp *= (n - cnt[k])) %= mod;
		ans += tmp; if(ans >= mod)ans -= mod;
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int isPrime(int n);
int main(){
  int n,dp[250000]={},i;
  for(i=2;i<250000;i++){
    dp[i]=dp[i-1]+isPrime(i);
  }
  cin >> n;
  while(n!=0) {
    cout << dp[2*n] - dp[n] << endl;
    cin >> n;
  }
  return 0;
}

int isPrime(int n){
  int i;
  for(i=2;i*i<=n;i++) if(n%i==0) return 0;
  return 1;
}

Measured memory_bytes: 2144
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char c) {return to_string((string) &c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll k,q; cin >> k >> q;
    vector<ll> d(k);
    rep(i,0,k) cin >> d[i];
    while(q--){
        ll n,x,m; cin >> n >> x >> m;
        n--;
        ll sum = 0;
        x %= m;
        ll zero = 0;
        rep(i,0,k){
            sum += d[i] % m;
            if(d[i] % m == 0)zero++;
        }
        debug(sum);

        ll cnt = sum / m;
        sum %= m;

        ll t = n / k;
        ll n2 = n % k;

        ll ans = 0;
        ans = cnt * t;
        zero *= t;

        sum *= t;
        sum += x;
        debug(sum, ans, t, cnt, n2);
        rep(i,0,n2){
            sum += d[i] % m;
            if(d[i] % m == 0)zero++;
        }
        
        ans += sum / m;
        debug(sum, ans, zero);
        cout << n - ans - zero << "\n";
    }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

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

    int N;
    cin >> N;
    map<int, int> m;
    bool f = false;
    REP(i, N){
        int x;
        cin >> x;
        m[x]++;
    }
    if(N%2 == 0){
        REP(i, N){
            i++;
            if(m[i] != 2) f = true;
        }
    }else{
        REP(i, N){
            if(i == 0){
                if(m[0] != 1) f = true;
            }
            else if(m[i] != 2) f = true;
            i++;
        }
    }
    if(f){
        puts("0");
        return 0;
    }
    llint ans = 1;
    REP(i, m.size()-N%2){
        ans = (ans*2) %MOD;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main(){

    int H, W;
    cin >> H >> W;

    char map[H][W];

    for(int x = 0; x < H; x++){
        for(int y = 0; y < W; y++){
            cin >> map[x][y];
        }
    }

    for(int x = 0; x < 2 * H; x++){
        for(int y = 0; y < W; y++){
            cout << map[x/2][y];
        }
        cout << endl;
    }



}

Measured memory_bytes: 256
#include <math.h>
#include <ctype.h>
#include <limits.h>
#include <string.h>
#include <assert.h>

#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>

#define nl                std::cout << "\n"
#define in(x)             std::cin  >> (x)
#define out(x)            std::cout << (x) << " "
#define err(x)            std::cerr << "DBG: " << #x << " " << (x) << "\n"

#define inn(x)            int x; in(x)
#define rep(i, n)         for (int i =  0 ; i < (n); ++i)
#define repr(i, l, r)     for (int i = (l); i < (r); ++i)
#define rrep(i, n)        for (int i = (n) - 1; i > -1; --i)

#define no                puts("NO")
#define yes               puts("YES")

using ll  = long long int;
using vi  = std::vector<int>;
using ii  = std::pair<int, int>;
using iii = std::pair<ii, int>;
using vii = std::vector<ii>;

const int N = 1010101;
const int MD = 1e9 + 7;

int nC2(int n) { return n*(n - 1)/2; }

void solve() {
    inn(n);
    inn(k);

    vii ans;
    rep(i, n - 1) {
        int t = std::min(k, n - 2 - i);
        k -= t;
        repr(j, i + t + 1, n) {
            ans.push_back({i + 1, j + 1});
        }
    }
    if (k) { out(-1); return; }

    out((int) ans.size()), nl;
    for (auto& i: ans) {
        out(i.first), out(i.second), nl;
    }
}

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

    //int t; in(t); repr(tc, 1, t + 1)
    solve();

    return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        long H = Long.parseLong(s.next());
        System.out.println(atack(H));
    }

    // 再帰でやるとこう
    static long atack(long h) {
        if (h == 1) {
            return 1;
        }
        return atack(h / 2) * 2 + 1;
    }

}


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

using i64 = int64_t;

int main(){
    string s;
    cin >> s;
    string hands;
    for(int i=0;i<s.size();++i){
        hands.push_back(i%2 ? 'p' : 'g');
    }
    int ans = 0;
    for(int i=0;i<s.size();++i){
        if(hands[i] == 'p' && s[i] == 'g')ans++;
        else if(hands[i] == 'g' && s[i] == 'p')ans--;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
class Program{
    static void Main(){
        string[] s = Console.ReadLine().Split();
        long n = long.Parse(s[0]);
        long p = long.Parse(s[1]);
        long m = (long)Math.Pow(p,1.0/n) + 1;
        for (;m >= 1;m--){
            long m2 = (long)Math.Pow(m,n);
            if (p % m2 == 0){
                Console.WriteLine(m);
                return;
            }
        }
    }
}

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

// syntax sugar: `for (int i = 0; i < N; ++i)`
#define rep(i, N) for (int i = 0; i < (int)(N); ++i)
#define rep2(i, startValue, N) for (int i = (int)(startValue); i < (int)(N); ++i)
// syntax sugar: `for (int i = 0; i < N; ++i)`
#define REP(type, name, beginValue, endCondValue) \
  for (type name = beginValue; name < endCondValue; ++name)
// syntax sugar: 多次元vector
#define VECTOR_DIM3(T, name, d1, d2, d3, initValue) \
    std::vector<std::vector<std::vector<T>>> name(d1, std::vector<std::vector<T>>(d2, std::vector<int>(d3, initValue)));
#define VECTOR_DIM2(T, name, d1, d2, initValue) \
    std::vector<std::vector<T>> name(d1, std::vector<T>(d2, initValue));
#define VECTOR_DIM1(T, name, d1, initValue) \
    std::vector<T> name(d1, initValue);
#define ll long long
#define ld long double
#define DUMP(v) "," #v ":" << v


// 「みんなのプロコン 2019」
// C - When I hit my pocket...
int main(){
  ll k, a, b;
  cin >> k >> a >> b;

  ll ans = 0;
  if (a + 2 > b) {
    // 交換効率が悪いので叩き続けたほうがお得
    ans = k+1;
  } else {
    // Bisket Aに到達できるか
    if (k < a-1) {
      ans = k+1;
    } else {
      k -= a-1;
      ans = a + (b - a) * (k / 2);
      if (k%2 == 1) {
        ans++; // 残り1回はたたく
      }
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define endl "\n"
#define fast_in_out ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod=998244353;

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

int lcm(int a , int b)
{
	return (a*b)/gcd(a,b);
}

int power(int a , int b , int c)
{
    if(a==0) return 0;
    if(b==0) return 1;

    int res=1;
    a=a%c;
    while(b>0)
    {
        if(b&1)
        {
            res=(res*a)%c;
        }
        a=(a*a)%c;
        b>>=1;
    }
    return res;
}

int32_t main()
{

    fast_in_out;

    int t=1;
    //cin>>t;
    while(t--)
    {
		int n ,k,sum = 0;
   		cin>>n>>k;
   		vector<vector<int>>a(k,vector<int>(2));

   		for(int i = 0;i<k ;i++)
   			cin>>a[i][0]>>a[i][1];

   		int dp[n+1]={};
   		int pref[n+1] = {};
   		dp[1] = pref[1] = 1;
   		for(int i = 2;i<= n ;i++)
   		{
   	 		for(int j= 0;j<k ;j++)
   	 		{
   	 			if(i>a[j][0])
   	 			{
   	 				dp[i] += pref[i -a[j][0]];
   	 				if(i > a[j][1])
   	 					dp[i] -= pref[i-a[j][1]-1];
   	 		
   	 				dp[i] = (dp[i] + mod)%mod; 
   	 			}
   	 		}
   	 		pref[i]+= (pref[i-1]+dp[i])%mod;
   		}
  		cout<<dp[n]<<endl;
    }

    return 0;
}


Measured memory_bytes: 6772
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ii=pair<ll,ll>;
using vi=vector<ll>;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (ll)1e18
#define all(x) (x).begin(),(x).end()
#define print(a); for(auto x:a)cout<<x<<" "; cout<<"\n";
#define mset(a); memset(a,0,sizeof(a));

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	ll x,y;cin>>x>>y;
    if(y>=2*x&&y<=4*x&&y%2==0)cout<<"Yes\n";
    else cout<<"No\n";

}


Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
struct edge{
    int u,v;
    double cost;
}es[1000005];
struct dot{
    int x,y;
};
int n,m;
dot dd[10005];
int par[10005],rrank[10005];
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
        rrank[i]=0;
    }
    return;
}
int ffind(int x)
{
    if(x==par[x]) return x;
    else return par[x]=ffind(par[x]);
}
void unite(int x,int y)
{
    x=ffind(x);
    y=ffind(y);
    if(x==y) return;
    if(rrank[x]<rrank[y]) par[x]=y;
    else {
        par[y]=x;
        if(rrank[x]==rrank[y]) rrank[x]++;
    }
    return;
}
bool same(int x,int y)
{
    return ffind(x)==ffind(y);
}
double dis(int s,int t)
{
    int p=dd[s].x-dd[t].x;
    int q=dd[s].y-dd[t].y;
    return sqrt(p*p+q*q);
}
bool comp(const edge& a,const edge& b)
{
    return a.cost>b.cost;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        int s,t;
        scanf("%d%d",&s,&t);
        dd[i].x=s;dd[i].y=t;
    }
    double ssum=0,psum=0;
    for(int i=0;i<m;i++) {
        int s,t;
        scanf("%d%d",&s,&t);
        edge e;
        e.u=s;e.v=t;
        e.cost=dis(s,t);
        es[i]=e;
        ssum+=e.cost;
    }
    sort(es,es+m,comp);
    init(n);

    for(int i=0;i<m;i++) {
            edge e=es[i];
        if(!same(e.u,e.v)) {
            unite(e.u,e.v);
            psum+=e.cost;
        }
    }
    printf("%.3lf\n",ssum-psum);

    return 0;
}



Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int N,K;
    string S;
    cin>>N>>S>>K;

    K--;
    string ans=S;
    rep(i,N){
        if(S[i]!=S[K]) ans[i]='*';
    }
    cout << ans << endl;





}


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

int main() {
  int n, m;
  cin >> n >> m;
  
  int h[n];
  
  rep(i, n){
    cin >> h[i];
  }
  
  vector<vector<int> >road(n);
  
  rep(i, m){
    int a, b;
    cin >> a >> b;
    road[a-1].push_back(b-1);
    road[b-1].push_back(a-1);
  }

  int res = 0;  
    
  rep(i, n){
      if(road[i].size() == 0){
          ++res;
      }else{
          bool not_peak= false;
          rep(j, (int)road[i].size()){
              if(h[i] <= h[road[i][j]]){
                    not_peak = true;
              }
          }
          if(!not_peak) ++res;
      }
  }
  
  cout << res << endl;
    
  return 0;
}

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

int main() {
  int n, a, b;
  string s;
  cin >> n >> a >> b;
  cin >> s;
  int cnt1 = 0, cnt2 = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'a' && cnt1 < a + b) {
      cout << "Yes" << endl;
      cnt1++;
    }
    else if(s[i] == 'b' && cnt1 < a + b && cnt2 < b ) {
      cout << "Yes" << endl;
      cnt1++;
      cnt2++;
    }
    else {
      cout << "No" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)
#define MP(a,b) make_pair(a,b)

#if __has_include("debug.hpp")
#include "debug.hpp"
#else
template<typename T>
void debug(T& obj) {}
#endif

//----------------------------------------------------------------------
void solve() {

	ll n,res=0;
	string s;
	cin >> n >> s;
	rep(i,n-2) {
		if (s[i]=='A' && s[i+1]=='B' && s[i+2]=='C') {
			res++;
		}
	}
	cout << res;

}
//----------------------------------------------------------------------

int main(int argc, char* argv[]) {
	solve();
	return 0;
}


Measured memory_bytes: 3624
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <typeinfo>
using namespace std;
using ll = long long;

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

	if (k % 2 == 0)
	{
		ans = (k / 2)*(k / 2);
	}
	else
	{
		ans = (k / 2 + 1)*(k / 2);
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
#include<stdio.h>
void print(int N,int A[]){
  for(int i = 0; i < N; i++){
    if(i < (N - 1) ){
      printf("%d ",A[i]);
    }else{
      printf("%d",A[i]);
    }
  }
  putchar('\n');
}
void insertion(int N,int A[]){
  for(int i = 1; i < N; i++){
    int v = A[i];
    int j = i - 1;
    while(j >= 0 && A[j] > v){
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
    print(N,A);
  }
}
#define LEN 100
int main(){
  int N,A[LEN];
  scanf("%d",&N);
  for(int i = 0; i < N; i++){
    scanf("%d",&A[i]);
  }
  print(N,A);
  insertion(N,A);

}



Measured memory_bytes: 2040