akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define int long long
#define For(i,x,y) for(int i = x; i <= y; ++i)
#define FOR For
#define rev_For(i,x,y) for(int i = x; i >= y; --i)
#define REV_FOR rev_For
#define ll long long
#define Size(v) ((int)v.size())
#define _section "\n--------------------\n"
#define fi first
#define se second
#define pb push_back
using namespace std;
// using namespace __gnu_pbds;


int k;

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

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

int phi(int n) {
    int result = n;
    for (int i = 2; i*i <= n; ++i)
    {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

void input() {
	cin >> k;
}

void solve() {
	int sum = 0;
	for (int a = 1; a <= k; ++a) {
		for (int b = 1; b <= k; ++b) {
			for (int c = 1; c <= k; ++c) {
				sum += gcd(a, gcd(b, c));
			}
		}
	}

	cout << sum;
}

signed main() {
#ifdef _DEBUG
	// freopen("INPUT.inp", "r", stdin);
	//freopen("OUTPUT.out", "w", stdout);
	clock_t start, end;
	start = clock();
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//------------------------------------------------------------------------------------
//----------------------------------MAIN PROGRAM--------------------------------------
	int t = 1;
	while (t--) {
		input();
		solve();
	}
//--------------------------------------END-------------------------------------------
//------------------------------------------------------------------------------------
#ifdef _DEBUG
	end = clock();
	cerr << "\n----------\nTime Elapsed: " << fixed << double(end - start) / double(CLOCKS_PER_SEC) << setprecision(6) << '\n';
#endif
	return 0;
}

Measured memory_bytes: 3660
#include<iostream>
#include<vector>
#include<map>
using namespace std;

int main() {
	map<int,int> nums; 
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		if(nums.count(tmp) == 0) {
			nums[tmp] = 0;
		}
		nums[tmp]++;
	}
	int sum = 0;
	for(map<int,int>::iterator it = nums.begin(); it != nums.end(); ++it) {
		if(it->second > 0) {
			if(it->second - it->first > 0) {
				sum += it->second - it->first;
			} else if(it->second - it->first < 0) {
				sum += it->second;
			}
		}
	}
	cout << sum;
}



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

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;

int main(){

  int a, b, c, d;
  scanf("%d %d %d %d", &a, &b, &c, &d);

  int push[101] = {};
  FOR(i,a,b){
    push[i]++;
  }
  FOR(i,c,d){
    push[i]++;
  }
  int res = 0;
  REP(i,101){
    if(push[i] == 2){
      res++;
    }
  }
  printf("%d\n", res);
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAX 1000000
#define ll unsigned long long
#define upperlimit 1000100
#define INF 1e18
#define eps 1e-8
#define endl '\n'
#define pcc pair<char,char>
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define MOD 1000000007
#define slld(t) scanf("%lld",&t)
#define sd(t) scanf("%d",&t)
#define pd(t) prllf("%d\n",t)
#define plld(t) prllf("%lld\n",t)
#define mp(a,b) make_pair(a,b)
#define FF first
#define SS second
#define pb(x) push_back(x)
#define vi vector<ll>
#define clr(a) memset(a,MOD,sizeof(a))
#define debug(a) printf("check%d\n",a)
#define csl ios::sync_with_stdio(false);cin.tie(0);
#define INT_SIZE 32
using namespace std;
 
ll gcd(ll n1,ll n2){
	if(n1%n2==0)return n2;
	return gcd(n2,n1%n2);
}
ll powmod(ll base,ll exponent,ll mod)
{
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll phi[MAX];
std::map<ll, ll> mphi;
ll fphi(ll x)
{
	if(x<MAX)
		return phi[x];
	if(mphi[x])
		return mphi[x];
	ll n=x;
	ll result=x;
	for(ll i=2LL;i*i<=x;i++)
	{
		if(x%i==0)
		{
			while(x%i==0)
				x/=i;
			result-=result/i;
		}
	}
	if(x>1)
		result-=result/x;
	mphi[n]=result;
	return result;
}
ll f(ll a,ll n,ll m)
{
	if(n==1)
		return 1;
	if(n%2==0)
	{
		ll first=f(a,n/2LL,m);
		ll second=powmod(a,n/2LL,m)*first;
		second%=m;
		second+=first;
		second%=m;
		return second;
	}
	else
	{
		ll first=f(a,n/2LL,m);
		ll second=powmod(a,n/2LL,m)*first;
		//cout<<second<<" DEBUG "<<first<<endl;
		second%=m;
		second+=first+powmod(a,n-1LL,m);
		second%=m;
		return second;
	}
}
int main()
{
	/*for(ll i=1;i<MAX;i++)
		phi[i]=i-1;
	for(ll i=2;i<MAX;i++)
	{
		if(phi[i]==i-1)
			for(ll j=2*i;j<MAX;j+=i)
				phi[j]-=phi[j]/i;
	}*/
	ll t,cnt=0;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		if(n&1)
			cnt++;
	}
	if(cnt%2==0)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
}

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

int main(){
    int n,A[100],i;
    cin >> n;
    for(int i=0;i<n;i++) cin >> A[i];

    int x = 0;
      for(int i=0;i<n;i++){
    int minj=i;
    for(int j=i;j<n;j++){
      if(A[j]<A[minj]){
	minj=j;
      }
    }
    if(i!=minj){
      swap(A[i],A[minj]);
      x++;
    }
  }

    for(int i=0;i<n;i++){
        if(i==0)cout << A[i];
        else cout << " " << A[i];
    }

    cout << endl;
    cout << x << endl;

    return 0;
}


Measured memory_bytes: 3084
use std::io;
use std::io::BufRead;

fn main() {
    let stdin = io::stdin();
    let mut stdin = stdin.lock();
    
    let n: usize = {
        let mut n = String::new();
        stdin.read_line(&mut n).unwrap();
        n.trim().parse::<usize>().unwrap()
    };

    let w: Vec<i32> = {
        let mut w = String::new();
        stdin.read_line(&mut w).unwrap();
        w.trim().split_whitespace().map(|s| s.parse::<i32>().unwrap()).collect()
    };


    let mut cur: usize = n-1;
    
    let a: i32 = w.iter().take(cur).sum();
    let b: i32 = w.iter().skip(cur).sum();

    if a <= b {
        println!("{}", b-a );
        return;
    }
    
    let mut prev: i32 = a - b;
    let mut diff: i32 = prev;
    
    'outer: while diff > 0 {
        prev = diff;
        
        cur -= 1;
        diff -= w[cur] + w[cur];
            
        if cur == 0 { break 'outer; }
    }

    diff = diff * diff.signum();

    if diff < prev { 
        println!("{}", diff );
    } else {
        println!("{}", prev );
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;

int main() {
  ll N, M, R;
  cin >> N >> M >> R;
  vector<ll> towns(R);
  for (ll i = 0; i < R; i++) {
    ll t;
    cin >> t;
    towns[i] = t - 1;
  }
  vector< vector<ll> > dist (N, vector<ll>(N, 1LL << 60));
  for (ll i = 0; i < N; i++) {
    dist[i][i] = 0;
  }
  for (ll i = 0; i < M; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    dist[a-1][b-1] = c;
    dist[b-1][a-1] = c;
  }
  // warshal-floyd
  for (ll k = 0; k < N; k++) {
    for (ll i = 0; i < N; i++) {
      for (ll j = 0; j < N; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

  ll ans = 1LL << 60;
  sort(towns.begin(), towns.end());
  do {
    ll tmp = 0;
    for (ll i = 0; i < R - 1; i++) {
      tmp += dist[towns[i]][towns[i+1]];
    }
    ans = min(ans, tmp);
  } while (next_permutation(towns.begin(), towns.end()));

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


Measured memory_bytes: 512
from operator import sub
def coeff(n, i):
  return i*(i+1) + (n-2*i)*(i+1)
  
Mod = 10**9+7
n, m = map(int, input().split())
x = sorted(map(int, input().split()))
y = sorted(map(int, input().split()))
dx = map(sub, x[1:], x)
dy = map(sub, y[1:], y)

sx = 0
for i, v in enumerate(dx):
  sx += v * coeff(n-1, i)
  sx %= Mod
  #print(v, coeff(n-1, i), v * coeff(n-1, i), sx) 
  
sy = 0
for i, v in enumerate(dy):
  sy += v * coeff(m-1, i)
  sy %= Mod  
  #print(v, coeff(m-1, i), v * coeff(m-1, i), sy) 
  
print(sx * sy % Mod)  

Measured memory_bytes: 18752
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
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<class Value>using vec = vector< Value >;
using ll = long long;
using P = pair< long long, long long >;
#define fi first
#define se second
#define el endl
#pragma endregion


void Main();
void solve(long long N);

int main(){
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
}

void solve(long long N){
    cout << (int)((N+999)/1000)*1000-N << el;
}



Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ld long double
#define dd double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef vector<pll> vplll;
ll mod = 1e9+7;
const ld PI = 2 * acos(0.0);
const vector<ll> dx = {1, -1, 0, 0};
const vector<ll> dy = {0, 0, 1, -1};
#define round(x, y) ((x + y - 1) / y)
#define ce(x, y) ((x + y - 1) / y)
#define amax(x, y) \
    if (y > x)     \
        x = y;
#define amin(x, y) \
    if (y < x)     \
        x = y;
#define lcm(x, y) ((x) * (y) / __gcd(x, y))
#define len(x) (ll) x.length()
#define sq(x) ((x) * (x))
#define cb(x) ((x) * (x) * (x))
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b,c,t,n,m,k,q; 
    t = 1;
    // cin>>t;
    while(t--)
    {
    	string s;
    	cin>>s;
    	if(s=="ABC")
    	cout<<"ARC"<<endl;
    	else
    	cout<<"ABC"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

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

int n;

int main(){
	cin>>n;
	int g=0;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		g=gcd(g,x);
	}
	cout<<g<<endl;
}

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

vector<int> scc_deconpose(const vector<vector<int>>& G){
  int n = G.size();
  vector<int> P;
  {
    vector<int> visited(n,false);
    auto dfs = [&](auto dfs, int v) -> void {
                 visited[v] = true;
                 for(auto v_ : G[v]){
                   if(visited[v_]) continue;
                   dfs(dfs,v_);
                 }
                 P.push_back(v);
               };
    for(int i = 0; i < n; ++i){
      if(visited[i]) continue;
      dfs(dfs,i);
    }
    reverse(P.begin(), P.end());
  }
  vector<vector<int>> G_rev(n);
  for(int i = 0; i < n; ++i){
    for(auto j : G[i])
      G_rev[j].push_back(i);
  }
  vector<int> A(n,-1);
  int t = 0;
  auto dfs = [&](auto dfs, int v) -> void {
               A[v] = t;
               for(auto v_ : G_rev[v]){
                 if(A[v_] >= 0) continue;
                 dfs(dfs,v_);
               }
             };
  for(auto v : P){
    if(A[v] >= 0) continue;
    dfs(dfs,v);
    ++t;
  }
  return A;
}

int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<int>> G(n);
  for(int i = 0; i < m; ++i){
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
  }
  vector<int> C = scc_deconpose(G);
  // for(auto c : C)
  //   cerr << c << " ";
  // cerr << endl;
  int Q;
  cin >> Q;
  while(Q--){
    int u, v;
    cin >> u >> v;
    cout << (C[u] == C[v]) << endl;
  }
}



Measured memory_bytes: 4400
#include <stdio.h>
 
int main(void) {

	char word[1201];
	int i;
     
	fgets(word, 1201, stdin);

	for(i=0; '\0'!=word[i]; i++ ) {//65=A 90=Z 97=a 122=z
		if(65<=word[i] && word[i]<=90) {
			word[i]=32+word[i];
	}	/* ???????????\?????????????????§??????????????? */

	else if(97<=word[i] && word[i]<=122) {
		word[i]=word[i]-32;//65-97
	}	/* ??\??????????????±?????????????????§?°??????\????????? */

	else{
		printf("");
		}
	}	/* ??\??????????????±????????????????????????????????? */

	word[i]='\0';
		printf("%s", word);	/* ??§?°??????\???????????£?????±??????????????? */

	return 0;
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
#define init ios::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL);
using namespace std;

//  =========     /\       /|    |====/|
//      |        /  \       |    |   / |
//      |       /____\      |    |  /  |
//      |      /      \     |    | /   |
//  ========= /        \  =====  |/====|  
//  code

int main(){
    init;
    long long int H,W,i,j,k,l,MOD = 1e9 + 7;
    cin>>H>>W;
    string board[H];
    long long int dp[H+1][W+1];
    memset(dp,0,sizeof(dp));

    for(i=0;i<H;i++){
        cin>>board[i];
    }

    dp[1][1] = 1;

    for( i = 1; i <= H; i++){
        for(j = 1; j<= W; j++){
            if(i == 1 && j == 1)
                continue;
            if(board[i-1][j-1] == '.'){
                dp[i][j] = (dp[i][j] + dp[i-1][j] + dp[i][j-1])%MOD;
            }
            else dp[i][j] = 0;
        }
    }
    cout<<dp[H][W]<<endl;
    return 0;
}

Measured memory_bytes: 9216
def resolve():
    N = int(input())
    AC = 0
    WA = 0
    TLE = 0
    RE = 0

    results = [input() for _ in range(N)]
    for result in results:
        if result == 'AC':
            AC+=1
        elif result == 'WA':
            WA+=1
        elif result == 'TLE':
            TLE+=1
        else:
            RE+=1
    print(f'AC x {AC}\nWA x {WA}\nTLE x {TLE}\nRE x {RE}')

resolve()

Measured memory_bytes: 79320
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
   for j in range(w):
      if S[i][j]=="#":
         continue
      else:
         D=[[inf for _ in range(w)]for _ in range(h)]
         D[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                  if D[ni][nj]>D[si][sj]+1:
                     D[ni][nj]=D[si][sj]+1
                     ans=max(ans,D[si][sj]+1)
                     que.append((ni,nj))
print(ans)
                 

Measured memory_bytes: 48348
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
	int32_t N, x;
	cin >> N >> x;

	vector<int32_t> a(N);
	for (int32_t i = 0; i < N; i++) {
		cin >> a[i];
	}

	int64_t res = 0;
	for (int32_t i = 0; i < N - 1; i++) {
		int32_t over = a[i] + a[i + 1] - x;
		if (over > 0) {
			if (a[i + 1] > over) {
				a[i + 1] -= over;
			} else {
				a[i + 1] = 0;
				a[i] -= over - a[i + 1];
			}
			res += over;
		}
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define pb push_back
#define mod 1000000007
#define pll pair<long long,long long>
using namespace std;
long long power(long long a,long long b){
    long long ans=1;
    while(b>0){
        if(b&1){ans=(ans*a)%mod;}
                a=(a*a)%mod;
                b>>=1;
        }
    return ans;
}
bool prime(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0)return false;
    }
    return true;
}
int dp[100005];
int fun(int n,int a[]){
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++){
        dp[i]=min(dp[i-1]+abs(a[i-1]-a[i]),dp[i-2]+abs(a[i-2]-a[i]));
    }
    return dp[n-1];
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    cout<<fun(n,a);
    return 0;
}

Measured memory_bytes: 5168
n = int(input())
a = list(map(int,input().split()))
cnt = 0
for i in range(n-1):
    for j in range(n-1):
        if a[j]>a[j+1]:
            a[j],a[j+1] = a[j+1],a[j]
            cnt += 1
print(*a)
print(cnt)


Measured memory_bytes: 5612
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    int ans=0;
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d %d",&l,&r);
        ans+=(r-l+1);
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main( void )
{
  int n,prev,d[5001],ret;
  while( 1 ){
    cin >> n;
    if( n==0 ) break;
    cin >> d[0];
    ret = d[0];
    for( int i=1; i<n; i++ ){
      cin >> d[i];
      for( int j=0; j<i; j++ ) d[j] += d[i];
      ret = max( *max_element( d, d+i+1 ), ret );
    }
    cout << ret << endl;
  }
  return 0;
}

Measured memory_bytes: 0
using System;
using System.Collections.Generic;
class _0028
{
    public static void Main()
    {
        int n, maxCount = 0;
        string str;
        Dictionary<int, int> nums = new Dictionary<int, int>();
        List<int> ans = new List<int>();
        while ((str = Console.ReadLine()) != null)
        {
            n = int.Parse(str);
            if (nums.ContainsKey(n)) nums[n]++;
            else nums[n] = 1;
        }
        foreach (KeyValuePair<int, int> dic in nums) maxCount = (maxCount < dic.Value) ? dic.Value : maxCount;
        foreach (KeyValuePair<int, int> dic in nums) if (dic.Value == maxCount) ans.Add(dic.Key);
        ans.Sort();
        for (int i = 0; i < ans.Count; i++) Console.WriteLine(ans[i]);
    }
}

Measured memory_bytes: 6252
R,G,B=map(int,input().split())
K=int(input())


for i in range (K+1):
    if R < G < B:
        print ('Yes')
        exit()
    else:
        pass
    
    if G < B:
        pass
    else:
        B*=2
        continue

    if R < G:
        pass
    else:
        G*=2
        continue

print('No')


Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
template<typename T> inline void chkmin(T &a, const T &b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T &a, const T &b) { a = a > b ? a : b; }

const int MAXN = 2000005, MOD = 1e9 + 7;
int fac[MAXN], inv[MAXN], X[6], Y[6];
struct Point { int x, y, c; } p1[4], p2[4];
LL modpow(LL a, int b) {
	LL res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
	}
	return res;
}

void init() {
	int n = 2e6;
	for (int i = fac[0] = 1; i <= n; i++)
		fac[i] = (LL)fac[i - 1] * i % MOD;
	inv[n] = modpow(fac[n], MOD - 2);
	for (int i = n; i > 0; i--)
		inv[i - 1] = (LL)inv[i] * i % MOD;
}

LL go(int x1, int y1, int x2, int y2) {
	x2 -= x1, y2 -= y1;
	return (LL)fac[x2 + y2] * inv[x2] % MOD * inv[y2] % MOD;
}

LL calc(int x1, int y1, int x2, int y2) {
	LL ans = 0;
	for (int i = X[2]; i <= X[3]; i++) {
		ans -= go(x1, y1, i, Y[2] - 1) * go(i, Y[2], x2, y2) % MOD * (i + Y[2] - 1);
		ans += go(x1, y1, i, Y[3]) * go(i, Y[3] + 1, x2, y2) % MOD * (i + Y[3]);
		ans %= MOD;
	}
	for (int i = Y[2]; i <= Y[3]; i++) {
		ans -= go(x1, y1, X[2] - 1, i) * go(X[2], i, x2, y2) % MOD * (i + X[2] - 1);
		ans += go(x1, y1, X[3], i) * go(X[3] + 1, i, x2, y2) % MOD * (i + X[3]);
		ans %= MOD;
	}
	if (ans < 0) ans += MOD;
	return ans;
}

int main() {
	init();
	for (int i = 0; i < 6; i++) scanf("%d", X + i);
	for (int i = 0; i < 6; i++) scanf("%d", Y + i);
	p1[0] = Point { X[0] - 1, Y[0] - 1, 1 };
	p1[1] = Point { X[1], Y[0] - 1, -1 };
	p1[2] = Point { X[0] - 1, Y[1], -1 };
	p1[3] = Point { X[1], Y[1], 1 };
	
	p2[0] = Point { X[5] + 1, Y[5] + 1, 1 };
	p2[1] = Point { X[4], Y[5] + 1, -1 };
	p2[2] = Point { X[5] + 1, Y[4], -1 };
	p2[3] = Point { X[4], Y[4], 1 };
	
	LL ans = 0;
	for (int i = 0; i < 4; i++)
	for (int j = 0; j < 4; j++)
		ans += p1[i].c * p2[j].c * calc(p1[i].x, p1[i].y, p2[j].x, p2[j].y);
	printf("%lld\n", (ans % MOD + MOD) % MOD);
	return 0;
}

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


int main(){
int n,t,sum=0,fin,ans=0,big=0;
    long int t2;
cin>>n>>t;
fin=t;
for(int i=0;i<n;i++){
cin>>t2;
if(t2<=fin){
fin=t2+t;
}
else{
ans=ans+fin-big;
big=t2;
fin=t+t2;
}
}
ans=ans+fin-big;
cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(i, n)   for(int i = 0; i < (int)(n); i++)
#define MAX_N   100000

void solve(){

}

int main (){
    int n;
    cin >> n;
    int d[n];
    REP(i, n)
        cin >> d[i];
    sort(d, d + n);
    if(n % 2)
        cout << 0 << endl;
    else{
        cout << d[n / 2] - d[n / 2 - 1] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e17;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t = "#";
    cin >> s;
    int n = s.length();
    int ans = n;
    s += '#';
    int i = 0;
    while(i < n){
        if (t.length() == 1 && s[i] == t[0]){
            ans--;
            t = s[i]+s[i+1];
            i += 2;
        }
        else{
            t = s[i];
            i++;
        }
    }
    PRINT(ans);
}


Measured memory_bytes: 720
k = int(input())

L = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(L[k-1])

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int A;
  vector<int> C(N);
  for (int i = 0; i < N; i++) {
    cin >> A; 
  while (A % 2 == 0) {
    A /= 2;
    C.at(i)++;
  }
    C.at(0) = min (C.at(0), C.at(i));
  
  }
  cout << C.at(0) << endl;
}
  

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

vector<string> a = {"AC", "WA", "TLE", "RE"};

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  map<string, int> mp;
  int n;
  cin >> n;
  rep(i, n) {
    string s;
    cin >> s;
    mp[s]++;
  }
  rep(i, 4)
    cout << a[i] << " x " << mp[a[i]] << endl;
  return 0;
}

Measured memory_bytes: 3656
prime_number=[]
def prime():
    for i in range(2,int((10**8)**0.5+1)):
        flag=1
        for j in prime_number:
            if i%j==0:flag=0
        if flag:prime_number.append(i)

def checker(n):
    for i in prime_number:
        if n==i:
            return True
        if n%i==0:return False
    return True

prime()
count=0
for i in list(int(input()) for j in range(int(input()))):
    if checker(i):count +=1
print(count)


Measured memory_bytes: 6072
#include <cstdio>
#include <algorithm>
int n,odd[100005],even[100005];
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		int v;scanf("%d",&v);
		if(i&1) ++odd[v];
		else ++even[v];
	}
	int mxodd=0,lmxodd=0,oddele=0,mxeven=0,lmxeven=0,evenele=0;
	for(int i=1;i<=100000;++i) {
		if(odd[i]>mxodd) {
			mxodd=odd[i];
			oddele=i;
		}
		if(even[i]>mxeven) {
			mxeven=even[i];
			evenele=i;
		}
	}
	for(int i=1;i<=100000;++i) {
		if(i^oddele) lmxodd=std::max(lmxodd,odd[i]);
		if(i^evenele) lmxeven=std::max(lmxeven,even[i]);
	}
	if(oddele==evenele) printf("%d\n",n-std::max(mxodd+lmxeven,lmxodd+mxeven));
	else printf("%d\n",n-mxodd-mxeven);
	return 0;
}


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

using namespace std;

int main(void){
  int n, a, b, c, d;
  string s;
  cin >> n >> a >> b >> c >> d;
  cin.ignore();
  cin >> s;
  cin.ignore();

  // a<b<dより、ふぬけ君から先に行けばいい

  // 0-origin
  a--;
  b--;
  c--;
  d--;

  // ふぬけ
  int len = s.length();

  int su = a;
  int fu = b;

  //for(int i =b; i < len; i++){

  if (d < c){
  // d < c の場合、まずすぬけがふぬけを追い越す必要がある
  // 追い抜ける場所は、前後に岩がないところ=p
  // とりあえずふぬけをそっちに移動
  // すぬけが先にゴールにいく
  // ふぬけが後

    // pを見つける
    int p = b;

    //0方向にすぬけ、前が空白の場合はそのまま

    if((p>0) && (s[p+1] == '.') && (a == p - 1)){
      p = b;
    } else {
      while(p <= d){

        // 場所が条件を満たすか判定
        if((s[p-1] == '.') && (s[p+1] == '.')){
          break;
        }

        // pの条件判定
        // pが末尾dの場合、すでに無理
        if(p>=d){
          cout << "No" << endl;
          return 0;
        } else if((p == d - 1) && (s[d] == '#')){ //n pが後ろから2つめ、前が岩
          cout << "No" << endl;
          return 0;
        } else if((s[p] == '#') && (s[p + 1] == '#')){ // 2連続で岩ならその時点でNG
          cout << "No" << endl;
          return 0;
        }

        // 前が岩なら2つ進める
        // 文の条件から、ぜったいにdにたどり着く
        if(s[p + 1] == '#'){
          p+=2;
        } else {
          p++;
        }
      }
    }
    fu = p;

    // すぬけはふぬけの開始位置-1までいければ追い抜ける
    // その途中に岩が2連続でなければOK
    for(int i = a + 1; i < b - 1; i++){
      if((s[i] == '#') && (s[i+1] == '#')){
        cout << "No" << endl;
        return 0;
      }
    }

    // すぬけはふぬけを追い越した
    su = fu + 1;

    // すぬけから先にゴール

    for(int i = su + 1; i < c - 1; i++){
      if((s[i] == '#') && (s[i+1] == '#')){
        cout << "No" << endl;
        return 0;
      }
    }

    for(int i = fu + 1; i < d - 1; i++){
      if((s[i] == '#') && (s[i+1] == '#')){
        cout << "No" << endl;
        return 0;
      }
    }
    cout << "Yes" << endl;
    return 0;
  } else { // c < d
    // ふぬけから先に動かす
    for(int i = b + 1; i < d - 1; i++){
      if((s[i] == '#') && (s[i+1] == '#')){
        cout << "No" << endl;
        return 0;
      }
    }

    for(int i = a + 1; i < c - 1; i++){
      if((s[i] == '#') && (s[i+1] == '#')){
        cout << "No" << endl;
        return 0;
      }
    }
    cout << "Yes" << endl;
    return 0;
  }

  cout << "Illegal" << endl;
  return 0;
  
}

    

        


Measured memory_bytes: 640
// https://atcoder.jp/contests/abc104/tasks/abc104_d

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")
#define DUMP2DLL(a, n, m) REP(_i, n) REP(_j, m) printf("%lld%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")

const int S_MAX = 1e5;
const int MOD = 1e9+7;
const int A = 1;
const int AB = 2;

char S[S_MAX + 1];

int N;
ll dp[S_MAX + 1][3];
ll c;

void solve() {
  N = strlen(S);
  c = 1;
  REP(i, N) {
    switch (S[i]) {
      case 'A':
        dp[i + 1][0] = dp[i][0];
        dp[i + 1][A] = (dp[i][A] + c) % MOD;
        dp[i + 1][AB] = dp[i][AB];
        break;
      case 'B':
        dp[i + 1][0] = dp[i][0];
        dp[i + 1][A] = dp[i][A];
        dp[i + 1][AB] = (dp[i][AB] + dp[i][A]) % MOD;
        break;
      case 'C':
        dp[i + 1][0] = (dp[i][0] + dp[i][AB]) % MOD;
        dp[i + 1][A] = dp[i][A];
        dp[i + 1][AB] = dp[i][AB];
        break;
      default:
        dp[i + 1][0] = (dp[i][0] * 3 + dp[i][AB]) % MOD;
        dp[i + 1][A] = (dp[i][A] * 3 + c) % MOD;
        dp[i + 1][AB] = (dp[i][AB] * 3 + dp[i][A]) % MOD;
        c = (c * 3) % MOD;
        break;
    }
  }
  // DUMP2DLL(dp, N + 1, 3);
  printf("%lld\n", dp[N][0]);
}

void input() {
  scanf("%s", S);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 2688
#include <bits/stdc++.h> 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define MAX 100005
#define DEBUG 0 
#define LIMIT (LONG_MAX / 10)
#define POSITIVE_LAST_D (LONG_MAX % 10)
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;


int main(){
    string s,s1,s2;
    cin>>s;
    int q,cnt=0;
    cin>>q;
    rep(i,q){
        int t;
        cin>>t;
        if(t==1){
            cnt++;
        }else{
            int f;
            char c;
            cin>>f>>c;
            if(f==1){
                if(cnt%2==0){
                    s1+=c;
                }else{
                    s2+=c;
                }
            }else{
                if(cnt%2==0){
                    s2+=c;
                }else{
                    s1+=c;
                }
            }
        }
    }
    if(cnt%2!=0){
        reverse(s.begin(),s.end());
        reverse(s2.begin(),s2.end());
        s+=s1;
        s2+=s;
        cout<<s2<<endl;
        return 0;
    }else{
        reverse(s1.begin(),s1.end());
        s+=s2;
        s1+=s;
        cout<<s1<<endl;
        return 0;
    }
}


Measured memory_bytes: 1280
#include <iostream>

using namespace std;

int main()
{
  int N, M, K;
  cin >> N >> M >> K;
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= M; j++) {
      if ((N - i)*j + (M - j)*i == K) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl; 
#define n_max 55
string A[n_max],B[n_max];
int n,m;



bool issame(int row,int col){
    REP(i,m){
        REP(j,m){
            if(A[i+row][j+col] != B[i][j] or i+row >=n or j +col >=n){
                return false;
            }
        }
    }
    return true;
}

int main(){
    cin >> n >> m;
    REP(i,n) cin >> A[i];
    REP(i,m) cin >> B[i];

    bool flag=false;
    REP(i,n-m +2){
        REP(j,n-m+2){
            if(issame(i,j)) flag = true;
        }
    }
    if(flag) cout << "Yes" << endl;
    else print("No");

}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()
#define VEC(TYPE, A, NAME, INIT) vector<TYPE> NAME(A, INIT)
#define VEC2(TYPE, A, B, NAME, INIT) vector<vector<TYPE>> NAME(A, vector<TYPE>(B, (INIT)))

int main()
{
	ull n = 0;
	string s;
	cin >> n;
	cin >> s;
	map<char, ull> mp;
	REP( i, n )
	{
		mp[s[i]]++;
	}
	ull ans = 1;
	for( const auto& m : mp )
	{
		ans = ( ans * ( m.second + 1 ) ) % 1000000007;
	}

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

Measured memory_bytes: 512
#include<stdio.h>
#include<string.h>
int main(void)
{
    char S[50];
  	char T[50];
  	char U[50];
  int s,t,u;
    // 整数の入力
    scanf("%s %s\n", S,T);
    // スペース区切りの整数の入力
    scanf("%d%d\n",&s,&t);
    // 文字列の入力
    scanf("%s\n",U);
    if(strcmp(S,U)==0)
      printf("%d %d\n",s-1,t);
  else if(strcmp(T,U)==0)
      printf("%d %d\n",s,t-1);
  
    return 0;
}

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

using namespace std;

int main() {
    int N;
    long long int A, B;
    cin >> N >> A >> B;
    vector<long long int> H(N);
    long long int r=0, cnt=0;
    for(int n=0; n<N; n++) {
        long long int tmp;
        cin >> H[n];
        
        cnt += H[n]/A;
        if(H[n]%A) {
            cnt += 1;
        }

        tmp = H[n]/B;
        if(H[n]%B) {
            tmp += 1;
        }
        r = max(r, tmp);
    }
    r = min(r, cnt);
    long long int l=0, mid;
    while(r-l>1) {
        mid = (r+l)/2;
        long long int tmp=0;
        for(int n=0; n<N; n++) {
            long long int tt = max(H[n]-mid*B, (long long int)0);
            tmp += tt/(A-B);
            if(tt%(A-B)) {
                tmp++;
            }
        }
        if(tmp==mid) {
            r=mid;
            break;
        } else if(tmp>mid) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << r << endl;

    return 0;
    
}

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

int main() {
    ll n, x;
    cin >> n;
    vector<ll> nums;
    for (ll i=0; i<n; i++) {
        cin >> x;
        nums.push_back(x);
    }
    bool inc = false;
    ll recent = 0;
    vector<ll> nums2;
    for (ll i=1; i<n; i++) {
        if (nums[i]>nums[i-1] && !inc) {
            inc = true;
            nums2.push_back(nums[i-1]);
            recent = nums[i-1];
        }
        else if (nums[i]<nums[i-1] && inc) {
            inc = false;
            nums2.push_back(nums[i-1]);
            recent = nums[i-1];
        }
    }
    if (nums[n-1]>recent) nums2.push_back(nums[n-1]);
    ll res = 1000;
    ll stock = 0;
    n = nums2.size();
    if (nums2.size()==1) {
        cout << 1000;
        return 0;
    }
    for (ll i=0; i<n; i++) {
        if (i%2==0) {
            stock+=(res/nums2[i]);
            res%=nums2[i];
        }
        else {
            res+=(nums2[i]*stock);
            stock = 0;
        }
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 3584
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <iomanip>
#include <deque>
#include <queue>
#include <unordered_map>
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
ll intpow(ll N, ll P){
    if(P==0) return 1;
    if(P%2==0){
        ll t = intpow(N, P/2);
        return t*t;
    }
    return N * intpow(N, P-1);
}
ll modpow(ll N, ll P,ll k){
    if(P==0) return 1;
    if(P%2==0){
        ll t = modpow(N, P/2,k)%k;
        return t*t%k;
    }
    return N * modpow(N, P-1,k)%k;
}
ll modkai(ll n,ll m,ll k){//n*(n-1)*(n-2)*...(m+1)%k
    if(n == m)return 1;
    return modkai(n-1,m,k)*n%k;
}
ll mod_cnb(ll n,ll m,ll k){//nCm%k,kは十分大きい素数
  int m_=modkai(m,0,k);
  return modkai(n,n-m,k)*modpow(m_,k-2,k)%k;
}
ll gcd(ll n,ll m){
    ll n_ = max(n,m);
    ll m_ = min(n,m);
    if(n_%m_ == 0)return m_;
    return gcd(m_,n_%m_);
}
ll lcm(ll n,ll m){
    return n*m/gcd(n,m);
}
int main(){
    int n;cin>>n;
    ll sum=0;
    for(ll i=0;i<n;i++)sum+=i+1;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            if(i==j)continue;
            sum+=gcd(i+1,j+1)*3;
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=i+1;j<=n;j++){
            for(ll k=j+1;k<=n;k++){
                sum+=gcd(i,gcd(j,k))*6;
            }
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3620
//organize and stay in moment
//Abhinav - IIITA
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ar array
int32_t main(){
	int n,d,a;
	cin>>n>>d>>a;
	ar<int,2> br[n];
	int cm[n+1];
	for(int i=0;i<=n;++i)
		cm[i]=0;
	for(int i=0;i<n;++i)
		cin>>br[i][0]>>br[i][1];
	sort(br,br+n);
	int ans=0;
	for(int i=0,j=0;i<n;++i){
		while(j<n && br[j][0]<=br[i][0]+2*d)
			++j;
		j--;
		int bomb=max((int)0,(br[i][1]-cm[i]*a+a-1)/a);
		ans+=bomb;
		cm[i]+=bomb;
		cm[j+1]-=bomb;
		cm[i+1]+=cm[i];
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 4992
MOD = 998244353


def main():
    # もらうdp + 累積和
    N, K = (int(i) for i in input().split())
    LR = [[int(i) for i in input().split()] for j in range(K)]

    dp = [0] * (N+2)
    dpsum = [0] * (N+1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N+1):
        for le, ri in LR:
            L = max(0, i - ri - 1)
            R = i - le
            if R < 1:
                continue
            dp[i] += dpsum[R] - dpsum[L]
            dp[i] %= MOD
        dpsum[i] += dpsum[i-1] + dp[i]
        dpsum[i] %= MOD
    print(dp[N])
    # print(dpsum)


if __name__ == '__main__':
    main()


Measured memory_bytes: 76840
import collections
N = int(input())


def prime_factorize(n):
    a = collections.defaultdict(int)
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a


ans = 0
for v in prime_factorize(N).values():
    for i in range(1, 100):
        if (i + 1) * (i + 2) // 2 > v:
            break
    ans += i
print(ans)


Measured memory_bytes: 9364
n, m = map(int, input().split())
left = 0
right = n + 1
for i in range(m):
    l, r = map(int, input().split())
    if left < l:
        left = l
    if right > r:
        right = r
if right < left:
    print(0)
else:
    print(right-left + 1)


Measured memory_bytes: 43480
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <limits>
using namespace std;
// 素因数分解
typedef pair<long long, long long> P;
vector<P> prime_factorize(long long n)
{
vector<P> res;
for (long long p = 2; p * p <= n; ++p)
{
if (n % p != 0)
continue;
int num = 0;
while (n % p == 0)
{
++num;
n /= p;
}
res.push_back(make_pair(p, num));
}
if (n != 1)
res.push_back(make_pair(n, 1));
return res;
}
// 因数分解
long long gcd(long long x, long long y)
{
  if (y == 0)
  {
    return x;
  }
  else
  {
    return gcd(y, x % y);
  }
}
const int MOD = 1000000007;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < (n); i++)

int main()
{
    string s;
    cin >> s;
    set<char> set;
    rep(i,3){
        set.insert(s[i]);
    }
    if(set.size()==2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3576
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	aa := make([]int, n)
	for i := 0; i < n; i++ {
		aa[i] = getNextInt(scanner)
	}
	m := getNextInt(scanner)
	bb := make([]int, m)
	for i := 0; i < m; i++ {
		bb[i] = getNextInt(scanner)
	}
	for i := 0; i < n && i < m; i++ {
		if aa[i] < bb[i] {
			fmt.Fprintln(writer, 1)
			return
		}
		if aa[i] > bb[i] {
			fmt.Fprintln(writer, 0)
			return
		}
	}
	if n < m {
		fmt.Fprintln(writer, 1)
		return
	}
	fmt.Fprintln(writer, 0)
}



Measured memory_bytes: 1248
#a,bの最大公約数
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

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

N=int(input())
g=int(input())
for n in range(N-1):
    t=int(input())
    g=lcm(g,t)
print(g)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define INF 2147483647
#define INF_LL 9223372036854775807
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	cout << min(A, B) << " " << max(A + B - N, 0) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define _ ios::sync_with_stdio(false);cin.tie(0);
#define __ cout<<fixed;cout<<setprecision(10);
#define int long long

void solve() {
	int n;
	cin >> n;
  	if(n%1000==0){
      cout<<"0\n";
      return;}
  cout << 1000 - n % 1000 << "\n";
}

int32_t main() {
	_ __
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}

#ifndef ONLINE_JUDGE
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
#endif

	return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int n, l;
    cin>>n>>l;
    string s[n];
    for (int i=0; i<n; i++) cin>>s[i];
    sort(s, s+n);
    for (int i=0; i<n; i++) cout<<s[i];
    cout<<'\n';
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
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 double PI = acos(-1.0);
// cout << fixed << setprecision(14);

//深さ優先探索
vector<bool> seen;
int ans[100010];
bool ok = true;
void dfs(const Graph &G, int v){
    seen[v] = true; // v を訪問済みにする
	if(ok){
		// vから行ける各頂点 next_v について
		for(auto nv : G[v]){
			// if(seen[nv]) continue; // next_v が探索済みだったらスルー
			if(ans[nv] != 0){
				if(ans[nv] * ans[v] == -1) continue;
				else{
					ok = false;
					break;
				}
			}
			ans[nv] = ans[v] * -1;
			dfs(G, nv); // 再帰的に探索
		} 
	}
}
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	Graph G(N);
	char C[N][N];
	int A[N][N];
	rep(i,N){
		rep(j,N){
			cin >> C[i][j];
			if(i == j) A[i][j] = 0;
			else if(C[i][j] == '0' && i != j) A[i][j] = INF;
			else{
				G[i].push_back(j);
				A[i][j] = 1;
			}
		}
	}

	seen.assign(N, false); // 全頂点を「未訪問」にして初期化
	ans[0] = 1;
    dfs(G, 0);
	if(ok){
		rep(k,N){
			rep(i,N){
				rep(j,N){
					chmin(A[i][j], A[i][k]+A[k][j]);
				}
			}
		}
		int ans1 = 0;
		rep(i,N){
			rep(j,N){
				if(A[i][j] < MOD){
					chmax(ans1, A[i][j]);
				}
			}
		}
		cout << ans1+1 << endl;
	}
	else cout << -1 << endl;
}

Measured memory_bytes: 4144
#include <stdio.h>

int main(void) {
	int H,W,i,j;
	for(;;){
		scanf("%d %d",&H,&W);
		if(H==0&&W==0) break;
		if(H>=1&&H<=300&&W>=1&&W<=300){
			for(i=0;i<H;i++){
				for(j=0;j<W;j++){
					if((i+j)%2==0) printf("#");
					else printf(".");
				}
				printf("\n");
			}
			printf("\n");
		}
	}
	return 0;
}



Measured memory_bytes: 2072
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define rsort(x) sort(all(x));reverse(all(x))
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool debug=false;
/*---------------------------------------------------*/

int main(){
  string s;
  cin>>s;
  rep(i,s.size())if(!(i%2))cout<<s[i];
  cout<<endl;
  return 0;
}


Measured memory_bytes: 512