akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;
typedef long long int ll;
int main() {
	while (1) {
		int R, C;
		cin >> R >> C;
		if (R == 0 && C == 0)break;
		vector<vector<bool> > map(R, vector<bool>(C, 0));
		for (int i = 0; i < R; i++)for (int j = 0; j < C; j++) {
			bool tmp; cin >> tmp;
			map[i][j] = tmp;
		}

		int ans = 0;
		for (int i = 0; i < 1 << R; i++) {
			vector < vector<bool> > newmap = map;
			int tmp = 0;
			for (int j = 0; j < R; j++) {
				if ((i & (1 << j)) == 1 << j)newmap[j].flip();
			}
			for (int j = 0; j < C; j++) {
				int cnt = 0;
				for (int k = 0; k < R; k++) cnt += newmap[k][j];
				tmp += max(cnt, R - cnt);
			}
			if (ans < tmp) ans = tmp;
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 3184
#include<iostream>

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

int main(){

   while(1){
      int N;
      cin>> N;
      if(!N) break;

      int n[N], dd[N];
      for(int i=0; i<N-1; i++){
         cin>> n[i]>> dd[i];
      }

      int l, r, u, d;
      l=r=u=d=0;
      int py[N], px[N];
      py[0]=px[0]=0;
      for(int i=0; i<N-1; i++){
         int y=py[n[i]]+dy[dd[i]];
         int x=px[n[i]]+dx[dd[i]];
         l=min(l, x);
         r=max(r, x);
         u=min(u, y);
         d=max(d, y);
         py[i+1]=y; px[i+1]=x;
      }

      cout<< r-l+1<<" "<< d-u+1<< endl;
   }
   return 0;
}

Measured memory_bytes: 2964
import java.util.HashMap;
import java.util.Scanner;

class Main{
	static int []par;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int N = sc.nextInt();
		int K = sc.nextInt();
		int L = sc.nextInt();
		par = new int[N];
		for(int i = 0;i < N;i++){
			par[i] = i;					//初期化
		}
		for(int i = 0;i < K;i++){					//unionfind木の作成
			int p = sc.nextInt() -1;
			int q = sc.nextInt() -1;
			unite(p, q);
		}
		
		int[] road = new int[N];
		for(int i  = 0;i < N;i++){
			road[i] = root(i);					//さっきparで作ったunionfind木をroadとしてコピー
		}
		
		for(int i = 0;i < N;i++){
			par[i] = i;					//初期化
		}
		for(int i = 0;i < L;i++){					//unionfind木の作成
			int r = sc.nextInt() -1;
			int s = sc.nextInt() -1;
			unite(r, s);
		}
		
		int[] rail = new int[N];
		for(int i  = 0;i < N;i++){
			rail[i] = root(i);					//さっきparで作ったunionfind木をroadとしてコピー
		}
		
		HashMap<Long, Integer> map = new HashMap<Long,Integer>();
		for(int i  =0;i < N;i++){
			long g  =(long)N * (long)road[i] + (long)rail[i];				//road,railの親のーどを見ることで、同じだったらカウントを
			if(map.containsKey(g)){
				map.put(g, map.get(g)+1);
			}else{
				map.put(g, 1);
			}
		}
		for(int i = 0; i < N; i++) {					//答え
		      int ans = map.get((long)N * (long)road[i] + (long)rail[i]);
		      if(i == N - 1) {
		        System.out.print(ans);
		      } else {
		        System.out.print(ans + " ");
		      }
		}
				
		
		
	}
	static int root(int x){				//親ノードを見つける
		if(x == par[x]){
			return x;
		}
		return par[x]  = root(par[x]);
	}
	
	
	static void unite(int x,int y){					//結合
		int rootx = root(x);
		int rooty = root(y);
		if(rootx != rooty){
			par[rootx] = rooty;
		}
	}
}



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

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  int st = -1;
  for(int i=0; i<s.length(); i++){
    if(s[i] == t[0] || s[i] == '?'){
      int cnt = 1;
      for(int j=i, k=1; j<s.length(); k++){
        if(cnt == t.length()) break;
        else if(s[j+k] != '?' && s[j+k] != t[k]) break;
        else cnt++;
      }
      if(cnt == t.length()){
        st = max(st, i);
      }
    }
  }
  if(st != -1){
    int cnt = 0;
    for(int i=st; i<s.length(); i++){
      s[i] = t[cnt];
      cnt++;
      if(cnt == t.length()) break;
    }
    for(int i=0; i<s.length(); i++){
      if(s[i] == '?') s[i] = 'a';
    }
    cout << s << endl;
  }else{
    cout << "UNRESTORABLE" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
loop do
  n = gets.to_i
  break if n==-1
  ans = 1150
  case n
  when 11..20
    ans += (n-10)*125
  when 21..30
    ans +=10*125+(n-20)*140
  when 31..100
    ans += 10*125+10*140+(n-30)*160
  end
  puts 4280-ans

end

Measured memory_bytes: 2280
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


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

int binarysearch(int a[],int n,int key){
    int low=0,high=n,mid;
    while(low<high){
        mid=(low+high)/2;
        if (key==a[mid])
            return 1;
        if (key>a[mid])
            low=mid+1;
        else if (key<a[mid])
            high=mid;
    }
    return 0;
}

int main() {
    int i,n,q,s[1000000],key,sum=0;
    cin>>n;
    for (i = 0; i < n; ++i) {
        cin>>s[i];
    }
    cin>>q;
    for (i = 0; i < q; ++i) {
        cin>>key;
        if(binarysearch(s,n,key))
            sum++;
    }

    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 3456
r, c = map(int, input().split())

sheet = [[0]*c for i in range(r+1)]

for i in range(r):
    sheet[i] = list(map(int, input().split()))

for j in range(c):
    for i in range(r):
        sheet[r][j] += sheet[i][j]

for i in range(r+1):
    m = 0
    for j in range(c):
        m += sheet[i][j]
        print(sheet[i][j], end=' ')
    print(m)


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

int N, M;
vector<int> L, R;

int main() {
  cin >> N >> M;
  L.resize(M);
  R.resize(M);
  for (int i = 0; i < M; i++) {
    cin >> L[i] >> R[i];
  }


  int left = L[0];
  int right = R[0];
  for (int i = 1; i < M; i++) {
    if (left <= L[i] && L[i] <= right) {
      left = L[i];
    } else if (L[i] > right) {
      cout << 0 << endl;
      return 0;
    }
    
    if (left <= R[i] && R[i] <= right) {
      right = R[i];
    } else if (R[i] < left) {
      cout << 0 << endl;
      return 0;
    }
  }
  cout << right-left+1 << endl;
  return 0;
}

Measured memory_bytes: 1024
N = list(input())
N = [int(N[i]) for i in range(len(N))]
K = int(input())
if len(N) < K:
  for i in range(len(N)):
    if not N[i] == 1:
      print(N[i])
      break
  else:
    print(1)
else:
  for i in range(K):
    if not N[i] == 1:
      print(N[i])
      break
  else:
    print(1)


Measured memory_bytes: 9124
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

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

	ll ans = 0;
	rep(i, n){
		ans += (n - i + 1) * (n - i) / 2;
	}
	ce(ans);

	rep(i, n - 1){
		ll u, v;
		cin >> u >> v;
		if (u > v) swap(u, v);
		ans -= u * (n + 1 - v);
	}
	co(ans);

	return 0;
}


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

int main(){
	int n;
	cin >> n;
	int c=0;
	int v_n = n;
	while(v_n!=0){
		v_n /= 10;
		c ++;
	}
	vector<int> a(c);
	for(int i =0; i < c; i++){
		a.at(i) = n %10;
		n /= 10;
	}
	int sum = 0;
	int zero = 0;
	for(int i = 0; i < (c-1); i++){
		if(a.at(i) == 0) zero++;
		sum += a.at(i);
	}
	if(zero == c-1 && a.at(c-1) == 1){
		sum += 10;
	}else{
		sum += a.at(c-1);
	}
	cout << sum << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>
#define pii pair<int,int>
using namespace std;
int A[101000], B[101000], n, mid, cnt, ord[201000], X[201000], SCC[201000];
set<pii>Set;
bool v[201000];
void DFS(int a, int x){
    int x2, pp;
    if(a<=n)x2 = X[a+n], pp=a+n;
    else x2 = X[a-n], pp=a-n;
    v[a] = true;
    Set.erase(pii(x2,pp));
    while(!Set.empty()){
        auto it = Set.lower_bound(pii(x-mid+1, -1));
        if(it==Set.end() || it->first > x+mid-1)break;
        int y = it->second;
        if(y==a){
            it++;
            if(it==Set.end() || it->first > x+mid-1)break;
            y = it->second;
        }
        if(y>n)DFS(y-n,X[y-n]);
        else DFS(y+n,X[y+n]);
    }
    ord[++cnt] = a;
}
void DFS2(int a, int x){
    SCC[a] = cnt;
    Set.erase(pii(x,a));
    int x2;
    if(a<=n)x2 = X[a+n];
    else x2 = X[a-n];
    while(!Set.empty()){
        auto it2 = Set.lower_bound(pii(x2-mid+1, -1));
        if(it2==Set.end() || it2->first > x2+mid-1)break;
        int y = it2->second;
        if(y==a-n || y==a+n){
            it2++;
            if(it2==Set.end() || it2->first > x2+mid-1)break;
            y = it2->second;
        }
        DFS2(y,X[y]);
    }
}
bool Pos(){
    int i;
    Set.clear();
    for(i=1;i<=n+n;i++){
        Set.insert(pii(X[i],i));
        v[i]=false;
        SCC[i] = 0;
    }
    for(i=1;i<=n+n;i++)v[i]=false;
    cnt = 0;
    for(i=1;i<=n+n;i++){
        if(!v[i])DFS(i, X[i]);
    }
    cnt = 0;
    for(i=1;i<=n+n;i++){
        Set.insert(pii(X[i],i));
    }
    for(i=n+n;i>=1;i--){
        if(!SCC[ord[i]]){
            cnt++;
            DFS2(ord[i],X[ord[i]]);
        }
    }
    for(i=1;i<=n;i++)if(SCC[i] == SCC[i+n])return false;
    return true;
}
int main(){
    int b = 0,e = 1000000000, res = 0, i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d",&A[i],&B[i]);
        X[i]=A[i],X[n+i]=B[i];
    }
    while(b<=e){
        mid = (b+e)>>1;
        if(Pos()){
            b = mid + 1;
            res = mid;
        }
        else e = mid -1;
    }
    printf("%d\n",res);
}

Measured memory_bytes: 2432
public class Main {

	static final int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

	public static void main(String[] args) {

		StringBuilder sb = new StringBuilder();
		for (int i : nums) {
			for (int j : nums) {
				sb.append(String.format("%dx%d=%d\n", i, j, i * j));
			}
		}
		System.out.print(sb.toString());
	}
}

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

int main(){
  int N;
  int64_t sum=0;
  cin >> N;
  for(int i=1;i<=N;i++){
    if(i%3!=0 && i%5!=0){
      sum+=i;
    }
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
// make pair, tuple
// __gcd(int, int)
// bool isPrime(int n){
//       if(n <= 1)return false;
//       if(n <= 3)return true;
//       if(n % 2 == 0 || n % 3 == 0)return false;
//       for(int i = 5;i * i <= n;i += 6){
//             if(n % i == 0 || n % (i + 2) == 0)return false;
//       }
//       return true;
// }
// int countSubString(string s, string temp){
//       int ans = 0;
//       size_t f = s.find(temp);
//       while(f != string::npos){
//             ans++;
//             f = s.find(temp, f + 1);
//       }
//       return ans;
// }

int main(){
    int n;cin >> n;
    int arr[n + 5];
    for(int i = 1;i <= n;i++){
        int t;cin >> t;
        arr[t] = i;
    }
    for(int i = 1;i <= n;i++){
        cout << arr[i] << " ";
    }
}

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

ll N, W;
vector<ll> w, v;
vector<vector<ll>> dp;

void solve() {
  dp.resize(N + 1, vector<ll>(W + 1));
  for (int w = 0; w <= W; w++) {
    dp[0][w] = 0;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= W; j++) {
      if (j >= w[i]) {
        dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
      } else {
        dp[i + 1][j] = dp[i][j];
      }
    }
  }
  cout << dp[N][W] << "\n";
}

int main() {
  cin >> N >> W;
  w.resize(N);
  v.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> w[i] >> v[i];
  }
  solve();
  return 0;
}

Measured memory_bytes: 80256
import java.util.Iterator;
import java.util.Scanner;
import java.util.HashSet;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
		String S = sc.next();

		HashSet hs = new HashSet();
		for (int i = 0; i < N; i++){
			hs.add(S.charAt(i));
		}

		int cnt = 0;

	    for (int i = 0; i < N; i++) {
	    	for(int j = i + 1; j <= N; j++){
	    		String s1 = S.substring(i, j);
	    		String s2 = S.substring(j);
//	    		System.out.println("j= "+ j +":"+ s1);
//	    		System.out.println("j= "+ j +":"+ s2);
	            Iterator it = hs.iterator();
	            int wkcnt = 0;
	            while (it.hasNext()) {
	            	String chr = it.next().toString();
//	            	System.out.println(chr);
	                if(s1.contains(chr) && s2.contains(chr)){
	                	wkcnt++;
	                }
	            }
	            cnt = Math.max(cnt, wkcnt);
	    	}
	    }


		System.out.println(cnt);

	}
}

Measured memory_bytes: 34644
from collections import Counter
MOD = 998244353

N = int(input())
D = list(map(int, input().split()))
if D[0] != 0 or D.count(0) != 1:
    print(0)
    exit()
c = Counter(D)
if len(set(D)) != max(D) + 1:
    print(0)
    exit()
answer = 1
prev = 1
for k, v in c.items():
    answer *= prev ** v
    answer %= MOD
    prev = v
print(answer)

Measured memory_bytes: 22364
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <bitset>
#include <iomanip>
#include <deque>
#include <tuple>
#include <algorithm>

using namespace std;

int main()
{
    string s, t;

    cin >> s >> t;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] != t[i]) {
            cout << "No" << endl;
            return (0);
        }
    }

    cout << "Yes" << endl;

}


