akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

    def root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.root(self.table[x])
            return self.table[x]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1


def main():
    n = I()
    A = LI()
    B = LI()
    a_sort_index = sorted(range(n), key=lambda x:A[x])
    b_sort_index = sorted(range(n), key=lambda x: B[x])
    flag = 0
    U = UnionFind(n)
    for i in range(n):
        if A[a_sort_index[i]] > B[b_sort_index[i]]:
            return 'No'
        elif i != 0 and A[a_sort_index[i]] <= B[b_sort_index[i - 1]]:
            flag = 1
        U.union(a_sort_index[i], b_sort_index[i])
    if U.group_num == 1 and not flag:
        return 'No'
    else:
        return 'Yes'



print(main())



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

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	string s;
	cin >> s;

	sort(all(s));
	for(int i = 1; i < s.size(); i++)
		if(s[i] == s[i-1])
		{
			cout << "no" << endl;
			return 0;
		}

	cout << "yes" << endl;
	return 0;	
}

Measured memory_bytes: 256
// Aizu 2259: Programming Contest
// 2017.9.22 bal4u@uu

#include <stdio.h>
#include <string.h>

int f[22];

int main()
{
	int m, n, i, j, a, ans;

	scanf("%d%d", &m, &n);
	memset(f, 0, sizeof(f));
	for (i = 0; i < m; i++) for (j = 0; j < n; j++) scanf("%d", &a), f[i] += a;
	for (ans = 0, i = 0; i < m; i++) if (f[i] > ans) ans = f[i];
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1800
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int cnt[1000010] = {0};
int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        if (cnt[a[i]] > 1 || (a[i] > 1 && cnt[1] > 0)) {
            ans++;
        } else {
            for (int j=2; j*j <= a[i] && j < a[i]; j++) {
                if (a[i] % j == 0) {
                    if (cnt[j] > 0 || cnt[a[i] / j] > 0) {
                        ans++;
                        break;
                    }
                }
            }
        }
    }
    cout << n - ans << '\n';
    return 0;
}

Measured memory_bytes: 8264
#include<iostream>
using namespace std;
int main(){
    int len;
    string s;
    cin>>len>>s;
    long long s1=0,s2=0,s3=0,sum=0;
    for(int i=0;i<len;i++){
        if(s[i]=='R') s1++;
        if(s[i]=='G') s2++;
        if(s[i]=='B') s3++;
    }
    sum=s1*s2*s3;
    for(int i=0;i<len;i++){
        for(int j=i;j<len;j+=2){
            if(s[i]!=s[j] && s[i]!=s[(i+j)/2] && s[j]!=s[(i+j)/2]) sum--;
        }
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 3636
def main():
    N, M, X, Y = map(int, input().split())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    flg = False

    for z in range(X + 1, Y + 1):
        if max(x) < z <= min(y):
            flg = True

    if flg:
        print("No War")
    else:
        print("War")

main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int dansuu = 0;
  
  int N;
  cin >> N;
  
  
  vector<int> d(N);
  for (int i = 0; i < N; i++) {
    
    cin >> d.at(i);
    
  }
  
  
    
    
  for (int i = 0; i < N; i++) {
    
    int a = d.at(i);
    
    if (a == 0) {
      
      continue;
      
    } else {
      
      dansuu++;
      
      for(int i = 0; i < N; i++) {
      
        if (a == d.at(i)) {
        
          d.at(i) = 0;
        
        } else {
        
          continue;
        
        }
      
      }
      
    }
    
    
    
  }
  
  cout << dansuu << endl;
  
}
 
  
  


Measured memory_bytes: 3624
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	char a[100001];
	cin>>a;
	if(a[0]==a[strlen(a)-1])
	{
		if(strlen(a)%2==1) cout<<"Second";
		else cout<<"First";
	}
	else
	{
		if(strlen(a)%2==0) cout<<"Second";
		else cout<<"First";
	}
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>

#define rep(i,n) for(int i = 0;i < n;i++)
#define Rep(i,m,M) for(int i = m;i < M;i++)
#define print(var) cout<<#var" = "<<var<<endl;
#define mod 1000000007
typedef long long ll;

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;

int main()
{
	int N;
	cin >> N;
	vint factor(N+1);
	const vint PRIME = {
	2, 3, 5, 7, 11,
	13, 17, 19, 23, 29,
	31, 37, 41, 43, 47,
	53, 59, 61, 67, 71,
	73, 79, 83, 89, 97,
	101, 103, 107, 109, 113,
	127, 131, 137, 139, 149,
	151, 157, 163, 167, 173,
	179, 181, 191, 193, 197,
	199, 211, 223, 227, 229,
	233, 239, 241, 251, 257,
	263, 269, 271, 277, 281,
	283, 293, 307, 311, 313,
	317, 331, 337, 347, 349,
	353, 359, 367, 373, 379,
	383, 389, 397, 401, 409,
	419, 421, 431, 433, 439,
	443, 449, 457, 461, 463,
	467, 479, 487, 491, 499,
	503, 509, 521, 523, 541,
	547, 557, 563, 569, 571,
	577, 587, 593, 599, 601,
	607, 613, 617, 619, 631,
	641, 643, 647, 653, 659,
	661, 673, 677, 683, 691,
	701, 709, 719, 727, 733,
	739, 743, 751, 757, 761,
	769, 773, 787, 797, 809,
	811, 821, 823, 827, 829,
	839, 853, 857, 859, 863,
	877, 881, 883, 887, 907,
	911, 919, 929, 937, 941,
	947, 953, 967, 971, 977,
	983, 991, 997 };
	const int Pnum = PRIME.size();
	for(int i = 2;i<=N;i++)
	{
		int m = i;
		while (m >= 2)
		{
			for (int j = 0; j < Pnum; j++)
			{

				if (m % PRIME[j] == 0)
				{
					factor[j]++;
					m = m / PRIME[j];
				}
			}
		}
	}
	ll ans = 1;
	for(int i = 0; i < Pnum and PRIME[i] <= N;i++)
	{
	//	cout << PRIME[i] << " : " << factor[i] << endl;
		ans = (ans * (factor[i] + 1)) % mod;
	}
	cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n,q;
vector<int>G[200010];
int a[200010];
int ans[200010];
void dfs(int x,int pr=-1){
	ans[x]=ans[pr]+a[x];
	for(auto to:G[x])if(to!=pr){
		dfs(to,x);
	}
}
int main(){
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		G[x].pb(y);
		G[y].pb(x);
	}
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		a[x]+=y;
	}
	dfs(1);
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
	puts("");
	return 0;
}


