akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

#define NIL -1
#define MAX 100005
struct Node{
  int p;
  int l;
  int r;
};
struct Node T[MAX];
int n,D[MAX];


int rec(int,int);
int main(){
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    T[i].p=NIL;
    T[i].l=NIL;
    T[i].r=NIL;
  }
  for(i=0;i<n;i++){
    scanf("%d %d",&v,&d);
    for(j=0;j<d;j++){
      scanf("%d",&c);
      if(j==0)T[v].l=c;
      else T[l].r=c;
      l=c;
      T[c].p=v;
    }
  }
  for(i=0;i<n;i++){
    if(T[i].p==NIL)r=i;
  }
  rec(r,0);
  for(i=0;i<n;i++){
    printf("node %d: parent = %d, depth = %d, ",i,T[i].p,D[i]);
    if(T[i].p==NIL)printf("root, ");
    else if(T[i].l==NIL)printf("leaf, ");
    else printf("internal node, ");
    printf("[");
    for(j=0,c=T[i].l;c!=NIL;j++,c=T[c].r){
      if(j)printf(", ");
      printf("%d",c);
    }
    printf("]\n");
  }
  return 0;
}
int rec(int u, int p){
  D[u]=p;
  if(T[u].r!=NIL)rec(T[u].r,p);
  if(T[u].l!=NIL)rec(T[u].l,p+1);
}

Measured memory_bytes: 5300
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
int d[]=new int[n];
int sum=0;
for(int i=0;i<n;i++){
	d[i]=sc.nextInt();
sum+=d[i];
}
int ans=0;
for(int i=0;i<n;i++){
	ans+=d[i]*(sum-d[i]);
}
System.out.println(ans/2);

	}
}

Measured memory_bytes: 21972
n = int(input())

total = 0

for i in range(1, int(n**0.5)+1):
    if n%i == 0:
        a = i
        b = n//i

        if a != 1 and (n//(a-1))*a == n:
            total += a-1
        if b != a and (n//(b-1))*b == n:
            total += b-1

print(total)

Measured memory_bytes: 9344
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int Q=in();
	list<int> V;
	auto itr=V.end();
	REP(i,Q){
		int q=in();
		int d;
		switch(q){
		case 0:
			itr=V.insert(itr,in());
			break;
		case 1:
			advance(itr,in());
			break;
		default:
			itr=V.erase(itr);
		}
	}

	for(auto& x:V) out(x);
	return 0;
}


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

def main():
  if 0 in A:
    print(0)
    return
 
  count = 1
  for i in A:
    count *= i
    if count > 1000000000000000000:
      print(-1)
      return
 
  print(count)

main()


Measured memory_bytes: 21580
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N, Inc,Dec;
int32_t res[600000];
auto iter = res;
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >>N>> Inc>>Dec;

	{
		//for (int32_t i = Inc-1; i >= 0 ; --i)
		//{
		//	*iter++ = N - i;
		//}
		//for (int32_t i = Dec - 2; i >= 0; --i)
		//{
		//	*iter++ = i+1;
		//}
		for (int32_t i = 1; i <= Inc; i++) {
			if (iter >= (res + N)) { out << -1 << endl; return 0; }
			*iter++ = N - Inc + i;
		}
		for (int32_t i = 1; i <= Dec - 1; i++) {
			if (iter >= (res + N)) { out << -1 << endl; return 0; }
			*iter++ = Dec - i;
		}

		//int32_t rem = N - (iter - res);
		//if (rem<0 || rem > (Dec - 1)*(Inc - 1)) {
		//	out << -1 << endl; return 0;
		//}

		int32_t count = 1;
		int32_t start = Dec - 1;
		while (iter < (res + N))
		{
			start += Dec - 1;
			start = std::min(start, N - Inc + 1 - 1);
			for (int32_t i = 0; i < Dec - 1 && iter < (res + N); i++) {
				*iter++ = start - i;
			}
			++count;
			if (count > Inc) {
				//assert(false);
				out << -1 << endl; return 0;
			}
		}
		/*
		int32_t bottom = Dec;
		while (iter < (res + N)) {
			auto iter_last = iter;
			iter += (Dec - 1);
			iter = std::min(res + N, iter);
			auto iter_next = iter;
			for (int32_t i = 0; i < Dec-1 && iter_last<iter; i++)
			{
				*--iter = i + bottom;
			}
			iter = iter_next;
			//for (int32_t i = Dec - 1 - 1; iter != (res + N) && i >= 0; --i)
			//{
			//	*iter++ = i + bottom;
			//}
			bottom += Dec - 1;
			if (bottom >= N - (Inc - 1)) { break; }
		}
		*/
		out << res[0];
		for (int32_t i = 1; i < N; i++)
		{
			out << ' ' << res[i];
		}
		out << endl;
	}

	return 0;
}
#endif


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

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
#define rep(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

ll INF = 1ll << 60;

int main(){
  int a, b;
  cin >> a >> b;
  
  rep(i, 0, max(a,b)){
    cout << min(a, b);
  }
  cout << endl;
  
  return 0;
  
}