Measured memory_bytes: 3628
import java.util.*; 

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

        while(true){ 
            int a = sc.nextInt(); 
            int b = sc.nextInt(); 
            int c = sc.nextInt(); 
            int sum = a + b; 
            if(a == -1 && b == -1 && c== -1){ 
                break; 
            }else if(a == -1 || b == -1){ 
                System.out.println("F"); 
            }else{ 
                if(sum<30){ 
                    System.out.println("F"); 
                }else if(sum<50){ 
                    if(c<50){ 
                        System.out.println("D"); 
                    }else{ 
                        System.out.println("C"); 
                    } 
                }else if(sum<65){ 
                    System.out.println("C"); 
                }else if(sum<80){ 
                    System.out.println("B"); 
                }else{ 
                    System.out.println("A"); 
                } 
            } 
        } 
        sc.close(); 
    } 
}


Measured memory_bytes: 26308
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
  int N,M,X,a[102],i,j,count,cost[2],costmin;
  char str[1000],*p;
  
  fgets(str,sizeof(str),stdin);
  p=strtok(str," \n");
  N=atoi(p);
  p=strtok(NULL," \n");
  M=atoi(p);
  p=strtok(NULL," \n");
  X=atoi(p);
  
  fgets(str,sizeof(str),stdin);
  p=strtok(str," \n");
  a[1]=atoi(p);
  for(i=2;i<M+1;i++){
    p=strtok(NULL," \n");
  	a[i]=atoi(p);
  }
  a[0]=0,a[M+1]=N;
  count=0;
  while(a[count]<X){
   count++; 
  }
  for(i=X,j=count-1,cost[0]=0;i>0;i--){
   if(i==a[j]){
    cost[0]++,j--; 
   }
  }
  
  for(i=X,j=count,cost[1]=0;i<N;i++){
    if(i==a[j]){
      cost[1]++,j++;
    }
  }
  if(cost[0]<=cost[1]){
   costmin=cost[0]; 
  }else{
   costmin=cost[1]; 
  }
  printf("%d\n",costmin);
  
 return 0; 
}

