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

#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

char S[4];

int main()
{
  int cnt;
  int i;

  cnt = scanf("%s", &S);

  for(i=1; i<4; i++) {
    if (S[i] == S[i - 1]) {
      printf("Bad");
      return 0;
    }
  }
  
  printf("Good");
  
  return 0;
}



Measured memory_bytes: 128
#!/usr/bin/env python3

N, M = map(int, input().split())
H = list(map(int, input().split()))
X = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    X[A-1].append(B)
    X[B-1].append(A)

ans = set()

for i in range(N):
    if len(X[i]) == 0:
        ans.add(i)
    else:
        if all(H[i] > H[j-1] for j in X[i]):
            ans.add(i)

print(len(ans))

Measured memory_bytes: 38632
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <list>
#include <functional>
#include <numeric>
#include <stack>
#include <tuple>

using namespace std;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
const int INF = 100000000;
const long long LINF = 1000000000000000000;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-6;
using pii = std::pair<int, int>;
using ll=long long;  
using pLL = std::pair<ll, ll>;

#define SORT(v) std::sort(v.begin(), v.end())
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N ,K,ct1=0,ct2=0,ct3=0,ct4=0;
    for(int i=0;i<3;++i){
        cin >> N >> K;
        if(N==1){
            ct1++;
        }else if(N==2){
            ct2++;
        }else if(N==3){
            ct3++;
        }else if(N==4){
            ct4++;
        }
        
        if(K==1){
            ct1++;
        }
        if(K==2){
            ct2++;
        }
        if(K==3){
            ct3++;
        }
        if(K==4){
            ct4++;
        }
    }
    if((ct1==1&&ct2==1&&ct3==2&&ct4==2)||(ct1==1&&ct2==2&&ct3==1&&ct4==2)||(ct1==1&&ct2==2&&ct3==2&&ct4==1)
        ||(ct1==2&&ct2==1&&ct3==1&&ct4==2)||(ct1==2&&ct2==1&&ct3==2&&ct4==1)||(ct1==2&&ct2==2&&ct3==1&&ct4==2)){
        cout << "YES";
    }else{
        cout << "NO";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(raw_input())
A = sorted(map(int, raw_input().split()))
ans = 1
for i in range(N):
    if A[i] == 2*((i + N%2) / 2) + (1 - N % 2):
        if i % 2 == 1:
            ans = (ans * 2) % (10**9 + 7)
    else:
        ans = 0
        break
print ans

Measured memory_bytes: 11328
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <cstring>
#include <cctype>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <complex>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for(int i = a; i < (int)b; i++)
const int INF = 1<<28;

bool com(const pair<int, pair<int, int> >& left, const pair<int, pair<int, int> >& right) {
	if(left.second.first == right.second.first) {
		if(left.second.second == right.second.second)
			return left.first < right.first;
		else
			return left.second.second < right.second.second;
	}
	else
		return left.second.first > right.second.first;
}

int main() {
	int T, P, R;
	while(cin >> T >> P >> R, T|P|R) {
		vector< pair<int, pair<int, int> > > vp;
		multiset<int> w;
		REP(i, T)
			vp.push_back(make_pair(i+1, make_pair(0, 0)));
		REP(j, R) {
			int tid, pid, time;
			string message;
			cin >> tid >> pid >> time >> message;
			if(message == "CORRECT") {
					vp[tid-1].second.first++;
					vp[tid-1].second.second += w.count(tid * 100 + pid) * 1200 + time;
			}
			else if(message == "WRONG")
				w.insert(tid * 100 + pid);
		}
		sort(vp.begin(), vp.end(), com);
		REP(i, vp.size())
			cout << vp[i].first << ' ' << vp[i].second.first << ' ' << vp[i].second.second << endl; 
	}
	return 0;
}

Measured memory_bytes: 3228
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <sstream>
#include <set>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define repp(i,k,n) for(int i=k;i<(int)n;i++)
#define rei(n) for(int i=0;i<(int)n;i++)
#define rel(n) for(int l=0;l<(int)n;l++)
#define al(s) s.begin(),s.end()
#define INT_MAX 2147483647
#define debug(x) cout<<#x<<": "<<x<<endl;
#define PI 2*acos(0,0)
#define pb push_back
#define inin(x) int x; cin>>x;
struct Calendar
{
	long long year;
	long long month;
	long long day;
	long long dat[2][13];
	Calendar(long long y, long long m, long long d)
	{
		year = y;
		month = m;
		day = d;
		dat[0][0] = dat[1][0] = 0;
		dat[0][1] = dat[1][1] = 31;
		dat[0][2] = dat[1][2] = 28;
		dat[0][3] = dat[1][3] = 31;
		dat[0][4] = dat[1][4] = 30;
		dat[0][5] = dat[1][5] = 31;
		dat[0][6] = dat[1][6] = 30;
		dat[0][7] = dat[1][7] = 31;
		dat[0][8] = dat[1][8] = 31;
		dat[0][9] = dat[1][9] = 30;
		dat[0][10] = dat[1][10] = 31;
		dat[0][11] = dat[1][11] = 30;
		dat[0][12] = dat[1][12] = 31;
		dat[1][2] = 29;
	}
	int uruu()
	{
		if (year % 4 == 0)
		{
			if (year % 400 != 0 && year % 100 == 0)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
		return 0;
	}
	int uruu(long long y)
	{
		if (y % 4 == 0)
		{
			if (y % 400 != 0 && y % 100 == 0)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
		return 0;
	}
	long long pday(long long d)
	{
		day += d;
		for (;; month++)
		{
			if (month >= 13)
			{
				year++;
				month = 1;
			}

			if (dat[uruu()][month] < day)
			{
				day -= dat[uruu()][month];
			}
			else
			{
				break;
			}
		}
		pmonth(0);
		return d;
	}
	long long pmonth(long long m)
	{
		month += m;
		for (;; year++)
		{
			if (month > 12)
			{
				month -= 12;
			}
			else
			{
				break;
			}
		}
		return m;
	}
	long long pyear(long long y)
	{
		year += y;
		return y;
	}
	long long dif(Calendar c)
	{
		long long ans = 0;
		Calendar a(year, month, day);
		ans -= a.day;
		ans += c.day;
		a.day = 0;
		c.day = 0;
		for (; a.month >= 1; a.month--)
		{
			ans -= dat[a.uruu()][a.month-1];
		}
		for (; c.month >= 1; c.month--)
		{
			ans += dat[c.uruu()][c.month-1];
		}
		for (; a.year != c.year; a.year++)
		{
			ans += 365;
			if (a.uruu())ans++;
		}
		return ans;
	}


};



int main()
{
	int ans = 0;
	int x;
	rei(10)
	{
		cin >> x;
		ans += x;
	}
	cout << ans << endl;
}

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


int a,b,answer;
int main(){
	cin>>a>>b;
	answer+=max(a,b);
	if(a>=b){
		a--;
	}else{
		b--;
	}
	answer+=max(a,b);
	if(a>=b){
		a--;
	}else{
		b--;
	}
	cout<<answer<<endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod;
ll n,a,b,c,d;
string s;
int main(){
  cin>>n>>a>>b>>c>>d>>s; a--,b--,c--,d--;
  bool ok=1;
    for(int i=a;i+1<c;i++){
      if(s[i]=='#'&&s[i+1]=='#')ok=0;
    }
    for(int i=b;i+1<d;i++){
      if(s[i]=='#'&&s[i+1]=='#')ok=0;
    }
  if(c>d){
    bool t=0;
    for(int i=b;i<=d;i++){
      if(s[i-1]=='.'&&s[i]=='.'&&s[i+1]=='.')t=1;
    }
    ok&=t;
  }
   cout<<(ok?"Yes":"No")<<endl;
  return 0;
}


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

string a, b;

int main() {
    cin >> a >> b;
    for(int i = 1; i <= 105; ++i) {
        if(a == b) return !printf("Yes");
        char ret = a.back(); a.pop_back();
        a = ret + a;
    }
    puts("No");
}

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

signed main(){
  string S,T;
  cin>>S>>T;
  int SS=S.size(),TS=T.size();
  int ans=TS;
  for(int i=0;i<=SS-TS;i++){
    int num=0;
    for(int j=0;j<TS;j++){
      if(S[i+j]!=T[j])num+=1;
    }
    ans=min(ans,num);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3656
/*
██╗  ██╗ █████╗ ██████╗ ███████╗███████╗███╗   ███╗        ██╗  ██╗██╗  ██╗ █████╗ ██╗     ███████╗██████╗
██║ ██╔╝██╔══██╗██╔══██╗██╔════╝██╔════╝████╗ ████║        ██║ ██╔╝██║  ██║██╔══██╗██║     ██╔════╝██╔══██╗
█████╔╝ ███████║██████╔╝█████╗  █████╗  ██╔████╔██║        █████╔╝ ███████║███████║██║     █████╗  ██║  ██║
██╔═██╗ ██╔══██║██╔══██╗██╔══╝  ██╔══╝  ██║╚██╔╝██║        ██╔═██╗ ██╔══██║██╔══██║██║     ██╔══╝  ██║  ██║
██║  ██╗██║  ██║██║  ██║███████╗███████╗██║ ╚═╝ ██║███████╗██║  ██╗██║  ██║██║  ██║███████╗███████╗██████╔╝
╚═╝  ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝╚══════╝╚══════╝╚═╝     ╚═╝╚══════╝╚═╝  ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝╚══════╝╚══════╝╚═════╝
Believe in yourself ,( try and try and then try ), You can do it
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
#define endl "\n"
#define Ceil(x,y) ((x+y-1)/y)
#define clr(arr, x) memset(arr, x, sizeof arr)
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define rt(s) return cout<<s,0
#define watch(x) cout<<(#x)<<" = "<<x<<endl
#define sz(s)	(int)(s.size())
#define OO 0x3f3f3f3f3f3f3f3fLL
const int oo = 0x3f3f3f3f, Mod = 1e9 + 7;
using namespace std;
typedef long long ll;
int dx[] { 1, -1, 0, 0, 1, 1, -1, -1 };
int dy[] { 0, 0, 1, -1, 1, -1, 1, -1 };
void K_K(){ 
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
 

int main(){
	K_K();
	int h1, m1, h2, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;
	int h = h1 * 60 + m1 + k;
	cout << (h2 * 60 + m2) - h;
}

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

int main(){
	int N, i;
	double A, ans = 0;
	scanf("%d", &N);
	for(i = 0; i < N; i++){
		scanf("%lf", &A);
		ans += 1 / A;
	}
	ans = 1 / ans;
	printf("%.10lf\n", ans);
	return 0;
}

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

ll inf=9223372036854775806;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	int i,n,a[100000],m,t,ans=0;
	cin>>n;
	for (i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	for (i=0;i<n;i++){
		if (i==0){
			t=1;
			m=a[i];
		}
		else {
			if (a[i]==m){
				t++;
			}
			else {
				if (m>t){
					ans+=t;
				}
				else {
					ans+=t-m;
				}
				t=1;
				m=a[i];
			}
		}
	}
	if (m>t){
		ans+=t;
	}
	else{
		ans+=t-m;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 640
//Name: (iwi)
//Level: 2
//Category: 文字列,アドホック,Ad-hoc
//Note:

/**
 * 文字列を両端から読んでいき、線対称になっていなければどちらか片方を変更すればよい。
 *
 * オーダーは O(|S|)。
 */
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

bool solve() {
    string s;
    if(!(cin >> s)) return false;

    int l = 0, r = (int)s.size()-1;
    int ans = 0;
    while(l <= r) {
        if((s[l] == 'i' && s[r] == 'i') ||
           (s[l] == 'w' && s[r] == 'w') ||
           (s[l] == '(' && s[r] == ')') ||
           (s[l] == ')' && s[r] == '(')) {
        } else {
            ans++;
        }
        l++;
        r--;
    }
    cout << ans << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

Measured memory_bytes: 1184
n = int(input())
s = input()
lis = [[0, 0], [0, 1], [1, 0], [1, 1]]
for c in s:
    c = 0 if c=='o' else 1
    for li in lis:
        li.append(li[-1]^li[-2]^c)
for li in lis:
    if li[0]==li[-2] and li[1]==li[-1]:
        ans = ['W' if i else 'S' for i in li[1:-1]]
        print(''.join(ans))
        break
else:
    print(-1)

Measured memory_bytes: 13980
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;

int main(){

  int n;
  cin >> n;
  int t[n];
  for (int i = 0;i < n; i ++){
    cin >> t[i];
  }
  int m;
  cin >> m;
  int p, x;
  int ans[m];
  for (int i = 0; i < m; i++){
    int a = 0;
    cin >> p >> x;
    for (int j = 0; j < n; j++){
      if (j == (p - 1)){
        a += x;
      }
      else {
        a += t[j];
      }
    }
    ans[i] = a;
  }

  for (int i = 0; i < m; i++){
    cout << ans[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<ctype.h>

int main() {
  char c;
 
  scanf("%s", &c);
  
  if(islower(c) == 0) {
    
    printf("A");
    
  } else {
    
    printf("a");
    
  }
  
  return 0;
}

Measured memory_bytes: 1596
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define V 21000
struct edge{int to, cap, rev;};
vector<edge> G[V];
bool used[V];

void add_edge(int from, int to, int cap){
	G[from].push_back((edge){to, cap, G[to].size()});
	G[to].push_back((edge){from, 0, G[from].size()-1});
	//G[to].push_back((edge){from, cap, G[from].size()-1});
}

int dfs(int v, int t, int f){
	if(v==t) return f;
	used[v] = true;
	for(int i = 0; i < G[v].size(); i++){
		edge &e = G[v][i];
		if(!used[e.to] && e.cap > 0){
			int d = dfs(e.to, t, min(f, e.cap));
			if(d>0){
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int s, int t){
	int flow = 0;
	while(1){
		memset(used, 0, sizeof(used));
		int f = dfs(s, t, INF);
		if(f==0) return flow;
		flow += f;
	}
}

#define N 101
int h, w;
string g[N];

int main(){
	cin>>h>>w;
	int nn = h*w;
	rep(i, h) cin>>g[i];
	int s, t;
	rep(i, h) rep(j, w){
		if(g[i][j]=='S') s = i*w+j;
		if(g[i][j]=='T') t = i*w+j;
	}
	if(s%w==t%w || s/w==t/w){
		cout<<-1<<endl;
		return 0;
	}
	s += nn;
	rep(i, h) rep(j, w){
		if(g[i][j]=='.') continue;
		add_edge(i*w+j, i*w+j+nn, 1);
		rep(k, j){
			if(g[i][k]!='.'){
				add_edge(i*w+j+nn, i*w+k, INF);
				add_edge(i*w+k+nn, i*w+j, INF);
			}
		}
	}
	rep(j, w) rep(i, h){
		if(g[i][j]=='.') continue;
		rep(l, i){
			if(g[l][j]!='.'){
				add_edge(i*w+j+nn, l*w+j, INF);
				add_edge(l*w+j+nn, i*w+j, INF);
			}
		}
	}
	cout<<max_flow(s, t)<<endl;
	return 0;
}


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

const long long inf = (long long) 1e18;

int A[16][16];
long long cost[(1<<16)+5], dp[(1<<16)+5];

long long solve(int mask)
{
    if(mask == 0)
        return 0;
    
    if(dp[mask] != -1)
        return dp[mask];
    
    long long ans = cost[mask];
    
    for(int i = mask; i > 0; i = (i-1) & mask)
    {
        if(i == mask)
            continue;
        
        ans = max(ans, solve(i) + solve(mask ^ i));
    }
    
    return dp[mask] = ans;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    
    int N;
    cin >> N;
    
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> A[i][j];
    
    for(int i=0; i<(1<<N); i++)
    {
        for(int j=0; j<N; j++)
        {
            if(!(i & (1 << j)))
                continue;
            
            for(int k=j+1; k<N; k++)
                if(i & (1 << k))
                    cost[i] += A[j][k];
        }
    }
    
    memset(dp, -1, sizeof(dp));
    
    cout << solve((1 << N)-1) << "\n";
    return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <utility>
#include <iomanip>
#include <climits>
using namespace std;
#define ll long long
#define MOD 1000000007
#define MAX 1000000000000000000
#define ln "\n"
#define pb push_back
#define pll pair<ll,ll>
#define mp make_pair
#define f first
#define s second
#define Test ll t;cin>>t; while(t--)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
int main() 
{
	fast_io;
	ll r;
	cin>>r;
	cout<<(r*r);
	return 0;
}

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

int main(void){
    long int a,b,c;
    scanf("%ld %ld %ld",&a,&b,&c);
    long int d=c-a-b;
    if(4*a*b<d*d && d>0){
        printf("Yes");
    }
    else{
        printf("No");
    }

    return 0;
}

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

#define rep(i,n) for(ll i=0;i<ll(n);i++)
#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
const double pi = 3.14159265358979;



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

    ll x;
    cin >> x;

    ll n = x/11;
    ll m = x%11;

    if (m == 0){
        cout << 2*n << endl;
    }
    else if (m <= 6){
        cout << 2*n+1 << endl;
    }
    else{
        cout << 2*n+2 << endl;
    }
}

Measured memory_bytes: 3636
#include <iostream>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <stdio.h> 
#include <map>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
	long long n;
	cin>>n;
	
	//map<long long, pair<long long, pair<long long, long long> > > mp;
	vector<pair<long long, long long> > v;
	//mp[1] = make_pair(1,make_pair(1,1));
	//mp[2] = make_pair(2,make_pair(3,3));
	//mp[4] = make_pair(4,make_pair(7,7));
	//mp[8] = make_pair(8,make_pair(15,15));
	long long num = 1;
	while(true) {
		if(num > 1099511627779LL) {
			break;
		}
		v.push_back(make_pair(num, (num*2LL)-1));
		//mp[num] = make_pair(num, make_pair((num*2LL)-1, (num*2LL)-1));
		num = num * 2LL;
	}
	
	/*for (map<long long, pair<long long, pair<long long, long long> > >::iterator it = mp.begin(); it!=mp.end(); it++) {
		//cout << it->first <<" "<<it->second.second.first <<"=>>"<<(it->first >= n)<<endl;
		if(it->first >=n && n<=it->second.second.first) {
			cout << it->second.second.first;
			break;
		}
	}*/
	
	for (int i=v.size()-1; i>=0; i--) {
		if(v[i].second==n) {
			cout << v[i].second;
			break;
		} else if(v[i].second < n) {
			cout << v[i+1].second;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
vector<long long int> tree[100001];
pair<long long int, long long int> dp[100001];

const long long int mod = 1e9 + 7;
void foo(long long int r, long long int p)
{
    bool fg = 0;
    for (long long int i = 0; i < tree[r].size(); ++i)
    {
        if(tree[r][i] == p) continue;
        foo(tree[r][i], r);
        fg = 1;
    }

    if(!fg)
    {
        dp[r].first = 1;
        dp[r].second = 1;
        return;
    }
    
    dp[r].first = 1;
    dp[r].second = 1;
    for (long long int i = 0; i < tree[r].size(); ++i)
    {
        if(tree[r][i] == p) continue;

        dp[r].first *= dp[tree[r][i]].second;
        dp[r].second *= (dp[tree[r][i]].second + dp[tree[r][i]].first) % mod;
        dp[r].first %= mod;
        dp[r].second %= mod;
        
    }


}
int main()
{
    long long int n;
    cin >> n;
    for (long long int i = 0; i < n-1; ++i)
    {
        long long int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    foo(1, 0);
    cout << (dp[1].first + dp[1].second) % mod;

    return 0;
}

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

int main() {
  int n = 0;
  cin >> n;
  int s = 0;
  if (n%1000 == 0) {
    s = n/1000;
  } else {
    s = (n/1000)+1;
  }
  
  cout << s*1000-n << endl;
}

Measured memory_bytes: 3608
N = int(input())
A = list(map(int, input().split()))
S = set()
sa = 0
for i in A:
    a = i // 400
    if a < 8:
        S.add(a)
    else:
        sa += 1
ans1 = max(len(S), 1)
ans2 = len(S) + sa
print(ans1, ans2)


Measured memory_bytes: 9192
using System;
using System.Collections.Generic;
using System.Windows;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    public class Program
    {
        private static long mod = 1000000007;
        private static long max = 999999999999;

        static void Main(string[] args)
        {
            var s = Read();
            var t = Read();
            var count = 0L;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] != t[i])
                {
                    count++;
                }
            }
            WriteRead(count);
        }

        public static string Read()
        {
            return Console.ReadLine();
        }

        public static string[] ReadSplit()
        {
            return Console.ReadLine().Split(' ');
        }

        public static void WriteRead(object str)
        {
            Console.WriteLine(str);
            Read();
        }

        public static void Write(object str)
        {
            Console.WriteLine(str);
        }

        private static bool ChangeMin<T>(ref T a, T b) where T : IComparable
        {
            if (a.CompareTo(b) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }

        private static bool ChangekMax<T>(ref T a, T b) where T : IComparable
        {
            if (b.CompareTo(a) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }
    }
}


public static class Extentions
{
    public static int Int(this object obj)
    {
        return int.Parse(obj.ToString());
    }

    public static long Long(this object obj)
    {
        return long.Parse(obj.ToString());
    }

    public static decimal Decimal(this object obj)
    {
        return decimal.Parse(obj.ToString());
    }

    public static double Double(this object obj)
    {
        return double.Parse(obj.ToString());
    }

    public static T2 GetValueZero<T1, T2>(this Dictionary<T1, T2> d, T1 key) where T2 : struct
    {
        T2 value;
        if (d.TryGetValue(key, out value))
        {
            return value;
        }
        return new T2();
    }
}



Measured memory_bytes: 18216
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  //a
  int x, a;
  cin >> x >> a;
  cout << (bool) (x >= a) * 10 << endl;
  return 0;
}

Measured memory_bytes: 256
while 1:
    n=int(input())
    if n==0:break
    count=0
    member=[0]*4001
    mem_check=[]
    mem_check2=[]
    for i in range(n):
        e,p,q=map(int,input().split())
        member[e]+=p*q
        mem_check.append(e)
    for i in mem_check:
        if not(i in mem_check2):
            if member[i]>=1000000:
                print(i)
                count+=1
                mem_check2.append(i)
    if count==0:
        print("NA")


Measured memory_bytes: 5828
N = int(input())
CSF = []
for _ in range(N - 1):
    c, s, f = map(int, input().split())
    CSF.append((c, s, f))
for i in range(N):
    t = 0
    for c, s, f in CSF[i:]:
        t = max(t, s)
        t = ((t - 1) // f + 1) * f
        t += c
    print(t)


Measured memory_bytes: 3188
import math

a, b, h, m = map(int, input().split())

aa = h/6 * math.pi + (m/30 * math.pi)/12
bb = m/30 * math.pi
kakudo = max(aa, bb) - min(aa, bb)
x = a**2 + b**2 - 2*a*b*math.cos(kakudo)
print(math.sqrt(x))

Measured memory_bytes: 9460
class Checker:
    d = {
        1: { 2: (3,4,5,6), 3: (5,2,4,6), 4: (2,5,3,6), 5: (4,3,2,6) },
        2: { 1: (4,3,6,5), 3: (1,6,4,5), 4: (6,1,3,5), 6: (3,4,1,5) },
        3: { 1: (2,5,6,4), 2: (6,1,5,4), 5: (1,6,2,4), 6: (5,2,1,4) },
        4: { 1: (5,2,6,3), 2: (1,6,5,3), 5: (6,1,2,3), 6: (2,5,1,3) },
        5: { 1: (3,4,6,2), 3: (6,1,4,2), 4: (1,6,3,2), 6: (4,3,1,2) },
        6: { 2: (4,3,5,1), 3: (2,5,4,1), 4: (5,2,3,1), 5: (3,4,2,1) }
        }

    def __init__(self, s):
        l = s.split()
        self.tbl = {}
        for c,i in zip(l, range(1,7)):
            if c in self.tbl:
                self.tbl[c].append(i)
            else:
                self.tbl[c] = [i]
        self.pip = dict(zip(range(1,7), l))

    def __call__(self, s):
        l = s.split()

        if not (l[0] in self.tbl):
            return False
        if not (l[1] in self.tbl):
            return False

        for i0 in self.tbl[l[0]]:
            for i1 in self.tbl[l[1]]:
                if i1 in self.d[i0]:
                    for i,j in zip(self.d[i0][i1], range(2,6)):
                        if self.pip[i] != l[j]:
                            break
                    else:
                        return True
        return False

def g():
    n = int(input()) - 1
    c = Checker(input())
    for _ in range(n):
        yield c(input())

if any(g()):
    print("No")
else:
    print("Yes")

Measured memory_bytes: 7956
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;

bool is_prime(int x){
    if(x <= 1) return false;
    for(int i = 2; i * i < x; ++i) if(x % i == 0) return false;
    return true;
}

int main()
{
    int x;
    cin >> x;
    int p = x;
    while(!is_prime(p)) p++;
    cout << p << endl;
    return 0;
}

Measured memory_bytes: 3592
import java.util.*;
public class Main{
	public static void main(String [] args){
		Scanner sc = new Scanner (System.in);
		int n = sc.nextInt(); 
		int Rt [] = new int[n];
        for(int i = 0; i < n; i++) {
			Rt[i] = sc.nextInt();
		}
		int Rmax = Integer.MIN_VALUE;
        int Rmin = Rt[0];
		
		for(int j = 1; j < n; j++) {
			Rmax = Math.max(Rmax, Rt[j] - Rmin);
			Rmin = Math.min(Rmin, Rt[j]);
		}
		System.out.println(Rmax);
	}
}

Measured memory_bytes: 100876
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	string s;
	std::cin >> s;
	if (s[2] == s[3] && s[4] == s[5]) {
		std::cout << "Yes" << endl;
	}
	else {
		std::cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
*B="[>]\0%p_\0B$`\0jFc";*F=" %d %d %d\n\0 pre-meiji\0  taisho\0 showa\0  heisei";y,m,d;main(e){for(;~scanf(F,&y,&m,&d);e?printf(F,y-B[e-1]/3271+1,m,d,printf(F+e*2+2)):puts(F+3))for(e=0;e<4&&y*3271+m*64+d>B[e];e++);}

Measured memory_bytes: 0
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<math.h>
using namespace std;

int main(){
    int i, j, k, n,m;
    int c=0;
    double kk;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>j;
        n = n - j;
    }

    if(n<0) cout<<-1<<endl;
    else cout<<n<<endl;

}



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

const int d = 365;
int main() {
  vector<int> c(26);
  for (int i = 0; i < 26; i++) {
    cin >> c[i];
  }
  vector<vector<int>> s(d, vector<int>(26));
  for (int i = 0; i < d; i++) {
    for (int j = 0; j < 26; j++) {
      cin >> s[i][j];
    }
  }

  vector<int> t(26);
  for (int i = 0; i < 26; i++) {
    t[i] = i + 1;
  }

  for (int i = 0; i < d; i++) {
    cout << t[rand() % 26] << endl;
  }

  return 0;
}


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

long long MOD = 1e9+7;
int MAX_INT = 1e9;

// 最大公約数
long long gcd(long long a, long long b){
  if(b == 0) return a;
  return gcd(b, a % b);
}
// 最小公倍数
long long lcm(long long a, long long b) {
  return a / gcd(a, b) * b;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, X, T;
  cin >> N >> X >> T;

  cout << ((N + (X - 1)) / X) * T << endl;

  return 0;
}


Measured memory_bytes: 3608
import itertools
A = list(range(10))
A_sum = []
A_pair = list(itertools.product(A,repeat=4))
for i in range(len(A_pair)):
    A_sum.append(sum(A_pair[i]))

while True:
    try:
        n = int(input())
    except:
        break
    if 36<n:
        print(0)
    else:
        print(A_sum.count(n))


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

int main(){
    int k;cin>>k;
    int t=7%k,i=1,ans;
    int Check[k]={0};
    while(true){
        if(t==0){ans=i;break;}
        if(Check[t]==1){ans=-1;break;}
        Check[t]=1;
        t=10*t+7;
        t%=k;
        i++;
    }
    cout<<ans<<endl;
}

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

#define ll long long
#define pb push_back

const int maxn = 1e6 + 20;
const int mod = 998244353;

int fac[maxn] , caf[maxn];

int bpw(int a , int b)
{
	if(!b)
		return 1;
	int x = bpw(a , b / 2);

	x = 1LL * x * x % mod;
	if(b&1)
		x = 1LL * x * a % mod;

	return x;
}

inline void mkay(int &a)
{
	if(a >= mod)
		a -= mod;
	else if(a < 0)
		a += mod;
}

int c(int s , int r)
{
	if(r > s || r < 0)
		return 0;

	return (1LL * fac[s] * caf[r] % mod) * caf[s - r] % mod;
}

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

	fac[0] = 1;
	for(int i = 1; i < maxn; i++)
		fac[i] = 1LL * fac[i - 1] * i % mod;

	caf[maxn - 1] = bpw(fac[maxn - 1] , mod - 2);
	for(int i = maxn - 1; i > 0; i--)
		caf[i - 1] = 1LL * caf[i] * i % mod;

	int n , k;
	cin >> n >> k;

	int res = 0;
	for(int r = 0; r <= k; r++)
	{
		int b = k - r;
		if(r < b || r < n)
			continue;

		int K = n - r;
		if(r == b)
			mkay(res += c(k - 1 , r) - c(k - 1 , r - K + 1));
		else
			mkay(res += c(k , r) - c(k , r - K + 1));
	}

	cout << res << endl;
}
























Measured memory_bytes: 8064
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
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; }
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
int n;
vector<string> a;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string temp;
        cin >> temp;
        a.push_back(temp);
    }
    int ans=0;
    for(int k=0;k<n;k++){
        bool check=false;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(a[i][(j+k)%n]!=a[j][(i+k)%n]){
                    check=true;
                }
            }
        }
        if(!check)ans++;
    }
    cout << ans*n << "\n";
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define debug(x) cerr << "\n" \
                      << #x << " = " << x << ".\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define print(xx) cout << (xx) << endl
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vint;
const int INF = ((1LL << 30) + (1LL << 29));
const ll MOD = 1000000007;

/* 
*/

//=================================================
int N;
vector<int> A;
//=================================================
void input()
{
    cin >> N;
    A = vector<int>(N + 1);
    rep(i, N)
    {
        cin >> A[i + 1];
    }
}

//=================================================
void solve()
{
    map<int, int> ans;
    vector<bool> b(N + 1);
    for (int i = N; i >= 1; --i)
    {

        int cnt = 0; // iの倍数(iを除く)で何個ボールをいれたか．
        for (int j = i * 2; j <= N; j = j + i)
        {
            if (b[j])
            {
                cnt++;
            }
        }

        if (cnt % 2 != A[i]) 
        {
            b[i] = true; // ボールを入れたフラグ.
            ans[i]++; // i番目の箱にボールをいれる．
        }
        else {
            // DO NOTHING.
            // ボールをいれない.
        }

    }

    // OUTPUT.
    cout << ans.size() << endl;
    for (auto x : ans)
    {
        cout << x.first << " ";
    }
    cout << endl;
}

//=================================================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 10496
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;

const int SAKAIME = 2048;
const int MAX_W = 100000;
const int MAX_N = 300000;

vector<vector<int>> memo(SAKAIME+1, vector<int>(MAX_W+1, 0));
vector<Pii> VW(MAX_N + 1);

int dfs(int v, int l) {
    if (v <= SAKAIME) return memo[v][l];

    int t = 0;
    if (l - VW[v].second >= 0) t = VW[v].first + dfs(v/2, l - VW[v].second);
    return max(dfs(v/2, l), t);
}

int main() {
    int N; cin >> N;
    for (int i = 1; i <= N; i++) cin >> VW[i].first >> VW[i].second;

    for (int i = 1; i <= min(SAKAIME, N); i++) {
        for (int j = 1; j <= MAX_W; j++) {
            if (j - VW[i].second >= 0) memo[i][j] = VW[i].first + memo[i/2][j-VW[i].second];
            memo[i][j] = max(memo[i/2][j], memo[i][j]);
        }
    }
    int Q; cin >> Q;
    while (Q--) {
        int v, l; cin >> v >> l;
        cout << dfs(v, l) << endl;
    }
}

Measured memory_bytes: 808568
#include<stdio.h>

int main(void)
{
	int n, x = 0;
	int tmp;
	
	scanf("%d", &n);
	
	tmp = n;
	
	while(1){
		x += n % 10;
		n = n / 10;
		if(n <= 0){
			break;
		}
	}
	
	if(tmp % x == 0){
		puts("Yes");
	}else{
		puts("No");
	}
	
	return 0;
}

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

using namespace std;

#define ll long long

int main() {
    ll n, m;
    cin >> n >> m;
    vector<bool> cor(n);
    vector<ll> wrong(n);
    ll p;
    string s;
    ll correct = 0;
    ll pen = 0;
    while (m--) {
        cin >> p >> s;
        --p;
        if (s == "AC") {
            if (!cor[p]) {
                cor[p] = 1;
                correct++;
                pen += wrong[p];
            } else {
                continue;
            }
        } else {
            wrong[p]++;
        }
    }
    cout << correct << " " << pen;

}



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

typedef unsigned long long ull;

typedef vector<char> vec;
typedef vector<vec> mat;
typedef pair<int,int> P;
typedef pair<P,mat> P1;

ull tohash(mat &A){
  
  ull res = 0;
  
  for(int i=0;i<4;i++){
    
    for(int j=0;j<4;j++){
      
      res = res * 1777771 + A[i][j];
      
    }
    
  }
  
  return res;
}

bool check(mat &A){
  
  for(int i=0;i<4;i++){
    
    for(int j=0;j<4;j++){
      
      int num = ( i * 4 + j + 1 ) % 16;
      
      if( A[i][j] != num ) return false;
      
    }
    
  }
  
  return true;
}

int yosou(mat &A){
  
  int res = 0;
  
  for(int i=0;i<4;i++){
    
    for(int j=0;j<4;j++){
      
      if( A[i][j] ){
	
	int y = ( A[i][j] - 1 ) / 4;
	int x = ( A[i][j] - 1 ) % 4;
	
	res += abs( i - y ) + abs( j - x );
	
      }
      
    }
    
  }

  return res;
}

int dijkstra(mat s){
  
  priority_queue<P1,vector<P1>,greater<P1> > Q;
  unordered_map<ull,P> memo;
    
  memo[ tohash( s ) ] = P( yosou( s ), 0 );
  
  Q.push( P1( P( yosou( s ), 0 ), s ) );
  
  while( !Q.empty() ){
    
    P1 t = Q.top(); Q.pop();
    
    int ycost = t.first.first;
    int cost = t.first.second;
    mat A = t.second;
    
    if( check( A ) == true ) return cost;
    
    //if( ycost > memo[ tohash( A ) ].first ) continue;
    
    int y, x;
    
    for(int i=0;i<4;i++){
      
      for(int j=0;j<4;j++){
	
	if( A[i][j] == 0 ) y = i, x = j;
	
      }
      
    }
    
    int dy[4] = {-1,0,1,0};
    int dx[4] = {0,1,0,-1};
    
    for(int i=0;i<4;i++){
      
      int ny = y + dy[i], nx = x + dx[i];
      
      if( ny < 0 || nx < 0 || 4 <= ny || 4 <= nx ) continue;
      
      swap( A[y][x], A[ny][nx] );
      
      int ncost = cost + 1;
      int nycost = ncost + yosou( A );
      
      if( nycost > 45 ){
	swap( A[y][x], A[ny][nx] );
	continue;
      }
      
      ull hash = tohash( A );
      
      if( !memo.count( hash ) ){
	
	memo[ hash ] = P( nycost, ncost );
	Q.push( P1( P( nycost, ncost ), A ) );
	
      }
      
      swap( A[y][x], A[ny][nx] );
      
    }
    
  }
  
  return 0; 
}

signed main(){
  
  mat s = mat( 4, vec( 4 ) );
  
  for(int i=0;i<4;i++){
    
    for(int j=0;j<4;j++){
      
      int a;
      cin>>a;
      
      s[i][j] = (char)a;
      
    }
    
  }
  
  cout<<dijkstra(s)<<endl;
  
  return 0;
}



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

using ll=long long;

#define error(args...) { vector<string> _debug = split(#args, ',');err(begin(_debug), args);}

vector<string> split(const string& s, char c){
	vector<string> v;stringstream ss(s);string x;
	while (getline(ss, x, c)) v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {cerr << endl;}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a,Args... args){
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " ",err(++it, args...);
}

vector<int> primes;
int p, phi;

inline int power(int a, int x){
	int b = 1;
	while(x){
		if(x & 1) b = 1LL * b * a % p;
		a = 1LL * a * a % p;
		x >>= 1; 
	}
	return b;
}

void init(){
	phi = p - 1;
	ll cur = phi;
	for(ll i = 2LL; i * i <= cur; ++i){
		if(cur % i) continue;
		ll tmp = 1LL;
		while(cur % i == 0){
			tmp *= i;
			primes.push_back(tmp);
			cur /= i;
		}
	}
	if(cur != 1) primes.push_back(cur);
}

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

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

ll calc(int val){
	int ret = 1;
	for(auto &elem:primes){
		const int tmp = power(val, phi / elem);
		if(tmp == 1){
			ret = lcm(ret, elem);
		}
	}
	return ret;
}

int ary[100010];

int main(void){

	int t;
	scanf("%ld %d", &p, &t);
	init();

	rep(loop, t){
		int k,a;
		scanf("%d", &k);
		rep(i, k) scanf("%d", ary +i);
		scanf("%d", &a);
		const ll goal = calc(a);
		const int all = p - 1;
		int period = p - 1;

		bool ok = false;
		rep(i, k){
			const ll idx = calc(ary[i]);
			period = gcd(period, idx);
		}

		if(goal % period == 0) ok = true;
		printf("%d\n", ok);
	}

	return 0;
}


Measured memory_bytes: 3648
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<complex>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef pair<int,int> pa;
typedef complex<double> E;
#define pi acos(-1)
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int l,r,o,n,a[500010];
char s[600010];
bool check(int o){
	FOR(i,1,n+1) a[i]=(s[i]!=s[i-1]);
	FOR(i,2,n){
		if (a[i]){
			if (i-o>=1) a[i]^=1,a[1]^=1;
			else if (i+o<=n+1) a[i]^=1,a[n+1]^=1;
			else return 0;
		}
	}
	return (a[1]==a[n+1]);
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	s[0]='0';
	s[n+1]='0';
	l=1,r=n;
	while (l<r){
		o=(l+r>>1)+1;
		if (check(o)) l=o;
		else r=o-1;
	}
	cout<<r<<endl;
	return 0;
}


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



int main() {
	int n,m;
	cin >> n >> m;
	cout<<n*(n-1)/2+m*(m-1)/2<<endl;
}

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

using namespace std;

#define ll long long

int dp[100001][3];

int p[100001][3], n;

int pound(int in, int st)

{

		if (dp[in][st] != -1)

				return dp[in][st];

				

		return dp[in][st] = max(pound(in - 1, (st + 1) % 3), pound(in - 1, (st + 2) % 3)) + p[in][st];

}

int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	

	memset(dp, -1, sizeof(dp));

	

	cin >> n;

	for (int i = 0; i < n; ++i) 

			cin >> p[i][0] >> p[i][1] >> p[i][2];

			

	for (int i = 0; i < 3; ++i)

			dp[0][i] = p[0][i];

			

	for (int i = 0; i < 3; ++i)

			pound(n - 1, i);

	

	cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));

	

	return 0;

}

Measured memory_bytes: 7424
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
using namespace std;

bool cells[502][502];
int lft[502][502];

int main() {
    int H, W;
    while (cin >> H >> W, H) {
        char c;
        for (int i=1; i<=H; ++i) {
            for (int j=1; j<=W; ++j) {
                cin >> c;
                cells[i][j] = c == '*';
            }
        }
        memset(lft, 0, sizeof lft);
        for (int i=1; i<=H; ++i) {
            for (int j=1; j<=W; ++j) {
                lft[i][j] = (cells[i][j] ? 0 : lft[i][j-1] + 1);
            }
        }
        int ans = 0;
        for (int i=1; i<=W; ++i) {
            stack<pair<int,int>> st;
            for (int j=1; j<=H+1; ++j) {
                int t = -1;
                while ( ! st.empty() && lft[j][i] < st.top().first) {
                    ans = max(ans, st.top().first * (j - st.top().second));
                    t = st.top().second;
                    st.pop();
                }
                if (0 < t) {
                    st.push(make_pair(lft[j][i], t));
                } else {
                    st.push(make_pair(lft[j][i], j));
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 2432
import java.io.*;
import java.math.*;
import java.util.*;





public class Main {

    static MyScanner in = new MyScanner();
    static   PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    int N;
    static int max = 200001;
    static int [] dr = {1,-1,0,0};
    static int [] dc={0,0,-1,1};
    static boolean [][] grid;
    static int [] bishopr = {-1,1,-1,1};
    static int [] bishopc = {1,1,-1,-1};
    static long H,W,cnt;
    public static void main(String args[]) throws IOException {
        int [] arr = new int[100000];
        int n = in.nextInt();
        int N = 10001;
        for(int x=1;x<=N;x++)
            for(int y=1;(x*x)+(y*y)+(x*y)<=N;y++)
                for(int z = 1;(x*x)+(y*y)+(x*y)+(z*z)+(y*z)+(z*x)<=N;z++){
                    arr[(x*x)+(y*y)+(x*y)+(z*z)+(y*z)+(z*x)]++;
                }
        for(int i=1;i<=n;i++){
            out.println(arr[i]);
        }

        out.flush();
        }
       static boolean isValid (int r, int c){
           if(r>=0&&r<H&&c>=0&&c<W){
               return true;
           }
           return false;
       }
        private static void dfs(int r, int c) {
            for(int i=0;i<4;i++){
                int nr = bishopr[i] +r;
                int nc = bishopc[i]+c;
                if(isValid(nr, nc)&&!grid[nr][nc]){
                    cnt++;
                    grid[nr][nc] = true;
                    dfs(nr, nc);
                }
            }
        }

        static boolean isEven(long a) {
            return (a&1)==0;
        }
       static  void swap (int a, int b){

        int temmp = b;
        b=a;
        a = temmp;
        }
    

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
   
        public MyScanner() {
           br = new BufferedReader(new InputStreamReader(System.in));
        }
   
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
   
        int nextInt() {
            return Integer.parseInt(next());
        }
   
        long nextLong() {
            return Long.parseLong(next());
        }
   
        double nextDouble() {
            return Double.parseDouble(next());
        }
   
        String nextLine(){
            String str = "";
        try {
           str = br.readLine();
        } catch (IOException e) {
           e.printStackTrace();
        }
        return str;
        }
  
     }
}

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s;

		StringBuilder sb  = new StringBuilder();
		while ((s = br.readLine()) != null) {
			for (int k = 1; k <= 26; k++) {
				sb = new StringBuilder();
				for (int i = 0; i < s.length(); i++) {
					if (s.charAt(i) == ' ') {
						sb.append(" ");
					} else if (s.charAt(i) == '.') {
						sb.append(".");
					} else if (s.charAt(i) + k > (int) 'z') {
						sb.append((char) ((int) 'a' - 1 + (s.charAt(i) + k - (int) 'z')));

					} else {
						sb.append((char) (s.charAt(i) + k));
					}
				}
				if (sb.indexOf("the") != -1 || sb.indexOf("this") != -1 || sb.indexOf("that") != -1) {
					break;
				}

			}
			System.out.println(sb.toString());
		}
	}

}

Measured memory_bytes: 24288
// A - September 9

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

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

	string ans;

	if (N[0] == '9' || N[1] == '9') ans = "Yes";
	else ans = "No";

	cout << ans << endl;

	return 0;
}

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

int main()
{
	int	Millennium = 1;
	for (int i = 1; i < 1000; i++)
	{
		if (i % 3 == 0)
			Millennium += 200;
		else
			Millennium += 195;
	}

	int n;
	cin >> n;
	while (n--)
	{
		int day = 0;
		int y, m, d;
		cin >> y >> m >> d;

		for (int i = 1; i < y; i++)
		{
			if (i % 3 == 0)
				day += 200;
			else
				day += 195;
		}
		if (y % 3 == 0)
		{
			day += (m - 1) * 20;
		}
		else
		{
			int EvenMonth = (m - 1) / 2;
			day += EvenMonth * 19;
			day += (m - 1 - EvenMonth) * 20;
		}
		day += d;

		cout << Millennium - day << endl;
	}

	return 0;
}

Measured memory_bytes: 1160