akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

bool finish(int n,int m,vvvi board)
{
	int dx[]={1,0,0, 1,0,1,-1,0,1, 1,-1,1,-1},
		dy[]={0,1,0, 1,1,0,1,-1,0, 1,1,-1,-1},
		dz[]={0,0,1, 0,1,1,0,1,-1, 1,1,1,1};
	rep(i,n) rep(j,n) rep(k,n) rep(l,13){
		bool flg=true;
		int x=i,y=j,z=k;
		rep(p,m){
			if(x<0 || n<=x || y<0 || n<=y || z<0 || n<=z
			|| z>=board[x][y].size() || board[x][y][z]!=board[i][j][k]){
				flg=false;
				break;
			}
			x+=dx[l],y+=dy[l],z+=dz[l];
		}
		if(flg) return true;
	}
	return false;
}

string solve(int n,int m,int p,vi rs,vi cs)
{
	vvvi board(n,vvi(n));
	rep(i,p){
		int color=i&1; // 0:black,1:white
		int r=rs[i],c=cs[i];
		board[r][c].push_back(color);
		if(finish(n,m,board))
			return string(color?"White":"Black")+" "+to_string(i+1);
	}
	return "Draw";
}

int main()
{
	for(int n,m,p;cin>>n>>m>>p && n|m|p;){
		vi rs(p),cs(p);
		rep(i,p){
			cin>>rs[i]>>cs[i];
			rs[i]--,cs[i]--;
		}
		cout<<solve(n,m,p,rs,cs)<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1272
N, M = map(int, input().split())
P = {}
for i in range(1, M+1):
    _p, _y = map(int, input().split())
    if _p not in P: 
        P[_p] = []
    P[_p].append((i, _y))

# P_i rank
numbers = {}

for _p in P:
    for j, t in enumerate(sorted(P[_p], key=lambda x: x[1])):
        numbers[t[0]] = "{:06d}{:06d}".format(_p, j+1)

for i in range(1, M+1):
    print(numbers[i])

Measured memory_bytes: 53732
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000
 
int main(){
  unsigned short *A, *B;
 
  int C[VMAX+1];
  int n, i, j;
  scanf("%d", &n);
 
  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);
 
  for ( i = 0; i <= VMAX; i++ ) C[i] = 0;
 
  for ( i = 0; i < n; i++ ){
    scanf("%hu", &A[i + 1]);
    C[A[i + 1]]++;
  }
 
  for ( i = 1; i <= VMAX; i++ ) C[i] = C[i] + C[i - 1];
 
  for ( j = 1; j <= n; j++ ){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
 
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", B[i]);
  }
  printf("\n");
 
  return 0;
}

Measured memory_bytes: 9656
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<28;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll L,R,dp[2][2];

int main(){
	cin>>L>>R;
	for(int i=60;i>=0;i--){
		ll t=1ll<<i;
		bool bl=(L&t),br=(R&t);
		ll DP[2][2]={{0,0},{0,0}};
		if(L<t*2&&t<=R) DP[t*2<=R][L<=t]=1;
		DP[1][1]+=dp[1][1]*3;
		DP[1][0]+=dp[1][0];
		if(!bl){
			DP[1][0]+=dp[1][0];
			DP[1][1]+=dp[1][0];
		}
		DP[0][1]+=dp[0][1];
		if(br){
			DP[0][1]+=dp[0][1];
			DP[1][1]+=dp[0][1];
		}
		if(!bl||br) DP[0][0]+=dp[0][0];
		if(!bl&&br){
			DP[1][0]+=dp[0][0];
			DP[0][1]+=dp[0][0];
		}
		for(int j=0;j<2;j++) for(int k=0;k<2;k++) dp[j][k]=DP[j][k]%mod;
	}
	cout<<(dp[0][0]+dp[0][1]+dp[1][0]+dp[1][1])%mod<<endl;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    char[][] s = new char[h][w];
    for (int i = 0; i < h; i++) {
      String t = sc.next();
      for (int j = 0; j < w; j++) {
        s[i][j] = t.charAt(j);
      }
    }

    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        if (s[i][j] == '.') {
          continue;
        }

        if ((i - 1) >= 0) {
          if (s[i - 1][j] == '#') {
            continue;
          }
        }

        if ((j - 1) >= 0) {
          if (s[i][j - 1] == '#') {
            continue;
          }
        }

        if ((i + 1) < h) {
          if (s[i + 1][j] == '#') {
            continue;
          }
        }

        if ((j + 1) < w) {
          if (s[i][j + 1] == '#') {
            continue;
          }
        }

        System.out.println("No");
        return;
      }
    }

    System.out.println("Yes");

  }
}

Measured memory_bytes: 35564
import math
A, B, H, M = map(int, input().split())

long = H * 30 + M * 0.5
short = M * 6
angle = abs(long-short)
if angle > 180:
  angle = 360 - angle
  
ans = A**2 + B**2 - 2*A*B*math.cos(math.radians(angle))
ans = (ans) ** (1/2)
print(ans)

Measured memory_bytes: 9584
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try(Scanner sc = new Scanner(System.in)) {
			String s = sc.next();
			ArrayDeque<String> deque = new ArrayDeque<>();
			for(int i = 0 ; i < s.length() ; i++) {
				deque.addLast(s.substring(i, i + 1));
			}
			int q = sc.nextInt();
			boolean asc = true;
			for(int i = 0 ; i < q ; i++) {
				int t = sc.nextInt();
				if(t == 1) {
					asc = !asc;
				} else {
					int f = sc.nextInt();
					String c = sc.next();
					if(f == 1) {
						if(asc) {
							deque.addFirst(c);
						} else {
							deque.addLast(c);
						}
					} else {
						if(asc) {
							deque.addLast(c);
						} else {
							deque.addFirst(c);
						}
					}
				}
			}
			int size = deque.size();
			if(asc) {
				for(int i = 0 ; i < size ; i++) {
					System.out.print(deque.pollFirst());
				}
			} else {
				for(int i = 0 ; i < size ; i++) {
					System.out.print(deque.pollLast());
				}
			}
		}

	}

}


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