Measured memory_bytes: 128
N = int(input())
S = list(input())
cnt_E = [S.count("E")]
flag = True
if S[0] == "W":
    cnt_W = [1]
else:
    cnt_W = [0]
    flag = False
SUM = [cnt_E[0]+cnt_W[0]]
for i in range(1,N):
    if S[i] == "W":
        cnt_W.append(cnt_W[i-1]+1)
        cnt_E.append(cnt_E[i-1])
    else:
        cnt_W.append(cnt_W[i-1])
        if flag:
            cnt_E.append(cnt_E[i-1])
            flag = False
        else:
            cnt_E.append(cnt_E[i-1]-1)
    SUM.append(cnt_W[i]+cnt_E[i])
print(min(SUM)-1)

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

int main(){
    string s, t; cin >> s >> t;
    int a, b; cin >> a >> b;
    string u; cin >> u;
    if(u == s){
        a--;
    }else{
        b--;
    }
    cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 2;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
//#define V vector<int>
//#define S set<int>
#define itn int
bool dbg = false;

int N;
string A;

/*
int kai[1010101];
int c[1010101];

void calc(){
    kai[0] = 1;
    FOR(i,1,N){
        kai[i] = c[0] * i;
        kai[i] %= 2;
    }
    FOR(i,0,N){
        c[i] = 
    }

}
*/

int C(int n, int r) {
    return (n == (r | (n - r)));
}

void solve() {
    int SUM = 0;
    bool flag2 = true;
    FOR(N) {
        if (A[i] % 2 == 1) {
            flag2 = false;
        }
    }
    if (flag2) {
        for (auto& c : A)
            c /= 2;
    }

    FOR(N) {
        SUM += C(N - 1, i) * A[i];
    }
    SUM %= 2;
    if (SUM == 1) {
        if (flag2) {
            cout << 2 << endl;
        } else {
            cout << 1 << endl;
        }
        return;
    } else {
        cout << 0 << endl;
    }
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N;
    cin >> A;
    for (auto& c : A)
        c -= '1';


    solve();
    return 0;
}


Measured memory_bytes: 1948
// https://atcoder.jp/contests/abc107/tasks/abc107_a

#include <iostream>
using namespace std;

int main()
{
  /* Magic word */
  cin.tie(0);
  ios::sync_with_stdio(false);
  /* ---------- */

  int n, i;

  cin >> n >> i;

  cout << n - i + 1 << '\n';

  return 0;
}


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

#define REP(i, n) for (int i = 0; i < n; ++i)
#define INPUT_INT1(n) int n; std::cin >> n;
#define INPUT_INT2(n,m) int n,m; std::cin >> n >> m;
#define INPUT_INT3(n,m,l) int n,m,l; std::cin >> n >> m >> l;
#define INPUT_INT4(n,m,l,o) int n,m,l,o; std::cin >> n >> m >> l >> o;
#define INPUT_INT5(n,m,l,o,p) int n,m,l,o,p; std::cin >> n >> m >> l >> o >> p;
#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME
#define INPUT_INT(...) GET_MACRO(__VA_ARGS__,INPUT_INT4,INPUT_INT3,INPUT_INT2,INPUT_INT1)(__VA_ARGS__)
#define INPUT_VECTOR(T, NAME, N) std::vector<T> NAME(N); \
  REP(_i, N) { \
    std::cin >> NAME[_i]; \
  }

int main(int argc, char* argv[]) {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  /* */
  INPUT_INT(n, k);
  INPUT_VECTOR(int, unusable, k);
  std::set<int> usable;
  for (int i = 0; i < 10; ++i) usable.insert(i);
  for (auto itr = unusable.begin(); itr != unusable.end(); ++itr)
    usable.erase(*itr);

  int thinking = 1;
  while (thinking <= n) thinking *= 10;
  thinking /= 10;
  auto first_thinking = thinking;
  while (thinking > 0) {
    if (usable.find(n / thinking % 10) == usable.end()) {
      n = n / thinking * thinking + thinking;
      thinking = first_thinking * 10;
      if (thinking > n) thinking /= 10;
      continue;
    }

    thinking /= 10;
  }
  std::printf("%d\n", n);
  /* */

  return EXIT_SUCCESS;
}


Measured memory_bytes: 256
import fractions

a,b,c,d = map(int, input().split())
#print(a,b,c,d)
total = b-a+1
#print(total)
lcm = int(c*d / fractions.gcd(c,d))
#print(lcm)
x = (b//c) + (b//d) - (b//lcm)
y = ((a-1)//c) + ((a-1)//d) - ((a-1)//lcm)
#print(x,y)
print(total - (x - y))


Measured memory_bytes: 5344
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())

ll modP(ll x, ll y, ll MOD)
{
    ll r = 1; x %= MOD; while (y > 0) {
        if (y & 1) {r = (r * x) % MOD;}
        y = y >> 1; x = (x * x) % MOD;
    } return r;
}
ll max(ll a, ll b) {return (a > b ? a : b);}
ll min(ll a, ll b) {return (a < b ? a : b);}
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " = " << arg1 << " | "; __f(comma + 1, args...);
}
ll gcd( ll a, ll b )
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd( b, (a % b) );
    }
}
ll lcm (ll a, ll b)
{
    ll ans = (a  / gcd(a, b)) * b;
    return ans;
}
void solve()
{
    ll ans = 0;
    ll n; 
 string s; 
 cin>>n>>s; 
 bool white=0;
 ll first=-1,last=-1;
for(int i=0;i<n;i++)
{
    if(s[i]=='W') 
    {
        first=i; 
        break;
    }
}

if(first==-1) 
ans=0; 
else 
{
    ll r=0,w=0;
    for(int i=first;i<n;i++) 
    {
      if(s[i]=='R') r++; 
      else 
      w++;
    }
    ans+=min(w,r); 
    ll res=0; 
    w=0; 
    for(int i=first;i<n;i++) 
    {
        if(w==r) 
        {
            ans=min(ans,w); 
            break;
        }
        if(s[i]=='R') r--; 
        else
        {
            w++;
        }
        
    }
}
    cout<<ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t ;
    t = 1;
//    cin >> t;

    for (int i = 1; i <= t; i++)
    {
        solve();
    }
    return 0;
}