Measured memory_bytes: 3564
//ITNOA
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
const long long INF=1e9+10,MAX=2e5+1e4,MOD=1e9+7,MAXL=25;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
void OUT(long double o,int x){
	 cout<<fixed<<setprecision(x)<<o;
	 return;
}
ll a[MAX];
map<ll,bool> mp;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,x=0,y;
	cin>>n;
	while(n--){
		cin>>y;
		if(mp[y]){
			mp[y]=0;
			x--;
		}
		else{
			mp[y]=1;
			x++;
		}
	}
	cout<<x;
	return 0;
}


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

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

using namespace std;

int main() {
  int n,m;
  cin>>n>>m;
  vector<int> rev(n+2);
  REP(i,m) {
    int c,d;
    cin>>c>>d;
    for(int j=c;j<d;++j) rev[j]=1;
  }
  cout<<(n+1+count(begin(rev),end(rev),1)*2)<<endl;
  return 0;
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
#define LL long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=16035;
char s[16005];
int n,ex,ey,q[2][N];
bool visx[2][N],visy[2][N];
#define fx(i,j) visx[i][j+8000]
#define fy(i,j) visy[i][j+8000]
int main()
{
	scanf("%s%d%d",s+1,&ex,&ey); n=strlen(s+1);
	int now=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='T') break;
		ex--;now=i;
	}
	fx(0,0)=fy(0,0)=1;
	now++;
//	cout<<now<<endl;
	int k=1;
	for(int i=now+1,j;i<=n;i++){
		int cnt=0;
		for(j=i;j<=n;j++){
//			cout<<"gg "<<j<<' ';
			if(s[j]=='T') break;
			cnt++;
		}
//		cout<<' '<<i<<' '<<j<<' '<<cnt<<endl;
		if(k&1){
			for(int j=-8000;j<=8000;j++)
			  if(fy(0,j))
				fy(1,j+cnt)=fy(1,j-cnt)=1;//cout<<"goy "<<j-cnt<<' '<<j+cnt<<' ';
			memcpy(visy[0],visy[1],sizeof(visy[0]));
			memset(visy[1],0,sizeof(visy[1]));
//			for(int j=-10;j<=10;j++) cout<<fy(0,j)<<' '; cout<<endl;
		}
		else{
			 for(int j=-8000;j<=8000;j++)
			  if(fx(0,j))
				fx(1,j+cnt)=fx(1,j-cnt)=1;//cout<<"gox "<<j<<' ';
			memcpy(visx[0],visx[1],sizeof(visx[0]));
			memset(visx[1],0,sizeof(visx[1]));
//			for(int j=-10;j<=10;j++) cout<<fx(0,j)<<' '; cout<<endl;
		}
		i=j; k^=1;
	}
	if(fx(0,ex)&&fy(0,ey)) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#define NIL -1

int F[45];


int fibonacci(int n){
  if((n == 0)||(n == 1)) {
    return F[n] = 1;
  }

  if(F[n]!=NIL) return F[n];

  return F[n] = fibonacci(n-2) + fibonacci(n-1);
};

int main(){
  int n,i;

  for(i=0;i<45;i++) F[i]=NIL;
  
  scanf("%d",&n);

  printf("%d\n",fibonacci(n));

  return 0;
}
  



Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define RREP(i,a,n) for(int i=(a),i##_len=(n);i<i##_len;++i)
#define vec1(V,T,a) vector<T> V (a)
#define vec2(V,T,a,b) vector<vector<T>> V (a, vector<T>(b))
#define vec3(V,T,a,b,c) vector<vector<vector<T>>> V (a, vector<vector<T>>(b, vector<T>(c)))

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool>::reference b) { return to_string(bool(b)); }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) { return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " +
  to_string(get<2>(t)) + ")"; }
template <typename A>
string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; }

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

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  using t = tuple<string,int,int>;
  vec1(m,t,n);
  REP(i,n) {
    string s;
    int p;
    cin >> s >> p;
    m[i] = make_tuple(s,p,i+1);
  }
  sort(m.begin(), m.end(), [](const t& x,const t& y){
      if (get<0>(x) == get<0>(y)) {
        return get<1>(x) > get<1>(y);
      }
      return get<0>(x) < get<0>(y);
      });

  REP(i,n) cout << get<2>(m[i]) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<pair<int, int>> P(n);
  for (int i = 0; i < n; i++){
    cin >> P[i].first >> P[i].second;
  }
  sort(P.begin(), P.end());
  for (int i = 0; i < n; i++){
    cout << P[i].first << ' ' << P[i].second << endl;
  }
}


Measured memory_bytes: 3596
main :: IO ()
main = do
  [a,b] <- map read . words <$> getLine
  print $ numOfPlndrm a b

numOfPlndrm
  :: Int -> Int -> Int
numOfPlndrm a b = length [x | x <- [a .. b], isP x]

isP :: Int -> Bool
isP n = c == reverse c
  where
    c = show n

Measured memory_bytes: 892
//int a = stoi(c); 文字列をintへ
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
//チェックリストはマップを使う
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//またはかかつか
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//数が大きい時のせぐふぉはコードテストで試してみる
//スペルミスに注意
//stack<ll> s;
//s.push(要素);s.top();s.pop();
//queue<ll> q;
//q.push(要素);q.front();q.pop();
//同じ作業繰り返す系の問題：収束先を見つける
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

