akhauriyash/Code-Regression huggingface dataset:
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " <<"LINE:"<<__LINE__<<"  "<< #i <<":"<< i << std::endl

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<ll, ll>;

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

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

  ll n;
  std::cin>>n;

  ll ans=1;

  rep(i,0,n){
    ll a;
    std::cin>>a;

    ll g=gcd(ans,a);
    ans=ans/g*a;
  }

  std::cout<<ans<<"\n";

  return 0;
}

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

int main() {
    int N; cin >> N;
    int a,b,c;
    a=N/100;
    b=(N-a*100)/10;
    c=N%10;
    if(a==7||b==7||c==7) cout << "Yes" << endl;
    else cout << "No" << endl;
}

    

Measured memory_bytes: 3540
import java.util.Scanner;


public class Main {
	static int A,B;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		 A = sc.nextInt();
		 B = sc.nextInt();

		sc.close();

		if(B%A == 0){
			System.out.println(B+A);
		}else{
			System.out.println(B-A);
		}
	}
}

Measured memory_bytes: 21588
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

// ABC106 D-AtCoder Express2
// 2020.06.07
// 二次元累積和、包除原理

ll N, M, Q;
vector<vector<ll> > A;
vector<vector<ll> > AA;

ll func(ll l, ll r){
  ll res = 0;
  res += AA[r][r];
  if(l != 0){
    res -= AA[l-1][r];
    res -= AA[r][l-1];
    res += AA[l-1][l-1];
  } 
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M >> Q;
  A.assign(N, vector<ll>(N, 0));
  AA.assign(N, vector<ll>(N, 0));
  REP(i, M){
    ll L, R; cin >> L >> R; L--; R--;
    A[L][R]++;
  }
  REP(i, N){
    REP(j, N){
      if(i == 0){
        if(j == 0){
          AA[i][j] = A[i][j];
        }else{
          AA[i][j] = AA[i][j-1] + A[i][j];
        }
      }else{
        if(j == 0){
          AA[i][j] = AA[i-1][j] + A[i][j];
        }else{
          AA[i][j] = AA[i][j-1] + AA[i-1][j] - AA[i-1][j-1] + A[i][j];
        }
      }
    }
  }
  REP(i, Q){
    ll p, q; cin >> p >> q; p--; q--;
    cout << func(p, q) << endl;
  }
}

Measured memory_bytes: 4864
N=int(input())
H=list(map(int, input().split()) )

#print(N)
#print(H)

count0=0
count1=0
for j in range(N-1):
  if H[j]>=H[j+1]:
    count0=count0+1
    #print(j,count0)
  else:
    if count0>=count1:
      count1=count0
      count0=0
    else:
      count0=0
      
print(max(count0,count1))



Measured memory_bytes: 14224
from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(i,j):
    ma=j
    mi=i
    while ma-mi>1:
        mid = (ma + mi)//2
        a=A[j]-A[mid]
        b=A[mid-1]-A[i]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [A[mi]-A[i],A[j]-A[mi]]
num=10**14
for i in range(2,N-1):
    ans=[]
    ans+=dou(0,i)
    ans+=dou(i,N)
    #print(ans)
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)

Measured memory_bytes: 84984
import itertools
n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))

l = [int(x) for x in range(1,n+1)]
i = 0
p_i = 0
q_i = 0
for v in itertools.permutations(l, len(l)):
    i += 1
    if p==list(v):
        p_i = i
        #print(list(v))
    if q==list(v):
        q_i = i
        #print(i,list(v))
print(abs(p_i-q_i))


Measured memory_bytes: 9072
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (1E9+7)
#define PI 3.1415926535897932384

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