int main()
{
	int d,fd;
	unsigned long int ans;
	while(cin >> d){
		ans = 0;
		int n = 600/d;
		for(int i=0;i<n;i++){
			fd = d*i;
			ans += fd*fd*d;
		}		
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			if (n == 0) {
				break;
			}
			int[] scores = new int[n];

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

			int average = 0;
			int max = checkMax(scores);
			int min = checkMin(scores);
			//System.out.println(max + " " + min);
			for (int i = 0; i < n; i++) {
				if (i == max || i == min) {
					continue;
				}
				average += scores[i];
			}
			average /= (n - 2);
			System.out.println(average);
		}
	}

	public static int checkMax(int num[]) {
		int max = -1;
		int re = -1;
		for (int i = 0; i < num.length; i++) {
			if (num[i] > max) {
				max = num[i];
				re = i;
			}
		}
		return re;
	}

	public static int checkMin(int num[]) {
		int min = 1001;
		int re = -1;
		for (int i = 0; i < num.length; i++) {
			if (num[i] < min) {
				min = num[i];
				re = i;
			}
		}
		return re;
	}

}

Measured memory_bytes: 28340
#include <iostream>
#include <string>
#include <vector>
#include <ios>
#include <iomanip>
#include <stack>
#include <queue>
#include <algorithm>

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

using namespace std;

const int INF = 100000000;

bool isSame(string s,string t){
  int size = s.length();
  REP(i,size){
    if (s[i] != t[i]) {
      return false;
    }
  }
  return true;
}

int main(){
  string s,t;
  cin >> s;
  cin >> t;
  int size = s.length();
  int count = 0;

  while (true) {
    if (count == size) {
      cout << "No" << endl;
      break;
    }
    if (isSame(s,t)) {
      cout << "Yes" << endl;
      break;
    }
    string last(&s.back());
    s.pop_back();
    s = last + s;
    count++;
  }
  return 0;
}

Measured memory_bytes: 256
import std.conv;
import std.string;
import std.algorithm;
import std.array;
import std.stdio;

void main() {
	auto n = readln.chomp.to!int;
	auto a = readln.chomp.split(' ').map!(to!long).array;

	assert(n == a.length);

	auto s = sum(a);

	auto counts = new int[100000];

	foreach (e;a) {
		++counts[e];
	}

	auto q = readln.chomp.to!int;

	foreach (i;0..q) {
		int b, c;
		readf(" %s %s", &b, &c);
		assert(b != c);

		s += (cast(long)c - b) * counts[b];
		writeln(s);
		counts[c] += counts[b];
		counts[b] = 0;
	}
}