Measured memory_bytes: 24064
def c_alchemist():
    N = int(input())
    V = [int(i) for i in input().split()]
    v = sorted(V, reverse=True)
    while len(v) > 1:
        x = v.pop()
        y = v.pop()
        v.append((x + y) / 2)
    return sum(v)

print(c_alchemist())

Measured memory_bytes: 3060
//AtCoDeerandPaintCans.cpp (A)
#include <iostream>
using namespace std;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(a==b&&b==c) printf("1\n");
  else if(a==b||b==c||c==a) printf("2\n");
  else printf("3\n");
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long sum = 0;
    long ans = 0;
    for(int i = 0; i < n; i++) {
      long a = sc.nextLong();
      sum += a;
      if((a == 0) || (i == (n - 1))) {
        ans += (sum / 2);
        sum = 0;
      }
    }
    System.out.println(ans);
  }
}

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

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

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

 return 0;
}

Measured memory_bytes: 3120
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<climits>
#include<cmath>
#include<cstring>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define endl "\n"
typedef long long ll;
int mod=(int)1e9+7;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	ll ans=1ll*max(a,b)*max(c,d);
	ll temp=1ll*min(a,b)*min(c,d);
	ans=max(ans,temp);

	temp=1ll*max(a,b)*min(c,d);
	ans=max(ans,temp);
	
	temp=1ll*min(a,b)*max(c,d);
	ans=max(ans,temp);
	cout<<ans<<endl;
	return 0;
}

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

int main() {
	int x,n;
  	cin>>x>>n;
  
  	vector<int> p(110);
  	rep(i,n)cin>>p[i];
   
  //これパクればよいのでは
    int num[110] = {0};  // バケット
    for (int i = 0; i < n; ++i) {
        num[p[i]]++;  // p[i] が 1 個増える
    }

  //xがnにないやつ
  	bool xganai=true;
  
  for(int i=0;i<n;i++){
  	if(x==p[i]){
    	xganai=false;
    }
  }
  
    //xより小さいのを下から調べる
    int ue=0;
    
   for(int j=0;j<x;j++){
   	if(num[j]==0){
    	ue=j;
    }
    }	
     
     //xより大きいのを上から調べる
    int sita=101;
    
   for(int k=100;k>x;k--){
   	if(num[k]==0){
    	sita=k;
    }
    }	
     
     
	int uehikaku=x-ue;
  	int sitahikaku=sita-x;

  int joku=101-x;
  

 
  if(xganai){
  	cout<<x<<endl;
  }
  
 
  
  else if(uehikaku<=sitahikaku){
  cout<<ue<<endl;
}

 else{
 	cout<<sita<<endl;
 }
}


Measured memory_bytes: 3628
import Data.List