int main() {
	int  a, b;
	cin >> a >> b;
	bool s = false;
	if (a % 3 == 0)s=true;
	if (b % 3 == 0)s = true;
	if ((a+b) % 3 == 0)s = true;
	cout << (s ? "Possible" : "Impossible") << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
using namespace std;

int main() {

	string S;
	cin >> S;

	if (S.back() == 's') {
		S += "es";
	}
	else {
		S += "s";
	}

	cout << S << endl;

	return 0;
}

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> v{1, n + 1};

    int l, r;
    for (int i = 0; i < m; i++){
        cin >> l >> r;
        if (l > v[0]){
            v[0] = l;
        }
        if (r < v[1]){
            v[1] = r;
        }
    }

    if (v[1] - v[0] < 0){
        cout << 0 << endl;
    } else{
        cout << (v[1] - v[0] + 1) << endl;
    }
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll K, S;
  cin >> K >> S;
  int z;
  ll ans = 0;
  for (int x = 0; x <= S && x <= K; x++) {
    for (int y = 0; y <= S && y <= K; y++) {
      z = S - x - y;
      if (0 <= z && z <= K) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3640
<?php
$array = explode(" ", trim(fgets(STDIN)));
$N = $array[0];
$x = $array[1];
$ans = "Yes";
if(($x == 1) || ($x == 2 * $N - 1)) $ans = "No";
if($ans == "Yes") {
  print($ans);
  print("\n");
  $block = array();
  if($N == 2) {
    $block[0] = 1;
    $block[1] = 2;
    $block[2] = 3;
  } else {
    $q = array();
    if($x < 2 * $N - 2) {
      for($i = 1; $i < 2 * $N; $i++) {
        if(($i != $x - 1) && ($i != $x) && ($i != $x + 1) && ($i != $x + 2)) $q[] = $i;
      }
      $index = 0;
      for($i = 0; $i < 2 * $N - 1; $i++) {
        if($i == $N - 3) {
          $block[$i] = $x + 2;
        } else if($i == $N - 2) {
          $block[$i] = $x - 1;
        } else if($i == $N - 1) {
          $block[$i] = $x;
        } else if($i == $N) {
          $block[$i] = $x + 1;
        } else {
          $block[$i] = $q[$index];
          $index++;
        }
      }
    } else {
      for($i = 1; $i < 2 * $N; $i++) {
        if(($i != $x + 1) && ($i != $x) && ($i != $x - 1) && ($i != $x - 2)) $q[] = $i;
      }
      $index = 0;
      for($i = 0; $i < 2 * $N - 1; $i++) {
        if($i == $N - 3) {
          $block[$i] = $x - 2;
        } else if($i == $N - 2) {
          $block[$i] = $x + 1;
        } else if($i == $N - 1) {
          $block[$i] = $x;
        } else if($i == $N) {
          $block[$i] = $x - 1;
        } else {
          $block[$i] = $q[$index];
          $index++;
        }
      }
    }
  }
  for($i = 0; $i < 2 * $N - 1; $i++) {
    print($block[$i]);
    print("\n");
  }
} else {
  print($ans);
}
?>

Measured memory_bytes: 22256
#include <iostream>
using namespace std;
int main()
{
    int flg = 0;
    int N;
    int A;

    cin >> N;
    
    for (int i = 0;i < N;++i) {
        cin >> A;  
        if (A % 2 == 0) {
            if (A % 3 == 0 || A % 5 == 0){

            } else {
                flg = 1;
            }
        }
    }

    if (flg != 1) {
        cout << "APPROVED" << endl;
    } else {
        cout << "DENIED" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	int h;
	cin>>h;
	if (h%7==1) cout<<"fri"<<endl;
	if (h%7==2) cout<<"sat"<<endl;
	if (h%7==3) cout<<"sun"<<endl;
	if (h%7==4) cout<<"mon"<<endl;
	if (h%7==5) cout<<"tue"<<endl;
	if (h%7==6) cout<<"wed"<<endl;
	if (h%7==0) cout<<"thu"<<endl;
	return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORR(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(),x.end()
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl

int main() {
    int N,K;
    cin >> N >> K;
    vi A(N);
    REP(i,N) cin >> A[i];

    //和を求める
    ll sum = 0;
    REP(i,N) sum += A[i];


    //約数を求める
    set<ll> candidates;
    for(int i=1;i*i<=sum;i++){
        if(sum%i==0){
            candidates.insert(i);
            candidates.insert(sum/i);
        }
    }

    ll ans = 1;
    for(ll x : candidates){
        ll need = 0;
        {
            vector<ll> r(N);
            REP(i,N) r[i] = A[i]%x;
            sort(all(r));

            ll rSum = 0; //足す場合
            REP(i,N) rSum += x-r[i]; 

            ll lSum = 0; //引く場合
            need = 1e18;
            REP(i,N){
                lSum += r[i];
                rSum -= x-r[i];
                need = min(need,max(lSum,rSum));
            }

        }

        if(need<=K)ans = max(ans,x);
    }

    cout << ans << endl;

    return 0;

}



Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)


using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;

int main(){
    int a, b;
    cin >> a >> b;
    if(a * b == 15)cout << '*' << endl;
    else if(a + b == 15)cout << '+' << endl;
    else cout << 'x' << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int INF = 1000000007;
const int MOD = (int)1e9+7;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;
int dy[4] = {-2, -1};
int dx[4] = {-1, -2};

int n, t;
vector<pii> c;

int cache[3000][3000];
int solve(int pos, int time) {
	if(pos == n) return 0;
	if(time >= t) return 0;

	int& ret = cache[pos][time];
	if(ret != -1) return ret;
	ret = 0;

	ret = max(ret, solve(pos+1, time));
	ret = max(ret, solve(pos+1, time+c[pos].first) + c[pos].second);

	return ret;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("in.txt", "r", stdin);
	cin >> n >> t;
	rep(i,0,n) {
		int a, b;
		cin >> a >> b;
		c.pb(mp(a,b));
	}
	sort(all(c));
	memset(cache, -1, sizeof(cache));
	cout << solve(0,0) << endl;
	return 0;
}


Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

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

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};

const int dx8[8] = {1,1,0,-1,-1,-1,0,1};
const int dy8[8] = {0,1,1,1,0,-1,-1,-1};

vector< vector<int> > Graph;
vector< int > value;





int main(int argc, const char * argv[]) {
    
    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s; cin >> s;
    int num1 = 0;
    int num0 = 0;
    for(int i = 0; i < (int)s.size(); i++){
        if(s[i]=='0')num0++;
        else num1++;
    }
    cout << min(num0,num1)*2 << endl;
}



Measured memory_bytes: 640
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)
	ans := "No"
	if s[0] == s[1] && s[2] == s[3] && s[0] != s[2] {
		ans = "Yes"
	} else if s[0] == s[2] && s[1] == s[3] && s[0] != s[1] {
		ans = "Yes"
	} else if s[0] == s[3] && s[1] == s[2] && s[0] != s[1] {
		ans = "Yes"
	}
	fmt.Println(ans)
}


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

using namespace std;

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli r;
	lli d;
	lli x;
	cin>>r>>d>>x;

	for(lli i=2001;i<=2010;i++){
		x = r*x-d;
		cout<<x<<endl;
	}

	return 0;
}

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

using std::cin;
using std::cout;
using std::endl;
using std::string;

static int
fix(long a)
{
  return int(a % 1000000007);
}

static int
add_fix(int a, int b)
{
  return fix(long(a) + long(b));
}

// char-position unitvalue unitvalue%13
// 0 1 1
// 1 10 10
// 2 100 9
// 3 1000 12
// 4 10000 3
// 5 100000 4
// 6 1000000 1
// 7 10000000 10
// ...
static int const mods[] = {1, 10, 9, 12, 3, 4};
static int const mods_cycle = sizeof(mods) / sizeof(mods[0]);
static int memo[100000][13];
static string S;

static int const target_mod = 5;

// for recursive call
static int solve(int offset, int mod);

static int
calc(int offset, int mod)
{
  if (S[offset] != '?')
  {
    return solve(offset + 1, mod);
  }
  int count = 0;
  int delta = mods[(S.size() - offset - 1) % mods_cycle];
  for (int i = 0; i < 10; i++)
  {
    count = add_fix(count, solve(offset + 1, (mod + delta * i) % 13));
  }
  return count;
}

static int
solve(int offset, int mod)
{
  if (S.size() <= offset)
  {
    return mod == target_mod ? 1 : 0;
  }
  int value = memo[offset][mod];
  if (value == 0)
  {
    memo[offset][mod] = value = calc(offset, mod) + 1;
  }
  return value - 1;
}

int
main()
{
  cin >> S;
  int mod = 0;
  for (int i = 0; i < S.size(); i++)
  {
    int c = S[S.size() - i - 1];
    if (c != '?')
    {
      mod += mods[(i % mods_cycle)] * (c - '0');
    }
  }
  mod %= 13;
  cout << solve(0, mod) << endl;
  return 0;
}


Measured memory_bytes: 13312
N, K = map(int, input().split())
P = list(map(lambda x:int(x)-1, input().split()))
C = list(map(int, input().split()))
done = [False] * N
ans = -10**30
must_negative = all([c < 0 for c in C])
for i in range(N):
  if done[i]:
    continue
  loop = [i]
  done[loop[-1]] = True
  while not done[P[loop[-1]]]:
    loop.append(P[loop[-1]])
    done[loop[-1]] = True
    #print(loop, done)
  #print(loop)
  scores = [C[i] for i in loop]
  #print(scores)
  cumsum = [0]
  for s in scores * 3:
    cumsum.append(cumsum[-1] + s)
  #print(cumsum)
  L = len(scores)
  if cumsum[L] >= 0:
    # (L+K) // L  loops - max
    l = max(0, (K - L) // L )
    k_max = K - l * L
    #print(l, k_max)
    base_score = cumsum[L] * l
  else:
    k_max = min(K, 2 * L)
    #print(k_max)
    base_score = 0
  for i in range(L):
    for k in range(k_max+1):
      score = base_score + cumsum[i + k] - cumsum[i]
      #print(i, k, base_score, score)
      if must_negative and score == 0:
        continue
      ans = max(ans, score)
print(ans)

Measured memory_bytes: 69232
#include <stdio.h>
#include <math.h>

int max(int n1, int n2, int n3) {
    int max;
    
    max = n1;
    
    if(n2 > max)
        max = n2;
    if(n3 > max)
        max = n3;
    
    return(max);
}

int others(int n1, int n2, int n3) {
    int na = 0;
    int nb = 0;
    int two_pow2;
    
    if(n1 != max(n1, n2, n3)) {
        na = n1;
    }
    if(n2 != max(n1, n2, n3)) {
        if(na == 0)
            na = n2;
        else {
            nb = n2;
        }
    }
    if(n3 != max(n1, n2, n3)) {
        if(na == 0 || nb == 0){
            if(na == 0)
                na = n3;
            else {
                nb = n3;
            }
        }
    }
    
    two_pow2 = pow(na, 2) + pow(nb, 2);
    
    return(two_pow2);
    
}

void two_pow2(int n1, int n2, int n3) {
    
    if(others(n1, n2, n3) == pow(max(n1, n2, n3), 2))
        puts("YES");
    else
        puts("NO");
    
}

int main(void) {
    int n1, n2, n3;
    int num, i;
    
    scanf("%d", &num);
    
        
    for(i = 0; i < num; i++) {
        if(num > 1000) break;
        
        scanf("%d %d %d", &n1, &n2, &n3);
    
        two_pow2(n1, n2, n3);
    }
    
    return(0);
}

Measured memory_bytes: 580
import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    S = input()
    cnt = 0
    for s, r in zip(S[: int(len(S) / 2) + 1], S[: int(len(S) / 2) - 1 : -1]):
        # print(s, r)
        if s != r:
            cnt += 1

    return cnt


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 3060
/*---> 11 January 2020 <--- > 05:08:11 <---*/
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define F first
#define S second
#define mod 1000000007
#define inf (int)1e18+5
#define sz(x) (int)x.size()
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vpii vector<pair<int,int> > 
#define vvi vector<vector<int> >
#define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long double ld;
typedef pair<int,int> pii;
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////
const int N=1e5+5;

int32_t main(){__
	int n;
	cin>>n;
	vi a(n),b(n),c(n);
	for(int i=1;i<=n;i++){
		a[i-1]=i;
	}
	for(int i=0;i<n;i++){
		cin>>b[i];
	}
	for(int j=0;j<n;j++){
		cin>>c[j];
	}
	int cnt=1;
	vi t;
	do{
		if(a==b){
			t.push_back(cnt);
		}
		if(a==c){
			t.push_back(cnt);
		}
		cnt++;
	}while(next_permutation(all(a)));

	cout<<abs(t.back()-t[0])<<"\n";
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int main()
{
	int N;
	cin >> N;
 
	vector<int> v(N + 1, 0);
	int max = (int)sqrt((double)N);
	for (int x = 1; x < max; x++) {
		for (int y = 1; y < max; y++) {
			for (int z = 1; z < max; z++) {
				int result = (x * x) + (y * y) + (z * z) + (x * y) + (y * z) + (z * x);
				if (result <= N) {
					v[result]++;
				}
				//else {
				//	goto END;
				//}
			}
		}
	}
//END:
	for (int n = 1; n <= N; n++) {
		cout << v[n] << endl;
	}
 
	return 0;
}

Measured memory_bytes: 3704
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 10000
using namespace std;
int a[N],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    cout<<a[n]-a[1];
}
/*
 5
 1 1 1
 111
 3 1 8
 1
 2
 4
 1 2
 2 3
 3 2 10
 4 7
 8 9
 2 3
 1 2
 2 3
 4 2 99
 0 1
 0 1
 0 1
 0 0
 4 1
 2 4
 4 3
 4 3 99
 0 1 0
 0 1 0
 0 1 0
 0 0 0
 4 1
 2 4
 4 3
 */


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            String N = sc.next();
            int K = sc.nextInt();

            long ans = main(N, K);

            System.out.println(ans);
        }
    }

    static long main(String N, int K) {
        long ans = calc(N.length() - 1, K);

        int n = Integer.parseInt(N.substring(0, 1));

        if (K == 1) {
            ans += n;
        } else {
            if (n > 1) {
                ans += calc(N.length() - 1, K - 1) * (n - 1);
            }
            for (int i = 1; i < N.length(); i++) {
                if (N.charAt(i) != '0') {
                    ans += main(N.substring(i), K - 1);
                    break;
                }
            }
        }

        return ans;
    }

    static long calc(int M, int K) {
        long ans = 0;

        for (int i = 1; i <= M; i++) {
            if (K == 1) {
                ans += comb(i - 1, i - 1) * 9;
            } else if (K == 2) {
                ans += comb(i - 1, i - 2) * 9 * 9;
            } else if (K == 3) {
                ans += comb(i - 1, i - 3) * 9 * 9 * 9;
            }
        }

        return ans;
    }

    static long comb(int a, int b) {
        if (b < 0) {
            return 0;
        }

        if (b > a - b) {
            b = a - b;
        }

        long x = 1;
        for (int i = 0; i < b; i++) {
            x *= (a - i);
        }
        for (int i = 0; i < b; i++) {
            x /= (1 + i);
        }

        return x;
    }

}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define Mp make_pair
#define X first
#define Y second
#define N 111111
using namespace std;
int n,m,i,id,x,V[N];
string s,str[N];char ch[9];
set<pair<int,int> >S,S2;
set<pair<int,int> >::iterator it;
pair<int,int>era;
map<string,int>mp;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		cin>>s;
		mp[s]=++id;str[id]=s;
		scanf("%d",&x);
		V[id]=x;
		S2.insert(Mp(x,id));
	}
	for(i=1;i<=n/5;i++){
		it=S2.end();
		it--;
		S.insert(*it);
		S2.erase(S2.find(*it));
	}
	scanf("%d",&m);
	for(i=1;i<=m;i++){
		scanf("%s",ch);
		cin>>s;
		if(ch[0]=='-'){
			x=mp[s];
			if(S.count(Mp(V[x],x))){
				S.erase(S.find(Mp(V[x],x)));
				if((S.size()+S2.size()+1)%5!=0){
					it=S2.end();
					it--;
					cout<<str[(*it).Y];
					puts(" is working hard now.");
					S2.erase(S2.find(*it));
					S.insert(*it);
				}
			}else{
				S2.erase(S2.find(Mp(V[x],x)));
				if((S.size()+S2.size())%5==4){
					it=S.begin();
					cout<<str[(*it).Y];
					puts(" is not working now.");
					S.erase(S.find(*it));
					S2.insert(*it);
				}
			}
		}else{
			scanf("%d",&x);
			mp[s]=++id;str[id]=s;
			V[id]=x;
			if(S.size()==0){
				S2.insert(Mp(x,id));
				if(S2.size()==5){
					it=S2.end();
					it--;
					if((*it)==Mp(x,id)){
						cout<<str[id];puts(" is working hard now.");
					}else{
						cout<<str[id];puts(" is not working now.");
						cout<<str[(*it).Y];puts(" is working hard now.");
					}
					S2.erase(S2.find(*it));
					S.insert(*it);
				}else{
					cout<<str[id];puts(" is not working now.");
				}
			}else{
				it=S.begin();
				if(Mp(x,id)>*it){
					era=*it;
					S.erase(S.find(*it));
					S.insert(Mp(x,id));
					cout<<str[id];puts(" is working hard now.");
					if((S.size()+S2.size()+1)%5==0){
						S.insert(era);
					}else{
						S2.insert(era);
						cout<<str[era.Y];puts(" is not working now.");
					}
				}else{
					S2.insert(Mp(x,id));
					if((S.size()+S2.size())%5==0){
						it=S2.end();
						it--;
						if(Mp(x,id)==(*it)){
							cout<<str[id];puts(" is working hard now.");
						}else{
							cout<<str[id];puts(" is not working now.");
							cout<<str[(*it).Y];puts(" is working hard now.");
						}
						S2.erase(S2.find(*it));
						S.insert(*it);
					}else{
						cout<<str[id];puts(" is not working now.");
					}
				}
			}
		}
	}
}

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

