akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
const int N = 3e5 + 1100,mod = 1e9 + 7;
int n; char s[N];
int f[N][4][4];
int main()
{
	scanf("%s",s + 1); n = strlen(s +1); f[0][0][0] = 1;
	for(int i = 0;i < n;i ++)
	{
		if(s[i + 1] != '1')
		{
			for(int j = 0;j < 3;j ++)
				for(int k = 0;k < 3;k ++)
				{
					if(k == 2) f[i + 1][j][k - 1] = (f[i + 1][j][k - 1] + f[i][j][k]) % mod;
					else f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % mod;
				}
		}
		if(s[i + 1] != '0')
		{
			for(int j = 0;j < 3;j ++)
				for(int k = 0;k < 3;k ++) 
				{
					if(k == 0) f[i + 1][j + (j != 2)][k] = (f[i + 1][j + (j != 2)][k] + f[i][j][k]) % mod;
					else f[i + 1][j][k - 1] = (f[i + 1][j][k - 1] + f[i][j][k]) % mod;
				}
		}
	}
	int ans = 0;
	for(int i = 0;i < 3;i ++) for(int j = 0;j <= i;j ++) ans = (ans + f[n][i][j]) % mod;
	cout << ans << "\n";
	return 0;
}


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

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

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

struct Query{
        int l,r,i,block;
        Query(int _l,int _r,int _i) : l(_l), r(_r), i(_i){}
        bool operator <(const Query &q)const {
                int c_o = l/block, c_q = q.l/block;
                if(c_o == c_q)return r < q.r;
                return c_o < c_q;
        }
};

const int maxn = 500000+10;
int cnt[maxn],N,Q;

void add(int v,int &res){
        if(++cnt[v] == 1) res++;
}
void remove(int v,int &res){
        if(--cnt[v] == 0)res--;
}
vector<ii> Mos(vector<Query> &queries,vector<int> A){
        int Nn = A.size();
        vector<ii> ans;

        int block = sqrt(Nn);
        for(auto &q : queries)q.block = block;

        sort(queries.begin(),queries.end());
        int mo_l = 0,mo_r = -1;
        int res = 0;

        for(auto &q : queries){
                // [l,r]
                while(mo_r < q.r){
                        mo_r++;
                        add(A[mo_r],res);
                }
                while(mo_r > q.r){
                        remove(A[mo_r],res);
                        mo_r--;
                }
                while(mo_l < q.l){
                        remove(A[mo_l],res);
                        mo_l++;
                }
                while(mo_l > q.l){
                        mo_l--;
                        add(A[mo_l],res);
                }
                ans.push_back({q.i,res});
        }
        sort(all(ans));
        return ans;
}


int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> Q;
	vector<int> A(N);
	forn(i,0,N) cin >> A[i];
	vector<Query> queries;
	forn(i,0,Q){
		int l,r; cin >> l >> r; l--; r--;
		queries.pb(Query(l,r,i));
	}
	vector<ii> res =  Mos(queries,A);
	for(auto &x : res)cout << x.se << '\n';

	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
*/


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

int cross(int a, int b, int c, int d) {
    return a * d - b * c;
}

int main() {
    int n;

    cin >> n;
    while (n--) {
        int xp[3], yp[3], x[2], y[2];
        int cp[2][3];

        for (int i = 0; i < 3; i++) {
            cin >> xp[i] >> yp[i];
        }   
        for (int i = 0; i < 2; i++) {
            cin >> x[i] >> y[i];
        }

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                int k = (j+1) % 3;
                cp[i][j] = cross(xp[k]-xp[j], yp[k]-yp[j], x[i]-xp[j], y[i]-yp[j]) > 0;
            }
        }
        bool judge = false;
        if (cp[0][0] == cp[0][1] && cp[0][0] == cp[0][2]) {
            if (cp[1][0] != cp[1][1] || cp[1][0] != cp[1][2]) {
                judge = true;
            }
        }
        else if (cp[1][0] == cp[1][1] && cp[1][0] == cp[1][2]) {
            judge = true;
        }
        cout << (judge? "OK": "NG") << endl;

    }
    return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
