akhauriyash/Code-Regression huggingface dataset:
N=int(input())
a=list(map(int,input().split()))
List=[]
x1=a[0]
y1=sum(a[1:N])
List.append(abs(x1-y1))
for i in range(1,N-1):
  x1+=a[i]
  y1-=a[i]
  List.append(abs(x1-y1))
print(min(List))

Measured memory_bytes: 23800
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#include <vector>
#define ll long long int
#define ve vector<ll>
#define vell vector<ll>
#define ve_pa vector<pair<ll,ll> >
#define pb push_back
#define mod 1000000007
#define ld long double 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define mll map<ll,ll>
#define mii map<int,int>
#define m_ve map<ll,vell >
#define min3(x,y,z) min(x,min(y,z))
#define max3(x,y,z) max(x,max(y,z))
#define se second
#define check cout<<"s"
#define checkx(x) cout<<x
#define W(x) while(x--)
#define ld long double
#define popcount(x) __builtin_popcountll(x)
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
//int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); 
cout.tie(NULL);
ll n;cin>>n;
ll a[n],gc=0;
for(int i=0;i<n;i++)
{
	cin>>a[i];
	gc=__gcd(a[i],gc);
}
int ans1=1;
mll pos;
for(int i=n-1;i>=0;i--)
{
	ll x=a[i];
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			if(pos[i])
			ans1=0;
			else
			pos[i]=1;
			while(x%i==0)
			{
				x/=i;
			}
		}
	}
	if(x!=1)
	{
		if(pos[x])
		ans1=0;
		else
		pos[x]=1;
	}
}
if(ans1)
{
	cout<<"pairwise coprime";
}
else if(gc==1)
{
	cout<<"setwise coprime";
}
else
cout<<"not coprime";




}
 
 


Measured memory_bytes: 16300
#include <bits/stdc++.h>
using namespace std;
int main() {
  //input
  string S,T;
  cin >> S >> T;

  
  for (int i = S.length()-T.length(); i>=0; i--) {
    bool valid = true;
    for (int j = 0; j < T.length() && valid; j++) {
      if (S[i+j] != T[j] && S[i+j] != '?') {
        valid = false;
      }
    }
    
    if (valid) {
      for (int j = 0; j < T.length(); j++) {
        S[i+j] = T[j];
      }
      for (int j = 0; j < S.length(); j++) {
        if (S[j] == '?') {
          S[j] = 'a';
        }
      }
      cout << S <<endl;;
      return 0;
    }
  }

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


Measured memory_bytes: 3544
#include <iostream>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <math.h>
using namespace std;

string M[7]={"Wednesday","Thursday","Friday","Saturday","Sunday","Monday","Tuesday"};

int main(){
	int m,d;
	while(cin>>m>>d,m){
		switch(m){
		case 12:d+=30;
		case 11:d+=31;
		case 10:d+=30;
		case 9:d+=31;
		case 8:d+=31;
		case 7:d+=30;
		case 6:d+=31;
		case 5:d+=30;
		case 4:d+=31;
		case 3:d+=29;
		case 2:d+=31;
		case 1:cout<<M[d%7]<<endl;
		}
	}
}

Measured memory_bytes: 0
import numpy as np
import random

mod=998244353


n,m=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]

#n,m=300,300
#A=[[int(random.randint(0,1)) for j in range(m)] for i in range(n)]


#A=np.array(A)

#print("A")
i=0
j=0
r=0 #rank
while i<n and j<m :
    #print(i)
    t=0
    if A[i][j]==0 :
        k=i
        while k<n and A[k][j]==0 :
            k+=1
        if k<n :
            A[i],A[k]=A[k],A[i]

            #print(A)
        else :
            t=1
            j+=1
    if t==0 :
        r+=1
        for p in range(i+1,n):
            if A[p][j]>0 :
                for kk in range(j,m):
                    A[p][kk]=(A[p][kk]-A[i][kk])%2
        i+=1
        j+=1



#r=0
#j=0
#for i in range(m):
#    if j<n :
#        if A[j][i]!=0 :
#            r+=1
#            j+=1

for i in range(n):
    for j in range(m):
        A[i][j]=int(A[i][j])
#print(A)
#print(r) #rank

a=1
b=1

for i in range(n+m-1):
    a=(a*2)%mod
for i in range(n+m-1-r):
    b=(b*2)%mod

print((a-b)%mod)


Measured memory_bytes: 16668
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, K, A, F):
    A.sort()
    F.sort(reverse=True)

    def f(x):
        sy = 0
        for a, f in zip(A, F):
            m = a * f
            if m > x:
                sy += (m - x + f - 1) // f
        return sy

    under = -1
    hi = 10**12 + 1
    while hi - under > 1:
        m = (hi + under) // 2
        if f(m) <= K: hi = m
        else: under = m
    print(hi)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    *F, = map(int, input().split())
    main(N, K, A, F)


Measured memory_bytes: 120848
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