Measured memory_bytes: 3784
s=int(input())
lis=[s]

for i in range(1000):
    if lis[i]%2==0:
        a=int(lis[i]/2)
        if a in lis:
            print(i+2)
            break
        else:
            lis.append(a)
            
    else:
        a=int(lis[i]*3+1)
        if a in lis:
            print(i+2)
            break
        else:
            lis.append(a)
        
        

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

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

  if (a < b) {
      cout << "a < b" << endl;
  }
  else if(a > b) {
      cout << "a > b" << endl;
  }
  else{
      cout << "a == b" << endl;
  }
}



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

constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3fLL;

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

    string s,t; cin >> s >> t;
    int ans = 0;
    for (int i = 0; i < (int)s.length(); i++) {
        ans += s[i] != t[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3788
from collections import defaultdict
from itertools import combinations


N = int(input())
d = defaultdict(int)
for _ in range(N):
    S = input()
    if S[0] in 'MARCH':
        d[S[0]] += 1

ans = 0
for a, b, c in combinations('MARCH', 3):
    ans += d[a] * d[b] * d[c]
print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <sstream>
using namespace std;



int main()
{	
	int n;
	cin >> n;
	int birth[1000][11][21];
	int ctn = 196470;
	for (int y = 1; y < 1000; y++) {
		for (int m = 1; m < 11; m++) {
			int ma;
			if (y % 3 == 0) ma = 20;
			else if (m % 2) ma = 20;
			else ma = 19;
			for (int d = 1; d <= ma; d++) {
				birth[y][m][d] = ctn;
				ctn--;
			}
		}
	}
	int y, m, d;
	while (n--) {
		cin >> y >> m >> d;
		cout << birth[y][m][d] << endl;
	}

	return 0;
}

Measured memory_bytes: 2060
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    int n;
    cin >> n;
    vector<tuple<ll, int, int>> ls;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        ls.emplace_back(a+b, a, b);
    }
    sort(rall(ls));
    ll T = 0, A = 0;
    bool flg = true;
    for (auto x : ls) {
        if (flg) T += get<1>(x);
        else A += get<2>(x);
        flg = flg ^ 1;
    }
    ll ans = T-A;

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

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

int a[5005];
int memo[5005][5005];

int N, K;
int M;

/*
// smallest index such that it is useless.
int dp(int i, int sum){
    if(sum >= A[i] - K && sum < K){
        return i;
    }else if(memo[i][sum] != -1){
        return memo[i][sum];
    }else{
        return memo[i][sum] = min(dp(i+1, sum+), dp(i+1, sum));
    }
}*/

bitset<5005> dp;

bool boleh(int i){
    dp = bitset<5005>();
    dp[0] = 1;
    for(int j = 0; j < M; j ++){
        if(j == i){continue;}
        dp |= (dp<<a[j]);
    }

    bool found = false;
    for(int j = K-a[i]; j < K; j ++){
        if(dp[j]){
            found = true;
            //printf("a[%d]=%d is necessary\n", i, a[i]);
            break;
        }
    }
    return found;
}

int main(){
    scanf("%d%d", &N, &K);

    for(int i = 0; i < N; i ++){
        scanf("%d", &a[i]);
    }
    sort(a, a+N);
    M = lower_bound(a, a+N, K)-a;

    int sum = 0;
    int P = M;
    for(int i = 0; i < M; i ++){
        sum += a[i];
        if(sum <= K){
            int indx = lower_bound(a+(i+1), a+M, K-a[i])-a;
            P = min(indx, P);
        }else{
            break;
        }
    }
    //printf("P=%d\n", P);

    //int ans = P;
    int lo = 0;
    int hi = P;
    while(lo < hi){
        int mid = (lo+hi)>>1;
        if(boleh(mid)){
            hi = mid;
        }else{
            lo = mid+1;
        }
    }


    /*
    for(int i = 0; i < P; i ++){
        dp = bitset<5005>();
        dp[0] = 1;
        for(int j = 0; j < M; j ++){
            if(j == i){continue;}
            dp |= (dp<<a[j]);
        }

        bool found = false;
        for(int j = K-a[i]; j < K; j ++){
            if(dp[j]){
                ans --;
                found = true;
                //printf("a[%d]=%d is necessary\n", i, a[i]);
                break;
            }
        }
        if(found){
            printf("%d\n", i);
            return 0;
        }
    }
    */

    printf("%d\n", lo);
    return 0;
}


Measured memory_bytes: 3864
#include<bits/stdc++.h>
#define MAX 3000
#define ll long long
#define mod (1000000000+7)
#define Fast ios_base::sync_with_stdio(false); cin.tie(NULL);

using namespace std;

int main()
{
    int h,w; cin>>h>>w;
    char ch;
    char G[h][w];
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
            cin>>G[i][j];
    }
    ll int T[h][w];
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            T[i][j] = 0;
        }
    }
    for(int j=0;j<w;j++)
    {
        if(G[0][j]=='.')
            T[0][j] = 1;
        else
            break;
    }
    for(int i=0;i<h;i++)
    {
        if(G[i][0]=='.')
            T[i][0] = 1;
        else
            break;
    }
    for(int i=1;i<h;i++)
    {
        for(int j=1;j<w;j++)
        {
            if(G[i][j]=='.')
                T[i][j] = (T[i-1][j] + T[i][j-1]) % mod;
        }
    }
    /*for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cout<<T[i][j]<<" ";
        }cout<<endl;
    }*/
    cout<<T[h-1][w-1];
}