//円周率
const double PI = 3.14159265358979323846;
//割るやつ
const ll M = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}


//a,bの最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1)) % M;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

//ABC158のE見る
int main() {
	double a, b, c, d; cin >> a >> b >> c >> d;

	ll x = ceil(a / d);
	ll y = ceil(c / b);

	if (x == y) cout << "Yes" << endl;
	else if(y < x) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 11024
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;

int main(void){
 char s[100][100];
 int H,W;
 int ok=1;
 cin>>H>>W;
 for(int i=0; i<H; i++)cin>>s[i];
 
 for(int i=0; i<H; i++)
  for(int j=0; j<W; j++)
   if(i-1>=0 &&i+1<H && j-1>0 && j+1<W && s[i][j]=='#' &&(s[i-1][j]=='.'&& s[i][j-1]=='.'&& s[i+1][j]=='.'&& s[i][j+1]=='.'))ok=0;

 if(ok)std::cout<<"Yes"<<std::endl;
 else std::cout<<"No"<<std::endl;
}
     

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string s;
    cin >> n >>s;
    int h=0;
    for(int i=0;i<n-2;i++){
        if(s.at(i)=='A'&&s.at(i+1)=='B'&&s.at(i+2)=='C')h++;
    }
    cout << h << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <iomanip>
#include <cmath>
#include <set>
#include <numeric>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
namespace mp = boost::multiprecision;
ll BASE_NUM = 1000000007;
int main()
{
    // 整数の入力
    ll N;
    cin >> N;
    vector<ll> A, B;
    ll SS = 1 << N;
    ll MAX_VALUE = 50;
    vector<vector<ll>> DP(SS, vector<ll>(MAX_VALUE+1, BASE_NUM));
    for (int i = 0; i < N; i++)
    {
        ll a;
        cin >> a;
        A.push_back(a);
    }

    for (int i = 0; i < N; i++)
    {
        ll b;
        cin >> b;
        B.push_back(b);
    }
    DP[0][0] = 0;

    for (int s = 0; s < SS; s++)
    {
        for (int i = 0; i < N; i++)
        {
            if (s & (1 << i))
            {
                continue;
            }
            ll s_count = 0;
            ll moves = 0;
            for (int j = 0; j < N; j++)
            {
                if (s & (1 << j))
                {
                    s_count++;
                }
                else if (j < i)
                {
                    moves++;
                }
            }
            ll value;
            if (abs(i - s_count) % 2 == 0)
            {
                value = A[i];
            }
            else
            {
                value = B[i];
            }

            for (int j = 0; j <= value; j++)
            {
                // cout << s << "-" << i  << "-" << j << "!" << DP[s][j] + moves << endl;
                DP[s | 1 << i][value] = min(DP[s | 1 << i][value], DP[s][j] + moves);
            }
        }
    }

    ll min_value = BASE_NUM;
    for (int i = 0; i <= MAX_VALUE; i++)
    {
        // cout << DP[SS-1][i] << endl;
        min_value = min(min_value, DP[SS - 1][i]);
    }
    if (min_value == BASE_NUM)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << min_value << endl;
    }
    return 0;
}

Measured memory_bytes: 112896
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

using namespace std;

const ll MOD = 998244353;

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

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

	map<ll, ll> D;
	vector <ll> DD(N);
	ll maxD = 0;
	for (int ii = 0; ii < N; ++ii){
		ll tmp;
		cin >> tmp;
		D[tmp]++;
		DD[ii] = tmp;
		maxD = max(maxD, tmp);
	}

	bool ok = true;
	if( (DD[0]!=0) ) {
		ok = false;
	}
	for (int ii = 1; ii < N; ++ii){
		if (DD[ii] == 0){
			ok = false;
		}
	}
	if (!ok){
		cout << 0 << "\n";
		return 0;
	}

	ll ans = 1;
	ll prev = 1;
	for (int ii = 0; ii <= maxD; ++ii){
		if (D[ii] == 0){
			ans = 0;
			break;
		} else {
			ans = (ans * modpow(prev, D[ii], MOD)) % MOD;
			prev = D[ii];
		}
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 7296
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
	int f;char c;
	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
	static char q[64];int cnt=0;
	if(!x)pc('0');if(x<0)pc('-'),x=-x;
	while(x)q[cnt++]=x%10+'0',x/=10;
	while(cnt--)pc(q[cnt]);
}
const int mod=998244353,maxn=200005;
int mo(const int x){
	return x>=mod?x-mod:x;
}
int V[maxn][10],_[maxn];
struct Value{
	int val,len;
	Value(int val=0,int len=0):
		val(val),len(len){}
	void set(int o){
		val=V[len][o];
	}
	Value operator + (const Value o){
		return Value(mo(1ll*val*_[o.len]%mod+o.val),len+o.len);
	}
}tr[maxn*4];
int tag[maxn*4];
void push(int x,int o){
	tag[x]=o;tr[x].set(o);
}
void pushdown(int x){
	if(tag[x]==-1)return;
	push(x<<1,tag[x]);
	push(x<<1|1,tag[x]);
	tag[x]=-1;
}
void pushup(int x){
	tr[x]=tr[x<<1]+tr[x<<1|1];
}
void build(int x,int l,int r){
	tr[x].len=r-l+1;tr[x].set(1);tag[x]=-1;
	if(l==r)return;int mid=(l+r)>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
}
void change(int x,int l,int r,int L,int R,int o){
	if(L<=l&&r<=R)return push(x,o);
	int mid=(l+r)>>1;pushdown(x);
	if(L<=mid)change(x<<1,l,mid,L,R,o);
	if(R>mid)change(x<<1|1,mid+1,r,L,R,o);
	return pushup(x);
}
int main(){
	int n,q;read(n),read(q);
	_[0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=9;++j){
			V[i][j]=mo(1ll*V[i-1][j]*10%mod+j);
		}
		_[i]=1ll*_[i-1]*10%mod;
	}
	build(1,1,n);
	while(q--){
		int L,R,d;
		read(L),read(R),read(d);
		change(1,1,n,L,R,d);
		write(tr[1].val),pc('\n');
	}
	return 0;
}