int main() {
  int x, y, z = 0; cin >> x >> y;
  vector<int> s = {4, 6, 9, 11}; bool j1 = false;
  for(int i = 0; i < 4; i++) {
    if(s[i] == x) z++;
    if(s[i] == y) z++;
  } if(z % 2 == 0) j1 = true;
  cout << (((x != 2 && y != 2) && j1) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
nums = Array.new
nums[0] = 0
i = 1

loop {
	nums[i] = gets.to_i
	if nums[i] == 0
		break
	end
	i += 1
}

i -= 1
cnt = 1


i.times do 
	print "Case ",cnt,": ",nums[cnt],"\n"
	cnt += 1
end

Measured memory_bytes: 6164
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;

#define INF   (1e9+7)
#define MAX_V (200)
#define MAX_E (10000)
#define MAX_R (1000)
#define MAX_C (1000)

struct Postman { int pos; int ship; int cost; };

int V, E, R;
int DL[MAX_V][MAX_V], DS[MAX_V][MAX_V], DP[MAX_R][MAX_V], PATH[MAX_R];

void warshall_floyd(int d[][MAX_V]) {
  for (size_t w = 0; w < V; w++)
    for (size_t u = 0; u < V; u++)
      for (size_t v = 0; v < V; v++) d[u][v] = min(d[u][v], d[u][w] + d[w][v]);
}

void solve() {
  warshall_floyd(DL);
  warshall_floyd(DS);

  for (size_t i = 0; i < R; i++)
    for (size_t v = 0; v < V; v++) DP[i][v] = INF;
  DP[0][PATH[0]] = 0;

  for (size_t i = 1; i < R; i++) {
    int u = PATH[i - 1], v = PATH[i];
    for (int w = 0; w < V; w++) {
      for (int x = 0; x < V; x++) {
//        printf("DP[%d][%d]+DL[%d][%d]+DS[%d][%d]+DL[%d][%d] = %d\n",i-1,w,u,w,w,x,x,v,d);
        int d;
        if (w == x) {
          d = DP[i-1][w] + DL[u][v];
        } else {
          d = DP[i-1][w] + DL[u][w] + DS[w][x] + DL[x][v];
        }
        DP[i][x] = (0 <= d)? min(DP[i][x], d): DP[i][x];
      }
    }
  }

  int ans = INF;
  for (size_t v = 0; v < V; v++) {
    ans = min(ans, DP[R-1][v]);
  }
  printf("%d\n", ans);
}

int main() {
  while (true) {
    scanf("%d %d", &V, &E);
    if (V == 0) break;
    for (size_t v = 0; v < V; v++)
      for (size_t u = 0; u < V; u++) DL[v][u] = DS[v][u] = (u == v)? 0: INF;

    for (size_t i = 0; i < E; i++) {
      int v, u, cost; char c;
      scanf("%d %d %d %c\n", &v, &u, &cost, &c);
      v--; u--;
      if (c == 'L') {
        DL[u][v] = DL[v][u] = min(DL[u][v], cost);
      } else {
        DS[u][v] = DS[v][u] = min(DS[u][v], cost);
      }
    }

    scanf("%d", &R);
    for (size_t i = 0; i < R; i++) {
      scanf("%d", &PATH[i]);
      PATH[i]--;
    }

    solve();
  }

  return 0;
}

Measured memory_bytes: 4308
#include"bits/stdc++.h"
using namespace std;

int main() {
    long long A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    if (X < Y) {
        swap(A, B);
        swap(X, Y);
    }

    long long ans = LLONG_MAX;
    for (long long i = 0; i <= X; i++) {
        //Aをi枚買う
        long long curr = A * i;

        //残りを半分で買う
        curr += (X - i) * 2 * C;

        //Bを足りるように買う
        curr += max(0LL, Y - (X - i)) * B;

        ans = min(curr, ans);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
s = gets.chomp.split("").map(&:to_i)

ans = 0
1.upto s.size do |i|
  ex = s[i-1]
  if s[i] == s[i-1]
    s[i] = (s[i-1]+1) % 2
    ans += 1
  end
end
puts ans

Measured memory_bytes: 7676
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int N;
	int count = 0;
	int a,b=0;
	cin >> N;
	vector<int> P(N);
	vector<int> Q(N);
	vector<int> R(N);
	for (int i = 0; i < N; i++) {
		cin >> P.at(i);
	}
	for (int i = 0; i < N; i++) {
		cin >> Q.at(i);
		R.at(i) = Q.at(i);
	}
	sort(R.begin(), R.end());
	do {
		if (R == P) {
			a = count;
		}
		if (R == Q) {
			b = count;
		}
			count++;
	} while (next_permutation(R.begin(), R.end()));
	cout << abs(a - b) << endl;
	return 0;
}

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

using namespace std;

const int N = (int)400 + 7;
const int mod = (int)1e9 + 7;

int add(int a, int b) {
	a += b;
	if (a > mod) a -= mod;
	return a;
}

int mul(int a, int b) {
	return (a * 1LL * b) % mod;
}

int n, c;
int a[N], b[N];
int sum[N][N];
int s[N][N];
int dp[N][N];

main() {
	scanf("%d %d", &n, &c);
	for (int i = 0; i < n; i++) 
		scanf("%d", &a[i]);
	for (int i = 0; i < n; i++) 
		scanf("%d", &b[i]);
	for (int i = 1; i < N; i++) {
		sum[i][0] = 1;
		for (int j = 1; j < N; j++) {
			sum[i][j] = mul(sum[i][j - 1], i);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = a[i]; j <= b[i]; j++) {
			for (int k = 0; k <= c; k++) {
				s[i][k] = add(s[i][k], sum[j][k]);
			}
		}
	}
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= c; j++) {
			if (!dp[i][j]) continue;
			for (int k = 0; k + j <= c; k++) {
				dp[i + 1][k + j] = add(dp[i + 1][k + j], mul(dp[i][j], s[i][k]));
			}
		}
	}
	printf("%d\n", dp[n][c]);
}


Measured memory_bytes: 2176
a, v = (int(i) for i in input().split(' '))
b, w = (int(i) for i in input().split(' '))
t = int(input())

flag = False
if a < b:
    l1 = a + v * t
    l2 = b + w * t
    if l1 >= l2:
        flag = True
else:
    l1 = a + (v * -1) * t
    l2 = b + (w * -1) * t
    if l1 <= l2:
        flag = True
print("YES" if flag else "NO")

Measured memory_bytes: 9128
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <typeinfo>
#include <cxxabi.h>
#define type_name(class)  demangle((typeid(class)).name())
char* demangle(const char *demangle) {
    int status;
    return abi::__cxa_demangle(demangle, 0, 0, &status);
}

using namespace std;

class KeyCoordinate{
public:
	int x;
	int y;
	KeyCoordinate(){x=0;y=0;}
	void DebugPrint(){
		cout<<"x = "<<x<<"   y = "<<y<<endl;
	}
};

bool isNeighbor(KeyCoordinate& first, KeyCoordinate& second){
	if(first.x == second.x && abs(first.y - second.y) == 1){
		return true;
	}else if((first.y == second.y && abs(first.x - second.x) == 1)){
		return true;
	}
	return false;
}

void getKeyCoordinate(const string& charactor, KeyCoordinate& kc){
	if(charactor == "A"){kc.x = 0;kc.y = 0;}
	if(charactor == "B"){kc.x = 1;kc.y = 0;}
	if(charactor == "C"){kc.x = 2;kc.y = 0;}
	if(charactor == "D"){kc.x = 0;kc.y = 1;}
	if(charactor == "E"){kc.x = 1;kc.y = 1;}
	if(charactor == "F"){kc.x = 2;kc.y = 1;}
	if(charactor == "G"){kc.x = 0;kc.y = 2;}
	if(charactor == "H"){kc.x = 1;kc.y = 2;}
	if(charactor == "I"){kc.x = 2;kc.y = 2;}
}

bool isUnicursal(string& str){
	//ボタン１つのみの入力も一筆書きとみなす
	if(str.length() == 1 ) return true;
	
	KeyCoordinate f,s;
	
	for(int i=0;i<str.length()-1;i++){
		
		getKeyCoordinate(str.substr(i,1), f);
		getKeyCoordinate(str.substr(i+1,1), s);
		
		// cout<<"i = "<<i<<endl;
		// f.DebugPrint();
		// s.DebugPrint();
		
		if(!isNeighbor(f,s)){return false;}
	}
	return true;
}

int main() {
	// your code goes here
	string str;
	while(cin>>str){
		if(isUnicursal(str)){
			cout<<str<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1184
import java.util.Scanner;

public class Main {

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

        while (true) {

            String nl = sc.nextLine();

            if ("0".equals(nl)) {
                break;
            }

            int ans = 0;

            for (int i = 0; i < nl.length(); i++) {
                ans += Character.getNumericValue(nl.charAt(i));
            }

            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 26408
#include<stdio.h>
int main()
{
	int N, count = 0;;
	char s[110][10];
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", s[i]);
		if (s[i][0] == 'Y') {
			count = 1;
		}
	}
	if (count == 1) {
		printf("Four");
	}
	else {
		printf("Three");
	}
}

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

using namespace std;

typedef long long ll;

const ll mod = (ll)1e9+7;
const ll N = 2e5;
ll iv[N+1];
ll po(ll x, ll n){
    if(n==0)
        return 1%mod;
    ll y = po(x, n/2)%mod;
    y = y*y%mod;
    if(n&1)
        y = y*x%mod;
    return y;
}
ll nck(ll n, ll k){
    ll ans = 1;
    for(ll i=1; i<=k; i++)
        ans = ans*(n-i+1)%mod*iv[i]%mod;
    return ans%mod;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, a, b;
    cin >> n >> a >> b;
    iv[1]=1;
    for(ll i=2; i<=N; i++)
        iv[i] = mod-mod/i*iv[mod%i]%mod;
    cout << ((po(2, n)+2*mod)-nck(n, a)-nck(n, b)+mod-1)%mod;
    return 0;
}


Measured memory_bytes: 1792
#include <cstring>
#include <map>
#include <unordered_map>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pii;

int gi() {
    int a;
    scanf("%d", &a);
    return a;
}

ll gli() {
    ll a;
    scanf("%lld", &a);
    return a;
}

int dp[100001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < 100000; i++)
        if (dp[i]) {
            for (int j = 100; j < 106 && i+j <= 100000; j++)
                dp[i+j] = 1;
        }

    printf("%d\n", dp[gi()]);

    return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
int main (void){
int N,L,i=0,j,sum=0,flag=0;
scanf("%d",&N);
scanf("%d",&L);
int taste[N+1];
for(j=0;j<N;j++){
taste[j]=L+j;
}
if(L<=0&&0<=L+N-1){
for(i=0;i<N;i++){
sum+=taste[i];
flag=1;
}
}
if(L>0&&flag!=1){
for(i=1;i<N;i++){
sum+=taste[i];
}
}else if(L<0&&flag!=1){
for(i=0;i<N-1;i++){
sum+=taste[i];
}
}
printf("%d",sum);
return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    multiset<ll> ms;
    rep(i, n) {
        auto it = ms.lower_bound(a[i]);
        if ((sz(ms) == 0) || (it == ms.begin())) {
            ms.insert(a[i]);
        }
        else {
            it--;
            ll v = *it;
            ms.erase(it);
            ms.insert(a[i]);
        }
    }
    cout << sz(ms) << endl;
    return 0;
}


Measured memory_bytes: 5760
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(N):
  f,g = 0,0
  for j in range(N):
    if A[i] > A[j]:
      g += 1
      if i < j:
        f += 1
  ans += ((f*K)+(g*(K*(K-1)//2)))%mod
print(ans%mod)

Measured memory_bytes: 3188
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
ll dp[105][200005];
int main(){
   ll n,k;
   cin>>n>>k;
   V<ll> a(n);
   for(int i=0;i<n;i++){
     cin>>a[i];
     dp[1][i]=a[i]-1;
   }
    for(int i=1;i<100;i++){
        for(int j=0;j<n;j++){
        dp[i+1][j]=dp[i][dp[i][j]];
        }
    }
    int now=0,cnt=1;
     while(k){
            if(k&1)now=dp[cnt][now];
            k>>=1;
            cnt++;
        }
        cout<<now+1<<"\n";
 }


Measured memory_bytes: 161072
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function bsearch(a,x);l,r=0,length(a)+1;while r-l>1;m=(r+l)>>1;if a[m]<=x;l=m;else;r=m;end;end;l;end

function main()
	n = readline() |> parseInt
	a = readline() |> split |> parseMap
	x = 0
	d = 0
	for i in 2:n
		if d==0
			if a[i]>a[i-1]
				d = 1
			elseif a[i]<a[i-1]
				d = -1
			end
		elseif d==1
			if a[i]<a[i-1]
				d = 0
				x+=1
			end
		elseif a[i]>a[i-1]
			d = 0
			x+=1
		end
	end
	println(x+1)
end

main()

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

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

#define INF INT_MAX

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

int main(int, char**)
{
    int n;
    cin >> n;

    switch (n % 10)
    {
    case 0:
    case 1:
    case 6:
    case 8:
        cout << "pon" << endl;
        break;
    case 3:
        cout << "bon" << endl;
        break;    
    default:
        cout << "hon" << endl;
        break;
    }

    return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define M 1000000007
#define sz(a) (ll)a.size()
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    string s;
    cin>>n>>s>>k;
    rep(i,0,n)
    {
    	if(s[i]==s[k-1])
    		cout<<s[i];
    	else
    		cout<<'*';
    }
}


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int z=0;
    set<int> s;
    for(int i=0;i<n;i++) {
        int x;
        cin >> x;
        if(x==0) z++;
        a[i]=x;
        s.insert(x);
    }
    if(z==n) {
        cout << "Yes" << endl;
        return 0;
    }
    if(n%3==0 && z==n/3 && s.size()==2){
        cout << "Yes" << endl;
        return 0;
    }
    if(s.size()==3){
        sort(a.begin(),a.end());
        if(a[n/3-1] != a[n/3] && a[n/3*2-1] != a[n/3*2] && (a[n/3-1]^a[n/3])==a[n/3*2]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;


    return 0;
}

Measured memory_bytes: 7176
N = int(input())
A = list(map(int,input().split()))
counts = [0 for x in range(N)]
ans = 1
for i in range(N):
	if A[i] == 0:
		ans = (ans * (3 - counts[0])) % 1000000007
		counts[0] += 1
	else:
		ans = (ans * (counts[A[i] - 1] - counts[A[i]])) % 1000000007
		counts[A[i]] += 1
print(ans)

Measured memory_bytes: 13964
#include <stdio.h>
int main(void)
{
	int b[4],cnt;
	scanf("%d",&b[1]);
	scanf("%d %d",&b[2],&b[3]);
	if(((b[1]==1)&&(b[2]==1))||((b[3]==1)&&((b[1]==0)&&(b[2]==0))))
		printf("Open\n");
	else
		printf("Close\n");
	scanf("%d",&b[1]);
	return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main()
{
	int n;
	cin >> n;
	vector<int> h(n);
	rep(i,n)cin >> h[i];
	int ma = h[0];
	rep(i,n)
	{
		if(ma-h[i]>1)
		{
			cout<<"No"<<endl;
			return 0;
		}
		ma = max(ma,h[i]);
		
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>


int keisan(int, int, int);


int main(void){
    //nとmの読み取り
    int n, m;
    scanf("%d %d", &n, &m);
    //計算
    int a, b, ans;
    a = m / n + 1;
    b = m % n - n;
    ans = keisan(a, b, n);
    //表示
    printf("%d\n", ans);

    return 0;
}

int keisan(int a, int b, int n){
    a -= 1;
    b += n;
    if(b % a != 0){
        a = keisan(a, b, n);
    }
    return a;
}

Measured memory_bytes: 128
k,s = gets.chomp.split.map(&:to_i)
kArraies = (0..k).to_a
count = 0
kArraies.repeated_permutation(2){|p1,p2|
  z = s - (p1+p2)
  count += 1 if z >= 0 && z <= k
}
puts count

Measured memory_bytes: 1916
import java.util.Arrays;
import java.util.Scanner;

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

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt() - (i+1);
        }

        Arrays.sort(a);
        int med = a[n/2];

        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.abs(a[i] - med);
        }

        System.out.println(ans);
    }
}

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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    int A,B,C;
    cin >> A >> B >> C;
    cout << max(10*C+A+B,max(10*A+B+C,A+10*B+C)) << endl;
    
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;

#define F first
#define S second
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define sz size()
#define all(A)    A.begin(), A.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define f0(i,b)   for(int i=0;i<(b);i++)
#define f1(i,b)   for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
#define mod 1000000007

#define forr(i,n)    for(i=0; i<n; i++)
#define whilee(i,t)  while(i!=t)
#define  sl(a)  scanf("%lld",&a)
#define  pl(a)  printf("%lld",a)

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;

//for(auto it =A.begin(); it!=A.end(); it++)
//sort(A.begin(),A.end());
//binary_search(A.begin(),A.end(),x);
//reverse(A.begin(), A.end());
//cout << *max_element(A.begin(), A.end());
//cout << *min_element(A.begin(), A.end());
//count(A.begin(), A.end(), X); //counts the occurrences of X
//distance(A.begin(),A.end());  //distance between first to last element
//accumulate(A.begin(), A.end(), 0); //add
//next_permutation(A.begin(), A.end());
//prev_permutation(A.begin(), A.end());
//swap(S[0], T[0]);
//scanf("%d",&x);
//printf("%d\n",x);

//vector <int> A;
//deque <int> A;
//queue <int> A;
//stack <int> A;
//set <int> A;
//map <int,int> A;
//pair <int,int> A ;
//vector <pair <int,int>> A ;
//bitset<32> bset1;
//char ch;
//string S, T, U;
ll i, j, k, a, b, c, d, f, g, h, l, m, n, p, q, r, s, t, u, v, w, x, y, z, maxx=INT_MIN, minn=INT_MAX, ans=0, sum=0, cnt=0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);//NULL
    cout.tie(nullptr);//NULL

    cin>>a>>b>>c>>d;
    int A[10]={0};
    A[a]++;
    A[b]++;
    A[c]++;
    A[d]++;

    if(A[1]==1 && A[9]==1 && A[7]==1 && A[4]==1)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }

    return 0;
}



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

using namespace std;


int main() {
    size_t n;
    cin >> n;
    for (size_t i = 1; i < 10; ++i) {
        for (size_t j = 1; j < 10; ++j) {
            if (i * j == n) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

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

using namespace std;

const int N = 8005;

typedef long long LL;

int n, sum[N][3], mp[300];

LL ans = 0;

char s[N], t[3] = { 'R', 'G', 'B' } ;

int main() {
	mp['R'] = 0, mp['G'] = 1, mp['B'] = 2;
	scanf("%d%s", &n, s + 1);
	for (int i = n; i; i--) {
		for (int j = 0; j < 3; j++)
			sum[i][j] = sum[i + 1][j];
		sum[i][mp[s[i]]]++;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (s[i] == s[j]) continue;
			int k = 3 - mp[s[i]] - mp[s[j]];
			ans += sum[j + 1][k];
			if (s[j + j - i] == t[k]) ans--;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  prim.clear();
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

void solve()
{
  ll N; cin >> N;
  ll ans = 0;
  map<ll, ll> lmap;
  rep1(i, N) {
    pf(i);
    rep(j, prim.size()) {
      //cerr<< "(" << prim[j].first << "," << prim[j].second << ")\n";
      lmap[prim[j].first] += prim[j].second;
    }
  }
  ans = 1;
  for(auto itr : lmap) {
    ans *= itr.second + 1;
    ans %= MOD;
  }
  
  cout << ans << endl;
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


Measured memory_bytes: 3644
n, m = map(int, input().split())
graph = [[float('inf')]*n for i in range(n)]
u_s=[]
v_s=[]
w_s=[]
for _ in range(m):
    u, v, w = map(int, input().split())
    u_s.append(u-1)
    v_s.append(v-1)
    w_s.append(w)
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0


def warshall_floyd(d):
    # d[i][j] : i から j への最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

dist=warshall_floyd(graph)

ans=0
for i in range(m):
    if w_s[i]>dist[u_s[i]][v_s[i]]:
        ans+=1

print(ans)

Measured memory_bytes: 9304
#include<iostream>
#include<stdlib.h>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
	ll N,M;
	cin >> N >> M;
	ll ac=0,wa=0,pen[N];
	ll i;
	ll p;
	string s;
	for(i=0;i<N;i++){
		pen[i]=0;
	}
	for(i=0;i<M;i++){
		cin >> p >> s;
		if(pen[p-1]!=-1){
			if(s=="AC"){
				ac++;
				wa+=pen[p-1];
				pen[p-1]=-1; 
			}else{
				++pen[p-1];
			}
		} 
	}
	cout << ac << " " << wa;
    return 0;
}


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


int main(int, char**) {
    std::ios::sync_with_stdio(false);
    int N; 
    string s;
    cin >> N >> s;

    vector<int> cntAll(26, 0);
    for (int i = 0; i < N; ++i) {
        ++cntAll[s[i] - 'a'];
    }

    vector<int> cntF(26, 0);
    int maxD = -1e6;
    for (int i = 0; i < N; ++i) {
        int x  = s[i] - 'a';
        ++cntF[x];
        --cntAll[x];
        int curD = 0;
        for (int j = 0; j < 26; ++j) {
            if (cntF[j] != 0 && cntAll[j] != 0)
                ++curD;
        }
        maxD = max(curD, maxD);
    }
    cout << maxD << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,(n)-1)
#define drrep(i,cc,n) for(int i=(cc);i>=(n);--i)
#define rrep(i,n) drrep(i,0,(n)-1)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,v.size())if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define arrprint(v,n) rep(i,n)if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define matprint(v,n,m) rep(i,n){rep(j,m){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
using ll = long long;
using P = pair<int,int>;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

int main(){
    int now = 0;
    ll ans = 0;
    int n;
    cin >> n;
    // vector<int> a(n);
    rep(i,n){
        int a;
        cin >> a;
        if(i != 0)ans += max(now - a,0);
        now = max(now, a);
    }


    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 3616
import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
N, Z, W = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
d = {}
def minmax(x, y, c, f):
    # print('x={}, y={}, c={}, f={}'.format(x, y, c, f))
    if (c, f) in d:
        return d[(c, f)]
    if c == N:
        return abs(x - y)
    if f == 0:
        ret = -float('inf')
        for i in range(1, N - c + 1):
            ret = max(ret, minmax(a[c+i-1], y, c+i, f^1))
    else:
        ret = float('inf')
        for i in range(1, N - c + 1):
            ret = min(ret, minmax(x, a[c+i-1], c+i, f^1))
    d[(c, f)] = ret
    return ret

print(minmax(Z, W, 0, 0))

Measured memory_bytes: 46936
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
#define inf 1e18+9
using namespace std;
const int mod=998244353;
int32_t main(){
	if(fopen("input.txt", "r"))
	freopen("input.txt", "r", stdin),
	freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int a,b,m,p=inf,q=inf,ans=inf;
	cin >> a >> b >> m;
	int x[a],y[b];
	for(int i=0;i<a;i++){
		cin >> x[i];
		p=min(p,x[i]);
	}
	for(int j=0;j<b;j++){
		cin >> y[j];
		q=min(q,y[j]);
	}
	ans=p+q;
	for(int i=0;i<m;i++){
		int d,e,f;
		cin >> d >> e >> f;
		ans=min(x[d-1]+y[e-1]-f,ans);
	}
	cout << ans;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	long long h, w;
	cin >> h >> w;

	long long mn = 1010101010101010;
	for (long long i = 1; i < h; i++) {
		long long a = i * w;
		long long b = (h - i) * ((w + 1) / 2);
		long long c = (h - i) * (w / 2);
		long long tmp = max({ a, b, c }) - min({ a, b, c });
		mn = min(mn, tmp);
	}
	for (long long i = 1; i < h - 1; i++) {
		long long a = i * w;
		long long b = (h - i) / 2 * w;
		long long c = (h - i + 1) / 2 * w;
		long long tmp = max({ a, b, c }) - min({ a, b, c });
		mn = min(mn, tmp);
	}
	for (long long i = 1; i < w; i++) {
		long long a = i * h;
		long long b = (w - i) * ((h + 1) / 2);
		long long c = (w - i) * (h / 2);
		long long tmp = max({ a, b, c }) - min({ a, b, c });
		mn = min(mn, tmp);
	}
	for (long long i = 1; i < w - 1; i++) {
		long long a = i * h;
		long long b = (w - i) / 2 * h;
		long long c = (w - i + 1) / 2 * h;
		long long tmp = max({ a, b, c }) - min({ a, b, c });
		mn = min(mn, tmp);
	}
	cout << mn << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        int N = sc.nextInt();
        int[] H = new int[N];
        int count = 0;
        int max = 0;
        for (int i = 0; i < N ; i++) {
            H[i] = sc.nextInt();
            if(max <= H[i]) {
                max = H[i];
                count++;
            }
        }
        System.out.println(count);

    }
}


Measured memory_bytes: 23764
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
using namespace std;
#define rep(I,N) for(int I = 0; I < (int)(N); I++)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;

int main(void){
	int N;
	cin >> N;
	rep(k, N){
		int a, b, c;
		cin >> a >> b >> c;
		a = pow(a, 2);
		b = pow(b, 2);
		c = pow(c, 2);
		bool flag = false;
		if(sqrt(c) == sqrt(a + b))flag = true;
		if(sqrt(b) == sqrt(a + c))flag = true;
		if(sqrt(a) == sqrt(b + c))flag = true;
		if(flag)cout << "YES"<<endl;
		else FIN("NO");

	}

	return 0;	
}

Measured memory_bytes: 1148
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int w,h,x,y;
    cin >> w >> h >> x >> y;
    cout << fixed << setprecision(13) << double(double(w) *double( h) / 2 )<< " ";
    if( x *2 == w and y * 2 == h) cout << 1 << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 256
S = input()

N = len(S) + 1
t = [0] * N
p = ''
for i in range(N - 2, -2, -1):
  if p == '>':
    t[i + 1] = t[i + 2] + 1
  p = S[i]
for i in range(N - 1):
  if S[i] == '<':
    t[i + 1] = max(t[i + 1], t[i] + 1)
print(sum(t))


Measured memory_bytes: 23336
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t;
    }
    return n*rep_jijo(n,x-1);
}

int main(){
    string s,t;
    int ans =0;
    cin >> s >> t;
    int len = s.size();
    rep(i,len){
        if(s[i]!=t[i]) ans++;
    }
    cout << ans << endl;

}

Measured memory_bytes: 3860
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n) 
#define SIZE(x) ((int)(x).size())
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
typedef vector<lint> vec;
typedef vector<vector<lint>> matrix;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

lint gcd(lint a, lint b) {
    lint r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

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

lint power(lint x, lint n, lint mod = MOD) {
    lint ret = 1;
    while(n > 0) {
        if(n & 1){
            (ret *= x) %= mod;
        }
        (x *= x) %= mod;
        n >>= 1;
    }
    return ret;
}

vector<lint> make_power(int n, lint base){
    lint num = 1;
    vector<lint> ret;
    for (int i=0; i<=n; ++i){
        ret.push_back(num);
        num *= base;
    }
    return ret;
}

lint euler_phi(lint n){
    lint ret = n;
    if(n == 0){
        return 0;
    }
    for (lint i=2; i*i <= n; ++i){
        if(n % i == 0){
            ret -= ret / i;
            while(n % i == 0){
                n /= i;
            }
        }
    }
    if(n > 1){
        ret -= ret / n;
    }
    return ret;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    lint n;
    cin >> n;
    cout << euler_phi(n) << endl;
    return 0;
}


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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

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;}

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

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

const ll mod = 1e9 + 7;

int main(){
    int n, m; cin >> n >> m;
    ll xf, yf; cin >> xf;
    vector<ll> xlis(n-1), ylis(m-1);
    REP(i, 0, n-1){
        ll a; cin >> a;
        xlis[i] = a - xf;
        xlis[i] %= mod;
        xf = a;
    }
    cin >> yf;
    REP(i, 0, m-1){
        ll a; cin >> a;
        ylis[i] = a - yf;
        ylis[i] %= mod;
        yf = a;
    }
    ll xsum = 0, ysum = 0;
    REP(i, 0, n-1){
        xlis[i] = xlis[i] * (i+1) * (n-1-i);
        xsum += xlis[i];
        xsum %= mod;
    }
    REP(i, 0, m-1){
        ylis[i] = ylis[i] * (i+1) * (m-1-i);
        ysum += ylis[i];
        ysum %= mod;
    }
    cout << (ysum * xsum) % mod << endl;
}

Measured memory_bytes: 4728
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const long long mod = 1000000007;
struct mint {
  long long x;
  mint(ll x = 0):x(x%mod) {}
  mint& operator+=(const mint a) {
    (x += a.x) %= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    (x += mod-a.x) %= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint ret(*this);
    return ret += a;
  }
  mint operator-(const mint a) const {
    mint ret(*this);
    return ret -= a;
  }
  mint operator*(const mint a) const {
    mint ret(*this);
    return ret *= a;
  }
  mint pow(ll t) const {
    if(t==0) return mint(1);
    mint a = pow(t>>1);
    a *= a;
    if(t&1) a *= *this;
    return a;
  }
  
  //for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint ret(*this);
    return ret /= a;
  }
};
ostream &operator<<(ostream& os, const mint& x) {
  os << x.x;
  return os;
}
class modutils {
  vector<mint> fact, invfact;
public:
  modutils(int n = 200005):fact(n+1),invfact(n+1) {
    fact[0] = 1;
    for(int i=1; i<=n; i++) fact[i] = fact[i-1] * i;
    invfact[n] = fact[n].inv();
    for(int i=n; i>=1; i--) invfact[i-1] = invfact[i] * i;
  }
  mint pow(mint x, ll n) {
    return x.pow(n);
  }
  mint comb(ll n, ll k) {
    if(n<0 || k<0 || n<k) return 0;
    return fact[n] * invfact[k] * invfact[n-k];
  }
  mint perm(ll n, ll k) {
    if(n<0 || k<0 || n<k) return 0;
    return fact[n] * invfact[n-k];
  }
  mint fac(ll n) {
    return fact[n];
  }
};
modutils mutil;

int N, K;
vector<int> G[100005];
mint ret;

void dfs(int now, int parent){
  if(parent == -1){
    int x = G[now].size();
    ret *= mutil.perm(K-1, x);

    rep(i,G[now].size()){
      dfs(G[now][i], now);
    }
  }else{
    int x = G[now].size() - 1;
    if(x == 0) ret;
    ret *= mutil.perm(K-2, x);

    rep(i,G[now].size()){
      if(G[now][i] == parent) continue;
      dfs(G[now][i], now);
    }
  }
}


int main(){
  cin >> N >> K;
  rep(i,N-1){
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  ret = mint(K);

  dfs(1,-1);

  cout << ret << endl;
  
  return 0;
}



Measured memory_bytes: 13568
input_line = input()
temp = input_line.split()
H = int(temp[0])
N = int(temp[1])

input_A = input()
A = input_A.split()
A = [int(x) for x in A]

sum_A = sum(A)
if sum_A >= H:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 14552
//第8回シンデレラガール総選挙は是非本田未央ちゃんに投票をお願いします！
//ファンのことも他のアイドルの子たちのことも本当に大事にしてて、今まで周りに色んなものを与えてくれました。
//今度は私たちが未央ちゃんにお返しをする番です。みんなでガラスの靴を履かせてあげましょう！
// #本田未央を一番星に #本田未央を令和のシンデレラガールに #第8回シンデレラガール総選挙
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint x[100100],p[100100];
int main()
{
	int n;lint s,out=0;
	cin>>n>>s;
	rep(i,n) cin>>x[i]>>p[i];
	int lo=0,hi=n-1,f=-1;
	while(x[hi]>s && x[lo]<s){
		if(p[hi]>p[lo]){
			if(f!=0) out+=x[hi]-x[lo];
			f=0;
			p[hi]+=p[lo];
			lo++;
		}
		else{
			if(f!=1) out+=x[hi]-x[lo];
			f=1;
			p[lo]+=p[hi];
			hi--;
		}
	}
	//cout<<out<<' '<<lo<<' '<<hi<<endl;
	if(x[hi]<s) out+=s-x[lo];
	else out+=x[hi]-s;
	cout<<out<<endl;
}


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

int main(){
  int N;
  cin >> N;
  int d[N];
  for (int i; i<N; i++) {
    cin >> d[i];
  }
  
  int sum;
  int x=0;
  int y=0;
  
  for (int i; i<N; i++) {
    x += d[i];
    y += d[i]*d[i];
  }
  
  sum = (x*x - y)/2;
  
  cout << sum << endl;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
c = [0 for i in range(N)]

for i in range(N):
  c[A[i] - 1] += 1

ans = [c[i] * (c[i] - 1) // 2 for i in range(N)]
s = sum(ans)

for val in A:
  m = c[val - 1] - 1
  print(s - m)


Measured memory_bytes: 24748
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int main (void){
  int N,K;
  double ans=0,base=1;
  scanf("%d\n",&N);
  scanf("%d\n",&K);


for (int i = N; i >= 1; i--) {
  while(i<K&&K>1) {
    base*=0.5;
    K-=K/2;
    //printf("%d\n", K);
  }
  //printf("+%lf\n",(double)1*base/N);
  ans+=(double)1*base/N;
}

printf("%.16lf\n",ans );
  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#define mod 1000000007

int max(int a,int b){
  if(a > b){
    return a;
  }
  return b;
}

int main(void){
  int N,M;
  scanf("%d%d",&N,&M);
  const int maximam = max(N,M);
  long long fact[maximam+1];
  long long ans;

  fact[1] = 1;
  for(int i = 2;i < maximam+1;i++){
    fact[i] = fact[i-1]*i;
    fact[i] %= mod;
  }

  if(abs(M-N) > 1){
    printf("0\n");
    return 0;
  }

  if(N == M){
    ans = fact[N]*fact[M];
    ans %= mod;
    ans *= 2;
    ans %= mod;
  }else{
    ans = fact[N]*fact[M];
    ans %= mod;
  }

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

Measured memory_bytes: 896
#include<iostream>
using namespace std;
int main(){
  int i,j,k;
  int r,c;
  int b;
  cin >> r >> c;
  int rsum[100]={};
  int csum[100]={};
  int sum=0;
  for(i=0;i<r;i++){
    cin >> b;
    cout << b;
    rsum[i]+=b;
    csum[0]+=b; 
    for(j=1;j<c;j++){
      cin >> b;
      cout <<" " << b;
      rsum[i]+=b;
      csum[j]+=b; 
    }
    cout << " " << rsum[i] << endl;
    sum+=rsum[i];
  }
  cout << csum[0];
  for(j=1;j<c;j++){
    cout << " " << csum[j];    
  }
  cout << " " << sum <<  endl;
  return 0;
}



Measured memory_bytes: 3092
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;

bool isEven(int x){
    if(x%2==0)return true;
    else return false;
}

int main(){
    int A,B,C,ans=0,bA,bB,bC,hA,hB,hC;
    cin>>A>>B>>C;
    bA=A;
    bB=B;
    bC=C;
    if(!isEven(A)||!isEven(B)||!isEven(C)){
        ans =0;
    }else{

        while(1){

        hA=A/2;
        hB=B/2;
        hC=C/2;

        A=hB+hC;
        B=hA+hC;
        C=hA+hB;

        ans++;

        if(!isEven(A)||!isEven(B)||!isEven(C))break;

        if(A==bA&&B==bB&&C==bC){
            ans=-1;
            break;
        }
        }
    }

    cout<<ans<<endl;

    return 0;
    
}

Measured memory_bytes: 256
S = input()
K = int(input())

if len(S) == 1:
    print(K//2)
    exit()

if len(set(S)) == 1:
    ans = len(S)*K//2
    print(ans)
    exit()

if S[0] != S[-1]:
    ans = 0
    tmp = ""
    for s in S:
        if s == tmp:
            ans += 1
            tmp = ""
            continue
        else:
            tmp = s
    ans *= K
    print(ans)
    exit()
elif S[0] == S[-1]:
    A = 0
    B = 0
    for s in S:
        if s == S[0]:
            A+=1
        else:
            break
    for s in S[::-1]:
        if s == S[0]:
            B+=1
        else:
            break
    ans = 0
    tmp = ""
    for s in S:
        if s == tmp:
            ans += 1
            tmp = ""
            continue
        else:
            tmp = s
    ans *= K
    ans = ans - (A//2 + B//2)*(K-1) + (A+B)//2*(K-1)
    print(ans)
    exit()


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<cctype>
#include <stdio.h>
using namespace std;

int main(){
    while(1){
        string str;
        cin >> str;
        if(str == "0") break;
        int sum = 0;
        for(int i=0; i<str.size(); i++){
            sum += str[i] - '0';
        }
        cout << sum << endl;
    }
    return 0;
} 

Measured memory_bytes: 3172