main = interact $ unlines . map (show . osaki) . read' . lines
 where
  read' ("0":_) = []
  read' (n:xs) = sort (map words hms) : read' xs'
   where (hms,xs') = splitAt (read n) xs

osaki hms = osaki' [] hms
 where
  osaki' acc [] = length acc
  osaki' [] ([d,a]:xs) = osaki' [a] xs
  osaki' acc ([d,a]:xs)
   | d >= minimum acc = osaki' (a : tail (sort acc)) xs
   | otherwise = osaki' (a:acc) xs

Measured memory_bytes: 24444
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

// a[n] := n層目の厚さ
// p[n] := n層目のパティ総数
// n 層目の下から x 番目までの総数
fn f(a: &Vec<isize>, p: &Vec<isize>, n: isize, x: isize) -> usize {
    if n == 0 {
        if x <= 0 {
            0
        } else {
            1
        }
    } else if x <= (1 + a[n as usize - 1]) as isize {
        // 一番下から1個前の層の厚さまで
        f(a, p, n - 1, x - 1) // n - 1 層目の x - 1 枚目まで
    } else {
        // それより上⇒n-1層目までのパティ+真ん中のパティ+そこから上のぶん
        (p[n as usize - 1] + 1) as usize + f(&a, &p, n - 1, x - 2 - a[n as usize - 1])
    }
}

fn main() {
    input! { n: isize, x: isize }
    let mut a: Vec<isize> = vec![];
    let mut p: Vec<isize> = vec![];
    a.push(1);
    p.push(1);
    let mut an = 1;
    let mut pn = 1;
    for i in 0..n {
        an = 2 * an + 3;
        pn = 2 * pn + 1;
        a.push(an);
        p.push(pn);
    }
    println!("{}", f(&a, &p, n, x));
}


Measured memory_bytes: 4352
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int a,b; cin >> a >>b;
    cout << ((a%2 == 0||b%2==0) ? "No" : "Yes") << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>



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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < n;i++)
#define rev(i, n) for(int i = n;i >= 0;i--)
#define Rep(i, m, n) for(int i = m;i < n;i++)
#define repeatrev(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define itn int

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef priority_queue<int> Pr;

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll int n;
    ll int ans = 0;
    cin >> n;
    for(ll int i=1 ; i*i<=n ; ++i){
        if(n % i == 0){
            ll int g = n / i;
            if(g - 1 > i) ans += g - 1;
        }
    }
    cout << ans << endl;
    }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