ll n, m, k, a=1, b=1, ans, M=1e9+7;
int main() {
	ll i;
	cin >> n >> m >> k;
	for(i=1; i<=k-2; i++) {
		a = a * (n * m - i - 1) % M;
		b = b * i % M;
	}
	for(i=M-2; i; i/=2) {
		if(i&1) a = a * b % M;
		b = b * b % M;
	}
	b = a * n % M * n % M;
	for(i=1; i<m; i++) ans += b * i % M * (m-i) % M;
	b = a * m % M * m % M;
	for(i=1; i<n; i++) ans += b * i % M * (n-i) % M;
	cout << ans % M;
	return 0;
}


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

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

    int n,cnt=0,ans;
    string s;
    cin >> n >> s;

    for(int i = 1; i < n; ++i){
        if(s[i] == 'E') cnt++;
    }
    ans = cnt;
    for(int i = 1; i < n; ++i){
        if(s[i] == 'E') cnt--;
        if(s[i - 1] == 'W') cnt++;
        if(ans > cnt) ans = cnt;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 720
#include <algorithm>
#include <cstdio>
#include <map>
#define N 200005
using namespace std;
typedef long long ll;

int n, a[N];

inline bool check(ll x) {
    map<ll, ll> num;
    for (int i = 2; i <= n; ++i) {
        if (a[i] > a[i - 1]) continue;
        while (!num.empty() && num.rbegin()->first >= a[i]) {
            num.erase(--num.end());
        }
        for (int j = a[i] - 1; j >= 0; --j) {
            ++num[j];
            if (num[j] == x) num.erase(j);
            else break;
            if (j == 0) return 0;
        }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
      bool flag = true;
    for (int i = 0; i < n - 1; ++i) {
        if (a[i] >= a[i + 1]) {
          flag = false;
          break;
        }
    }
    if (flag) {
        puts("1");
        return 0;
    }
    ll l = 2, r = n + 1, mid, ans;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = (ans = mid) - 1;
        else l = mid + 1;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int sum0=0, sum1=0;
  for(int i=0; i<S.size(); i++) {
    if(S.at(i)=='0') sum0++;
    if(S.at(i)=='1') sum1++;
  }
  cout << 2*min(sum0,sum1) << endl;
}

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

#define all(v) v.begin(), v.end()
#define V vector
#define P pair
typedef long long ll;

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

    V<V<ll> > num(10, V<ll>(10, 0));
    for(int i = 1; i <= n; i++){
        string s = to_string(i);
        int a = s[0] - '0';
        int b = s[s.size() - 1] - '0';
        num[a][b]++;
    }

    ll ans = 0;
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= 9; j++){
            ans += num[i][j] * num[j][i];
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
def prime_division(arg_n)
    n = arg_n
    division = []
    i = 2
    while( i * i <= arg_n ) do
        exp = 0
        while( n % i == 0 ) do
            n /= i
            exp += 1
        end
        division.push [i, exp] if exp >= 1
        i += 1
    end
    if n != 1
        division.push [n, 1]
    end
    division
end

# p (prime_division(gets.to_i))
N = gets.to_i
print N.to_s + ':'
divs = prime_division(N)
divs.each do |div|
    div[1].times do
        print ' ' + div[0].to_s
    end
end
print "\n"


Measured memory_bytes: 6876
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

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

	vector<int> a(n);
	long long ans = 1;
	int add = 1;
	rep(i,n){
		cin >> a[i];
		ans *= 3;
		if(a[i]  % 2 == 0) add *= 2;
	}
	cout << ans - add << endl;
}


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

int main() {
    int N;
    std::cin >> N ;
    char S[N];
    std::cin >> S;

    // std::cout << N/2 << std::endl;
    // std::cout << S[N/2] << std::endl;

    if((N%2)==1){
        std::cout << "No" << std::endl;
        return 0;
    }

    for(int i=0;i<(N/2);i++){
        if(S[i] == S[i+N/2]){
        }
        else{
            std::cout << "No" << std::endl;
            return 0;
        }
    }

    std::cout << "Yes" << std::endl;



    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int a,b,ans=0;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        ans+=b-a+1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

int main()
{
    int n, m;
    cin >> n >> m;
    vl hs;
    hs.resize(n);
    for(int i=0; i<n; i++) cin >> hs.at(i);
    vpi abb;
    abb.resize(m);
    for(int i=0; i<m; i++)
    {
        int a, b;
        cin >> a >> b;
        abb.at(i) = make_pair(a, b);
    }

    map<int, set<int>> mp;
    for(auto &p : abb)
    {
        mp[p.first].insert(p.second);
        mp[p.second].insert(p.first);
    }

    int cnt = 0;
    for(int i=1; i<=n; i++)
    {
        bool is_good = true;
        ll ch = hs.at(i-1);
        for(auto itr=mp[i].begin(); itr != mp[i].end(); itr++)
        {
            ll th = hs.at(*itr-1);
            if(ch <= th) is_good = false;
        }
        if(is_good) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 23588
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
int n,x,f,c,r,z;
cin>>n;
x=n/500;
f=x*500;
r=n-f;
c=r/5;
z=(f*2)+(c*5);
cout<<z;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
long long int mod=1e9+7;
bool debug=false;
typedef long long ll;
int main(){
	int n;
	cin>>n;
	vector<long long int> a(n),b(n);
	long long int min=1e9+1;
	int argmin;
	rep(i,n){
		cin>>a[i];
	}
	long long int sum=0;
	rep(i,n){
		if(i%2==0) sum+=a[i];
		else sum-=a[i];
	}
	b[0]=sum/2;
	rep(i,n-1){
		b[i+1]=a[i]-b[i];
	}
	rep(i,n-1)cout<<b[i]*2<<" ";
	cout<<b[n-1]*2<<endl;


	return 0;
}


Measured memory_bytes: 2944
H, W, M = map(int, input().split())
bomb = []
h_sum = [0]*W
w_sum = [0]*H
for _ in range(M):
    h, w = map(int, input().split())
    bomb.append((h,w))
    h_sum[w-1] += 1
    w_sum[h-1] += 1
max_h = max(h_sum)
max_w = max(w_sum)
target_cnt = h_sum.count(max_h)*w_sum.count(max_w)
for h, w in bomb:
    if h_sum[w-1] == max_h and w_sum[h-1] == max_w:
        target_cnt -= 1
if target_cnt == 0:
    print(max_h+max_w-1)
else:
    print(max_h+max_w)

Measured memory_bytes: 109624
#include<stdio.h>

int main(){
	int a[6000],n,i,j,total=0,amax=-99999999;
	while(1){
		scanf("%d",&n);
		if(!n) break;
		amax=-99999999;
		for(i=0;i<n;i++) scanf("%d",&a[i]);
		for(i=0;i<n;i++){
			for(j=i;j<n;j++){
				total+=a[j];
				if(amax<total) amax=total;
			}
			total=0;
		}
		printf("%d\n",amax);
	}
	return 0;
}

Measured memory_bytes: 620
#include<stdio.h>
int main()
{
	char s1[12],s2[12],s3[12];
	scanf("%s %s %s",s1,s2,s3);
	s1[0] = s1[0] - 32;
	s2[0] = s2[0] - 32;
	s3[0] = s3[0] - 32;
	printf("%c%c%c\n",s1[0],s2[0],s3[0]);
	return 0;
}




Measured memory_bytes: 128
n=int(input())
l=[]
ll=[0]*(n+1)
s=set()
for i in range(n):
    p=int(input())
    l.append(p)
    ll[p]=i
tmp=0
ans=0
b=-1
for i in range(1,n+1):
    if b<ll[i]:
        tmp+=1
    else:
        tmp=1
    b=ll[i]
    ans=max(ans,tmp)
print(n-ans)





Measured memory_bytes: 18968
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const double EPS = 1e-10;


int main (){
  ll n,k;
  ll an=0;
  ll an2=0;
  cin>>n>>k;
  vector<ll>a(n,0);
  vector<ll>b(43,0);
  vector<ll>c(43,0);
  for(ll i=0;i<n;i++){
    cin>>a[i];
    for(ll j=0;j<43;j++){
      if((ll)((ll)a[i]>>j)&(ll)1)b[j]++;
    }
  }
  ll cc=0;
  for(ll j=42;j>=0;j--){
    if(b[j]<(n+1)/2){
      c[j]=1;
      cc+=((ll)1<<j);
    }
  }
  if(cc<=k){
    ll d=cc;
    for(ll t=0;t<43;t++){
      if((ll)(d>>t)&(ll)1)an2+=((ll)(n-b[t]))*((ll)1<<t);
      else an2+=(ll)b[t]*((ll)1<<t);
    }
    cout<<an2<<endl;
    return 0;
  }
  for(ll j=42;j>=0;j--){
    if((cc&((ll)1<<j))>k){
      cc-=((ll)1<<j);
    }
  }
  for(ll j=42;j>=0;j--){
    ll d=(ll)cc&((ll)~((ll)1<<j));
    an2=0;
    if(d<=k){
      for(ll t=0;t<43;t++){
        if((ll)(d>>t)&(ll)1)an2+=((ll)(n-b[t]))*((ll)1<<t);
        else an2+=(ll)b[t]*((ll)1<<t);
      }
      an=max(an,an2);
    }
    else{
      cc=d;
    }

  }

  cout<<an<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <stdio.h>
 
using namespace std;
 
#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(i, a) for (auto &i: (a))
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()

void solve();

signed main () {
    cout.precision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif
    int t = 1; 
    // cin >> t;    
    int tt = t;
    while (t--) { 
        solve();
    }
    return 0;
}
void solve() { 
	int a, b;
	cin >> a >> b;
	int k;
	cin >> k;
	int m = min(a, k);
	a -= m;
	k -= m;
	m = min(b, k);
	b -= m;
	k -= m;
	cout << a << ' ' << b;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
ll n,i;
// std::vect  or<ll> a;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  // a.resize(n,0);
  ll total[100005] = {0};
  ll a[100005] = {0};
  repl(i,1,n+1){
    cin>>a[i];
    total[i] += (abs(a[i]-a[i-1]) + total[i-1]);
  }
  total[n+1] += total[n] + abs(a[n]-0);
  repl(i,1,n+1){
    cout<<(total[i-1]+abs(a[i+1]-a[i-1]) + total[n+1] - total[i+1])<<endl;
  }
}
int main(){
  solve();
  return 0;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'
#define int long long

typedef long long ll;

vector<string> s(1010);
int n;

signed main(){
    cin >> n;
    s.resize(n);
    for (int i = 0; i < n; i++){
        cin >> s[i];
    }

    int cnt = 0;
    int cnt_a = 0;
    int cnt_b = 0;
    int cnt_ba = 0;
    for (int i = 0; i < n; i++){
        if (s[i].front() == 'B') cnt_b++;
        if (s[i].back() == 'A') cnt_a++;
        if (s[i].front() == 'B' && s[i].back() == 'A') cnt_ba++;
        for (int j = 1; j < s[i].size(); j++){
            if (s[i][j-1] == 'A' && s[i][j] == 'B') {
                cnt++;
            }
        }
    }

    if (cnt_ba == cnt_a){
        if (cnt_ba == cnt_b){
            if (cnt_ba != 0){
                cnt += cnt_ba - 1;
            }
        } else {
            cnt += cnt_ba;
        }
    } else {
        if (cnt_ba == cnt_b){
            cnt += cnt_ba;
        } else {
            cnt += min(cnt_a, cnt_b);
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 768
A, B, K = map(int, input().split())


if B-A <= K:
    for i in range(A,B+1):
        print(i)
else:
    result = set(list(range(A, A+K))+list(range(B,B-K, -1)))

    for i in sorted(list(result)):
        print(i)

Measured memory_bytes: 3060
import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    A, B = map(int, input().split())
    def xor(B):
        if B >= 1:
            if B % 2 == 1:
                if (B - 1) % 4 == 0:
                    return 1
                else:
                    return 0

            else:
                if (B - 2) % 4 == 0:
                    return 1 ^ B
                else:
                    return 0 ^ B
        else:
            return 0
    print(xor(B)^xor(A-1))


resolve()

Measured memory_bytes: 38512
import java.io.*;
import java.util.*;
import java.math.*;
import java.awt.Point;
 
public class Main {
	//static final long MOD = 998244353L;
	//static final long INF = -1000000000000000007L;
	static final long MOD = 1000000007L;
	//static final int INF = 1000000007;

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		int N = sc.ni();
		if (N == 1) {
			pw.println("Hello World");
		} else {
			pw.println(sc.ni()+sc.ni());
		}
		
		pw.close();
	}
	
	//Find the GCD of two numbers
	public static long gcd(long a, long b) {
		if (a < b) return gcd(b,a);
		if (b == 0)
			return a;
		else
			return gcd(b,a%b);
	}
	
	//Fast exponentiation (x^y mod m)
	public static long power(long x, long y, long m) { 
		long ans = 1;
		x %= m;
		while (y > 0) { 
			if(y % 2 == 1) 
				ans = (ans * x) % m; 
			y /= 2;  
			x = (x * x) % m;
		} 
		return ans; 
	}
	
	public static int[][] shuffle(int[][] array) {
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    int[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		return array;
	}
	
    public static int[][] sort(int[][] array) {
    	//Sort an array (immune to quicksort TLE)
 
		Arrays.sort(array, new Comparator<int[]>() {
			  @Override
        	  public int compare(int[] arr1, int[] arr2) {
				  return arr1[0]-arr2[0]; //ascending order
	          }
		});
		return array;
	}
    
    public static long[][] sort(long[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    long[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<long[]>() {
			  @Override
        	  public int compare(long[] arr1, long[] arr2) {
				  return 0;
	          }
		});
		return array;
	}
    
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int ni() { 
            return Integer.parseInt(next()); 
        } 
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str;
        }
    }
}

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

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

map<PII,PII> mp;
bool dfs(PII pos, map<PII,int>& vis){
  int c = vis[pos];
  PII pos2 = mp[pos];
  REP(i,4){
	PII t = pos;
	t.first += dx[i], t.second += dy[i];
	if(t == pos2 || !mp.count(t)) continue;
	if(vis[t] == -1){
	  vis[t] = c;
	  vis[mp[t]] = 1-c;
	  if(!dfs(t,vis)){
		vis[t] = vis[mp[t]] = -1;
		return false;
	  }
	}
	else if(vis[t] != c)
	  return false;
  }

  c = 1 - c;
  REP(i,4){
	PII t = pos2;
	t.first += dx[i], t.second += dy[i];
	if(t == pos || !mp.count(t)) continue;
	if(vis[t] == -1){
	  vis[t] = c;
	  vis[mp[t]] = 1-c;
	  if(!dfs(t,vis)){
		vis[t] = vis[mp[t]] = -1;
		return false;
	  }
	}
	else if(vis[t] != c)
	  return false;
  }

  return true;
}

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

  int N;
  while(cin>>N,N){
	mp.clear();
	REP(i,N){
	  int x, y; char c; cin >> x >> y >> c;
	  if(c == 'x'){
		mp[MP(x,y)] = MP(x+1,y);
		mp[MP(x+1,y)] = MP(x,y);
	  }
	  else{
		mp[MP(x,y)] = MP(x,y+1);
		mp[MP(x,y+1)] = MP(x,y);
	  }
	}

	map<PII,int> vis;
	for(auto it=mp.begin();it!=mp.end();++it){
	  vis[it->first] = -1;
	}

	bool ans = true;
	for(auto it=mp.begin();it!=mp.end();++it){
	  if(vis[it->first] >= 0) continue;
	  vis[it->first] = 0, vis[mp[it->first]] = 1;
	  if(dfs(it->first, vis)) continue;
	  vis[it->first] = 1, vis[mp[it->first]] = 0;
	  if(dfs(it->first, vis)) continue;
	  ans = false;
	  break;
	}

	cout << (ans? "Yes": "No") << endl;
  }
  
  return 0;
}

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

int main() {
    int n; cin >> n;
    vector<int> m(4);
    m[0]=n/1000; n%=1000;
    m[1]=n/100; n%=100;
    m[2]=n/10; n%=10;
    m[3]=n;
    vector<string> f(3);
    for(int i=0;i<(1<<3);i++){
        int sum=m[0];
        bitset<3> p(i);
        for(int j=0;j<3; j++){
            if(p.test(j)){
                sum+=m[j+1];
            }else{
                sum-=m[j+1];
            }
        }if(sum==7){
            for(int k=0;k<3;k++){
                if(p.test(k)){
                    f[k]="+";
                }else{
                    f[k]="-";
                }
            }
            cout << m[0] << f[0]<<m[1]<<f[1]<<m[2]<<f[2]<<m[3]<<"=7"<<endl;
            return 0;
        }else{
            continue;
        }
    }
}

Measured memory_bytes: 256
from collections import defaultdict
N=int(input())
S=input()
A=S[:N]
B=S[N:]
B=B[::-1]
def f(A):
    dd=defaultdict(int)
    for i in range(1<<N):
        a=[]
        b=[]
        for j in range(N):
            if i&(1<<j):
                a.append(A[j])
            else:
                b.append(A[j])
        s=''.join(a)
        t=''.join(b)
        dd[(s,t)]+=1
    return dd
dd1=f(A)
dd2=f(B)
ans=0
for t,c in dd1.items():
    ans+=dd2[t]*c
print(ans)



Measured memory_bytes: 200060
from collections import deque
import sys


def bfs(M, sy, sx):
    queue = deque([[xs, ys]])
    M[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1 = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return M[x1][y1]
        
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            for k in range(1, K + 1):
                new_x = x1 + dx * k
                new_y = y1 + dy * k

                if (0 <= new_x < H) and (0 <= new_y < W):
                    if m[new_x][new_y] == "@":
                        break
                    elif M[new_x][new_y] == -1:  # まだ来たことない点だったという条件
                        M[new_x][new_y] = M[x1][y1] + 1
                        queue.append([new_x, new_y])  # 新しい点を足す。
                    elif M[new_x][new_y] < M[x1][y1] + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(M, xs, ys)

print(M[xg][yg])


Measured memory_bytes: 45144
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include<algorithm> 
#include <iomanip>
#include <math.h>
#include <cctype>
//小文字を大文字 c-0x20;


#define db double
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define maxn 5005
#define mod 998244353
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define vv(z,a,b) vector<vector<int>>z(a,vector<int>(b))
#define vvll(z,a,b) vector<vector<ll>>z(a,vector<ll>(b))
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(c) begin(c),end(c)
#define fix(k) fixed<<setprecision(k)
#define PI 3.141592653589793
using namespace std;


int main(){
    int n;cin>>n;
    string s;cin>>s;
    int flag=0;
    rep(i,n-2){
        string h=s.substr(i,3);
        if(h=="ABC")flag++;
    }
    cout<<flag<<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, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
p = LIST()
 
ans = 0
i = 0
for i, x in enumerate(p):
    if i+1 == x:
        if i == N-1:
            ans += 1
            break
        p[i], p[i+1] = p[i+1], p[i]
        ans += 1

print(ans)


Measured memory_bytes: 21408
#pragma comment(linker,"/STACK:10240000")
#include<iostream>
#include<stack>
#include<cstdlib>
#include<cstdio>
#include<set>
#define N 250
#define INT_MAX		0x3fffffff
using namespace std;
int dp[N][N];
int result=INT_MAX;
int getsum(int a[],int r){
 int temp=0;
 for(int i=0;i<r;i++){
            if(dp[a[i]][a[i+1]]!=INT_MAX){
                 temp+=dp[a[i]][a[i+1]];
            }
            else{
                temp = INT_MAX;
                break;
            }
       }
       return temp;
}
void swap(int *a, int *b)
{
    int m;
    m = *a;
    *a = *b;
    *b = m;
}
void perm(int list[], int k, int m)
{
    int i;
    if(k > m)
    {
       int tempresult=0;
       tempresult = getsum(list,m);
 //      for(int i=0;i<m;i++){
 //           if(dp[list[i]][list[i+1]]!=INT_MAX){
 //                tempresult+=dp[list[i]][list[i+1]];
 //           }
 //           else{
 //               tempresult = INT_MAX;
 //               break;
 //           }
 //      }
       if(tempresult<result){
        result = tempresult;
       }
       //return;
    }
    else
    {
        for(i = k; i <= m; i++)
        {
            swap(&list[k], &list[i]);
            perm(list, k + 1, m);
            swap(&list[k], &list[i]);
        }
    }
}
int main()
{
    int n,e,r;     //表示输入的顶点数和边数
   // cout<<INT_MAX<<endl;
    int a[8];
    //set<int> st;
    while(cin>>n>>e>>r&&e!=0)
    {   for(int i=0;i<r;i++){
         cin>>a[i];
        }
        int i,j;
        int s,t,w;      //表示存在一条边s->t,权值为w
        for(i=0;i<N;i++){
            for(j=0;j<N;j++){
                dp[i][j]=INT_MAX;
            }
        }
        for(i=0;i<e;i++)
        {
            cin>>s>>t>>w;
            dp[s][t]=w;
            dp[t][s]=w;
        }
      for(int k=1;k<=n;k++){
         for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) {
                if(dp[i][k]+dp[k][j]<dp[i][j]) {
                    dp[i][j]=dp[i][k]+dp[k][j];
                    //path[i][j]=path[i][k];
                }
            }
         }
      }
      perm(a,0,r-1);



        cout<<result<<endl;
    }
    return 0;
}


Measured memory_bytes: 512
#include<iostream>

using namespace std;

int main(){
  int A,B,C; cin >> A >> B >> C;
  bool flag = false;
  for(int i = 0; i < B; i++){
    if( A * i % B == C){flag = true;}}
  
  if(flag){cout << "YES" << endl;}
  else{cout << "NO" << endl;} return 0;}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <boost/math/common_factor_rt.hpp>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define SENTINEL 2000000000
typedef long long ll;

using namespace std;
// namespace mp = boost::multiprecision;
// namespace mt = boost::math
// using Bint = mp::cpp_int;

ll merge(int a[], int left, int mid, int right) {
    ll cnt = 0;
    int n1 = mid - left;
    int n2 = right - mid;
    int l[n1 + 1], r[n2 + 1];
    rep(i, n1) l[i] = a[left + i];
    rep(i, n2) r[i] = a[mid + i];
    l[n1] = r[n2] = SENTINEL;
    int p = 0, q = 0;
    for (int i = left; i < right; i++) {
        if (l[p] <= r[q]) {
            a[i] = l[p++];
        } else {
            a[i] = r[q++];
            cnt += n1 - p;
        }
    }
    return cnt;
}

ll mergeSort(int a[], int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        ll v1 = mergeSort(a, left, mid);
        ll v2 = mergeSort(a, mid, right);
        ll v3 = merge(a, left, mid, right);
        return v1 + v2 + v3;
    } else
        return 0;
}

int main() {
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];
    ll ans = mergeSort(a, 0, n);
    cout << ans << endl;
}


Measured memory_bytes: 4648
#include<iostream>
using namespace std;
int main(){
    char a;
    cin >> a;
    if(a == 'A') cout << "T" << endl;
    if(a == 'T') cout << "A" << endl;
    if(a == 'C') cout << "G" << endl;
    if(a == 'G') cout << "C" << endl;
}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main()
{
    int n;
    cin >> n;
    int a[2][n];

    rep(i, 2) rep(j, n) cin >> a[i][j];

    int maxv = 0;

    rep(i, n)
    {
        int sum = 0;
        for (int j = 0; j <= i; j++)
            sum += a[0][j];
        for (int j = i; j < n; j++)
            sum += a[1][j];
        maxv = max(maxv, sum);
    }

    OP(maxv);

    return 0;
}

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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli x,p;

int main(){
  cin >> x >> p;
  cout << setprecision(17);
  if(x%2 == 0) cout << 100.0/p*(x/2)<< endl;
  else cout << 100.0/p*((x+1)/2)*(100-p)/100+100.0/p*((x-1)/2)*p/100+1 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n],mi,ma,summin=INT_MAX,sum;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=a[0];i<=a[n-1];i++)
    {
        sum=0;
        for(int j=0;j<n;j++)
        {
            sum+=(a[j]-i)*(a[j]-i);
        }
        summin=min(summin,sum);
    }
    cout<<summin;
}


Measured memory_bytes: 256
n,m = map(int, input().split())
h = list(map(int, input().split()))

to = [list() for _ in range(n)]

for i in range(m):
    a,b = map(int, input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)

ans =0

for i in range(n):
    flag=True
    for j in to[i]:
        if h[i]<=h[j]:
            flag=False
    if flag:
        ans+=1

print(ans)

Measured memory_bytes: 92992
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <fstream>
#include <numeric>
#include <tuple>

using namespace std;

#define fori(t) for(int i = 0; i < t; ++i)
#define forj(n) for(int j = 0; j < n; ++j)
#define fork(n) for(int k = 0; k < n; ++k)
#define forai(a) for(auto& i : a)
#define foraj(a) for(auto& j : a)
#define forak(a) for(auto& k : a)
#define forp(s, n, d) for(int p = s; p < n; p += d)
#define fast cin.tie(0); cout.tie(0); std::ios_base::sync_with_stdio(0);
#define pb(a) push_back(a);
#define pob(a) pop_back(a);
#define sorti(a) sort(a.begin(), a.end());
#define sortm(a, n) sort(a, a + n);
#define reversi(a) reverse(a.begin(), a.end());
#define fi first
#define se second
#define yes cout << "Yes\n";
#define no cout << "No\n";
#define ans(a) cout << a << '\n';
#define res(a, n) a.resize(n);
#define read(a, n) a.resize(n); fori(n) cin >> a[i];
//#define int long long
//#define double long double

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<long long, long long> llll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int, int>> vii;
typedef vector<pair<int, pair<int, int>>> viii;
typedef pair<int, pair<int, int>> iii;
typedef vector<pair<long long, long long>> vllll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef pair<char, char> cc;
typedef pair<pair<char, char>, char> ccc;
typedef vector<char> vc;
typedef pair<int, char> ic;
typedef pair<ii, char> iic;
typedef vector<bool> vb;
typedef set<int> si;
typedef set<ii> sii;
typedef unsigned long long ull;
typedef pair<ull, ull> ullll;
typedef pair<double, double> dd;
typedef vector<dd> vdd;
typedef vector<pair<ull, ull>> vullll;
typedef pair<bool, bool> bb;
typedef vector<bb> vbb;
typedef vector<vector<ii>> vvii;
typedef vector<vector<iii>> vviii;

const int INF = 2147483647;
const ll LONGINF = 9223372036854775807;
const ll MOD = 1e9 + 7;

vll a;

void solve()
{
    int n;
    cin >> n;
    read(a, n)
    ll last = 0;
    ll res = 0;
    forai(a)
    {
        if (last > i) res += last - i;
        else last = i;
    }
    ans(res)
}

signed main()
{
    fast
    bool mult = false;
    if (mult)
    {
        int t;
        cin >> t;
        while (t--) solve();
    }
    else solve();
    return 0;
}


Measured memory_bytes: 4716
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main()
{
    int n, a,  b;

    cin >> n;
    cin >> a;
    cin >> b;

    if (n == 1) cout << "Hello World";
    if (n == 2) cout << a + b;
    return 0;
}

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

int main(){
	string s;
	cin>>s;
	
	int a,z;
	for(int i=0;i<s.length();i++){
		if(s[i]=='A'){
			a=i;
			break;
		}
	}
	
	for(int i=0;i<s.length();i++){
		if(s[i]=='Z')
			z=i;
	}
	
	cout<<z-a+1;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int main()
{
    fast;
    ll x;
    cin>>x;
    if(x==0)
        cout<<"1"<<endl;
    else cout<<"0"<<endl;
}


Measured memory_bytes: 3648
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>

#define int64 long long
#define uint64 unsigned long long
using namespace std;

int main()
{
	int64 nn, sum = 0, tmp = 0;
	cin >> nn;
	int64 aa[nn], ans[nn] = {0};
	for(int64 ii = 0;ii < nn;ii++)
	{
		cin >> aa[ii];
		sum += aa[ii];
	}
	for(int64 ii = 1;ii < nn;ii += 2)
	{
		tmp += aa[ii];
	}
	ans[0] = sum - 2 * tmp;
	for(int64 ii = 1;ii < nn;ii++)
	{
		ans [ii] = 2 * aa[ii - 1] - ans[ii - 1];
	}
	for(int64 ii = 0;ii < nn;ii++)
	{
		cout << ans[ii] << ' ';
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 2816
#include<bits/stdc++.h>
using namespace std;
#define oo (long long)1e18
#define ll long long
#define setdp memset(dp,-1,sizeof(dp))
const ll mod = 1e9+7;
void _IOS(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);}
#define PI 3.14159265359
int sx,sy,tx,ty;
struct threeElements{
int _1st,_2nd,_3rd;
};
vector<vector<int>>adj(100);
ll n;
ll a[2000009];
bool check(string s,string t)
{
    int n1=s.length(),n2=t.length(),j=0;
    for(int i=0;i<n1;i++)
    {
    if(s[i]==t[j])
            j++;
        if(j==n2)
            return 1;
    }
    return 0;
}
int main()
{
   // freopen ("jumping.in","r",stdin);
   _IOS();
   //18:52
    int n,m;
    cin>>n>>m;
    char b[200][200];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>b[i][j];
    for(int i=0;i<m+2;i++)
        cout<<"#";
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"#";
        for(int j=0;j<m;j++)
        {
            cout<<b[i][j];
        }
        cout<<"#"<<endl;
    }
    for(int i=0;i<m+2;i++)
        cout<<"#";
}


Measured memory_bytes: 3692
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,ok,i;
double a[2005],votes;
int main()
{
    cin>>n>>m;
    for (i=1;i<=n;++i)
        cin>>a[i],votes+=a[i];
    sort(a+1,a+n+1,greater<int>());
    for (i=1;i<=m;++i)
    {
        if (a[i]<votes/(4*m))
        {
            cout<<"No";
            ok=1;
            break;
        }
    }
    if (!ok) cout<<"Yes";
}



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

#define INF 0x334334334LL

typedef long long int LLI;
typedef pair<int, LLI> Pair;

int n;
int I;
int num_node;
int ls[1145141];
char buf[1145141];
bool is_leaf[1145141];
LLI size[1145141];
vector<Pair> es[1145141];

int dfs1(int k, int idx) {
  char *res;
  es[idx].clear();
  size[idx] = 0;
  while (k < n && buf[k] != ')') {
    int g = num_node++;
    LLI t = strtol(buf+k, &res, 10);
    if (buf+k == res) {
      t = 1;
      size[g] = 0;
      ls[g] = k;
      is_leaf[g] = true;
      while (k < n && 'A' <= buf[k] && buf[k] <= 'Z') {
        size[g]++;
        k++;
      }
    } else {
      is_leaf[g] = false;
      if (*res == '(') {
        k = dfs1(res-buf+1, g);
      } else {
        k = res-buf;
        size[g] = 0;
        ls[g] = k;
        is_leaf[g] = true;
        while (k < n && 'A' <= buf[k] && buf[k] <= 'Z') {
          size[g]++;
          k++;
        }
      }
    }
    es[idx].push_back(Pair(g, t));
    size[idx] = min(INF, size[idx] + size[g]*t);
  }
  return k+1;
}

void dfs2(int v, int I) {
  //printf("I: %d\n", I);
  //printf("size[%d]: %lld\n", v, size[v]);
  //printf("is_leaf[%d]: %d\n", v, is_leaf[v]);
  //if (is_leaf[v]) printf("ls[%d]: %d\n", v, ls[v]);
  if (is_leaf[v] && I < size[v]) {
    printf("%c\n", buf[ls[v]+I]);
    return;
  }

  bool found = false;
  //printf("%d:", v);
  for (int i=0; i<es[v].size(); i++) {
    Pair p = es[v][i];
    int u = p.first;
    LLI t = p.second;
    
    //printf(" %d", u);
    if (I < size[u]*t) {
      found = true;
      dfs2(u, I%size[u]);
      break;
    } else I -= size[u]*t;
  }
  //puts("");

  if (!found) puts("0");
}

int main() {
  while (1) {
    scanf("%s%d", buf, &I);
    if (buf[0] == '0' && I == 0) return 0;

    n = strlen(buf);
    num_node = 1;
    assert(dfs1(0, 0) >= n);
    dfs2(0, I);
  }
}

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

int N, K;
 
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> K;
    int ans = 1000000;
    rep(i, N+1) {
        int ans_cand = 1;
        rep(j, i) ans_cand *= 2;
        ans_cand += (N-i)*K;
        ans = min(ans, ans_cand);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort(x.begin(),x.end())
#define ALL(x) x.begin(),x.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;

void Main(){

  int sx,tx,sy,ty;

  cin>>sx>>sy>>tx>>ty;

  cout << 'L';
  rep(i,ty-sy+1){
    cout << 'U';
  }
  rep(i,tx-sx+1){
    cout << 'R';
  }
  cout << 'D';
  rep(i,tx-sx){
    cout << 'L';
  }
  rep(i,ty-sy+1){
    cout << 'D';
  }
  rep(i,tx-sx+1){
    cout << 'R';
  }
  rep(i,ty-sy+1){
    cout << 'U';
  }
  cout << 'L';
  rep(i,ty-sy){
    cout << 'D';
  }
  rep(i,tx-sx){
    cout << 'L';
  }

}

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


Measured memory_bytes: 256
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    String s=sc.next();
    int max=0;
    int begin=0;
    int end=0;
    for(int i=0;i<n;i++){
      if(s.charAt(i)=='(')begin++;
      else end++;
      max=Math.max(max,end-begin);
    }
    String ans="";
    for(int i=0;i<max;i++)ans+='(';
    ans+=s;
    for(int i=0;i<max+begin-end;i++)ans+=')';
    System.out.println(ans);
  }
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> A(H);
  
  for (int i = 0; i < H; i++) {
    
      cin >> A.at(i);
    
  }
 
  
  vector<string> B(H + 2);
  
  for (int i = 0; i < H + 2; i++) {
     if (i == 0 || i == H + 1) {
        string p = "";
        for (int j = 0; j < W + 2; j++) {
           p += "#";
        }
        B.at(i) = p;
     } else {
       string r = A.at(i - 1);
       r = "#" + r + "#";
       B.at(i) = r;
     }
  }
  
  for (int i = 0; i < H + 2; i++) {
    cout << B.at(i) << endl; 
  }
}

Measured memory_bytes: 256
def dfs(i, s, sum):
    if i == 3:
        if sum == 7:
            print(s + "=7")
            exit()
    else:
        dfs(i + 1, s + "+" + abcd[i + 1], sum + int(abcd[i + 1]))
        dfs(i + 1, s + "-" + abcd[i + 1], sum - int(abcd[i + 1]))
abcd = input()
dfs(0, abcd[0], int(abcd[0]))

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

const ll MOD = 1000000007;
const ll MAX = 100100;
const double PI = 3.1415926;

#define vll vector<ll>
#define max_heap priority_queue<int>
#define min_heap priority_queue<int , vector<int>, greater<int> >
#define pb push_back
#define all(container) container.begin(), container.end()
// #define traverse( container, it) for( typeof(container.begin()) it = container.begin(); it!=container.end(); it++)
ll v[MAX];
ll dp[MAX];
ll n,k;

ll fill(ll s)
{
	if (s < 1)
		return 1e9;
	if (s == 1)
		return 0;
	if (dp[s] != -1)
		return dp[s];

	ll temp;
	for(int i = 1; i <= k; i++)
	{
		temp = fill(s - i) + abs(v[s] - v[s - i]);
		if (dp[s] == -1)
			dp[s] = temp;
		dp[s] = min(temp,dp[s]);
	}
	return dp[s];
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	memset(dp,-1,sizeof(dp));
	for(int i = 1; i <= n; i++)
		cin >> v[i];
	cout << fill(n) << endl;
	return 0;
}

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

 int arr[101];
bool dp[100*100+1];
int main(){
	int n;
	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);

	dp[0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=n*100;j>=arr[i];j--){
			if(dp[j-arr[i]]) dp[j] = 1; 
		}
	}

	int res = 0;
	for(int i=1;i<=n*100;i++){
		if(dp[i] && i%10) res = max(res,i);
	}

	cout<<res;

}

Measured memory_bytes: 384
H,W=map(int,input().split())
a=[list(input()) for _ in range(H)]
b=[]
for i in range(H):
    if '#' in a[i]:
        b.append(a[i])
c=[[] for _ in range(len(b))]
for j in range(W):
    flag=False
    for i in range(len(b)):
        if b[i][j]=='#':
            flag=True
    if flag:
        for i in range(len(b)):
            c[i].append(b[i][j])
for i in range(len(c)):
    for j in range(len(c[i])):
        print(c[i][j],end='')
    print()


Measured memory_bytes: 9464
N = int(input())
A = list(map(int,input().split()))
a4 = 0
a2 = 0
a1 = 0

for a in A:
    if a % 4 == 0:
        a4 += 1
    elif a % 2 == 0:
        a2 += 1
    else:
        a1 += 1

if a2 == 0 and a1 <= a4 + 1:
    print('Yes')
elif a4 >= a1:
    print('Yes')
else:
    print('No')

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

using namespace std;

const int M=1000000007;

int main(){
    long long m, n;
    cin >> m >> n;
    char s[m][n];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin >> s[i][j];
        }
    }
    long long dp[m+1][n+1];
    memset(dp, 0, sizeof(dp));
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(i==1 && j==1){
                dp[i][j]=1;
            }
            else if(s[i-1][j-1]=='.'){
               // dp[i][j]=(dp[i-1][j])%M;
                dp[i][j]=((dp[i][j]+dp[i][j-1])%M+dp[i-1][j])%M;
            }
        }
    }
    cout << dp[m][n];
}


Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	if(a[0]==5&&a[1]==5&&a[2]==7){
		cout<<"YES"<<endl;
		return 0;
	}
	cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
X, Y = map(int, input().split())
# c, t
#2c + 2t = 2X
#2c + 4t = Y

#2t = Y - 2X
#2c = 2X - (Y - 2x)
#   = 4X - Y

if Y - 2*X >=0 and Y % 2 == 0 and 4 * X >= Y:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 61828
#!/usr/bin/env python
# -*- coding: utf-8 -*-
n = input()
m = input()
line = []
for i in range(0, n):
    line.append(i)
for i in range(0, m):
    change = map(int, raw_input().split(','))
    change[0] -= 1
    change[1] -= 1
    line[change[0]], line[change[1]] = line[change[1]], line[change[0]]
for i in range(0, n):
    print line[i] + 1
    
    

Measured memory_bytes: 4232
N = int(input())
temp = []
for i in range(N):
    temp.append(input())

last = input()
num = float("inf")
ans = 0

for i, m in enumerate(temp):
    if m.split()[0] == last:
        num = i
    if num < i:
        ans += int(m.split()[1])

print(ans)

Measured memory_bytes: 3060