Measured memory_bytes: 20496
#include <cstdio>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define SIZE 100333
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;

ll s,c,ret;

int main () {
	scanf("%lld%lld",&s,&c);
	ll a = c / 2;
	ll delta = min(a,s);
	ret = delta;
	c -= 2*delta, s -= delta;
	ret += c/4;
	printf("%lld\n",ret);
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append(a[i])
    b.append(a[i]+1)
    b.append(a[i]-1)
import heapq
cnt=0
c=1000000
d=0
ans=[]
heapq.heapify(b)
#print(b)
while len(b)>0:
    d=heapq.heappop(b)
    if c==1000000:
        c=d
        cnt+=1
    elif c!=d:
        ans.append(cnt)
        cnt=1
        c=d
    else:
        cnt+=1
print(max(ans))



Measured memory_bytes: 17892
/****************************>>>>HEADFILES<<<<****************************/
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
using namespace std;
/****************************>>>>>DEFINE<<<<<*****************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define FIN             freopen("input.txt","r",stdin)
#define rep(i,a,b)      for(int i = a;i <= b;i++)
#define MP(a,b)         make_pair(a,b)
#define PB(a)           push_back(a)
#define fst             first
#define snd             second
/****************************>>>>>>DEBUG<<<<<<****************************/
#define out(x)          cout<<x<<"  ";
/****************************>>>>SEPARATOR<<<<****************************/
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n,l,r;
    cin>>n>>l>>r;
    cout<<max(0ll,(n-1)*(r-l)+l-r+1)<<endl;
}
/*
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "YES" << endl
#define pyes cout << "Yes" << endl
#define POK cout << "OK" << endl
#define PNO cout << "NO" << endl
#define pno cout << "No" << endl
#define PNG cout << "NG" << endl
#define ret return 0

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>


signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  string s; cin >> s;
  int ssize = SIZE(s);
  int zero=0, one = 0;
  for(char i : s){
      zero += i=='0';
      one += i=='1';
  }
  cout << min(one,zero)*2 << endl;
  ret;
}


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

#define FOR(i,a,b)  for(ll (i)=a;(i)<(b);++(i))
#define RFOR(i,a,b) for(ll (i)=a;(i)>=(b);--(i))
#define REP(i,n)    FOR(i,0,n)
#define RREP(i,n)   RFOR(i,n,0)
#define ALL(v)      (v).begin(),(v).end()
#define BIT(n)      (1LL<<(n))
#define IN(x,l,r)   ((l)<=(x)&&(x)<=(r))
#define LEN(s)      (string(s)).length()
#define NPOS        string::npos
#define SHOW(x)     cout<<#x<<" = "<<x<<endl
#define SORT(v)     sort(ALL(v))
#define SZ(v)       (ll)(v).size()
#define UNIQ(v)     SORT(v);(v).erase(unique(ALL(v)),(v).end())
#define PERM(v)     for(bool p=1;p;p=next_permutation(ALL(v)))
#define PQ(T)       priority_queue<T,vector<T>,greater<T>>

template<class T>string join(const vector<T>& v,string d=" ")
{stringstream s;REP(i,SZ(v))s<<d<<v[i];return s.str().substr(LEN(d));}

template<class T>ostream& operator<<(ostream& s,const vector<T>& v)
{s<<"{";if(SZ(v))s<<join(v,", ");s<<"}";return s;}

template<class T>bool contain(const string& s,const T& v)
{return s.find(v)!=NPOS;}

template<class T,class U>string& replace(string& s,const T& f,const U& t)
{for(auto p=s.find(f);p!=NPOS;p=s.find(f,p+LEN(t)))s.replace(p,LEN(f),t);}

const ll INF = 1e15;
const ll MOD = 1e9+7;
const double EPS = 1e-10;

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

int main() {
    ll N; cin >> N;
    cout <<  N * (N + 1) / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
//
//AtCoder Beginner Contest 160
//D
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>
#include <bitset>
#include <numeric>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

const double PI = 3.14159265358979323846;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    int n, x, y;
    cin >> n >> x >> y;
    x--;y--;

    vector<int> ans(n, 0);
    REP(i, n){
        FOR(j, i+1, n-1){
            int d = min(j - i, abs(x - i) + 1 + abs(y - j));
            ans[d-1]++;
        }
    }
    REP(i,n-1) cout << ans[i] << endl;

    return 0;
}


Measured memory_bytes: 3600
#include "bits/stdc++.h"
using namespace std;
int Degree[5];

int main(){
    int a , b , i;
    
    for( i = 1 ; i <= 3 ; ++i ){
        scanf( "%d%d" , &a , &b );
        ++Degree[a];
        ++Degree[b];
    }

    int j , k;

    for( i = 1 ; i <= 4 ; ++i ){
        for( j = i + 1 ; j <= 4 ; ++j ){
            if( Degree[i] == 1 && Degree[j] == 1 ){
                for( k = 1 ; k <= 4 ; ++k ){
                    if( k != i && k != j ){
                        if( Degree[k] != 2 ) break;
                    }
                }

                if( k == 5 ){
                    puts( "YES" );
                    return 0;
                }
            }
        }
    }

    puts( "NO" );
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iomanip>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<stack>

#define int long long
#define all(x) x.begin(), x.end()
#define forn(i, x) for(int i = i; i < x; ++i)

using namespace std;

int INF = 1e16 + 7;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& a : a) cin >> a;
    int s = 0;
    int mod = 1e9 + 7;
    for (auto a : a) {
        s += a;
        s %= mod;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        s -= a[i];
        if (s < 0) s += mod;
        ans += a[i] * s;
        ans %= mod;
    }
    cout << ans;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cout << setprecision(10) << fixed;

    solve();

    return 0;
}

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

const int MAX_N=110,MAX_C=21,MAX_P=55,INF=1e9;

int N,M,C,S,G;
int dp[MAX_C][MAX_N][MAX_N],P[MAX_C],sum[MAX_C][MAX_P];
vector<int> Q[MAX_C],R[MAX_C];

int calc(int t,int d){
    int pos=upper_bound(Q[t].begin(),Q[t].end(),d)-Q[t].begin();
    int res=sum[t][--pos];
    res+=R[t][pos]*(d-Q[t][pos]);
    return res;
}

void solve(){
    for (int t=0;t<C;++t){
        for (int i=0;i<N;++i){
            for (int j=0;j<N;++j){
                dp[t][i][j]=(i==j?0:INF);
            }
        }
    }
    for (int i=0;i<M;++i){
        int x,y,d,c; cin >> x >> y >> d >> c; --x,--y,--c;
        dp[c][x][y]=dp[c][y][x]=min(dp[c][x][y],d);
    }
    for (int i=0;i<C;++i) cin >> P[i];
    for (int i=0;i<C;++i){
        Q[i].clear(); R[i].clear();
        Q[i].emplace_back(0);
        for (int j=0;j<P[i]-1;++j){
            int q; cin >> q;
            Q[i].emplace_back(q);
        }
        for (int j=0;j<P[i];++j){
            int r; cin >> r;
            R[i].emplace_back(r);
        }
        sum[i][0]=0;
        for (int j=0;j<P[i]-1;++j){
            sum[i][j+1]=sum[i][j]+R[i][j]*(Q[i][j+1]-Q[i][j]);
        }
    }
    for (int t=0;t<C;++t){
        for (int k=0;k<N;++k){
            for (int i=0;i<N;++i){
                for (int j=0;j<N;++j){
                    dp[t][i][j]=min(dp[t][i][j],dp[t][i][k]+dp[t][k][j]);
                }
            }
        }
        for (int i=0;i<N;++i){
            for (int j=0;j<N;++j){
                if (dp[t][i][j]==INF) continue;
                dp[t][i][j]=calc(t,dp[t][i][j]);
            }
        }
    }
    for (int t=0;t<C;++t){
        for (int i=0;i<N;++i){
            for (int j=0;j<N;++j){
                dp[0][i][j]=min(dp[0][i][j],dp[t][i][j]);
            }
        }
    }
    for (int k=0;k<N;++k){
        for (int i=0;i<N;++i){
            for (int j=0;j<N;++j){
                dp[0][i][j]=min(dp[0][i][j],dp[0][i][k]+dp[0][k][j]);
            }
        }
    }
    int ans=dp[0][--S][--G];
    cout << (ans==INF?-1:ans) << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> N >> M >> C >> S >> G,N){
        solve();
    }
}


Measured memory_bytes: 4104
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;cin>>n>>m;
  int a=m/n;
  int ans;
  for(int i=a;i>=1;i--){
    int b=m-i*n;
    if(b%i==0){
      ans=i;
      break;
    }
  }
  cout<<ans<<endl;
}

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

int main()
{
	ll n;
	while(cin >> n){
		for(int i = sqrt(n); i > 0; i--){
			if(n % i == 0){
				cout << (n / i) + i - 2 << endl;
				break;
			}
		}
	}
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<long long, long long >
#define ll long long
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define maxn 10000000000000
#define endl '\n'
#define trace(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
int mod(int x,int y)
{
  int s;
  s = abs(x)/y;
  if(x<0)s--;
  return x-y*s;
}
int dir8[2][8] = {{1,-1,0,0,1,-1,1,-1},{0,0,1,-1,1,-1,-1,1}};
int dir4[2][4] = {{1,-1,0,0},{0,0,1,-1}};
ll m,n,row,col;
ll memo[100006];
ll ara[100006];
ll dp(int i)
{
  if(i == n-1)return 0;
  if(memo[i]!=-1)return memo[i];
  ll p1=maxn,p2=maxn;
  if(i+1 < n)p1 = dp(i+1) + abs(ara[i]-ara[i+1]);
  if(i+2 < n)p2 = dp(i+2) + abs(ara[i] - ara[i+2]);
  memo[i] = min(p1,p2);
  return min(p1,p2);
}
void solve()
{
  scanf("%lld",&n);
  for(int w=0;w<n;w++)scanf("%lld",&ara[w]);
  ll ans = dp(0);
  printf("%lld\n",ans);
}
void test()
{
  int t;
  //scanf("%d",&t);
  t=1;
  for(int test=1;test<=t;test++)
  {
    memset(memo,-1,sizeof memo);
    solve();
  }
}
int main()
{
  test();
  return 0;
}


Measured memory_bytes: 6528
#include <iostream> 
using namespace std; 
int main() {
  int a, b, c, d; 
  cin >> a >> b >> c >> d; 
  bool qui = true; 
  while ((a > 0) && (c >0) ) {
    if (qui == true) {
      c-= b; 
      qui = false; 
    }
    else {
      a-= d; 
      qui = true; 
    }
  }
  if (a<= 0) 
    cout << "No"; 
  else
    cout << "Yes"; 
  return 0; 
}

Measured memory_bytes: 3632
/**
 *  Kaiwen Zhou,
 *  CUHK
**/
#include <bits/stdc++.h>
using namespace std;
#define INS ios::sync_with_stdio(false);cin.tie(0)
typedef long long LINT;
#define INF 1000000000000