int main()
{
	int n,i;
	ll s=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		if(i%3!=0&&i%5!=0)
			s+=i;
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 3624
#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>;
#define chmax(x,y) x = max(x,y);

vector<int> to[100005];
int dist[100005][3];
const int INF = 1001001001;

int main() {
    int n, m;
    cin >> n >> m;
    rep(i,m) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        to[u].push_back(v);
    }
    int sv, tv;
    cin >> sv >> tv;
    sv--; tv--;
    queue<P> q;
    q.emplace(sv,0);
    rep(i,n)rep(j,3) dist[i][j] = INF;
    dist[sv][0] = 0;
    while (!q.empty()) {
        int v = q.front().first;
        int l = q.front().second;
        q.pop();
        for (int u : to[v]) {
            int nl = (l+1)%3;
            if (dist[u][nl] != INF) continue;
            dist[u][nl] = dist[v][l] + 1;
            q.emplace(u,nl);
        }
    }
    int ans = 0;
    if (dist[tv][0] == INF) ans = -1;
    else ans = dist[tv][0]/3;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 10192
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define bFor(i,a,b) for(i=a;i>=b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
#define endl "\n"
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}while(0)

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

vec eratosthenes(ll N){
  ll i;
  vec ch(N+1,1),p;
  ch[0]=ch[1]=0;
  rep(i,N+1){
    if(ch[i]){
      p.push_back(i);
      for(ll j=2;i*j<=N;j++){
        ch[i*j]=0;
      }
    }
  }
  return ch;
}
int main(){
  ll i,j,N=100,a,b;
  cin>>a>>b;a--;b--;
  cout<<"100 100"<<endl;
  mat v(N,vec(N,0));
  rep(i,N/2){
    if(i%2)rep(j,N){
      if(a){
        if(j%2){
          v[i][j]=1;
          a--;
        }
      }else{
        break;
      }
    }
  }
  bFor(i,N-1,N/2){
    if(i%2)rep(j,N){
      if(b){
        if(j%2){
          v[i][j]=1;
          b--;
        }
      }else{
        break;
      }
    }
  }
  For(i,N/2,N){
    rep(j,N){
      v[i][j]^=1;
    }
  }
  rep(i,N){
    rep(j,N){
      if(v[i][j]){
        cout<<".";
      }else{
        cout<<"#";
      }
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 384
function howMuch(items, item, s) {
  try{
  var
  recipe, price = items[item].price,
  sum, flag = false, j;
  s = s || [];
//  console.log(item, s);
  if(recipe = items[item].recipe) {
    s.push(item);
    sum = 0; flag  = true;
    for(j = 0; j < recipe.length; j++) {
      if(s.indexOf(recipe[j]) !== -1 || !(recipe[j] in items)) {
        flag = false;
        break;
      }
      sum += howMuch(items, recipe[j], s);
    }
    if(flag) {
      price = min(price, sum);
    }
    s.pop();
  }
  }catch(e){throw [e,items,item];}
  
  return price;
}

function min(x, y) {
  return x < y ? x : y;
}

function main() {
  var
  i, n, m, line,
  len = input.length,
  items;
  for(i = 0; i < len;) {
    items = {};
    n = parseInt(input[i++], 10) + i;
    if(n === i) break;
    for(; i < n; i++) {
      line = input[i].split(' ');
      items[line[0]] = {price: parseInt(line[1], 10)};
    } 
    m = parseInt(input[i++], 10) + i;
    for(; i < m; i++) {
      line = input[i].split(' ');
      items[line[0]].recipe = line.slice(2);
    }
//    console.log(items);
    console.log(howMuch(items, input[i++]));
  }
}

var
input = '';

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
process.stdin.on('end', function() {
  input = input.split('\n');
  main();
});

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	string ans = "";
	for(int i=0; i<3; i++){
		string t;
		cin >> t;
		ans += t[0] - 'a' + 'A';
	}
	cout << ans << endl;
	
	return 0;
}


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

using namespace std;

/* return gcd(x, y) */
int gcd(int x, int y){
    return y ? gcd(y, x % y) : x;
}

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

    int ans1 = gcd(a, b);
    int ans2 = gcd(b, c);

    if((ans2 % ans1) == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	s := next()

	max := 0
	for i := 0; i < n; i++ {
		left, right := map[rune]bool{}, map[rune]bool{}
		for _, r := range s[:i] {
			left[r] = true
		}
		for _, r := range s[i:] {
			right[r] = true
		}

		c := 0
		for r, includeLeft := range left {
			if includeLeft && right[r] {
				c++
			}
		}

		if max < c {
			max = c
		}
	}

	fmt.Println(max)
}


Measured memory_bytes: 768
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

map<string, vector<long long int>>mp;
vector<long long int>two;
vector<long long int>by;

vector<long long int> Search(string s) {
	if (mp.find(s) != mp.end())return mp[s];
	vector<vector<long long int>>dp(3, vector<long long int>(s.size() + 1));
	dp[0][0] = 1;
	for (int i = 0; i < s.size(); i++) {
		for (int j = 1; j <= s.size(); j++) {
			for (int k = j * 2; k + i <= s.size(); k += j) {
				long long int num = 1;
				vector<int>v(j, 1);
				for (int l = i; l < i + k; l++) {
					v[(l - i) % j] &= s[l] == '1';
				}
				string t;
				for (auto l : v)t.push_back(l + '0');
				auto box = Search(t);
				num = two[accumulate(v.begin(), v.end(), 0)];
				for (int l = 0; l < 3; l++) {
					if (j > 1)dp[min(l + 1, 2)][i + k] += (dp[l][i])*(Search(t)[2]) % MOD*by[k / j] % MOD;
					else dp[min(l + 1, 2)][i + k] += (dp[l][i])*(Search(t)[1] + Search(t)[2]) % MOD*by[k / j] % MOD;
					dp[min(l + 1, 2)][i + k] %= MOD;
				}
			}
		}
		for (int j = 0; j < 3; j++) {
			dp[min(2, j + 1)][i + 1] += dp[j][i] * (1 + (s[i] == '1')) % MOD;
		}
	}
	mp[s] = { dp[0].back()%MOD,dp[1].back()%MOD,dp[2].back()%MOD };
	return mp[s];
}

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

	string s;
	cin >> s;
	N = s.size();
	by.resize(N + 1);
	by[1] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 2; i*j <= N; j++) {
			by[i * j] += by[i];
			
		}
	}
	two.resize(N + 1, 1);
	for (int i = 1; i <= N; i++) {
		two[i] = two[i - 1] * 2 % MOD;
	}
	cout << (Search(s)[0]+Search(s)[1]+ Search(s)[2])%MOD << endl;
}

Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;
const ll MOD = 1e9+7;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

// gcd
template <class T>
T gcd(T a, T b)
{
    if(b == 0) return a;
    return gcd(b, a%b);
}

ll mypow(ll x, ll n){
    ll ret = 1;
    while (n > 0)
    {
        if(n&1){
            ret *= x; ret %= MOD;
        }
        x = x * x;
        x %= MOD;
        n /= 2;
    }
    return ret; 
}