const int mod = 1e9 + 7, N = 1e5 + 10;

ll pw(ll a, ll b)
{
	ll r = 1;
	for(; b ; b >>= 1, a = a * a % mod)
	{
		if(b & 1)
		{
			r = r * a % mod;
		}
	}
	return r;
}

ll getinv(ll n)
{
	return pw(n, mod - 2);
}

void upd(ll &a, ll b)
{
	a = (a + b) % mod;
}

int n, q;

ll cnt[N]; // 记录每个颜色出现次数
ll sum[N]; // 记录每个颜色的边权和
ll S;

struct E
{
	int v, c, w;
};
vector<E> g[N];

int fa[N][22], dep[N];

struct T
{
	int ids;
	int x, y; // 把颜色x的长度都改成y
	int tag; // 对答案贡献 +-1
};
vector<T> G[N];
ll ans[N];

int main()
{
	scanf("%d%d", &n, &q);
	for(int i = 1 ; i < n ; ++ i)
	{
		int u, v, c, w;
		scanf("%d%d%d%d", &u, &v, &c, &w);
		g[u].push_back((E)
		{
			v, c, w
		});
		g[v].push_back((E)
		{
			u, c, w
		});
	}
	if(1)
	{
		function<void(int, int)> dfs = [&](int u, int fa)
		{
			dep[u] = dep[fa] + 1;
			:: fa[u][0] = fa;
			for(int i = 1 ; i <= 20 ; ++ i)
			{
				:: fa[u][i] = :: fa[:: fa[u][i - 1]][i - 1];
			}
			for(auto e : g[u])
			{
				int v = e.v;
				if(v != fa)
				{
					dfs(v, u);
				}
			}
		};
		dfs(1, 0);
	}

	function<int(int, int)> getlca = [&](int u, int v)
	{
		if(dep[u] < dep[v])
		{
			swap(u, v);
		}
		for(int i = 20 ; ~ i ; -- i)
		{
			if(dep[fa[u][i]] >= dep[v])
			{
				u = fa[u][i];
			}
		}
		if(u == v)
		{
			return u;
		}
		for(int i = 20 ; ~ i ; -- i)
		{
			if(fa[u][i] != fa[v][i])
			{
				u = fa[u][i];
				v = fa[v][i];
			}
		}
		return fa[u][0];
	};

	for(int i = 1 ; i <= q ; ++ i)
	{
		int x, y, u, v;
		scanf("%d%d%d%d", &x, &y, &u, &v);
		int lca = getlca(u, v);
		G[u].push_back((T)
		{
			i, x, y, 1
		});
		G[v].push_back((T)
		{
			i, x, y, 1
		});
		G[lca].push_back((T)
		{
			i, x, y, -2
		});
	}

	if(1)
	{
		function<void(int, int)> dfs = [&](int u, int fa)
		{
			for(auto e : G[u])
			{
				ll val = S - sum[e.x] + (ll) cnt[e.x] * e.y;
				ans[e.ids] += val * e.tag;
			}
			for(auto e : g[u])
			{
				int v = e.v;
				if(v != fa)
				{
					++ cnt[e.c];
					sum[e.c] += e.w;
					S += e.w;
					dfs(v, u);
					-- cnt[e.c];
					sum[e.c] -= e.w;
					S -= e.w;
				}
			}
		};
		dfs(1, 0);
	}

	for(int i = 1 ; i <= q ; ++ i)
	{
		printf("%lld\n", ans[i]);
	}
}