Measured memory_bytes: 9088
n,k=map(int,input().split())
a=list(map(int,input().split()))

f=[0 for _ in range(n)]
s=[0 for _ in range(n)]
for i in range(n):
  for j in range(n):
    if a[i]>a[j]:
      s[i]+=1
  for j in range(i,n):
    if a[i]>a[j]:
      f[i]+=1
sm=0
for i in range(n):
  sm=(sm+k*f[i]+k*(k-1)//2*s[i])%(10**9+7)
print(sm)
    

Measured memory_bytes: 9004
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> v(n+1, -1);
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    v[i+1] = k;
  }
  int c = 1;
  int count = 0;
  while (c != -1) {
    if (c == 2) {
      cout << count << endl;
      return 0;
    }
    int u = v[c];
    v[c] = -1;
    c = u;
    count++;
  }
  cout << "-1" << endl;
  return 0;
}

Measured memory_bytes: 640
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

c = Counter()
N, K = map(int, input().split())
for k in range(K):
    d = int(input())
    As = list(map(int, input().split()))
    for a in As: c[a] += 1
print(N - len(c))




Measured memory_bytes: 10852
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
const int INF = 1000000000;
typedef pair<int, int> P;
const int MAX_N = 1000000;
typedef int64_t ll;
template<class T> inline bool chmax(T & a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T & a, T b) { if (a > b) { a = b; return 1; } return 0; }