int main()
{
    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    for(int i=0; i<N; i++) cin >> A[i] >> B[i];

    for(int i=0; i<N; i++){
        if(A[i]==0){
            if(B[i]!=0) B[i] = 1;
        }else if(B[i]==0){
            A[i] = 1;
        }else{
            ll d = gcd(abs(A[i]), abs(B[i]));
            A[i] /= d;
            B[i] /= d;
            if(B[i] < 0){
                A[i] = -A[i];
                B[i] = -B[i];
            }
        }
    }

    ll z = 0;
    map<Pll, ll> mp, mp2;
    for(int i=0; i<N; i++){
        if(A[i]==0 && B[i]==0) z++;
        else if(B[i]==0 || A[i]>0) mp[Pll(A[i], B[i])]++;
        else mp2[Pll(A[i], B[i])]++;
    }

    ll ans = 1;
    for(auto& p: mp){
        auto itr = mp2.find(Pll(-p.first.second, p.first.first));
        if(itr == mp2.end()) ans *= mypow(2, p.second);
        else ans *= mypow(2, p.second) + mypow(2, itr->second) - 1;
        ans %= MOD;
        // cout << ans << "\n";
    }
    // cout << "\n";
    for(auto& p: mp2){
        auto itr = mp.find(Pll(p.first.second, -p.first.first));
        if(itr == mp.end()){
            ans *= mypow(2, p.second);
            ans %= MOD;
        }
        // cout << ans << "\n";
    }

    cout << (ans + z + MOD - 1) % MOD << endl;
    // for(auto& p: mp) cout << p.first.first << " " << p.first.second << " " << p.second << "\n";
    // cout << "\n";
    // for(auto& p: mp2) cout << p.first.first << " " << p.first.second << " " << p.second << "\n";
}

Measured memory_bytes: 18836
#include <iostream>
#include <climits>

using namespace std;


long A[2000001];
int H;


int parent(int i) { return i / 2; }
int left (int i) { return i * 2; }
int right (int i) { return i * 2 + 1; }


void max_heapify(int i)
{
    int max_i;
    int l, r;
    l = left(i);
    r = right(i);

    max_i = l <= H && A[l] > A[i] ? l : i;
    max_i = r <= H && A[r] > A[max_i] ? r : max_i;

    if (max_i != i) {
        long tmp = A[i];
        A[i] = A[max_i];
        A[max_i] = tmp;

        max_heapify(max_i);
    }
}


void build_max_heap()
{
    for (int i = H / 2; i >= 1; i--)
        max_heapify(i);
}


void increase_key(int i, long k)
{
    if (A[i] > k)
        return;

    A[i] = k;
    int t = i;
    while (t > 1 && A[parent(t)] < A[t]) {
        long tmp = A[t];
        A[t] = A[parent(t)];
        A[parent(t)] = tmp;

        t = parent(t);
    }
}


void insert(long k)
{
    A[++H] = LONG_MIN;
    increase_key(H, k);
}


long extract()
{
    long ret = A[1];
    A[1] = A[H--];
    max_heapify(1);
    return ret;
}


void print()
{
    for (int i = 1; i <= H; i++) {
        cout << " " << A[i];
    }
    cout << endl;
}


int main()
{
    while (true) {
        string cmd;
        cin >> cmd;
        if (cmd[0] == 'i') {
            long k;
            cin >> k;
            insert(k);
        } else if (cmd[1] == 'x') {
            cout << extract() << endl;;
        } else {
            break;
        }
        // print();
    }

    return 0;
}


Measured memory_bytes: 10968
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = n-1; i > 0; i--)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll INF=(1LL<<60);
const ld pi=acosl((ld)1);
const ll mod = 1000000007;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};

bool solve(){
  ll n;cin>>n;
  ll ans=0;
  rep(i,n){
    ll a;cin>>a;a--;
    ans+=a;
  }
  cout<<ans<<endl;
  return false;
}


signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout<<fixed;
	cout<<setprecision(30);
	return solve();
}


Measured memory_bytes: 256
loop do
    d, w = gets.split.map(&:to_i)
    break if d == 0
    a = (1..d).map {gets.split.map(&:to_i)}
    max = 0
    (0..d-1).to_a.combination(2) do |y1, y2|
        next if y1 >= y2 - 1
        (0..w-1).to_a.combination(2) do |x1, x2|
            next if x1 >= x2 - 1
            h1 = (a[y1][x1..x2] + a[y2][x1..x2] + a[y1..y2].map{|r| r[x1]} + a[y1..y2].map{|r| r[x2]}).min
            h2 = 0
            v = h1 * (y2 - y1 - 1) * (x2 - x1 - 1)
            (y1+1..y2-1).each do |y|
                (x1+1..x2-1).each do |x|
                    h2 = a[y][x] if a[y][x] > h2
                    v -= a[y][x]
                end
            end
            next if h2 >= h1
            max = v if v > max
        end
    end
    p max
end



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

int main() {
  int x, y;
  cin >> x >> y;
  int ans = 2100000000;
  if (y >= x) ans = min(ans, y - x);
  if (y >= -x) ans = min(ans, y + x + 1);
  if (-y >= x) ans = min(ans, -y - x + 1);
  if (-y >= -x) ans = min(ans, -y + x + 2);
  cout << ans << endl;
}