int main(void) {
    INS;
    int N;
    cin >> N;
    double dp[N + 1][N + 1];
    double p_1;
    cin >> p_1;
    dp[1][0] = 1.0 - p_1;
    dp[1][1] = p_1;
    for(int i = 2; i <= N; i ++) {
        double p;
        cin >> p;
        for(int j = 0; j <= i; j ++) {
            double temp = 0;
            if(i - 1 >= j)
                temp += (1.0 - p) * dp[i - 1][j];
            if(j > 0)
                temp += p * dp[i - 1][j - 1];
            dp[i][j] = temp;
        }
    }
    double ans = 0;
    for(int i = N; i >= N / 2 + 1; i --)
        ans += dp[N][i];
    cout.precision(10);
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 70016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll n,k,ans,cnt,p[51],sum[51];
void dep(ll now){
	if(cnt>=k){
		return;
	}
	if(now==0){
		ans++;
		cnt++;
		return;
	}
	cnt++;
	if(cnt+sum[now-1]<=k){
		cnt+=sum[now-1];
		ans+=p[now-1];
	}
	else{
	dep(now-1);
	}
	if(cnt>=k){
		return;
	}	
	ans++;cnt++;
	if(cnt>=k){
		return;
	}
	if(cnt+sum[now-1]<=k){
		cnt+=sum[now-1];
		ans+=p[now-1];
	}
	else{
	dep(now-1);
	}
	if(cnt>=k){
		return;
	}		
	cnt++;
}
int main() {
	p[0]=sum[0]=1;
	for(ll i=1;i<51;i++){
		p[i]=2*p[i-1]+1;
		sum[i]=2*sum[i-1]+3;
	}
	cin>>n>>k;
	dep(n);
//	cout <<cnt<<endl;
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
    using namespace std;
 
    int main(){
      int h,w;
      cin >> h >> w;
      char c[h][w];
      rep(i,h){
       rep(j,w){
        cin >> c[i][j]; 
       }
      }
      int d[5]={0,-1,0,1,0};
      bool bigflag=true;
      rep(i,h){
       rep(j,w){
        bool flag=false;
         if(c[i][j]=='.')flag=true;
         rep(k,4){
           int x=i+d[k];
           int y=j+d[k+1];
          if(0<=x && x<=h-1 && 0<=y && y<=w-1 && c[x][y]=='#'){
           flag=true; 
          }
         }
         if(flag==false){
           bigflag=false;
         }
       }
      }
      if(bigflag)cout << "Yes" << endl;
      else cout << "No" << endl;
      return 0;}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	long long x,money=100,year=0;
	printf("");
	scanf("%lld",&x);
	while(1){
		money=money*1.01;
		year++;
		if(x<=money){
			break;
		}
	}
	printf("%lld",year);
	return 0;
}


Measured memory_bytes: 2152
A,B,C,K = input().split()
A = int(A)
B = int(B)
C = int(C)
K = int(K)

output = 0

while True:
    if K == 0:
        break
    if A > 0:
        if K >= A:
            output = 1*A
            K -= A
            A = 0
            continue
        else:
            output = 1*K
            break
    if B > 0:
        if K >= B:
            K -= B
            B = 0
            continue
        else:
            break
    output -= 1*K
    K = 0

print(output)


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    cout << 0 << endl;
    string status;
    cin >> status;
    bool zero_is_male;
    if (status == "Vacant" ) {
        return 0;
    } else if (status == "Male") {
        zero_is_male = true;
    } else {
        zero_is_male = false;
    }

    int left = 0, right = n;
    while (true) {
        int mid = (left + right) / 2;
        cout << mid << endl;
        string status;
        cin >> status;
        if (status == "Vacant") {
            return 0;
        } else if (status == "Male") {
            if ((zero_is_male == true and mid % 2 == 0)
                    or (zero_is_male == false and mid % 2 == 1)) {
                left = mid;
            } else {
                right = mid;
            }
        } else {
            if ((zero_is_male == true and mid % 2 == 1)
                    or (zero_is_male == false and mid % 2 == 0)) {
                left = mid;
            } else {
                right = mid;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 852
#include <iostream>
#include <vector>
#include <map>

using namespace std;

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(0);
    ll n, MOD;
    cin >> n >> MOD;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    map<int, ll> ile;
    ll s = 0;
    ll odp = 0;
    for (int i = 0; i < n; ++i)
    {
        s = (s + a[i]) % MOD;
        if (ile.find(s) != ile.end())
            odp += ile[s];
        if (s % MOD == 0)
            ++odp;
        if (ile.find(s) == ile.end())
            ile[s] = 1;
        else
            ++ile[s];
    }
    cout << odp;
    return 0;
}


Measured memory_bytes: 4992
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

bool check(ll n,int k){
    while(n>=k){
        if(n%k==0) n/=k;
        else if(n%k==1) return 1;
        else return 0;
    }
    return n==1;
}
signed main(){
    FastIO;
    ll n;
    cin>>n;
    if(n==2) return cout<<1,0;
    int ans=0;
    rep(i,2,sqrt(n)){
        if(check(n,i) and n%i==0) ans++;
    }
    n--;
//    cout<<ans<<"::";
    rep(i,2,sqrt(n)){
        if(n%i==0){
            ans+=2;
            if(1ll*i*i==n) ans--;
        }
    }
    cout<<ans+2;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int nmax = 100005;
const ll mod = 1e4;
const ll inf = 1e9;
const ld EPS = 1e-2;
const ld PI = acos(-1.0);
const int kor = 320;
vector<vector<int> > g;
int hh[2005];
int l;
int up[2005][12];
int d[2005][2005];
int tin[2005];
int tout[2005];
int am[2005];
int tt;
void dfs(int v, int p, int h){
    up[v][0] = p;
    hh[v] = h;
    tin[v] = tt++;
    for(int i = 1; i < 12; ++i){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int j = 0; j < g[v].size(); ++j){
        int to = g[v][j];
        if (to != p) dfs(to, v, h + 1);
    }
    tout[v] = tt++;
}
int par(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b){
    if (par(a, b)) return a;
    if (par(b, a)) return b;
    for(int i = 11; i >= 0; --i){
        if (!par(up[a][i], b)) a = up[a][i];
    }
    return up[a][0];
}
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    int k;
    cin >> n;
    cin >> k;
    g.assign(n, vector<int>());
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0, 0, 0);
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            int lc = lca(i, j);
            d[i][j] = hh[i] + hh[j] - hh[lc] - hh[lc];
            d[j][i] = d[i][j];
        }
    }
    set<pair<pair<int, int>, int> > s;
    for(int i = 0; i < n; ++i){
        int tmp = 0;
        for(int j = 0; j < n; ++j){
            if (d[i][j] > k) tmp++;
        }
        s.insert({{tmp, hh[i]}, i});
        am[i] = tmp;
    }
    int cnt = 0;
    while(1){
        auto x = s.end();
        x--;
        pair<pair<int, int>, int> v = *x;
        s.erase(x);
        if (!v.first.first) break;
        for(int i = 0; i < n; ++i){
            if (d[v.second][i] > k){
                s.erase({{am[i], hh[i]}, i});
                am[i]--;
                s.insert({{am[i], hh[i]}, i});
                d[v.second][i] = -1;
                d[i][v.second] = -1;
            }
        }
        am[v.second] = 0;
        cnt++;
    }
    cout << cnt << '\n';
    return 0;
}