Measured memory_bytes: 33908
import java.util.*;
import java.util.stream.*;
 
public class Main {
    private static Scanner scanner = new Scanner(System.in);
 
    public static void main(String[]$) {
        int n = scanner.nextInt(), m = scanner.nextInt(), a[] = new int[m], b[] = new int[m], num[] = new int[n + 1];
        long[] ans = new long[m];
        fa = IntStream.rangeClosed(0, n).toArray();
        for (int i = 0; i < m; i++) {
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
        }
        Arrays.fill(num, 1);
        ans[m - 1] = (long)n * (n - 1) / 2;
        for (int i = m - 1; i > 0; i--) {
            ans[i - 1] = ans[i];
            if (fd(a[i]) != fd(b[i])) {
                ans[i - 1] -= num[fa[a[i]]] * num[fa[b[i]]];
                num[fa[b[i]]] += num[fa[a[i]]];
                fa[fa[a[i]]] = fa[b[i]];
            }
        }
        Arrays.stream(ans).forEach(System.out::println);
    }
 
    static int[] fa;
    static int fd(int a) {
        return fa[a] == a ? a : (fa[a] = fd(fa[a]));
    }
}

Measured memory_bytes: 96532
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

void f(const vector<pair<int, int>>& vp, int k, long long int& res) {
    long long int r = 0;
    for (int i = 0; i < vp.size(); i++) {
        if ((vp[i].first | k) == k) {
            r += vp[i].second;
        }
    }
    res = max(res, r);
}