Measured memory_bytes: 3644
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
	int a[100000];
	int b[100000];
	int m[100000];
	int n[100000];
	int x;
	long long s = 1;
	for (int i = 0; i< 100000; i++){
		a[i] = 0;
		b[i] = 0;
		m[i] = 0;
		n[i] = 0;
	}
	scanf("%d", &x);
	scanf("%d", &a[0]);
	m[0] = a[0];
	n[0] = 1;
	for (int i = 1; i < x; i++){
		scanf("%d", &a[i]);
		if (a[i] > a[i - 1])
		{
			m[i] = a[i];
			n[i] = 1;
		}
		else{
			m[i] = a[i];
			n[i] = 0;
		}
	}
	for (int i = 0; i < x; i++){
		scanf("%d", &b[i]);
	}
	if (n[x - 1] == 0){
		if (b[x - 1] <= m[x - 1]){
			m[x - 1] = b[x - 1];
			n[x - 1] = 1;
		}
		else m[x - 1] = 0;
	}
	else{
		if (m[x - 1] != b[x - 1]){
			m[x - 1] = 0;
		}
	}
	for (int i = x - 2; i >= 0; i--){
		if (b[i] > b[i + 1])
		{
			if (n[i] == 0){
				if (b[i] <= m[i]){
					m[i] = b[i];
					n[i] = 1;
				}
				else m[i] = 0;
			}
			else{
				if (m[i] != b[i]){
					m[i] = 0;
				}
			}
		}
		else{
			if (n[i] == 0){
				if (b[i] < m[i]) m[i] = b[i];
			}
			else{
				if (m[i] > b[i]){
					m[i] = 0;
				}
			}
		}
	}
	for (int i = 0; i < x; i++){
		if (n[i] == 0){
			s = s*m[i];
			s = s % 1000000007;
		}
		if (m[i] == 0) s = 0;
		
	}	
		printf("%d", s);
	return 0;
}

Measured memory_bytes: 1792
object Main extends App {
	override def main(args: Array[String]){
		val sc = new java.util.Scanner(System.in)
		val input = sc.nextLine
		input.map{
			case ch:Char if ('a' to 'z') contains ch => (ch - 'a'+'A').asInstanceOf[Char]
			case ch:Char if ('A' to 'Z') contains ch => (ch - 'A'+'a').asInstanceOf[Char]
			case ch:Char => ch
		}.foreach(print)
		println
	}
}

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

		String S=sc.next();
		char[] c=S.toCharArray();

		for(int i=0;i<S.length();i++) {
			if(i%2==0) {
				System.out.print(c[i]);
			}
		}
	}
}

Measured memory_bytes: 47132
import java.math.*;
import java.util.*;

public class Main {
	public static void main(String []args){
		Scanner cin = new Scanner(System.in);
		BigInteger a,b,c;
		String s,ss,sss;
		int n = cin.nextInt();
		while(n-- != 0){
			a = cin.nextBigInteger();
			b = cin.nextBigInteger();
			
			s = a.toString();
			ss = b.toString();
			
			if(s.length()>80 || ss.length()>80){
				System.out.println("overflow");
				continue;
			}
			else {
				c = a.add(b);
				sss = c.toString();
				if(sss.length()>80){
					System.out.println("overflow");
					continue;
				}
				else System.out.println(c);
			}
		}
	}
}

Measured memory_bytes: 18544
#include <cstdio>
#include <cstring>
using namespace std;

#define L 3194304
bool HA[L];
char T[256];

inline int get( unsigned char c ) {
    return T[c];
}

int main() {
    int n, sum, t, c;
    T['A'] = 1, T['C'] = 2, T['G'] = 3, T['T'] = 4;
    scanf("%d", &n);
    while ( getchar() != '\n' );
    for ( register int i = 0; i++ < n; ) {
        sum = 0;
        t = 1;
        bool flag = ( c = getchar() ) == 'i';
        while ( ( c = getchar() ) != ' ' );
        while ( ( c = T[getchar()] ) != 0 ) {
            sum += c * t;
            t *= 4;
        }
        if ( flag ) {
            HA[sum] = true;
        } else {
            puts( HA[sum] ? "yes" : "no" );
        }
    }
    return 0;
}

Measured memory_bytes: 2100
(N,K) = map(int,input().split())
A = list(map(int,input().split()))
route = [1]
App = [0]*N
past = 1
for i in range(K):
    past = A[past-1]
    if App[past-1]==1:
        loop = (route.index(past),i+1)
        flag = 0
        break
    else:
        App[past-1] = 1
        flag = 1
        route.append(past)
if flag == 1:
    print(route[-1])
else:
    print(route[loop[0]+(K-loop[0])%(loop[1]-loop[0])])


Measured memory_bytes: 32356
import java.util.Scanner;

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

		if(S.length() % 4 == 1) {
			int l = (S.length()-1 )/ 2;
			for(int i = 0; i < l/2 ; i++) {
				if(S.charAt(i) != S.charAt(l-i-1)) isStrong = false;
			}
			if(!S.substring(0, l).equals( S.substring(l+1))) isStrong = false;
		}else {
			int l = (S.length()-1 )/ 2;
			for(int i = 0; i < (l-1)/2 ; i++) {
				if(S.charAt(i) != S.charAt(l-i-1)) isStrong = false;
			}
			if(!S.substring(0, l).equals( S.substring(l+1))) isStrong = false;
			
		}

		if(isStrong) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}




	}
}