Measured memory_bytes: 6248
#include <stdio.h>
int main(int argc, char const *argv[])
{
	char at,top;
	scanf("%c %c",&at,&top);
	if(at == 'H'){
		printf("%c\n",top);
	}
	else if(at == 'D'){
		if(top == 'H'){
			printf("D\n");
		}
		else if(top == 'D'){
			printf("H\n");
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(void){

int n, a, b, c;

scanf("%d ", &n);
if(n==1)
 printf("Hello World\n");
else if(n==2){
 scanf("%d %d", &a, &b);
 c=a+b;
 printf("%d\n", c);

}

return 0;
}


Measured memory_bytes: 128
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 6
0 1
1 0
1 2
2 4
4 3
3 2
4
0 1
0 3
2 3
3 4

output:
1
0
1
1
"""
import sys

sys.setrecursionlimit(int(1e6))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
    return init_adj_table


def graph_dfs(u, low, disc, stack_member, st):
    global Time
    # Initialize discovery time and low value
    disc[u] = Time
    low[u] = Time
    Time += 1
    stack_member[u] = True
    st.append(u)
    scc_set = set()

    # Go through all vertices adjacent to this
    for v in adj_table[u]:

        # If v is not visited yet, then recur for it
        if disc[v] == -1:

            graph_dfs(v, low, disc, stack_member, st)

            # Check if the subtree rooted with v has a connection to
            # one of the ancestors of u
            # Case 1 (per above discussion on Disc and Low value)
            low[u] = min(low[u], low[v])

        elif stack_member[v]:

            '''Update low value of 'u' only if 'v' is still in stack
            (i.e. it's a back edge, not cross edge).
            Case 2 (per above discussion on Disc and Low value) '''
            low[u] = min(low[u], disc[v])

    # head node found, pop the stack and print an SCC
    w = -1  # To store stack extracted vertices
    if low[u] == disc[u]:
        while w != u:
            w = st.pop()
            scc_set.add(w)
            stack_member[w] = False
        ans.append(scc_set)

    return None


def scc():
    # Mark all the vertices as not visited
    # and Initialize parent and visited,
    # and ap(articulation point) arrays
    disc = [-1] * vertices
    low = [-1] * vertices
    stack_member = [False] * vertices
    st = []

    # Call the recursive helper function
    # to find articulation points
    # in DFS tree rooted with vertex 'i'
    for v in range(vertices):
        if disc[v] == -1:
            graph_dfs(v, low, disc, stack_member, st)

    return ans


def solve():
    for question in q_list:
        flag = False
        ele1, ele2 = map(int, question)
        for each in scc_sets:
            if (ele1 in each) and (ele2 in each):
                flag = True
                break
        if flag:
            print('1')
        else:
            print('0')
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:edges + 1])
    q_num = int(_input[edges + 1])
    q_list = map(lambda x: x.split(), _input[edges + 2:])

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    Time = 0
    ans = []
    scc_sets = scc()
    solve()

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

#define INF 2e+9
#define MAX_N 100000

int dp[MAX_N];
int n;
vector<int> a;

void solve() {
    fill(dp, dp+n, INF);
    for (int i=0; i<n; ++i) {
        *upper_bound(dp, dp+n, a[i]) = a[i];
    }
    cout << lower_bound(dp, dp+n, INF) - dp << endl;
}

int main() {
    cin >> n;
    a.resize(n);
    for(int i=n-1; i>=0; --i) cin >> a[i];
    solve();
    system("pause");
    return 0;
}

Measured memory_bytes: 1272
MOD = 10 ** 9 + 7
N = int(input())
S1 = input()
S2 = input()

ans = 1
prv_ptn = 0 # 1 or 2
i = 0
while i < N:
    if S1[i] == S2[i]:
        if prv_ptn == 0:
            ans *= 3
        elif prv_ptn == 1:
            ans *= 2
        else:
            ans *= 1
        ans %= MOD
        prv_ptn = 1
        i += 1
    else:
        if prv_ptn == 0:
            ans *= 6
        elif prv_ptn == 1:
            ans *= 2
        else:
            ans *= 3
        ans %= MOD
        prv_ptn = 2
        i += 2
print(ans % MOD)


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
#define int long long
int N;
int M;
vector<vector<double> > dp;
vector<vector<double> > p;

double solve(int i, int j) {
	if (dp[i][j] > -0.5) {
		return dp[i][j];
	}
	if (i == M)return 1;
	double res = 0;
	for (int x = 0; x < N; x++) {
		if (j & (1 << x)) {
			double tmp = 0;
			double prob = 1;
			for (int m = i; m <= M; m++) {
				tmp += prob * (1 - p[x][m]) * solve(m, j ^ (1 << x));
				prob *= p[x][m];
			}
			res = max(res, tmp);
		}
	}
	dp[i][j] = res;
	return dp[i][j];
}
signed main() {
	
	cin >> N >> M;
	p.resize(N, vector<double>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> p[i][j];
		}
		p[i].push_back(0);
	}
	dp.resize(M + 1, vector<double>((1 << N), -1));
	dp[M][0] = 1;
	for (int i = 0; i < M; i++) {
		dp[i][0] = 0;
	}
	cout << fixed << setprecision(15) << solve(0, (1 << N) - 1) << endl;
}


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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int n;

struct rest {
  string s; int rating; int idx;
  bool operator<(rest other) const {
    if (s == other.s) {
      return rating > other.rating;
    }
    return s < other.s;
  }
};

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  //cout << fixed << setprecision(6);
  cin>>n;
  vector<rest> v(n);
  for (int i=0; i<n; i++) {
    rest r;
    cin>>r.s>>r.rating;
    r.idx = i+1;
    v[i] = r;
  }
  sort(v.begin(),v.end());

  for (auto r: v) {
    cout<<r.idx<<'\n';
  }
  

  return 0;
}


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

const int mN = 100100;
int h[mN];
vector<int> adj[mN];

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin >> h[i];
    for (int i=1,a,b; i<=m; i++) {
    	cin >> a >> b;
    	adj[a].push_back(b);
    	adj[b].push_back(a);
	}
    int cnt = 0;
    for (int i=1; i<=n; i++) {
    	bool check = true;
    	for (int j : adj[i]) check &= h[i] > h[j];
    	cnt += check;
	}
	cout << cnt;
    return 0;
}


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

using namespace std;

const int N = 1e5+10;

int dp[N];

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

	vector<int> v(n);
	for(int i = 0; i < n; i++) cin >> v[i];

	//for(int i = 0; i < v[0]; i++) dp[i] = 1;
	for(int i = v[0]; i <= k; i++) {
		bool f = 0;
		for(auto j: v) {
			if(i-j >= 0 && dp[i-j] == 0) {
				f = 1;
				break;
			}
		}

		if(f) dp[i] = 1;
	}

	// for(int i = 0; i <= k; i++) cout << dp[i] << " ";
	// cout << endl;

	if(dp[k]) cout << "First";
	else cout << "Second";
}

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


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T,N,k;
  long long int total;
  cin >> T;
  for(int t=1;t<=T;t++)
  {
    total=0;
    cin >> N;
    long long int l,r;
    vector<long long int> Ph[N],Pt[N];
    priority_queue<long long int, vector<long long int>, greater<long long int>> H;
    priority_queue<long long int, vector<long long int>, greater<long long int>> T;
    for(int i=0;i<N;i++)
	{
      cin >> k >> l >> r;
      k = k-1;
      if(l>r)
	  {
        Ph[k].push_back(l-r);
        total = total +r;
      }
	  else
	  {
        Pt[k].push_back(r-l);
        total = total + l;
      }
    }
    for(int i=0;i<N;i++)
	{
      for(int j:Ph[i])
        H.push(j);
      while(H.size()>i+1)
        H.pop();
      
    }
    for(int i=0;i<N;i++)
	{
      for(int j:Pt[N-i-1])
        T.push(j);
      while(T.size()>i)
        T.pop();
      
    }
    while(H.size())
	{
      total = total + H.top();
      H.pop();
    }
    while(T.size())
	{
      total = total + T.top();
      T.pop();
    }
    cout << total <<endl;
  }
  
  return 0;
}





Measured memory_bytes: 19652
import numpy
H,W = map(int,input().split())
S = numpy.array([[1 if i == '.' else 0 for i in input().strip()] for _ in range(H)])
S = numpy.array([S, S])

for w in range(1, W):
    S[0, :, w] += S[0, :, w] * S[0, :, w - 1]
for w in range(W - 2, -1, -1):
    S[0, :, w] = (S[0, :, w] != 0) * numpy.maximum(S[0, :, w], S[0, :, w + 1])
for h in range(1, H):
    S[1, h] += S[1, h] * S[1, h - 1]
for h in range(H - 2, -1, -1):
    S[1, h] = (S[1, h] != 0) * numpy.maximum(S[1, h], S[1, h + 1])

S = S[0]+S[1]
print(numpy.max(S)-1)

Measured memory_bytes: 129232
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pi (acos(-1))
#define ull  unsigned long long
#define ld long double
///freopen("input.txt","r",stdin);
///freopen("output.txt","w",stdout);
#define M 100000
ll LCM(ll a, ll b)
{
    ll g = __gcd(a,b);
    return (a*b)/g ;
}
string numtostr(ll n)
{
    ostringstream str1 ;
    str1 << n ;
    return str1.str();
}
ll strtonum(string s)
{
    ll x ;
    stringstream str1(s);
    str1 >> x ;
    return x ;
}
string s;
int l,i;
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>s;
    l=s.length();
    for(i=0;i<l;++i)
    {
        if(s[i]=='?')
            cout<<'D';
        else
            cout<<s[i];
    }
    cout<<'\n';
    return 0;
}


Measured memory_bytes: 3752
/**
 *  author:   TakeruOkuyama
 *  created:  2020-04-15 11:17:28
**/
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MOD = 1000000007;
const int INF = 999999999;

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> G(M);
    rep(i, N){
        int K;
        cin >> K;
        vector<int> A(K);
        rep(j, K){
            cin >> A[j];
            G[A[j] - 1]++;
        }
    }
    int ans = 0;
    rep(i, M){
        if(G[i] == N){
            ans++;
        }
    }
    cout << ans << endl;
return 0;}

/**
 * g++ code.cpp
 * ./a.out
 * shift + ctrl + i
**/ 

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

int main(){
    char a;

    cin>>a;
    if(a=='A'){
        cout<<'T'<<endl;
    }
    else if(a=='C'){
        cout<<'G'<<endl;
    }
    else if(a=='G'){
        cout<<'C'<<endl;
    }
    else{
        cout<<'A'<<endl;
    }
    
    return 0;
}

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

using namespace std;

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  int n;cin>>n;
  int hoge[2][n];
  for(int i=0;i<2;i++)for(int j=0;j<n;j++)cin>>hoge[i][j];
  int cnt,ans=0;
  for(int shake=n;shake>0;shake--){
    cnt=0;
    for(int i=0;i<shake;i++){
      cnt+=hoge[0][i];
    }
    for(int i=shake-1;i<n;i++){
      cnt+=hoge[1][i];
    }
    ans=max(cnt,ans);
  }
  cout<<ans<<endl;
}


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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define int ll
#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using vs  = vector<string>;
using pii = pair<int,int>;
constexpr ll inf = 1ll<<61;
constexpr ll mod = 1e9+7;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>T add(const T &a, const T &b){return (a+b)%mod;}

signed main(){
  int n, m; cin >> n >> m;
  set<int> a;
  rep(i,m){
    int x; cin >> x;
    a.insert(x);
  }
  vi dp(n+1);
  dp[0] = 1;
  rep(i,n){
    if(a.count(i+1) == 1) continue;
    dp[i+1] = dp[i];
    if(i > 0) dp[i+1] = add(dp[i+1],dp[i-1]);
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define fast_io ios::sync_with_stdio(false); cin.tie(NULL)
using namespace std;

int main(){
	string s;
	cin>>s;
	int a=0;
	for(int i=0;i<4;i++){
		for(int j=i+1;j<4;j++){
		if(s[i]==s[j])a++;
	}
	}
	if(a==2)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
int bubbleSort(int a[], int n) {
    bool flag = true;
    int s = 0;
    for (int i = 0; flag; i++) {
        flag = false;
        for (int j = n - 1; j >= i + 1; j--) {
            if (a[j - 1] > a[j]) {
                s++;
                flag = true;
                int t = a[j];
                a[j] = a[j-1];
                a[j-1] = t;
            }
        }
    }
    return s;
}

int main() {
    int n;
    cin >> n;
    int a[100];
    for (int i = 0; i < n; i++) cin >> a[i];
    int s = bubbleSort(a, n);
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << a[i];
    }
    cout << endl;
    cout << s << endl;
    return 0;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j,k;
    ll n,m;
    cin >> n >> m;
    vector<vector<ll>> graph(n,vector<ll>(n,1e9));
    for(i = 0;i < n;++i){
        graph.at(i).at(i) = 0;
    }
    vector<ll> a(m);
    vector<ll> b(m);
    vector<ll> c(m);
    for(i = 0;i < m;++i){
        cin >> a.at(i) >> b.at(i) >> c.at(i);
        --a.at(i);  --b.at(i);
        graph.at(a.at(i)).at(b.at(i)) = c.at(i);
        graph.at(b.at(i)).at(a.at(i)) = c.at(i);
    }
    rep(k,n){
        for(i = 0;i < n;++i){
            rep(j,n){
                graph.at(i).at(j) = min(graph.at(i).at(j), graph.at(i).at(k) + graph.at(k).at(j));
            }
        }
    }
    ll ans = 0;
    for(i = 0;i < m;++i){
        if(graph.at(a.at(i)).at(b.at(i)) < c.at(i)) ++ans;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
/* Just_Do_It ___________ICARUS__________________*/
	                 
	#include <bits/stdc++.h>
	using namespace std;
	       
	typedef long long ll;
	#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	#define rep(i,a,n) for(ll i=a;i<n;i++)
	#define per(i,a,n) for (ll i=n-1;i>=a;i--)
	#define te ll t; std::cin >> t; while(t--)
	#define SZ 100001
	//# define M_PIl  3.141592653589793238462643383279502884L 
	/*   Proceed with CAUTION   */

	int main(){
		fastio;
		ll n,k,m;
		cin>>n>>m;
		ll a[n][m],b[n][m],o=0,cnt=0;;
		rep(i,0,n) rep(j,0,m) 		{
			cin>>a[i][j];
			b[i][j] = a[i][j];
		}
		ll j=0;
		rep(i,0,n){
			if(i%2){
				for( j=m-1; j>0;j--){
					if(a[i][j]%2) {cnt++;
						a[i][j-1]+=a[i][j];
						//cout<<i+1<<" "<<j+1<<" "<<i+1<<" "<<j<<endl;
					}
				}
				if( i!= n-1 && a[i][0]%2){
					a[i+1][0]+=a[i][0];cnt++;
				//	cout<<i+1<<" "<<1<<" "<<i+2<<" "<<1<<endl;
				}
			} else {
				for( j = 0; j < m-1; j++){
					if(a[i][j]%2){
						a[i][j+1]+=a[i][j];cnt++;
					//	cout<<i+1<<" "<<j+1<<" "<<i+1<<" "<<j+2<<endl;
					}
				} 
				if(i!=n-1 && a[i][m-1]%2){
					a[i+1][m-1]+=a[i][m-1];cnt++;
					//cout<<i+1<<" "<<m<<" "<<i+2<<" "<<m<<endl;
				}
			}
		} j=0;
		cout<<cnt<<endl;
		rep(i,0,n){
			if(i%2){
				for( j=m-1; j>0;j--){
					if(b[i][j]%2) {
						b[i][j-1]+=b[i][j];
						cout<<i+1<<" "<<j+1<<" "<<i+1<<" "<<j<<endl;
					}
				}
				if( i!= n-1 && b[i][0]%2){
					b[i+1][0]+=b[i][0];
					cout<<i+1<<" "<<1<<" "<<i+2<<" "<<1<<endl;
				}
			} else {
				for( j = 0; j < m-1; j++){
					if(b[i][j]%2){
						b[i][j+1]+=b[i][j];
						cout<<i+1<<" "<<j+1<<" "<<i+1<<" "<<j+2<<endl;
					}
				} 
				if(i!=n-1 && b[i][m-1]%2){
					b[i+1][m-1]+=b[i][m-1];
					cout<<i+1<<" "<<m<<" "<<i+2<<" "<<m<<endl;
				}
			}
		}
	}

Measured memory_bytes: 6016
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
string YN(bool ok){
  string ans;
  if(ok) ans="Yes";
  else ans="No";
  return ans;
}
int main(){
  int n;
  cin>>n;
  vector<pair<int,int>> v(n);
  for(int i=0; i<n; i++){
    int a,b;
    cin>>a>>b;
    v.at(i)=make_pair(b,a);
  }
  sort(v.begin(), v.end());
  int time=0;//現在時刻
  bool ok=true;
  for(int i=0; i<n; i++){
    time += v.at(i).second;
    if(time>v.at(i).first){
      ok=false;
      break;
    }
  }
  string ans;
  cout<<YN(ok)<<endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define print(a) {for(auto xxxxx : (a)) cout << xxxxx << ' '; cout << '\n';}
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

ll next(){ll x; cin >> x;return x;}
const int maxn = 3e5 + 2, intf = 2e9;
const ll inf = 2e18, mod = 998244353;
const ld eps = 1e-9;


void solve(){
	ll n , m; cin >> n >> m;
	vector <ll> a(n);
	ll sum = 0;
	for (auto &x : a){
		cin >> x;
		sum += x;
	}
	sort(rall(a));
	for (int i = 0; i < m; i ++){
		if (a[i]*4*m < sum){
			cout << "No\n";
			return;
		}
	}
	cout << "Yes\n";
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
    
    for (int t = 1; t--;) solve();

	return 0;
}
/*


*/



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

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef pair<LL, LL> PLL;
typedef vector<PLL> VPLL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
//#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SORT_DESC(c) sort((c).rbegin(),(c).rend())
#define REV(c) reverse((c).begin(), (c).end())
#define SIZE(a) int((a).size())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF*(LL)INF;
const int MOD = 1e9+7;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

void Main()
{
    LL n,l;cin>>n>>l;
    int idx=-1;
    VL a(n);
    REP(i,n){
        cin>>a[i];
    }
    REP(i,n-1){
        if(a[i]+a[i+1]>=l){
            idx=i+1;
            break;
        }
    }
    if(idx==-1){
        cout<<"Impossible"<<endl;
        return;
    }
    
    cout<<"Possible"<<endl;
    FOR(i,1,idx){
        cout<<i<<endl;
    }
    for(int i=n-1;i>idx;i--){
        cout<<i<<endl;
    }
    cout<<idx<<endl;

	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,t,a[101]={0},an=0;
  cin>>n>>m>>t>>a[1];
  an+=a[1]-m;
  for(int i=2;i<=n;i++){
    cin>>a[i];
    if(a[i]-a[i-1]>2*m)an+=a[i]-a[i-1]-2*m;
  }  
  if(t-a[n]>m)an+=t-a[n]-m;
  cout<<an<<endl;
  return 0;
}

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

int main(){ 
    unsigned long long int a,b,n,m;

    while(cin >> a >> b){
        if(a >= b){
            m = a;  
            n = b;  
        }       
        else{   
            n = a;  
            m = b;  
        }       

        while(n != 0){
            unsigned long int i = n;
            n = m % n;
            m = i;  
        }       
        n = a*b/m;

        cout << m << " " << n << endl;
    }
    return 0;

}

Measured memory_bytes: 0
X,K,D=map(int,input().split())
if abs(X)>=K*D:
    print(abs(X)-K*D)
else:
    k1=abs(X)//D
    k2=k1+1
    ans1=abs(X)-k1*D
    ans2=abs(ans1-D)
    if (K-k1)%2==0:
        print(ans1)
    else:
        print(ans2)

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

#define __STDC_FORMAT_MACROS
#define p64 PRId64

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)    FOR (i,0,n)
#define ALL(f,x,...) ([&](decltype((x)) ALL) {                          \
            return (f)(begin(ALL), end(ALL), ## __VA_ARGS__); })(x)

using namespace std;
using ll = int64_t;

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

    vector<ll> A(N);

    REP (i, N) cin >> A[i];

    vector<ll> B(N);

    REP (i, N) cin >> B[i];

    ALL (sort, B);

    ll amax = *ALL (max_element, A);

    ll abmax = amax + B[N - 1];

    int t = 1 << 1;

    vector<ll> ta(N);
    vector<ll> tb(N);

    ll ans = 0;
    while ((t >> 1) <= abmax)
    {

        REP (i, N)
        {
            ll all = t - 1;
            ta[i] = A[i] & all;
            tb[i] = B[i] & all;
        }

        ALL (sort, tb);

        ll sumx = 0;

        REP (i, N)
        {
            auto l1 = ALL (lower_bound, tb, (t >> 1) - ta[i]);
            auto u1 = ALL (lower_bound, tb, 2 * (t >> 1) - ta[i]);

            auto l2 = ALL (lower_bound, tb, 3 * (t >> 1) - ta[i]);
            auto u2 = ALL (lower_bound, tb, 4 * (t >> 1) - ta[i]);


            ll x = u1 - l1 + u2 - l2;

            sumx += x;
        }

        if (sumx % 2 == 1) ans += t >> 1;

        t <<= 1;
    }

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


Measured memory_bytes: 6528
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define LL long long
#define MOD 1000000007
#define INF 2000000000
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
ll N, M, K,H,W, mi1,mi2,sum,B[100000],C[102];
LL ans;
LL no;
bool b,bb[1000000000];
string s,t;

int main() {
	cin >> N;
	ans = 0;
	no = 0;
	K = INF;
	for (int i = 0; i <N; i++) {
		cin >> B[i];
		if (B[i] < 0)no++;
		K = min(K, abs(B[i]));
		ans += abs(B[i]);
	}
	if (no % 2 == 1)ans = ans - (2 * K);
	cout << ans << endl;



	return 0;
}



Measured memory_bytes: 2688
use proconio::input;
use std::collections::HashMap;

fn main() {
    input! {
        n: usize,
        aa: [usize; n],
    }

    let mut map = HashMap::new();

    for &a in aa.iter() {
        *map.entry(a).or_insert(0) += 1;
    }

    let has_zero = if let Some(&count) = map.get(&0) {
        if count == n {
            println!("Yes");
            return;
        }
        true
    } else {
        false
    };

    if map.len() == 2 && has_zero {
        let zero = map.remove(&0).unwrap();
        let (_, other) = map.into_iter().next().unwrap();
        if zero == n/3 && other == n * 2 / 3 {
            println!("Yes");
            return;
        }
    } else if map.len() == 3 {
        for (_, &count) in map.iter() {
            if count != n/3 {
                println!("No");
                return;
            }
        }
        let keys = map.iter().map(|(&k, _)| k).collect::<Vec<_>>();
        
        let (x, y, z) = (keys[0], keys[1], keys[2]);
        if x ^ y ^ z == 0 {
            println!("Yes");
            return;
        }
    }

    println!("No");
}


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

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

  int k;
  cin >> k;

  int a[] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };

  cout << a[k-1] << '\n';

  return (0);
}


Measured memory_bytes: 3592
/*input

*/
#include <bits/stdc++.h>
#define up(i,a,b) for(int (i) = (a);(i)<=(b);++(i))
#define down(i,b,a) for(int (i) = (b);i>=(a);--i)
#define debug(x) cerr << (x) << '\n';
#define bits(x,i) ((x >> i) & 1)
#define mid ((l+r)/2)
#define pr pair<int,int>
using namespace std;
const int N = 500005;
const int mod = 1e9 + 7; 
#define long long long
long fact[N];
int n,m;
void init(){
	fact[0] = 1;
	for(int i=1;i<=m;++i) fact[i] = (1LL * fact[i-1] * i) % mod;
}
long power(long x,int n){
	long ans = 1;
	for (int i = 0; i < 31; ++i){
		if (bits(n, i)){
			ans = (1LL * ans * x) % mod;
		}
		x = (1LL * x * x) % mod;
	}
	return ans;
}
long inv(long num, long den){
	return (1LL * num * power(den, mod - 2)) % mod;
}
long C(int k,int n){
	long num = fact[n];
	long den = (1LL * fact[k] * fact[n-k]) % mod;
	return inv(num, den);
}
long P(int k,int n){
	return inv(fact[n], fact[n-k]);
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	init();
	long ans = 0;
	for(int k=0;k<=n;++k){
		long cPi = (P(n-k, m-k) * P(n-k, m-k)) % mod;
		cPi = (cPi * P(k, m)) % mod;
		cPi = (cPi * C(k,n)) % mod;
		// cout << cPi << '\n';
		ans = (ans + (k & 1 ? 1LL*mod*mod - cPi : cPi)) % mod;
		// if (ans <= 0) ans = (ans + mod * mod) % mod;
	}
	cout << ans;
}

Measured memory_bytes: 7456
#ifdef _MSC_VER
#include <__msvc_all_public_headers.hpp>
#undef min
#undef max
#else
#define NDEBUG
#include <bits/stdc++.h>
#endif

using namespace std;
using large = long long;

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    auto v = vector<int>(n + 2);

    auto parts = vector<int>();
    parts.push_back(1);
    auto last = s[0];
    for (auto i = 1; i < n; ++i) {
        if (s[i] == last) {
            parts.back()++;
            continue;
        }

        parts.push_back(1);
        last = s[i];
    }

    for (auto i = 0; i < k; ++i) {
        if (parts.size() <= 1)
            break;

        if (parts.size() == 2) {
            parts.front() += parts.back();
            parts.pop_back();
            break;
        }

        auto last = parts[parts.size() - 1];
        auto secondlast = parts[parts.size() - 2];

        parts[parts.size() - 3] += last + secondlast;
        parts.resize(parts.size() - 2);
    }

    auto sum = accumulate(parts.begin(), parts.end(), 0LL, [](auto sum, auto item) { return sum + max(0, item - 1); });
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 4412
N=int(input())
a=[int(i) for i in input().split()]
a.sort(key=lambda x:x)
n=a[N-1]
d=10**10
for i in range(N):
  if i<=N-2:
    if d>abs(a[i]-(n/2)):
      d=abs(a[i]-(n/2))
      r=a[i]
print(n,r)
  

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  int n, k;cin>>n>>k;
  vector<int> p(n);
  rep(i, n)cin>>p[i];

  vector<int> cp(n);
  rep1(i, n-1)if(p[i-1]<p[i])cp[i]++;
  rep(i, n-1)cp[i+1]+=cp[i];
//for(auto p:cp)cout<<p<<' ';cout<<endl;

  int result=0;
  bool has_sorted = false;
  // 最初のk個がソート済みと同じ状態でないなら、初手のソートでは結果が+1される。
  // メインループは初手のソートを終えたところから始まるので、初手のresult++はループ開始前に実行する
  if(cp[k-1]==k-1)has_sorted=true;
  if(!has_sorted)result++;
  
  set<int> s;
  rep(i, k)s.insert(p[i]);
  // このループは1個目の要素をpopして、k+1個目の要素をpushするところから始まる。
  rep(i, n-k){
    bool minf = (p[i]==*s.begin());
    s.erase(p[i]);
    s.insert(p[i+k]);
    bool maxf = (p[i+k]==*s.rbegin());
    if(cp[i+k]-cp[i+1]==k-1){
      has_sorted=true;
    }else if(!(minf && maxf) ){
      result++;
    }
  }

  // なにもしなくてもすでにソートされている区間が1つ以上ある場合、その区間のいずれもソートすれば全体は同じ数列になる。なので区間の数によらず+1する。
  if(has_sorted)result++;

  cout<<result<<endl;

  return 0;
}

Measured memory_bytes: 11136
//第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)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
lint gcd( lint m, lint n )
{
	int a=max(m,n),b=min(m,n);
	if(m==0) return n;if(n==0) return m;
	if(a%b==0) return b;
	return gcd(b,a-b*(a/b));
}
int n;
lint a[10100],b[10100];
bool ng[4001000];
vector<lint> so;
bool cal(lint ko){
	rep(i,n+1) b[i]=a[i]%ko;
	for(int i=n;i>=ko;i--){
		b[i-ko+1]+=b[i];
		b[i]=0;b[i-ko+1]%=ko;
	}
	rep(i,n+1){
		if(b[i]!=0L) return false;
	}
	return true;
}
int main()
{
	cin>>n;
	for(int i=n;i>=0;i--) cin>>a[i];//cout<<a[0]<<a[1]<<a[2]<<a[3]<<endl;
	memset(ng,false,sizeof(ng));
	for(int i=2;i<4000100;i++){
		if(ng[i]) continue;
		so.pb(i);
		for(int j=i*2;j<4000100;j+=i) ng[j]=true;
	}
	lint sum=0;
	rep(i,n+1) sum=gcd(sum,abs(a[i]));
	//cout<<sum<<endl;
	vector<lint> ko;
	rep(i,so.size()){
		if(sum%so[i]==0){
			ko.pb(so[i]);
			while(sum%so[i]==0) sum/=so[i];
		}
	}
	if(sum>1) ko.pb(sum);
	//if(f<1 && sum>1) ko.pb(sum);
	//rep(i,ko.size()) cout<<ko[i]<<endl;
	REP(i,2,n+10){
		if(!ng[i]) ko.pb(i);
	}
	//rep(i,ko.size()) cout<<ko[i]<<endl;
	sort(All(ko));ko.erase(unique(All(ko)),ko.end());
	//rep(i,ko.size()) cout<<ko[i]<<endl;
	rep(i,ko.size()){
		if(cal(ko[i])) cout<<ko[i]<<endl;
	}
}


Measured memory_bytes: 10480
#include<stdio.h>
#include<string.h>
#define INF 1000000000

void insert(int *,int);
void maxHeapfy(int *,int);
int extract(int *);
void increase(int *,int ,int);

int size;//外部変数だから0に初期化される

int main(){
  int i, x,A[2000000];
  char com[20];
 
  for ( i = 0; ; i++ ){
    scanf("%s", com);
    if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(A,x);
    }else if(com[0]=='e'&&com[1]=='x'){
      printf("%d\n",extract(A));
    }else{
      break;
    }
  }
  return 0;
}



void maxHeapify(int *A,int i){
  int l,r,largest,a;
  l=2*i;
  r=2*i+1;
  
  if(l<=size&&A[l]>A[i]){
    largest=l;
  }else{
    largest=i;
  }

  if(r<=size&&A[r]>A[largest]){
    largest=r;
  }

  if(largest!=i){
    a=A[i];
    A[i]=A[largest];
    A[largest]=a;
    maxHeapify(A,largest);
  }
}



int extract(int *A){
  int max;
  if(size<1){
    return -INF;
  }
  max = A[1];
  A[1]=A[size];
  size--;
  maxHeapify(A,1);
  return max;
}

void increase(int *A,int i,int key){
  int temp;
  if(key<A[i]){
    return;
  }
  A[i]=key;
  while(A[i/2]<A[i]&&i>1){
    temp=A[i/2];
    A[i/2]=A[i];
    A[i]=temp;
    i=i/2;
  }
}


void insert(int *A,int key){
  size++;
  A[size]=-INF;
  increase(A,size,key);
}





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

const int M = 10000005;

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

  vector<int> cnt(n+1);
  ll ans = 0;
  for (ll i = 1; i < n+1; i++){
      for (ll j = i; j < n+1; j+= i){
          cnt[j]++;
      }
  }
  for (ll i = 1; i< n+1; i++ ){
      ans += i*(cnt[i]);
  }
  cout << ans << endl;
  return 0;
}


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

const ll mod = 1000000007;

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

ll inv(ll x, ll mod) {
  ll res = pow_mod(x, mod - 2, mod);
  return res;
}

ll comb_mod(ll n, ll r, ll mod) {
  ll res;
  ll x = 1, y = 1;
  for (ll i = 0; i < r; i++) {
    x *= n-i;
    x %= mod;
    y *= r-i;
    y %= mod;
  }
  res = x * inv(y, mod);
  res %= mod;
  return res;
}

int main() {
  ll N, K;
  cin >> N >> K;
  for (ll i = 0; i < K; i++) {
    ll ans = 0;
    if (i > N-K) {
      cout << 0 << endl;
    }
    else {
      ans = comb_mod(K-1, i, mod) * comb_mod(N-K+1, i+1, mod);
      ans %= mod;
      cout << ans << endl;
    }
  }
}

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

int main(){
  int n, a, b, c, l[10], cnt1, cnt2, cnt3, mn=1e9;
  cin >> n >> a >>b >> c;
  for(int i=0;i<n;i++)cin >> l[i];
  for(int i=0;i<pow(4, n);i++){
    int tmp = i;
    int tmpa=a,tmpb=b,tmpc=c;
    cnt1=0;cnt2=0;cnt3=0;
    for(int j=0;j<n;j++){
      if(tmp%4==1){
        cnt1++;
        tmpa-=l[j];
      }
      if(tmp%4==2){
        cnt2++;
        tmpb-=l[j];
      }
      if(tmp%4==3){
        cnt3++;
        tmpc-=l[j];
      }
      tmp/=4;
    }
    if(cnt1==0 || cnt2==0 || cnt3==0)continue;
    int ans = abs(tmpa) + abs(tmpb) + abs(tmpc);
    ans += (cnt1>1?(cnt1-1)*10:0)+(cnt2>1?(cnt2-1)*10:0)+(cnt3>1?(cnt3-1)*10:0);
    mn = min(mn, ans);
  }
  cout << mn << endl;
}

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

using namespace std;

typedef long long ll;

const double pi = 3.14159265358979323846;

#define rep(i, n) for (ll i = 0; i < n; i++)
#define mod 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define CIN(v) cin >> v;
#define COUT(v) cout << v << endl;

int main() {
  string S, T;
  CIN(S >> T);

  int c = 0;
  if (S[0] == T[0])
    c++;
  if (S[1] == T[1])
    c++;
  if (S[2] == T[2])
    c++;

  COUT(c);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define MAX 100005
#define NIL -1

struct Node {int p, l, r;};

Node T[MAX];
int n, D[MAX];

void print(int u){
	int i, c;
	cout << "node " << u << ": ";
	cout << "parent = " << T[u].p << ", ";
	cout << "depth = " << D[u] << ", ";
	
	if(T[u].p == NIL) cout << "root, ";
	else if (T[u].l == NIL) cout << "leaf, ";
	else cout << "internal node, ";
	
	cout << "[";
	
	for(i = 0, c = T[u].l; c != NIL; i++, c = T[c].r){
		if(i)cout << ", ";
		cout << c;
	}
	cout << "]" << endl;
}

int rec(int u, int p){
	D[u] = p;
	if(T[u].r != NIL) rec(T[u].r, p);
	if(T[u].l != NIL) rec(T[u].l, p + 1);
	return 0;
}

int main(void){
	int i, j, d, v, c, l, r;
	cin >> n;
	for(i = 0; i < n; i++) T[i].p = T[i].l = T[i].r = NIL;
	
	for(i = 0; i < n; i++){
		cin >> v >> d;
		for(j = 0; j < d; j++){
			cin >> c;
			if(j == 0) T[v].l = c;
			else T[l].r = c;
			l = c;
			T[c].p = v;
		}
	}
	for(i = 0; i < n; i++){
		if(T[i].p == NIL) r = i;
	}
	
	rec(r, 0);
	
	for(i = 0; i < n; i++) print(i);
	
	return 0;
}



Measured memory_bytes: 7780
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i, s, n) for(int i=(s); i<=(n); ++i)
#define outl(x) cout<< (x) << '\n'
using namespace std;

class UnionFind {
private:
   int *par;
   int *rank;
   const size_t N;

public:
   UnionFind(size_t n): N(++n), par(new int[N]), rank(new int[N]) {
      reps(i,0,N) par[i] = i, rank[i] = 0;
   }
   ~UnionFind() {
      delete[] par;
      delete[] rank;
   }
   int root(const int x) {
      if(par[x] != x) par[x] = root( par[x] );
      return (par[x]);
   }

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

   //success: 1   failed: 0
   bool unite(int x, int y) {
      x = root(x), y = root(y);
      if(x == y)return (false);
      //link(x, y);
      par[x] = y;
      return (true);
   }

   //void link(const int x, const int y) {
   //   (rank[x] > rank[y]) ? par[y] = x : par[x] = y;
   //   if( rank[x] == rank[y] ) ++rank[y];
   //}
};

signed main()
{
   cin.tie(0), ios::sync_with_stdio(false);
   int N, Q;
   cin >> N >> Q;
   UnionFind S(N);

   while(Q--) {
      int x, y;
      bool com;
      cin >> com >> x >> y;
      if(com == 1)outl( S.same(x,y) );
      else S.unite(x,y);
   }
}




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

int main() {
	int hour, minute, second, ans, temp;
	for (int i = 0; i < 3; i++) {
		cin >> hour >> minute >> second;
		temp = hour * 3600 + minute * 60 + second;
		cin >> hour >> minute >> second;
		ans = hour * 3600 + minute * 60 + second;
		ans = ans - temp;
		hour = ans / 3600; second = ans % 60;
		minute = (ans - 3600 * hour) / 60;
		cout << hour << " " << minute << " " << second << endl;
	}
	return 0;
}


Measured memory_bytes: 3084
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define V vector
template <typename T> bool chmin(T &a, const T &b) {if(a > b){a = b; return true;} return false;}
template <typename T> bool chmax(T &a, const T &b) {if(a < b){a = b; return true;} return false;}
template<typename A, size_t N, typename T> void Fill (A (&array)[N], const T & val) {fill ((T*)array, (T*)(array+N), val);}
V<int> dx = {-1, 1,  0, 0, -1, -1,  1, 1};
V<int> dy = { 0, 0, -1, 1, -1,  1, -1, 1};

int main () {
    int n; cin >> n;
    V<ll> x(n), y(n); rep(i, n) cin >> x[i] >> y[i];
    V<ll> z(n), w(n);
    rep(i, n) z[i] = x[i] + y[i];
    rep(i, n) w[i] = x[i] - y[i];
    sort(all(z)); sort(all(w));
    ll ans = max(z[n-1] - z[0], w[n-1] - w[0]);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 9596
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
typedef long long ll;
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({ a * c, a * d, b * c, b * d }) << "\n";
    return 0;
}

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

int main(){
    string s;
    cin >> s;
    stack<char> st;
    rep(i, 0, s.size()){
        if(s[i] == 'B' && !st.empty()){
            st.pop();
        }else if(s[i] != 'B'){
            st.push(s[i]);
        }
    }

    string ans;
    while(!st.empty()){
        ans.push_back(st.top());
        st.pop();
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256