Measured memory_bytes: 16384
#D
n=int(input())
data=[]
for i in range(n):
    a,b=map(int,input().split())
    data.append([b,a])
data.sort()
time=0
for i in range(n):
    time+=data[i][1]
    if time>data[i][0]:
        print("No")
        break
else:
    print("Yes")

Measured memory_bytes: 76248
import java.io.*;
import java.util.*;

public class Main {
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);

	public void run() {
		while (true) {
			int n = in.nextInt(), p = in.nextInt();
			if (n == 0 && p == 0) break;
			
			int[] a = new int[n];
			int cur = 0;
			int rest = p;
			
			while (a[cur] != p) {
				if (rest != 0) {
					a[cur]++;
					rest--;
				} else {
					rest += a[cur];
					a[cur] = 0;
				}
				cur = (cur + 1) % n;
			}
			System.out.println(cur);
		}
		
		out.close();
	}

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

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

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

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}

Measured memory_bytes: 17072
N, x = map(int, input().split())
a = list(map(int, input().split()))
A = a
A.extend(a)
N *= 2

# N:  処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 2**31-1
seg_min = [INF]*(2*N0)


def update(index, value):
    index += N0 - 1
    seg_min[index] = value
    while index > 0:
        index = (index - 1) // 2
        seg_min[index] = min(seg_min[index * 2 + 1], seg_min[index * 2 + 2])