Measured memory_bytes: 23124
S = input()
T = input()
ans = 'No'
M = len(S)
if len(S) != len(T):
    pass
else:
    for i in range(M):
        SK = ''
        for j in range(M):
            SK += S[(j+i)%M]
        if T == SK:
            ans = 'Yes'
            break
print(ans)

Measured memory_bytes: 3060
import java.util.*;

public class Main {
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int ac = 0;
        int wa = 0;
        int tle = 0;
        int re = 0;
        
        for(int i = 0; i < n; i++){
            String s = stdIn.next();
            
            if(s.equals("AC")){
                ac++;
            }else if(s.equals("WA")){
                wa++;
            }else if(s.equals("TLE")){
                tle++;
            }else{
                re++;
            }
        }
        
        System.out.println("AC x " + ac);
        System.out.println("WA x " + wa);
        System.out.println("TLE x " + tle);
        System.out.println("RE x " + re);
    }
}


Measured memory_bytes: 58460
# 20200612_yorukatsu_e.py
import collections
N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
ans = 0
for i,v in C.items():
    # print(i,v)
    if i!=v:
        if i<v:
            ans += v-i
        else:
            ans += v
print(ans)

Measured memory_bytes: 18676
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N*3+5)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v+N+1)
        adj[u+N+1].append(v+2*N+2)
        adj[u+2*N+2].append(v)

    s, t = map(int, input().split())
    que = deque()
    que.append(s)
    seen = [-1] * (N*3+5)
    seen[s] = 0
    while que:
        v = que.popleft()
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)

    if seen[t] == -1:
        print(-1)
    else:
        assert seen[t] % 3 == 0
        print(seen[t] // 3)


if __name__ == '__main__':
    main()


Measured memory_bytes: 77604
import java.util.*;
     
    public class Main {
    	public static void main(String[] args){
    		Scanner sc = new Scanner(System.in);
            
            int n = sc.nextInt();
            int d = sc.nextInt();
            int x[][] = new int[n][d];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < d; j++) {
                    x[i][j] = sc.nextInt();
                }
            }
     
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    int sum = 0;
                    for (int k = 0; k < d; k++) {
                        sum += Math.pow((x[i][k] - x[j][k]), 2);
                    }
     
                    int diss = (int)Math.sqrt(sum);
                    if (sum == diss * diss) {
                        count++;
                    }
                }
            }
     
            System.out.println(count);
    	}
    }

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

ll f(ll a) {
  ll r = (a + 1) / 2 % 2;
  for (int i = 1; i < 40; i++) {
    if ((a >> i) & 1) {
      r |= (a - (a >> i << i) + 1) % 2 << i;
    }
  }
  return r;
}