int main() {        
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> vp;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        vp.emplace_back(a, b);
    }
    long long int res = 0;
    f(vp, k, res);
    for (int i = 29; i >= 0; i--) {
        if ((k & (1 << i)) > 0) {
            int kk = k - (1 << i);
            kk |= (1 << i) - 1;

            f(vp, kk, res);
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 4312
def c_green_bin(N, S):
    s = sorted([''.join(sorted(word)) for word in S])
    right = 1
    ans = 0
    for left in range(N):
        while right < N and s[left] == s[right]:
            right += 1
        ans += right - 1 - left
        if left + 1 == right:
            right += 1
    return ans

N = int(input())
S = [input() for _ in range(N)]
print(c_green_bin(N, S))

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

s = sum(B)
for i in range(N-1):
    if A[i+1] == A[i] + 1:
        s += C[A[i]-1]

print(s)

Measured memory_bytes: 38256
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<ll,pair<int,int>>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 2000000000
#define N 100005
#define MOD 1000000007
using namespace std;
 
int main() {
 
 	ll ans=0;
	int n;

	scanf("%d",&n);n++;

	vector<int> a(n+1),b(n+1);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<n;i++) {

		scanf("%d",&b[i]);

		int dc=min(a[i],b[i]);

		a[i]-=dc;
		b[i]-=dc;


		ans+=dc;

		dc=min(a[i+1],b[i]);

		a[i+1]-=dc;
		b[i]-=dc;

		ans+=dc;

	}

	printf("%lld",ans);

}

Measured memory_bytes: 1024
d = input().split(" ")
k = int(d[0])
n = int(d[1])
a = input().split(" ")
for i in range(n):
	a[i] = int(a[i])
a.sort()
p = 0
for i in range(n-1):
	c = a[i+1] - a[i]
	if c > p:
		p = c
e = a[0] + k - a[n-1]
if e > p:
	p = e
print(k - p) 

Measured memory_bytes: 18356
// Created by sz
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    int q;
    cin >> s >> q;
    vector<string> con(2);
    
    int r = 0;
    for (int i = 0; i < q; i++){
        int op;
        cin >> op;
        if(op == 1){
            r = !r;
            continue;
        }
        int f;
        char c;
        cin >> f >> c;
        if(!r){
            if(f == 1)con[0] += c;
            else con[1] += c;
        }
        else{
            if(f == 1)con[1]+=c ;
            else con[0] += c ;
        }
    }
    
    
    
    if(r){
        reverse(s.begin(), s.end());
        reverse(con[1].begin(), con[1].end());
        cout << con[1] + s + con[0] << "\n";
    }else{
        reverse(con[0].begin(), con[0].end());
        cout << con[0] + s + con[1] << "\n";
    }
    
    
    
    
    return 0;
}


