akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int i;
    if(s.size()%2!=0){
        cout << "No" <<endl;
        return 0;
    }
    for(i=0;i<=s.size()-1;i++){
        if(i%2==0){
            if(s[i]!='h'){
                cout << "No" <<endl;
                return 0;
            }
        }
        else {
            if(s[i]!='i'){
                cout << "No" <<endl;
                return 0;
            }
        }
    }
    cout << "Yes" <<endl;
    return 0;
}

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

using namespace std;

int main(){ 
	cin.tie(0);
	ios::sync_with_stdio(0);
	long long k,a,b;
	cin>>k>>a>>b;
	if(b-a<=1){ 
		cout<<k+1;
		return 0;
	} 
	if(k+1<a+2){ 
		cout<<k+1;
		return 0;
	} 
	k++;
	k-=(a+2);
	cout<<b+(k/2)*(b-a)+k%2;

	return 0;
}



Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

X = sorted([a for a in A if a > 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))

if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
    ans = 1
    if K % 2 == 1:
        ans *= X.pop()
        K -= 1

    XX = [(x1 * x2) for x1, x2 in zip(*[iter(X[::-1])] * 2)]
    YY = [(y1 * y2) for y1, y2 in zip(*[iter(Y[::-1])] * 2)]
    ZZ = sorted(XX + YY)

    for i in range(K // 2):
        ans *= ZZ.pop()
        ans %= MOD

    print(ans)

elif 0 in A:
    print(0)

else:
    ans = 1
    Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
    for i in range(K):
        ans *= Z.pop()
        ans %= MOD
    print(ans)


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

typedef long long int ll;

//const ll INF=(ll)1e18;
const int INF=(1<<21);

class UnionFindTree{
  public:
    vector<int> rank,p;

    UnionFindTree() {}

    UnionFindTree(int size){
      rank.assign(size, 0);
      p.assign(size, 0);
      REP(i,size)makeSet(i);
    }

    void makeSet(int x){
      p[x] = x;
      rank[x] = 0;
    }

    bool same(int x, int y){
      return findSet(x) == findSet(y);
    }

    void unite(int x, int y){
      if(findSet(x) == findSet(y))return;

      x = findSet(x);
      y = findSet(y);

      if(rank[x] > rank[y]){
        p[y] = x;
      }else{
        p[x] = y;
        if(rank[x] == rank[y]){
          rank[y]++;
        }
      }

    }

    int findSet(int x){
      if(x != p[x]){
        p[x] = findSet(p[x]);
      }
      return p[x];
    }

    void print(){
      REP(i,p.size()){
        cout << p[i] << " ";
      }
      cout << endl;
      REP(i,p.size()){
        cout << rank[i] << " ";
      }
      cout << endl;

    }

};

int main(){
  int n,q;

  cin >> n >> q;

  UnionFindTree uft(n);

  REP(i,q){
    int com, x, y;

    cin >> com >> x >> y;
    

    if(com==0){
      uft.unite(x,y);
    }else{
      cout << (uft.same(x,y) ?  1 : 0) << endl;
    }

  }


}




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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

typedef long long ll;
#define INF 1e9;
int N, A, B, C;

int dfs(int cur, int a, int b, int c, vector<int>l){
  if(cur == N){
    if(a==0 || b==0 || c==0){
      return INF;
    }
    else{
      return abs(a -A) + abs(b-B) + abs(c-C)-30;
    }
  }

  int ret0 = dfs(cur+1, a, b, c, l);
  int ret1 = dfs(cur+1, a+l[cur], b,c,l)+10;
  int ret2 = dfs(cur+1, a, b+l[cur], c,l)+10;
  int ret3 = dfs(cur+1, a, b,c+l[cur],l)+10;

  return min(ret0, min(ret1,min(ret2,ret3)));
}

int main(){
  cin >> N >> A >> B >> C;
  vector<int> l(N);
  REP(i, N){
    cin >> l[i];
  }

  cout << dfs(0, 0, 0, 0, l) << endl;
  return 0;
}

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

 long long diff( long long a,  long long b,  long long c) {
	
	long long minimum = min(min(a,b), min(b,c));
	long long maxmam = max(max(a, b), max(b, c));

	return maxmam - minimum;
}

int main()
{
	long long H, W;
	long long a, b, c;
	cin >> H >> W;
	long long ans = H*W;
	
	for ( long long i = 1; i < H; i++) {
		a = i * W;
		b = ((H - i) / 2)*W;
		c = ((H - i) - (H - i) / 2)*W;
		ans = min(ans,diff(a, b, c));

		b = (H - i)*(W / 2);
		c = (H - i)*(W - W / 2);
		ans = min(ans,diff(a, b, c));
	}

	swap(H, W);
	for (long long  i = 1; i < H; i++) {
		a = i * W;
		b = ((H - i) / 2)*W;
		c = ((H - i) - (H - i) / 2)*W;
		ans = min(ans, diff(a, b, c));

		b = (H - i)*(W / 2);
		c = (H - i)*(W - W / 2);
		ans = min(ans,diff(a, b, c));
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<functional>
#include<string.h>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<queue>
#include<deque>
#include<string>
#include<stack>
using namespace std;

map<int, int>m;
signed main() {
	int a; cin >> a;
	for (int i = 0; i < a; i++) {
		int b; cin >> b;
		m[b]++;
	}
	int b; cin >> b;
	for (int c = 0; c < b; c++) {
		int d; cin >> d;
		if (m[d]) {
			m[d]--;
		}
		else {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
int main(){
    int a, b ,c;
    cin >> a >> b >> c;
    if(a == b && b == c){
        cout << "No" << endl;
    }
    else if(c == b || a == b  || c == a){
        cout <<"Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0;i<(int)(n);i++)
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
const int inf=1e9+1;
template <class T>
void print(T x){cout << x << '\n';}



void solve(long long a, long long b){
    if((a*b)%2==0)print("Even");
    else print("Odd");

}

int main(){
  long long a;
  scanf("%lld",&a);
  long long b;
  scanf("%lld",&b);
  solve(a, b);
  return 0;
}


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

int main(){
  ll a,b,c;
  cin >> a >> b >> c;
  ll ans = 0;
  while( a%2 == 0 && b%2 == 0 && c%2 == 0 ){
    ll pa = a,pb = b,pc = c;
    a = pb/2 + pc/2;
    b = pa/2 + pc/2;
    c = pa/2 + pb/2;
    ans++;
    if( ans == 1000000 ){
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
  return 0;
}


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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    string S, T; cin >> S >> T;
    T += T;
    int lenS = S.length();
    for(int i = 0; i < lenS; i++){
        bool ok = true;
        for(int j = i; j < lenS+i; j++){
            if(T[j] != S[j-i]) ok = false;
        }
        if(ok){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
h, w = map(int, input().split())
s = [input() for _ in range(h)]
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            flag = 0
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if nx < 0 or w <= nx:
                    continue
                if ny < 0 or h <= ny:
                    continue
                if s[ny][nx] == '#':
                    flag = 1
            if flag == 0:
                print('No')
                exit()
else:
    print('Yes')


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

using namespace std;

int main() {
	char c[3][3];
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> c[i][j];
		}
	}

	cout << c[0][0] << c[1][1] << c[2][2] << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define V vector<int>
#define VLL vector<long long>
#define VV vector<vector<int>>
#define be(x) begin(x),end(x)
#define For(a) for(int i=0;i<a;i++)
#define For(a,b) for(int i=a;i<b;i++)
#define len(a) a.size()
#define pb push_back 
#define mp make_pair
#define Um unordered_map
#define S unordered_set

void solve();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    #ifndef ONLINE_JUDGE 
        freopen("input.txt", "r", stdin); 
        freopen("output.txt", "w", stdout); 
    #endif 
    
    /*int t;
    cin>>t;
    while(t--)
    {
        //solve();
        //solve();cout<<"\n";
        //cout<<"Case #"<<tc<<": "<<solve()<<endl;
        cout<<solve()<<endl;
    }*/
	solve();cout<<"\n";
return 0;
}
void solve()
{
   ll d,s,t;
   cin>>d>>t>>s;
   double dd=(double)d/s;
    if(dd<=t)
		cout<<"Yes";
	else cout<<"No";
}

Measured memory_bytes: 3648
import sys
input = sys.stdin.readline

n, k = [int(item) for item in input().split()]
if n - 2 * k + 1 < 0:
    print(-1)
    exit()
for i in range((n + 1) // 2):
    a = k + 2*i
    b = k + n + ((n+1) // 2) - 1 - i
    c = k + 2 * n + i
    print(a, b, c)
for i in range(n // 2):
    a = k + 1 + 2*i
    b = k + 2*n - 1 - i
    c = k + 2*n + ((n+1) // 2) + i
    print(a, b, c)

Measured memory_bytes: 5288
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long int LL;
const LL MAX=2e9;
LL pos[1005][2];

void check(int a,int t){
	int i,j,k;
	t=1<<t;
	if(abs(pos[a][0])>abs(pos[a][1])){
		if(pos[a][0]>0){
			cout<<'R';
			pos[a][0]-=t;
		}else{
			cout<<'L';
			pos[a][0]+=t;
		}
	}else{
		if(pos[a][1]>0){
			cout<<'U';
			pos[a][1]-=t;
		}else{
			cout<<'D';
			pos[a][1]+=t;
		}
	}
}

int main(){
	int n;
	int i,j,k;
	LL a,b,c,d;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>pos[i][0]>>pos[i][1];
	}
	a=(pos[0][0]+pos[0][1]+MAX)%2;
	for(i=0;i<n;i++){
		b=(pos[i][0]+pos[i][1]+MAX)%2;
		if(a!=b){
			cout<<-1<<endl;
			return 0;
		}
	}
	cout<<(32-a)<<endl;
	for(i=30;i>0;i--){
		cout<<(1<<i)<<" ";
	}
	if(a==1)cout<<1<<endl;
	else cout<<1<<" "<<1<<endl;
	
	for(i=0;i<n;i++){
		for(j=30;j>=0;j--){
			check(i,j);
		}
		if(a==0)check(i,0);
		cout<<endl;
	}
	
	return 0;
	
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);
//cin.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll inf=1000000000000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(int i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll gya[2000100];
ll kai[2000100];
ll beki(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k%2==1){
            ret*=now;
            ret%=mod3;
        }
        now*=now;
        now%=mod3;
        k/=2;
    }
    return ret;
}
ll gyaku(ll n){
    return beki(n,mod3-2);
}
void nckinit(ll n){
    kai[0]=1;
    kai[1]=1;
    for(int i=2;i<=n;i++){
        kai[i]=kai[i-1]*i;
        kai[i]%=mod3;
    }
    gya[n]=gyaku(kai[n]);
    for(int i=n-1;i>=1;i--){
        gya[i]=gya[i+1]*(i+1);
        gya[i]%=mod3;
    }
    gya[0]=1;
}
ll nck(ll n,ll k){
    if(k<0)return 0;
    if(k==0||n==k)return 1;
    ll ret=kai[n];
    ret*=gya[n-k];
    ret%=mod3;
    ret*=gya[k];
    ret%=mod3;
    return ret;
}
ll npk(ll n,ll k){
    if(k<0)return 0;
    if(k==0)return 1;
    ll ret=kai[n];
    ret*=gya[n-k];
    ret%=mod3;
    return ret;
}
int main(){
    int q;cin>>q;
    nckinit(1000002);
    //rep(i,0,10)cout<<kai[i]<<" ";
    rep(i,0,q){
        ll x,d,n;cin>>x>>d>>n;
        if(x==0){
            cout<<0<<endl;
            continue;
        }
        if(d==0){
            cout<<beki(x,n)<<endl;
            continue;
        }
        ll y=x*gyaku(d);
        y%=mod3;
        if(n-1+y>=1000003){
            cout<<0<<endl;
            continue;
        }
        ll a=kai[n-1+y];
        ll b=kai[y-1];
        a*=gyaku(b);
        ll cc=beki(d,n);
        a%=mod3;
        a*=cc;
        a%=mod3;
        cout<<a<<endl;
    }
}


Measured memory_bytes: 19328
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int[][] map;
	static int a, b;
	static int route;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while (!(line = br.readLine()).equals("0 0")) {
			a = Integer.parseInt(line.substring(0, line.indexOf(' ')));
			b = Integer.parseInt(line.substring(line.indexOf(' ') + 1));
			map = new int[a][b];
			route = 0;

			int a1, b1, n = Integer.parseInt(br.readLine());
			for (int i = 0; i < n; i++) {
				line = br.readLine();
				a1 = Integer.parseInt(line.substring(0, line.indexOf(' ')));
				b1 = Integer.parseInt(line.substring(line.indexOf(' ') + 1));
				map[a1 - 1][b1 - 1] = 1;
			}
			go(new int[] { 0, 0 });
			System.out.println(route);
		}

	}

	static void go(int[] p) {
		if (p[0] + 1 == a && p[1] + 1 == b) {
			route++;
			return;
		}
		
		int[] e = east(p);
		int[] n = north(p);
		if (e != null)
			go(e);
		if (n != null)
			go(n);
	}

	static int[] east(int[] p) {
		if (p[0] + 1 < a && map[p[0] + 1][p[1]] != 1)
			return new int[] { p[0] + 1, p[1] };
		else
			return null;

	}

	static int[] north(int[] p) {
		if (p[1] + 1 < b && map[p[0]][p[1] + 1] != 1)
			return new int[] { p[0], p[1] + 1 };
		else
			return null;
	}
}

Measured memory_bytes: 56452
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).unwrap();
    word.trim().to_owned()
}

fn main() {
    let n: usize = get_input().parse().unwrap();
    let mut a:Vec<i64> = get_input().split_whitespace().map(|x| x.parse().unwrap()).collect();
    let mut b:Vec<i64> = get_input().split_whitespace().map(|x| x.parse().unwrap()).collect();

    let mut ans = 0;
    for i in 0..n {
        for j in i..i+2 {
            let m = std::cmp::min(b[i], a[j]);
            ans += m;
            b[i] -= m;
            a[j] -= m;
        }
    }

    println!("{}", ans);
}

Measured memory_bytes: 9972
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>
#include<iomanip>
#include<list>
#include<math.h>
#include<stack>

using namespace std;


int main(int argc, char **argv)
{
	int n;
	stack<int> rail;
	while (cin >> n) {
		if (n != 0) {
			rail.push(n);
		} else {
			cout << rail.top() << endl;
			rail.pop();
		}
	}
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

// Common memset settings
//memset(memo, -1, sizeof memo); // dp memoization with -1
//memset(arr, 0, sizeof arr); //clear array of integers




int main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	int n;

	cin >> n;

	vector <pair <long long, long long>> towns(n);

	long long a,b;

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

		towns[i] = make_pair(a,b);
	}


	long double total_dist = 0;

	double j = 0;

	sort(towns.begin(), towns.end());

	do{
		j++;
		long double dist = 0;

		for(int i =0;i<n-1;i++){
			double x_dist = (towns[i].first - towns[i+1].first);
			double y_dist = (towns[i].second - towns[i+1].second);

			dist += hypot(x_dist, y_dist);

		}

		total_dist += dist;

		
	}while(next_permutation(towns.begin(), towns.end()));
	

	cout << setprecision(9) << total_dist/j;

	return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
#define lpin(a,i,n) for(int i=0;i<n;i++){cin>>a[i];}

int a[1000][1000];
int main(){
  while(1){
    lp(i,1000){
      lp(j,1000){
	a[i][j]=0;
      }
    }
    
    int n;
    cin>>n;
    if(n==0) break;
    int b,d;
    lp(i,n){
      cin>>b;
      lp(j,b){
	cin>>d;
	a[i][d]=1;
      }
    }
    int count=0,ans=0,check;
    int c;
    cin>>c;
    int x[1000];
    lpin(x,i,c);
    lp(i,n){
      check=0;
      lp(j,c){
	if(a[i][x[j]]==1) 1;
	else check=1;
      }
      if(check==0){
	ans=i;
	count++;
      }
    }
    if(count==1) cout<<ans+1<<endl;
    else cout<<"-1"<<endl;
  }
  return 0;
}



Measured memory_bytes: 7004
#include<bits/stdc++.h>
//In wrong answers we believe//
#define db 				double
#define ll 				long long int
#define ld				long long double
//#define int 			long long int
#define ull 			unsigned long long
#define vii 			vector <int>
#define vll 			vector < ll >
#define pii 			pair <int, int>
#define fi 				first
#define se 				second
#define rep(i,a,n)      for(int i=a;i<n;i++)
#define endl 			'\n'
#define mem(a,b) 		memset(a, b, sizeof a)
#define mkp 			make_pair
#define pb 				push_back
#define max3(a,b,c) 	max(a,max(b,c))
#define min3(a,b,c) 	min(a,min(b,c))
#define w(t)            int t; cin>>t; while(t--)
#define all(a)			a.begin(), a.end()
using namespace std;
db pi		 =			2*acos(0.0);
db eps       =			0.000001;
ll mod       =			(1e9+7);   //998244353
const ll INF =			1000000000000000LL;
void print(vector <int> &arr){
    for(int i=0;i<arr.size();i++)
        cout<<arr[i]<<" ";
    
    cout<<endl;
}
void printll(vector <ll> &arr){
    for(int i=0;i<arr.size();i++)
        cout<<arr[i]<<" ";
    
    cout<<endl;
}

ll ncr(ll n, ll r)
{
    r=min(r,n-r);
    ll A[r],i,j,B[r];
    iota(A,A+r,n-r+1);  
    iota(B,B+r,1);     

    ll g;
    for(i=0;i<r;i++)
    for(j=0;j<r;j++)
    {
        if(B[i]==1)
            break;
        g=__gcd(B[i], A[j] );
        A[j]/=g;
        B[i]/=g;
    }
    ll ans=1;
    for(i=0;i<r;i++)
        ans=(ans*A[i]%mod);
    return ans;
}
const int SIZE=100001;
bool judgePermutation(int a[], int n){
    static int used[SIZE+1];
    for(int i = 1; i <= n; i++) used[i] = 0;
    for(int i = 0; i < n; i++) used[a[i]] = 1;
    for(int i = 1; i <= n; i++) {
        if(!used[i]) return 0;
    }
    return 1;
}


int main(){	
//CONDITION && cout << "YES" || cout << "NO"; cout << '\n';
//////////////////////////////////////////////////////////////////////
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cerr.tie(NULL);
//For fast IO
///////////////////////////////////////////////////////////////////// 
//  std::cout.unsetf ( std::ios::floatfield );  // floatfield not set
//  std::cout.precision(10);
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	ll a,b,n;
	cin>>a>>b>>n;
	if(n>=2*b-1) cout<<a-(a/b)<<endl;
	else if(n>=b && n<2*b-1) cout<<a*(b-1)/b<<endl;
	else cout<<(a*n)/b<<endl;
	return 0;
    
    }

Measured memory_bytes: 3600
#define _CRT_SECURE_NO_WARNINGS

/* include ***********************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

/* define *************************/
//for
#define REP(i,n) for(int i=0,i##_len=(int)(n);i<i##_len;i++)
#define REPS(i,n) for(int i=1,i##_len=(int)(n);i<=i##_len;i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define RREPS(i,n) for(int i=(int)(n);i>0;i--)
#define FOR(i,s,n) for(int i=(int)(s),i##_len=(int)(n);i<i##_len;i++)

//printf
#define PRINTD(d) printf("%d\n",(d))
#define PRINTL(d) printf("%lld\n",(d))

//memset
#define m0(s) memset(s,0,sizeof(s))
#define ml(s) memset(s,63,sizeof(s))
#define fill(s,c) memset(s,c,sizeof(s))

#define INF 1e9

typedef long long ll;
int a[200000];
int sum[200000] = { 0 };

int diff[4][2] = {
	{ 0, -1 },
	{ -1, 0 },
	{ 1, 0 },
	{ 0, 1 },
};

int Min(int a, int b) {
	return (a)<(b) ? (a) : (b);
}
int Max(int a, int b) {
	return (a) > (b) ? (a) : (b);
}
void Swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main() {
	int n;
	//*
	scanf("%d", &n);
	REP(i, n) {
		scanf("%d", &a[i]);
	}
	/*/
	n = 2 * 1e5;
	REP(i, n) {
		a[i] = i;
	}
	//*/
	sum[n-1] = a[n-1];
	RREP(i, n - 1) {
		sum[i] += sum[i + 1] + a[i];
	}

	ll cnt = 0;
	int lim = 0;
	REPS(i, n-1) {
		FOR(j,lim, i) {
			/*
			printf("i:%d,j:%d, sum[%d]:%d sum[%d]:%d, a[%d]:%d\n", i, j, j, sum[j], i, sum[i], i, a[i]);
			//*/
			if (((sum[j]-sum[i]) & a[i]) == 0) {
				cnt+=(i-1)-j+1;
				//printf("cnt:%lld, lim:%d\n", cnt, lim);
				break;
			}
			else {
				lim = j+1;
			}
			/*
			printf("cnt:%lld, lim:%d\n", cnt, lim);

			//*/
		}
	}
	PRINTL(cnt+n);
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

ll DP[120][210000];

int main(){
    int N, W;
    cin >> N >> W;
    vector<ll> WL(N);
    vector<ll> V(N);
    REP(i,N){
        ll w, v;
        cin >> w >> v;
        WL[i] = w;
        V[i] = v;
    }

    REP(i,N){
        REP(j,2*W){
            DP[i][j] = -1;
        }
    }

    DP[0][0] = 0;
    REP(i,N){
        ll w = WL[i];
        ll v = V[i];
        REP(j,W){
            if(DP[i][j] == -1) continue;
            chmax(DP[i+1][j+w], DP[i][j]+v);
            chmax(DP[i+1][j], DP[i][j]);
        }
    }

    ll ans = 0;
    REP(i,W+1){
        chmax(ans, DP[N][i]);
    }

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


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

int main(){
  string s;
  cin>>s;
  map <char,int> m;
  int flag = 0;
  for(int i=0;i<s.size();i++){
  	m[s[i]]++;
  }
  
  for(auto it=m.begin();it!=m.end();it++){
  	if(it->second!=2){
    	flag = 1;
      	break;
    }
  }
  
  if(flag==1)
    cout<<"No"<<"\n";
  else{
  	cout<<"Yes"<<"\n";
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define REPS(i,n) for (ll i = 1; i<=(ll)(n); i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.141592653



int main(){
	ll s, w; cin >> s >> w;
	if (s<=w){
		cout << "unsafe" << endl;
	}
	else{
		cout << "safe" << endl;
	}
}

Measured memory_bytes: 3620
// https://atcoder.jp/contests/dp/tasks/
#include <bits/stdc++.h>

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    map<string, int> m;
    string s;
    int maxcount = 0;
    vector<string> ans;

    rep(i, n) {
        cin >> s;
        map<string, int>::iterator it = m.find(s);
        if (it != m.end()) {
            (it->second)++;
            maxcount = max(maxcount, it->second);
        } else {
            m.emplace(s, 1);
            maxcount = max(maxcount, 1);
        }
    }

    for (auto it = m.begin(); it != m.end(); it++) {
        if (it->second == maxcount) {
            ans.push_back(it->first);
        }
    }

    sort(ans.begin(), ans.end());
    for (auto it = ans.begin(); it != ans.end(); it++) {
        cout << *it << endl;
    }

    return 0;
}


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

using namespace std;

int main() {
	string a, b;
	cin >> a >> b;
	if (a > b) {
		cout << ">" << endl;
	}
	else if (a < b) {
		cout << "<" << endl;
	}
	else {
		cout << "=" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
using namespace std;


int main(){
    int n,c=1;
    string s;
    cin>>n>>s;
    rep(i,n-1){
        if(s[i]!=s[i+1]) c++;
        }
    cout<<c<<endl;
    return 0;
}

Measured memory_bytes: 512
N=int(input())
for h in range(1,3501):
  for n in range(1,3501):
    if 1/h+1/n>=4/N:continue
    if (N*h*n)%(4*h*n-N*(h+n))==0:print(h,n,(N*h*n)//(4*h*n-N*(h+n)));exit()

Measured memory_bytes: 3060
n=int(input())
x = [int(i) for i in input().split()]
xx = sorted(x)
ans=0
aaa=0
if n%2==0:
  for i in range(n//2):
    ans+=xx[i*2+1]-xx[i*2]
  print(ans)
else:
  for i in range(n//2):
    ans+=xx[i*2+1]-xx[i*2]
  aaa=xx[n-1]-ans
  print(aaa)

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

#define INF 1000000000000000ll

int main() {
  ll A,B,Q;
  cin >> A >> B >> Q;
  vector<ll> s(A+2);
  vector<ll> t(B+2);
  vector<ll> x(Q);
  s[0] = - INF;
  s[A+1] = INF;
  t[0] = - INF;
  t[B+1] = INF;
  for (ll i=0;i<A;i++){
    cin >> s[i+1];
  }
  for (ll i=0;i<B;i++){
    cin >> t[i+1];
  }
  for (ll i=0;i<Q;i++){
    cin >> x[i];
  }
  rep(i,Q){
    ll m = INF;
    ll s_l = lower_bound(s.begin(),s.end(),x[i]) - s.begin();
    ll t_l = lower_bound(t.begin(),t.end(),x[i]) - t.begin();
    for (ll j=0;j<2;j++){
      ll sidx = s_l -j;
      ll sx = s[sidx];
      for (ll k=0;k<2;k++){
        ll tidx = t_l -k;
        ll tx = t[tidx];
        m = min(m, abs(x[i] - sx) + abs(sx - tx));
        m = min(m, abs(x[i] - tx) + abs(sx - tx));
      }
    }
    cout << m << endl;
  }
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }
template<class T>
ostream &operator<<(ostream &os,const vector<T> &v){
	for(int i = 0;i < v.size();i++) os << (i ? "," : "[") << v[i];
	os << "]";
	return os;
}

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }

const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n;
	cin >> n;
	string s;
	while(1){
		n--;
		s = (char)('a' + n % 26) + s;
		n /= 26;
		if(n == 0) break;
	}
	cout << s << endl;
}

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define SORTG(v) sort(v.begin(),v.end(),greater<>())
#define SORT(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/3

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<string> Vs;

template<class T> void chmax(T& a, T b) {if(a<b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a>b){a=b;}}
void YesNo(int a) {if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
void YESNO(int a) {if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}
void AorB(int a,string b,string c) {if(a){cout<<b<<endl;}else{cout<<c<<endl;}}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void start(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);}

signed main(){start();
    int n,suma=0,sumb=0,kaisuu=0;
    cin>>n;
    Vi a(n),b(n);
    REP(i,0,n){
        cin>>a[i];
        suma+=a[i];
    }
    REP(i,0,n){
        cin>>b[i];
        sumb+=b[i];
        if(a[i]<b[i]) kaisuu += RUP((b[i]-a[i]),2);
    }
    YesNo(kaisuu<=sumb-suma);
    return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long num = scan.nextLong();
		long sum = 0;
		for(int i = 1; i<=num; i++) {
			if(i%3==0||i%5==0) {

			}else{sum=sum+i;}
		}
		System.out.println(sum);
	}
}


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

using int64 = long long;

int main() {
  int64 n;
  cin >> n;
  vector<int64> A(n);
  for (int64& a : A)
    cin >> a;
  unordered_map<int64, int64> mp;
  for (int64& a : A)
    mp[a] = mp[a] + 1;
  int64 sum = 0;
  for (auto& p : mp) {
    int64 n = p.second;
    sum += n * (n - 1) / 2;
  }

  for (int64& a : A) {
    int64 n = mp[a];
    int64 m = n - 1;
    cout << sum - n * (n - 1) / 2 + m * (m - 1) / 2 << "\n";
  }
  
  return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define RALL(a)     (a).rbegin(),(a).rend()
#define PRINT(a)   cout << (a) << endl

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

using ll = long long int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

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

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

class UnionFindTree{
  public:
    vector<int> rank,p,count;

    UnionFindTree() {}

    UnionFindTree(int size){
      rank.assign(size, 0);
      p.assign(size, 0);
      count.assign(size,1);
      REP(i,size)makeSet(i);
    }

    void makeSet(int x){
      p[x] = x;
      rank[x] = 0;
    }

    bool same(int x, int y){
      return findSet(x) == findSet(y);
    }

    void unite(int x, int y){
      if(findSet(x) == findSet(y))return;

      x = findSet(x);
      y = findSet(y);
      
      if(rank[x] > rank[y]){
        p[y] = x;
      }else{
        p[x] = y;
        if(rank[x] == rank[y]){
          rank[y]++;
        }
      }

      int tmp = count[x] + count[y];
      count[x] = tmp;
      count[y] = tmp;
    }

    int findSet(int x){
      if(x != p[x]){
        p[x] = findSet(p[x]);
      }
      return p[x];
    }

    int getCount(int x){
      return count[findSet(x)];
    }

    void print(){
      REP(i,p.size()){
        cout << p[i] << " ";
      }
      cout << endl;
      REP(i,p.size()){
        cout << rank[i] << " ";
      }
      cout << endl;
    }

};

int main(){
  int n,m;
  cin >> n >> m;
  UnionFindTree tree(n);

  REP(i,m){
    int a,b;
    cin >> a >> b;
    a--;b--;
    tree.unite(a,b);
  }

  int ans=0;
  REP(i,n){
    chmax(ans,tree.getCount(i));
  }
  cout << ans << endl;
}



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

int main(){
  int N; cin>>N;
  int a[N];
  for(int i=0; i<N; i++)cin>>a[i];
  int cnt=0;
  while(1){
    bool ndiv=false;
    for(int i=0; i<N; i++){
      if(a[i]%2!=0)ndiv=true;
      if(a[i]%2==0)a[i]/=2;
    }
    if(ndiv)break;
    cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}
  


Measured memory_bytes: 3632
#include <iostream>

int partition(int *A, int p, int r){
	int i,j,x,temp;
	x = A[r];
	i = p-1;
	for(j=p;j<r;j++){
		if(A[j] <= x){
			i++;
			temp = A[i];
			A[i] = A[j];
			A[j] = temp;
		}
	}
	temp = A[i+1];
	A[i+1] = x;
	A[r]=temp;
	return i+1;
}

int main(void){
	int i,n,q;
	int *A;

	std::cin >> n;
	
	A = new int[n];
	for(i=0;i<n;i++){
		std::cin >> A[i];
	}
	q = partition(A, 0, n-1);
	for(i=0;i<n-1;i++){
		if(i==q){
			std::cout << "[" << A[i] << "] ";
		}
		else{
			std::cout << A[i] << " ";
		}
	}
	std::cout << A[i] << std::endl;
	
	delete A;
	return 0;
}

Measured memory_bytes: 3108
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
string A, B, C;
int main() {
	cin >> A >> B >> C;
	int ca=0,cb=0, cc=0;
	char head = 'a';
	while (true) {
		if (head == 'a') {
			if (ca == A.size()) {
				cout << "A" << endl;
				break;
			}
			head = A[ca];
			ca++;
		}
		else if (head == 'b') {
			if (cb == B.size()) {
				cout << "B" << endl;
				break;
			}
			head = B[cb];
			cb++;
		}
		else if (head == 'c') {
			if (cc == C.size()) {
				cout << "C" << endl;
				break;
			}
			head = C[cc];
			cc++;
		}
	}
	return 0;
}


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

int main()
{
    int a, b;
    int n, p;
    int _1, _2, _3;
    _1 = _2 = _3 = 0;

    cin >> n;
    cin >> a >> b;
    for (int i = 0; i < n; i++) {
        cin >> p;

        if (p <= a) {
            _1++;
        } else if (p <= b) {
            _2++;
        } else {
            _3++;
        }
    }

    cout << min(_1, min(_2, _3)) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
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;
}

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

  string s;cin>>s;
  int a(0),b(0),c(0);
  rep(i,0,s.size()){
    if(s[i]=='a')a++;
    else if(s[i]=='b')b++;
    else c++;
  }

  int x=abs(a-b),y=abs(b-c),z=abs(c-a);
  if(x<=1&&y<=1&&z<=1){
    cout<<"YES"<<endl;
  }
  else cout<<"NO"<<endl;

  return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {


    int a, b, c;
    public void solve() {
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();

        if (a == b) System.out.println(c);
        if (a == c) System.out.println(b);
        if (b == c) System.out.println(a);

    }

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

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

int main(){
  int a, b, c;
  cin>>a>>b>>c;

  if(a > b) swap(a, b);
  if(b > c) swap(b, c);
  if(a > b) swap(a, b);

  cout<<a<<" "<<b<<" "<<c<<endl;
  return 0;
    }    


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

using namespace std;

int main() {
	int x, c1 = 0, c2 = 0;
	for (int i = 0; i < 3; i++) {
		scanf("%d", &x);
		if (x == 5)
			c1++;
		if (x == 7)
			c2++;
	}
	if (c1 == 2 && c2 == 1)
		puts("YES");
	else 
		puts("NO");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
string S;
  cin>>S;
  int N=S.size();
  char ans='A';
  for(char i='a';i<='z';i++){
       bool x=true;
    for(int j=0;j<N;j++){
  if(i==S.at(j)){
     x=false; break;
  }
  }  if(x){
     ans=i; break;
    }
  
  }if(ans=='A')
    cout<<"None"<<endl;
  else
    cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 512
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

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

int main(){
  string s;
  cin>>s;
  
  if(s<="2019/04/30") cout<<"Heisei"<<endl;
  else cout<<"TBD"<<endl;

  return 0;
}

Measured memory_bytes: 3616
#include<iostream>
#include<set>
using namespace std;
int main(){
    int N;
    int A;
    set<int> st;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> A;
        if(st.erase(A) == 0) st.insert(A);
    }
    cout << st.size() << endl;
    return 0;
}


Measured memory_bytes: 4864
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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

int N,a=0,b;

int main(){
    cin>>N;
    rep(i,N){
        cin>>b;
        a=a^b;
    }
    if(a)out("No");
    else out("Yes");

    
    
    
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

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

	int ans;
	if (n % 2 == 0) {
		ans = n / 2 - 1;
	} else {
		ans = n / 2;
	}

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


Measured memory_bytes: 256
x, _ = gets.chomp.split(' ').map(&:to_i)
p = gets.chomp.split(' ').map(&:to_i)
arr = (0..101).to_a
p.each { |i| arr.delete(i) }
max = [arr.first, (x - arr.first).abs]
arr.each do |i|
  max = [i, (x - i).abs] if max[1] > (x - i).abs
end
puts max[0]

Measured memory_bytes: 14392
using namespace std;
#include<string>
#include<cmath>
#include<list>
#include <map>
#include <unordered_map>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ml map<ll,ll>
#define pb push_back
#define mp make_pair
#define ppl pair<ll,ll>
#define F first
#define S second
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

#define fr(i,a,b) for(ll i=a;i<b;i++)
#define ffr(i,a,b) for(ll i=a;i>=b;i--)
#include<bits/stdc++.h>
#include<vector>
#define vl vector<ll>
#define PI 3.141592654
const ll N = 1e9 + 7;
#include<iterator>
#define EPSILON numeric_limits<double>::epsilon()




void solve() {
	string n;
	ll s = 0; cin >> n;
	fr(i, 0, n.size()) {
		ll d = (int)n[i] - 48;
		s += d;
	}
	if (s % 9)cout << "No";
	else cout << "Yes";
}





int main() {
	fio;
#ifndef ONLINE_JUDGE
	// for getting input
	freopen("input.txt", "r", stdin);
	//for writing output
	freopen("jout.txt", "w", stdout);
#endif

	ll t;
	if (1)
		t = 1;
	else
		cin >> t;
	while (t--) {
		//cout << "Case #" << h << ":\n";
		solve();
		//h++;
		cout << '\n';
	}
	return 0;
}






Measured memory_bytes: 3776
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
A = [int(input()) for _ in range(N)]
Min = [A[-1]]
for i in range(N - 2, -1, -1):
    temp = bisect.bisect_right(Min, A[i])
    if temp == len(Min):
        Min.append(A[i])
    elif Min[temp] != A[i]:
        Min[temp] = A[i]
    elif temp + 1 != len(Min):
        Min[temp + 1] = A[i]
    else:
        Min.append(A[i])
print(len(Min))

Measured memory_bytes: 13040
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define LCIN(n) LL(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

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

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())
#define ENDL cout<<endl
#define MAXE(a,b) a=max(a,b)
#define MINE(a,b) a=min(a,b)

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    int from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};

int main(){
    vector<int> v;
    int a,b,c,d;cin >> a >> b >> c >> d;
    v = {a,b,c,d};
    YES(count(ALL(v),1) == 1&&count(ALL(v),9) == 1&&count(ALL(v),7) == 1&&count(ALL(v),4) == 1);
    return 0;
}


Measured memory_bytes: 256
/* This Template is property of Pranav Khiste aka desmond_kaneki*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi(x,n) for(ll i=x;i<n;i++)
#define fj(x,n) for(ll j=x;j<n;j++)
#define vll vector<ll>
#define pb push_back
#define qll queue<ll>
#define mp make_pair
#define fst first
#define snd second
#define pll pair<ll,ll>
#define vpll vector<pll>
#define debug(x) cout<<#x<<' '<<x<<endl;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define mod 1000000007
#define SUP LLONG_MAX
#define INF LLONG_MIN
#define test() ll var;  cin>>var; while(var--)
#define fileio freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);  // use cin cout only!!
main()
{
    fastio;
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll ans=0;
    while(b<=a)
    {
        b=b*2;
        ans++;
    }
    while(c<=b)
    {
        c=c*2;
        ans++;
    }
    if(ans<=k)
        cout<<"Yes"<<endl;
    else
    {
        
        cout<<"No"<<endl;
    }
    
    
}


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

int v[MAXN];

void solve(){
	int n, x;
	scanf("%d%d", &n, &x);
	ll ans = 0ll;
	REP(i, 0, n){
		scanf("%d", &v[i]);
		int dif = max(v[i] - x, 0);
		ans += dif;
		v[i] -= dif;
	}
	REP(i, 1, n){
		int dif = max(0, v[i] + v[i - 1] - x);
		ans += dif;
		v[i] -= dif;
	}
	cout << ans << endl;
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<random>

using namespace std;


int N, D;
int x[10][10];

int main() {
	cin >> N >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < D; j++) {
			cin >> x[i][j];
		}
	}


	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			int tmp = 0;
			for (int k = 0; k < D; k++) {
				tmp += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
			}

			double tmp2 = sqrt(tmp);
			int tmp3 = tmp2;

			if (tmp2 == tmp3) ans++;
		}
	}

	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int p[14][14];

void drop(int x, int y, int s)
{
    if (s == 1) {
        p[x + 1][y + 2]++;
        p[x + 2][y + 1]++;
        p[x + 2][y + 2]++;
        p[x + 2][y + 3]++;
        p[x + 3][y + 2]++;
    } else if (s == 2) {
        p[x + 1][y + 1]++;
        p[x + 1][y + 2]++;
        p[x + 1][y + 3]++;
        p[x + 2][y + 1]++;
        p[x + 2][y + 2]++;
        p[x + 2][y + 3]++;
        p[x + 3][y + 1]++;
        p[x + 3][y + 2]++;
        p[x + 3][y + 3]++;
    } else if (s == 3) {
        p[x    ][y + 2]++;
        p[x + 1][y + 1]++;
        p[x + 1][y + 2]++;
        p[x + 1][y + 3]++;
        p[x + 2][y    ]++;
        p[x + 2][y + 1]++;
        p[x + 2][y + 2]++;
        p[x + 2][y + 3]++;
        p[x + 2][y + 4]++;
        p[x + 3][y + 1]++;
        p[x + 3][y + 2]++;
        p[x + 3][y + 3]++;
        p[x + 4][y + 2]++;
    }
}

int main(void)
{
    int x, y, s;
    int c = 100;
    int m = 1;
    int i, j;

    while (scanf("%d,%d,%d", &x, &y, &s) != EOF) {
        drop(x, y, s);
    }

    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            if (p[i + 2][j + 2] >= 1) {
                c--;
                if (p[i + 2][j + 2] > m) {
                    m = p[i + 2][j + 2];
                }
            }
        }
    }

    printf("%d\n%d\n", c, m);

    return 0;
}

Measured memory_bytes: 600
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${TY%Wi`(5WFMt58Fc(Xq*VD9x7D&BPj>l7_bTkIj*Ai>${5yulNExGoBr<UD>{aRttH)I;%|$Qg=gd9dxR@Di;P73FNP9dUGDQ<!!6lSu|K~YBh-_ms0mLUn?gYZW#)-aa9<|QdNMzm)C?=0Ye!0PSL>Nlrr!HyueleslJL(9LLK>v^G%;rmuCIg#qB2DZxNO4vB|vjcygBlZci;a!M4%3#=<-KH%*=17Q{aUKnzd7$r^Mh?)~>JZY8tu?FNSSF3obEX4)B&4>QOg%{W&$?iM3r$#)#@1-i<G$3Tv!!YO=a7HK93>>2bH|?5DKSQZ$O1|v2Wz}2I=r-M5)Wxd_@vZhgv>n8k$Q*}~?$i?{b`*|*!&44o)o(qXPyC2tN78cW$sb`#As%5$;I{B+f6Pb!JtGS5K99vu#l*|yora61crqIw#8`%bf6>w5x%@H*ya+t$KlVq{`2")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Measured memory_bytes: 9900