int main() {
  ll a, b;
  cin >> a >> b;
  cerr << f(a - 1) << " " << f(b) << endl;
  cout << (f(a - 1) ^ f(b)) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 2000000000
#define InfLL 4000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

int main() {
	int N;
	cin >> N;
	vi V(N), W(N);
	const int Lmax = 101000;
	const int K = 9;
	const int K2 = (1 << K);
	rep(i, N)
		cin >> V[i] >> W[i];
	vector<vi> Vsum(K2);
	rep(i, K2)
		Vsum[i].resize(Lmax, 0);
	Vsum[0][W[0]] = V[0];
	rep(inext, K2) {
		if (inext >= N)
			break;
		if (inext == 0)
			continue;
		int iprev = (inext + 1) / 2 - 1;
		rep(Wprev, Lmax) {
			Vsum[inext][Wprev] = max(Vsum[inext][Wprev], Vsum[iprev][Wprev]);
			int Wnext = Wprev + W[inext];
			if (Wnext >= Lmax)
				continue;
			Vsum[inext][Wnext] = max(Vsum[inext][Wnext], Vsum[iprev][Wprev] + V[inext]);
		}
	}
	rep(i, K2) {
		rep(j, Lmax) {
			if (j == 0)
				continue;
			Vsum[i][j] = max(Vsum[i][j], Vsum[i][j - 1]);
		}
	}
	int Q;
	cin >> Q;
	rep(q, Q) {
		int v, L;
		cin >> v >> L;
		v--;
		vi v_lower;
		while (1) {
			if (v < K2)
				break;
			v_lower.push_back(v);
			v= (v + 1) / 2 - 1;
		}
		int n = v_lower.size();
		int n2 = 1 << n;
		int ans = 0;
		rep(b, n2) {
			int L_lower = 0;
			int V_lower = 0;
			rep(i, n) {
				if ((b >> i) % 2) {
					int vtmp = v_lower[i];
					L_lower += W[vtmp];
					V_lower += V[vtmp];
				}
			}
			if (L_lower > L)
				continue;
			int L_upper = L - L_lower;
			int V_upper = Vsum[v][L_upper];
			int anstmp = V_lower + V_upper;
			ans = max(ans, anstmp);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 208076
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
ans = 0
xy = [list(map(int, input().split())) for _ in range(N)]
l = [int(x) for x in range(N)]
dist = 0
p = list(itertools.permutations(l, N))

for i in range(math.factorial(N)):
  for j in range(N-1):
    dist += math.sqrt((xy[p[i][j]][0]-xy[p[i][j+1]][0])**2+(xy[p[i][j]][1]-xy[p[i][j+1]][1])**2)
  ans += dist
  dist = 0

print(ans/math.factorial(N))


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

int gcd(int, int);

int main() {

	int N, X;
	cin >> N >> X;
	vector<int> x,from_X;

	int gcd_num = 0;

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		x.push_back(tmp);
	}

	for (int i = 0; i < N; i++) {
		from_X.push_back(abs(X - x[i]));
	}

	for (int i = 0; i < N; i++) {
		gcd_num = gcd(gcd_num, from_X[i]);
	}

	cout << gcd_num;
	return 0;
}

int gcd(int a, int b) {
	if (a < b) return gcd(b, a);
	if (b == 0) return a;
	int r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}

//made by myself

Measured memory_bytes: 3908
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

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

int main() {
  ll N, A, B;
  cin >> N >> A >> B;
  if(A > B || N == 1 && A != B) {
    cout << 0 << endl;
    return 0;
  }
  ll mn = A*(N-1)+B;
  ll mx = B*(N-1)+A;
  cout << mx-(mn-1) << endl;
  return 0;
}

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

#define mod 1000000007
vector<long long int>v;
long long int power(long long int x, long long int y, long long int p) 
{ 
	long long int res = 1;

	x = x % p; 

	while (y > 0) 
	{ 

		if (y & 1) 
			res = (res*x) % p; 


		y = y>>1; // y = y/2 
		x = (x*x) % p; 
	} 
	return res; 
} 


long long int modInverse(long long int n, long long int p) 
{ 
	return power(n, p-2, p); 
} 


long long int nCrModPFermat(long long int n, long long int r, long long int p) 
{ 
// Base case 
if (r==0) 
	return 1; 


// 	long long int fac[n+1]; 
// 	fac[0] = 1; 
// 	for (long long int i=1 ; i<=n; i++) 
// 		fac[i] = fac[i-1]*i%p; 

    // cout<<"V[n] = "<<n<<" "<<v[n]<<endl;

	return (v[n]* modInverse(v[r], p) % p * 
			modInverse(v[n-r], p) % p) % p; 
} 

int main() 
{ 
	
	long long int n,k,arr[100001],i,p=1000000007;
	cin>>n>>k;
	for(i=0;i<n;i++)
	{
	    cin>>arr[i];
	}
	sort(arr,arr+n);
	long long int fac[100001]; 
	fac[0] = 1;
	v.push_back(1);
	for (long long int i=1 ; i<=n; i++)
		{fac[i] = (fac[i-1]*i)%p;
		v.push_back(fac[i]);}
	
	long long int sum=0;
	for (i=k-1;i<n;i++) {
      sum=(sum%mod+ ((arr[i]%mod)*(nCrModPFermat(i, k-1, p)%mod))%mod)%mod;
    //   cout<<nCrModPFermat(i, k-1, p)<<endl;
   }
//   cout<<sum<<endl; 
   sort(arr, arr+n, greater<long long int>()); 
   long long int sum2=0;
	for (i=k-1;i<n;i++) {
      sum2=(sum2%mod+ ((arr[i]%mod)*(nCrModPFermat(i, k-1, p)%mod))%mod)%mod;
    //   cout<<nCrModPFermat(i, k-1, p)<<endl;
   }
//   cout<<sum2<<endl;
   cout<<(p+sum-sum2)%p<<endl;
} 


Measured memory_bytes: 2680
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

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

	int n, x, y;
	cin >> n >> x >> y;
	x--;
	y--;
	vector<int> ans(n);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int d = abs(i - j);
			d = min(abs(i - x) + 1 + abs(j - y), d);
			ans[d]++;
		}
	}
	for (int i = 1; i < n; i++) {
		cout << ans[i] << ' ';
	}
	cout << endl;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

A, B = MAP()

masu = []
for i in range(50):  # 上が白
	masu.append(["#"]*100)
for i in range(50):  # 下が黒
	masu.append(["."]*100)

row = 0
column = 0
for i in range(A-1):
	masu[row][column] = "."
	column += 2
	if column >= 100:
		column = 0
		row += 2

row = -1
column = 0
for i in range(B-1):
	masu[row][column] = "#"
	column += 2
	if column >= 100:
		column = 0
		row -= 2

print(100, 100)
for i in range(100):
	print(*masu[i], sep="")


Measured memory_bytes: 5248