int main() {
	string A, B;
	cin >> A >> B;
	
	if (A.size()> B.size())
	{
		cout << "GREATER" << endl;
	}
	else if (A.size() < B.size()) {
		cout << "LESS" << endl;
	}
	else {
		rep(i, A.size()) {
			if (A.at(i) > B.at(i))
			{
				cout << "GREATER" << endl;
				return 0;
			}
			else if (A.at(i) < B.at(i)) {
				cout << "LESS" << endl;
				return 0;
			}
			else {
				continue;
			}
		}
		cout << "EQUAL" << endl;
	}
		return 0;
}

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

int main(int argc, char const *argv[]) {
  string s;
  std::cin >> s;

  for(int i=0; i<5; i++) std::cout << s[i];
  std::cout << " " ;
  for(int i=6; i<13; i++) std::cout << s[i];
  std::cout << " " ;
  for(int i=14; i<s.size(); i++) std::cout << s[i] ;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a,b,c,d,max;
	while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
	{
		if(a>=d||b<=c)
		printf("0\n");
		else if(a<=c&&b>=c&&b<=d)
		printf("%d\n",b-c);
		else if(a<=c&&b>=d)
		printf("%d\n",d-c);
		else if(c<=a&&d>=a&&b>=d)
		printf("%d\n",d-a);
		else if(c<=a&&d>=b)
		printf("%d\n",b-a);
	}
	return 0;
}

Measured memory_bytes: 128
N,K= map(int,input().split())
h = list(map(int,input().split()))
dp =[0]*N
dp[0] = 0
dp[1] = h[0]
for j in range(1,N):
  dp[j] = dp[j-1] + abs(h[j] - h[j-1])
  for i in range(max(j-K,0),j):
    dp[j]=min(dp[i]+ abs(h[j]-h[i]),dp[j]) 
print(dp[-1])

Measured memory_bytes: 52448
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define lol(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	string t[8]={
		"+++",
		"++-",
		"+-+",
		"-++",
		"+--",
		"-+-",
		"--+",
		"---"
	};
	string s;
	cin>>s;
	for(int i=0;i<8;i++){
		int cnt=s[0]-'0';
		for(int j=0;j<3;j++){
			if(t[i][j]=='+')cnt+=s[j+1]-'0';
			else cnt-=s[j+1]-'0';
		}
		if(cnt==7){
			cout<<s[0];
			for(int j=0;j<3;j++)cout<<t[i][j]<<s[j+1];
			cout<<"=7"<<endl;
			break;
		}
	}
	return 0;
}


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

typedef vector< ll > 	vi;
typedef vector< vi > 	vvi;
typedef pair< ll,ll > 	ii;
#define pb 		push_back
#define all(c) 		(c).begin(),(c).end()
#define tr(c,i) 	for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) 	((c).find(x) != (c).end())

#define MOD 	1000000007
#define INF 	(int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))

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

	ll n,x;
	cin>>n;
	std::vector<ll> v;
	for(ll i=0; i<n; i++)
	{
		cin>>x; v.push_back(x);
	}

	sort(all(v));
	//tr(v, i)
	//	cout<< *i;
	double ans = v[0];
	for(ll i=1; i<n; i++)
	{
		ans = (double)((v[i]+ ans)/ 2 ); 
		//cout<<ans<<endl;
	}

	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
//小数点以下　cout << fixed << setprecision(10) << num << endl;
//桁数はlog10(mid)でやれ　log(mid)/log(10)はWA
//long*long<0で判定するな
//開区間と閉区間
//アルファベットが何番目かは x=s[i]-'a'
//bfsはmain()内で　rep(i,h)rep(j,w)rep(i,4)でバグ
//切り上げ：(a+(b-1))/b
//32bit以上は 1ull<<j]