def query(first, last):
    first += N0 - 1
    last += N0 - 1
    ret = INF
    while first <= last:
        if not first & 1:
            ret = min(ret, seg_min[first])
        if last & 1:
            ret = min(ret, seg_min[last])
        first = first // 2
        last = last // 2 - 1
    return ret


for i in range(N):
    update(i, A[i])

ans_min = float('inf')
for x_use in range(N//2):
    ans = x * x_use
    for i in range(N//2):
        ans += query(i, i+x_use)
    ans_min = min(ans, ans_min)

print(ans_min)


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

ll n,a[100100],sum[200100];
int main(){
  scanf("%lld",&n);
  for(int i=0;i<n;i++)scanf("%lld",&a[i]);
  for(int i=0;i<2*n;i++)sum[i+1] = sum[i] + a[i%n];

  int l = 0, r = 1;
  ll ans = 0, third = sum[n]/3;
  while(l<n){
    while(sum[r]-sum[l] <= third)r++;
    r--;
    ll fs = sum[r]-sum[l], half = (sum[n] - fs)/2;
    int pos = lower_bound(sum+r, sum+2*n, half + sum[r]) - sum;

    ll rem = min(sum[pos]-sum[r], sum[l+n]-sum[pos]);
    if(pos>0)rem = max(rem, min(sum[pos-1]-sum[r], sum[l+n]-sum[pos-1]));

    ans = max(ans, min(fs,rem));
    l++;
  }

  printf("%lld\n",ans);
}

Measured memory_bytes: 3536
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int N, K; cin >> N >> K; 
	int P[5010] = {}; 
	long long C[5010] = {}; 
	for(int i = 0; i < N; i++){
		cin >> P[i]; P[i] --; 
	}
	for(int i = 0; i < N; i++) cin >> C[i];
	long long ans = -1145141919; 
	long long A[5010][5010] = {}; // iがj回動く
	int period[5010] = {}; 
	for(int i = 0; i < N; i++){
		int now = i; 
		for(int j = 1; j <= N+5; j++){
			now = P[now]; A[i][j] = A[i][j-1] + C[now]; 
			if(now == i){
				period[i] = j; break; 
			}
		}
	}
	for(int i = 0; i < N; i++){
		long long sum = A[i][period[i]]; 
		for(int j = 1; j <= period[i]; j++){
			long long tmp1 = -1145141919; 
			long long tmp2 = -1145141919; 
			if(K >= j) tmp1 = A[i][j]; 
			if(sum > 0 && K >= j){
				long long num = (long long) (K - j) / period[i]; 
				tmp2 = A[i][j] + sum * num; 
			}
			ans = max({ans, tmp1, tmp2}); 
		}
	}
	cout << ans << "\n"; 
}

Measured memory_bytes: 199816
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
using PL = pair<ll, ll> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18
int main() {
    vector<int> di = {-1, 0, 1, 0} ;
    vector<int> dj = {0, -1, 0, 1} ;
    int h, w, k ;
    cin >> h >> w >> k ; 
    int si, sj, ti, tj ;
    cin >> si >> sj >> ti >> tj ;
    --si; --sj; --ti; --tj ;
    vector<string> g(h) ;
    rep(i, h) cin >> g[i] ;
    auto toid = [&](int i, int j, int v){
        return (i*w+j)*4 + v ;
    };
    vector<ll> dist(h*w*4, INF) ;
    priority_queue<PL, vector<PL>, greater<PL>> que ;
    auto push = [&](int i , int j, int v , ll x){
        int id = toid(i,j,v) ;
        if(dist[id] <= x) return ;
        dist[id] = x ;
        que.emplace(x, id) ;
    };
    auto modCeil = [&](ll x){
        return (x + k - 1)/k * k ;
    };
    rep(v, 4) push(si, sj, v, 0) ;
    while(!que.empty()){
        ll d = que.top().first ;
        ll id = que.top().second ;
        que.pop() ;
        if(dist[id] != d) continue ;
        int i = id/w/4 ;
        int j = id/4%w ;
        int v = id%4 ;
        rep(nv, 4){
            push(i, j, nv, modCeil(d)) ;
        }
        {
            int ni = i + di[v];
            int nj = j +  dj[v] ;
            if(0 <= ni && ni < h && 0 <= nj && nj < w){
                if(g[ni][nj] == '.'){
                    push(ni, nj, v, d + 1) ;
                }
            }
        }
    }
    ll ans = INF ;
    rep(v, 4) ans = min(ans, dist[toid(ti,tj,v)]) ;
    if(ans == INF){
        cout << -1 << endl ;
        return 0 ;
    }
    ans = modCeil(ans)/k ;
    cout << ans << endl ;
    return 0 ;  
} 

Measured memory_bytes: 44152