Measured memory_bytes: 1300
#include <iostream>

using namespace std;

int main(){
	int W=0,H=0,N=0;
	int x[100],y[100],a[100];
	bool **map=NULL;
	int i,ii;
	int j,jj;
	int count=0;

	cin>>W>>H>>N;

	map = new bool * [W];
	for(i=0;i<W;i++){
		map[i] = new bool [H];
		for(ii=0;ii<H;ii++){
			map[i][ii]=true;
		}
	}

	for(i=0;i<N;i++){
		cin>>x[i]>>y[i]>>a[i];

		switch(a[i]){
			case 1:
			for(j=0;j<x[i];j++){
				for(jj=0;jj<H;jj++){
					map[j][jj]=false;
				}
			}
			break;
			case 2:
			for(j=x[i];j<W;j++){
				for(jj=0;jj<H;jj++){
					map[j][jj]=false;
				}
			}
			break;
			case 3:
			for(j=0;j<W;j++){
				for(jj=0;jj<y[i];jj++){
					map[j][jj]=false;
				}
			}
			break;
			case 4:
			for(j=0;j<W;j++){
				for(jj=y[i];jj<H;jj++){
					map[j][jj]=false;
				}
			}
			break;

			default : 
			cout<<"error"<<endl;
			break;
		}

	}

	for(i=0;i<W;i++){
		for(ii=0;ii<H;ii++){
			if(map[i][ii]){
				count++;
			}
		}
	}

	cout<<count<<endl;



	for(i=0;i<W;i++){
		delete [] map[i];
	}
	delete [] map;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
  int n,m,x,y;
  cin >> n >> m >> x >> y;
  for (int i = 0; i < n; i++) {
    int xi;
    cin >> xi;
    x = max(x,xi);
  }
  for (int i = 0; i < m; i++) {
    int yi;
    cin >> yi;
    y = min(y,yi);
  }
  if (x < y) cout << "No War" << endl;
  else cout << "War" << endl;
  return 0;
}