int main(){
    int n; cin >> n;
    vector<int> d;
    rep(i,n){
        int a; cin >> a;
        d.pb(a);
    }
    sort(d.begin(),d.end());
    int ans=0;
    rep(i,n){
        if(d[i]!=d[i+1]) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <vector>

using namespace std;

class bestValueMaintainer {
 public:
  int best = -1, cand = -1;
  int bestIdx, candIdx;
  void update(int idx, int val) {  
    if (val > best) {
      cand = best; candIdx = bestIdx;
      best = val; bestIdx = idx;
    }
    else if (val > cand) {
      cand = val; candIdx = idx;
    }
  }
};

int sol(const vector<int>& v) {
  vector<int> stat[2];
  stat[0].resize(111111);
  stat[1].resize(111111);
  for (int i = 0 ; i != v.size() ; i++) {
    stat[i%2][v[i]]++;
  }
  bestValueMaintainer bvm[2];
  for (int k = 0 ; k < 2 ; k++) {
    for (int i = 0 ; i != stat[k].size() ; i++)
      bvm[k].update(i, stat[k][i]);
  }
  if (bvm[0].bestIdx != bvm[1].bestIdx) {
    return v.size() - bvm[0].best - bvm[1].best;
  }
  else if (bvm[0].best + bvm[1].cand > bvm[0].cand + bvm[1].best) {
    assert(bvm[1].cand >= 0);
    return v.size() - bvm[0].best - bvm[1].cand;
  }
  else {
    assert(bvm[0].cand >= 0);
    return v.size() - bvm[0].cand - bvm[1].best;
  }
}

int main()
{
  int n;
  cin >> n;
  vector<int> v;
  for (int i = 0 ; i != n ; i++) {
    int a;
    cin >> a;
    v.push_back(a);
  }
  cout << sol(v) << endl;
  return 0;
}



Measured memory_bytes: 1656
N,Y=map(int,input().split())
for i in range(0,N+1):
    for j in range(0,N-i+1):
        k=(Y-i*10000-j*5000)/1000
        if k>=0 and k%1==0.0 and i+j+k==N:
            k=int(k)
            print('{} {} {}'.format(i,j,k))
            exit()

print('{} {} {}'.format(-1,-1,-1))


Measured memory_bytes: 9024
H, W = map(int, input().split())
dungeon = []
for i in range(0, H):
	dungeon.append(input())
across = []
for i in range(0, H):
	lst = []
	r = []
	for j in range(0, W):
		if dungeon[i][j] == '.':
			if r == []: r.append(j)
		else:
			if r != []:
				r.append(j)
				lst.append(r)
				r = []
	if r != []:
		r.append(W)
		lst.append(r)
	across.append(lst)
acrossdungeon = []
for i in range(0, H):
	lst = []
	index = 0
	for j in range(0, W):
		if dungeon[i][j] == '.':
			lst.append(across[i][index][1]-across[i][index][0])
		else:
			if j != 0:
				if lst[-1] != -1:
					index += 1
			lst.append(-1)
	acrossdungeon.append(lst)
down = []
for i in range(0, W):
	lst = []
	r = []
	for j in range(0, H):
		if dungeon[j][i] == '.':
			if r == []: r.append(j)
		else:
			if r != []:
				r.append(j)
				lst.append(r)
				r = []
	if r != []:
		r.append(H)
		lst.append(r)
	down.append(lst)
downdungeon = []
for i in range(0, W):
	lst = []
	index = 0
	for j in range(0, H):
		if dungeon[j][i] == '.':
			lst.append(down[i][index][1]-down[i][index][0])
		else:
			if j != 0:
				if lst[-1] != -1:
					index += 1
			lst.append(-1)
	downdungeon.append(lst)
max = 0
for i in range(0, H):
	for j in range(0, W):
		if dungeon[i][j] != '#':
			lights = acrossdungeon[i][j] + downdungeon[j][i] - 1
			if max < lights: max = lights
print(max)

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

//素数判定関数
bool isPrime(int n){
    if (n < 2) return false;
    else if (n == 2) return true;
    else if (n % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtN = sqrt(n);
    for (int i = 3; i <= sqrtN; i += 2){
        if (n % i == 0){
            // 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}

int main(){
    int x;
    cin >> x;
    for(int i=x; ; i++){
        if(isPrime(i)){
            cout << i << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
Edge = [list(map(int,input().split())) for i in range(m)]

count = 0

for i in range(m):
    Edge_ = Edge[:i]+Edge[i+1:]

    Graph = [[] for i in range(n)]
    for edge in Edge_:
        Graph[edge[0]-1].append(edge[1]-1)
        Graph[edge[1]-1].append(edge[0]-1)

    visited = [False]*n
    visited[0] = True

    stack = [0]
    while stack:
        node = stack.pop()
        for adj in Graph[node]:
            if visited[adj] == False:
                visited[adj] = True
                stack.append(adj)
                
    if not all(visited):
        count += 1
        
print(count)

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

long long a[100010];
int sum[50];

int main(){
	int n; long long k;
	scanf("%d%lld", &n, &k);
	for (int i = 0; i < n; i++){
		scanf("%lld", &a[i]);
		for (int j = 0; j <= 40; j++){
			sum[j] += a[i] >> j & 1;
		}
	}
	long long ans = 0;
	for (int i = 40; i >= 0; i--){
		if (k < (1ll << i)) ans += sum[i] * (1ll << i);
		else {
			if (sum[i] > n - sum[i]) ans += sum[i] * (1ll << i);
			else ans += (n - sum[i]) * (1ll << i), k -= (1ll << i);
		}
	}
	printf("%lld\n", ans);
	return 0;
}


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

int dp[20][20];
int cnt;
int a, b;
int mx[2] = {0,1};
int my[2] = {1,0};

int solve(int x, int y){
  int ret = 0;
  if(dp[y][x] != -1){
    return dp[y][x];
  }

  for(int i = 0; i < 2; i++){
    int nx = mx[i] + x, ny = my[i] + y;
    if(nx >= 1 && ny >= 1 && nx <= a && ny <= b){
      ret += solve(nx,ny);
    }
  }
  return dp[y][x] = ret;
}

int main(){

  while(1){
    cin >> a >> b;
    if(a == 0 && b == 0) break;
    int n;
    cin >> n;

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

    dp[b][a] = 1;
    for(int i = 0; i < n; i++){
      int x, y;
      cin >> x >> y;
      dp[y][x] = 0;
    }

    int ans = solve(1,1);
    cout << ans << endl;
  }

}

Measured memory_bytes: 1156
use proconio::input;

const LIMIT: i64 = 1_000_000_000_000_000_000;

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

    if a.iter().any(|x| *x == 0) {
        println!("0");
        return;
    }

    let ans = a
        .iter()
        .copied()
        .fold(Some(1i64), |acc, x| acc.and_then(|y| y.checked_mul(x)))
        .and_then(|x| if x <= LIMIT { Some(x) } else { None })
        .unwrap_or(-1);
    println!("{}", ans);
}


Measured memory_bytes: 4492
#include<cstdio>
#include<bits/stdc++.h>
#define fi first
#define sc second
#define pb push_back


using namespace std;

int main() {

	int N;
	map<char, int> mep;
	cin >> N;
	for (int i = 0; i < N; i++) {
		char c;
		cin >> c;
		mep[c]++;
	}
	if (mep.size() == 3)  cout << "Three\n";
	else cout << "Four\n";
	return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	// Code for C - Otoshidama
	var N, Y int
	fmt.Scanf("%d %d", &N, &Y)

	var yen10000, count int
	var flag int = 0
	for i := 0; i <= N; i++ {
		for j := 0; j <= N; j++ {
			yen10000 = Y - 1000*i - 5000*j
			count = yen10000 / 10000
			if yen10000%10000 == 0 && count+i+j == N && yen10000 >= 0 {
				fmt.Println(count, j, i)
				flag = 1
				break
			}
		}

		if flag == 1 {
			break
		}
	}

	if flag == 0 {
		fmt.Println("-1 -1 -1")
	}
}


Measured memory_bytes: 1860
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  string s;
  ll k;
  cin >> s >> k;
  rep(i, s.length()){
    if(i + 1 == k){
      if(s[i] == '1') cout << 1 << endl;
      else cout << s[i] << endl;
      return 0;
    }
    if(s[i] != '1'){
      cout << s[i] << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int A, B;
    cin >> A >> B;
    if (A%3 == 0 || B%3 == 0 || (A+B)%3 == 0) cout << "Possible" << endl;
    else cout << "Impossible" << endl;
}

Measured memory_bytes: 256
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapq.heapify(A)

for i in range(M):
    a = heapq.heappop(A)
    a /= 2
    heapq.heappush(A, a)

ans = 0
for a in A:
    ans += - a//1
print(int(ans))

Measured memory_bytes: 14180
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  bool flag = true;
  for(int i=0; i<N; i++){
    if(vec.at(i) %2 == 0){
      if(vec.at(i) %3 != 0 && vec.at(i) %5 != 0){
        flag = false;
      }
    }
  }
  if(flag){
    cout << "APPROVED" << endl;
  }
  else{
    cout << "DENIED" << endl;
  }
}

Measured memory_bytes: 256
/* AUTHOR :  SHIVANK JAIN */

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false)
#define itt cin.tie(0)
#define now cout.tie(0)

using namespace std;

#define ll long long
#define li long int

#define pb push_back
#define rep(i,a,n) for(int i=a;i<n;i++)
#define reprev(i,n,a) for(int i=n;i>=a;i--)
#define endl "\n"

#define vi vector<int>
#define vll vector<ll>
#define vpi vector< pair<int , int> >
#define mapi map<int , int>
#define mapll map<ll ,ll >
#define seti set<int> 

#define fr first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair
#define sort(v) sort(v.begin() , v.end())

#define BIG 1000000007
int gcd(int a, int b) 
{ // builtin function __gcd(a,b)
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
int main(){

     fast;itt;now;
 
//    #ifndef ONLINE_JUDGE
//    // for getting input from input.txt
//    freopen("input.txt", "r", stdin);
//    // for writing output to output.txt
//     freopen("output.txt", "w", stdout);
//    #endif
    
     int n;   cin>>n;
     n = n % 10;
     if(n == 0 || n == 1 || n == 6 ||n == 8)
      cout<<"pon"<<endl;
     else{
	 if(n == 2 ||n == 4 || n == 5 || n == 7 || n == 9) 
	  cout<<"hon"<<endl;
	 else
	  cout<<"bon"<<endl;
 }
}

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

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

    int n, t, a;
    cin >> n >> t >> a;
    auto min_diff = (double)1e9;
    int pos;
    int h;

    for (int i = 1; i <= n; ++i) {
        cin >> h;
        auto diff = (double) abs(t - h * 0.006 - a);
        if (diff < min_diff) {
            min_diff = diff;
            pos = i;
        }
    }
    cout << pos << '\n';

    return 0;
}


Measured memory_bytes: 256