Measured memory_bytes: 3600
attrs = Array.new
while line = $stdin.gets
  attrs << line.chomp.split
end

N = attrs[0][0].to_i

case N % 10
when 2,4,5,7,9 then
  puts 'hon'
when 0,1,6,8 then
  puts 'pon'
when 3 then
  puts 'bon'
end

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

int main() {
	double w, h, x, y;
	std::cin >> w >> h >> x >> y;
	
	double cw = w / 2, ch = h / 2;
	
	bool ans = 0;
	if(cw == x and ch == y) ans = 1;
	
	std::cout << w * h / 2 << " " << ans << std::endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int ans,n;
int main()
{
  cin>>n;
  for (int i=0;i<n;i++)
  {
  	int x;cin>>x;
    ans=__gcd(ans,x);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
N,K = map(int,input().split())
*A, = map(int,input().split())

L = [0]*(N+2)
R = [0]*(N+2)
for i in range(1,N+1):
    L[i] = L[i-1]+max(0,A[i-1])
for i in range(N,0,-1):
    R[i] = R[i+1]+max(0,A[i-1])

ans = 0
S = sum(A[:K])
for i in range(N-K+1):
    ans = max(ans,L[i]+max(0,S)+R[i+K+1])
    S += -A[i] + A[(K+i)%N]
print(ans)

Measured memory_bytes: 17584
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = vector<int>;
using Vlli = vector<lli>;
using Wint = vector<Vint>;
using Wlli = vector<Vlli>;
using pii = pair<int, int>;
using pll = pair<lli, lli>;

const int MOD = 1e9 + 7;
const int INFi = 2e9 + 1;
const lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
const char BR = '\n';

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(i, vec) for(auto &(i) : (vec))


template <class T> inline int argmin(vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){a = max(a, b);}
template <class T> inline void chmin(T &a, T b){a = min(a, b);}
inline int toInt(string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline int toInt(const string s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res = "";
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~




int main(void){
  int n, m; cin >> n >> m;
  Vint number_balls(n, 1);
  vector<bool> Pexit(n, false); Pexit.at(0) = true;
  int x, y;
  REP(i, m){
    cin >> x >> y;
    x--; y--;
    number_balls.at(x)--;
    number_balls.at(y)++;
    if(Pexit.at(x)){
      Pexit.at(y) = true;
      if(number_balls.at(x) == 0){
        Pexit.at(x) = false;
      }
    }
  }
  cout << std::count(Pexit.begin(), Pexit.end(), true) << BR;
  return 0;
}

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

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF ((1LL<<62)-1)
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME ((1ll<<61)-1)

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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

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

template<class T>
inline void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

inline void out() {
	cout<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

bool isout(int h, int w, int H, int W) {
	return ( h<0 || h>=H || w<0 || w>=W );
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


int N,ans;
intvec A(100001,0);

void input() {
	cin>>N;
}

void solve() {
	for(int i=0; i<N; i++) {
		int a; cin>>a;
		A[max(a-1,0)]++;
		A[min(a+2,100000)]--;
	}
	for(int i=0; i<100000; i++) A[i+1] += A[i];
	sort(rall(A));
	cout<<A[0]<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}


Measured memory_bytes: 3640
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    m = II()
    print(48-m)
    return

#B
def B():
    a, b = LI()
    s = S()
    ans = list(map(str, range(10)))
    for num, si in enumerate(s):
        if num != a:
            if si in ans:
                continue
            print("No")
            return
        else:
            if si == "-":
                continue
            print("No")
            return
    print("Yes")
    return

#C
def C():
    n = II()
    csf = LIR(n - 1)
    for i in range(n - 1):
        b = 0
        for k in range(i, n - 1):
            c, s, f = csf[k]
            if b <= s:
                b = s + c
            else:
                b += c + (-b % f)
        print(b)
    print(0)
    return

#D
def D():
    a = II()
    ans = inf
    b = 0
    for k in range(1, 10 ** 5):
        b += a
        ans = min(ans, sum(list(map(int, list(str(b))))))
    print(ans)
    return

#Solve
if __name__ == '__main__':
    C()


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

int main(){
  string s;
  int q;
  cin>>s>>q;
  int cnt=0;
  deque<char> deq;
  rep(i,s.size()) deq.push_back(s[i]);
  rep(i,q){
    int t;
    cin>>t;
    if(t==1) cnt++;
    else{
      int f;
      char c;
      cin>>f>>c;
      if((f+cnt)%2==0){
	deq.push_back(c);
      }
      else deq.push_front(c);
    }
  }
  if(cnt%2==1)
    reverse(deq.begin(),deq.end());
  rep(i,deq.size())
      cout<<deq[i];
  return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define M 1000000007
int main()
{
    int N;cin >> N;
    vector<int> vec;
    for(int a = 0;a < N;a++){
        int b;cin >> b;
        vec.push_back(b);
    }
    sort(vec.begin(),vec.end());
    int A=0,B=0;
    int s = 0;
    for(int a = vec.size()-1;a >= 0;a--){
        if(s%2==0){
            A+=vec.at(a);
        }else{
            B+=vec.at(a);
        }
        s++;
    }
    cout<<A-B<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <cassert>
#include <fstream>
#include <iomanip>
#include <stack>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

const ll mod = 1e9 + 7;
const ll mmod = 998244353;

vector<ll> dx = {1, -1, 0, 0};
vector<ll> dy = {0, 0, 1, -1};

vector<string> g;
vector<vector<bool>> used;
vector<ll> d;

long long gcd(const long long& a, const long long& b)
{
    if (b == 0)
    {
        return a;
    }
    return gcd(b, a % b);
}

vector<long long> sieve(const long long& n)
{
    vector<long long> v(n + 1);
    vector<bool> c(n + 1, 1);
    vector<long long> ret;
    for (long long i = 2; i <= n; ++i)
    {
        if (c[i])
        {
            for (long long j = 2 * i; j <= n; j += i)
            {
                c[j] = 0;
            }
            ret.push_back(i);
        }
    }
    return ret;
}

int main() {
    
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    ll n;
    cin >> n;
    vector<ll> a(n);
    
    ll gc = -1;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        if (gc < 0)
        {
            gc = a[i];
            continue;
        }
        gc = gcd(a[i], gc);
    }
    
    vector<ll> c(1e6 + 1);
    
    vector<ll> p = sieve(1e6);
    
    vector<vector<ll>> div(1e6 + 1, vector<ll>(1, 1));
    for (int i = 0; i < p.size(); ++i)
    {
        for (int j = p[i]; j <= 1e6; j += p[i])
        {
            div[j].push_back(p[i]);
        }
    }
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 1; j < div[a[i]].size(); ++j)
        {
            c[div[a[i]][j]]++;
        }
    }
    bool f = 0;
    for (int i = 2; i <= 1e6; ++i)
    {
        if (c[i] > 1)
        {
            f = 1;
            break;
        }
    }
    
    if (!f)
    {
        cout << "pairwise coprime" << endl;
    }
    else
    {
        if (gc == 1)
        {
            cout << "setwise coprime" << endl;
        }
        else
        {
            cout << "not coprime" << endl;
        }
    }

    return 0;
}

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

typedef long long ll;

int main(){
    string S;
    cin >> S;
    
    int n = (int)S.length();
    
    ll sum=0;
    for(int bit=0; bit < (1<<(n-1)); bit++){
        
        vector<char> s;
        for(int i=0; i<n; i++){
            s.push_back(S[i]);
            if(bit & (1<<i)){
                s.push_back('+');
            }
        }
        ll tmp=0, k=1;
        for(int i=(int)s.size()-1; i>=0; i--){
            if(s[i]!='+'){
                tmp += (s[i] - '0') * k;
                k *= 10;
            }
            else {
                sum += tmp;
                tmp = 0;
                k = 1;
            }
        }
        sum += tmp;
    }
    cout << sum << endl;
}


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

int check(int s,int n)
{
    if(s>=n) return 1;
    return 0;
}

int main()
{
    int n,m;
    for(;;){
        cin >> n >> m;
        if(n==0&&m==0) break;
        int a[n],b[m];
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        for(int i=0;i<m;i++){
            cin >> b[i];
        }
        int s=1,c=0;
        if(check(s,n)==1){
            cout << c << endl;
            continue;
        }
        for(int i=0;i<m;i++){
            c++;
            s+=b[i];
            if(check(s,n)==1){
                cout << c << endl;
                break;
            }
            s+=a[s-1];
            if(check(s,n)==1){
                cout << c << endl;
                break;
            }
        }

    }
    return 0;
}



Measured memory_bytes: 3024