akhauriyash/Code-Regression huggingface dataset:
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}

import           Control.Applicative
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.Vector                 as V
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM

main :: IO ()
main = do
    n <- readLn
    edges <- U.unfoldrN (n-1) (readInt3.B.dropWhile isSpace) <$> B.getContents
    putStr . unlines . map show . solve $ undirectedGraph n edges

solve :: Graph -> [Cost]
solve gr = U.toList $ height gr

readInt3 :: B.ByteString -> Maybe ((Int,Int,Int), B.ByteString)
readInt3 bs = Just ((x,y,z),bsz)
  where
    Just (x, bsx) = B.readInt bs
    Just (y, bsy) = B.readInt $ B.unsafeTail bsx
    Just (z, bsz) = B.readInt $ B.unsafeTail bsy

type Vertex = Int
type Cost = Int
type Edge = (Vertex, Vertex, Cost)
type Graph = V.Vector (U.Vector (Vertex, Cost))

directedGraph :: Int -> U.Vector Edge -> Graph
directedGraph numV edges = V.map U.fromList
    . V.unsafeAccumulate (flip (:)) (V.replicate numV [])
    . U.convert
    . U.map (\(src, dst, cost) -> (src, (dst, cost)))
    $ edges

undirectedGraph :: Int -> U.Vector Edge -> Graph
undirectedGraph numV edges = directedGraph numV
    $ edges U.++ U.map reverseEdge edges

reverseEdge :: Edge -> Edge
reverseEdge (src, dst, cost) = (dst, src, cost)
{-# INLINE reverseEdge #-}

shortestPath :: Graph -> Vertex -> U.Vector Cost
shortestPath tree root = U.create $ do
    dist <- UM.unsafeNew (V.length tree)
    UM.unsafeWrite dist root 0
    U.forM_ (V.unsafeIndex tree root) $ \(v, cost) ->
        fix `flip` root `flip` v `flip` cost $ \dfs p u c -> do
            UM.unsafeRead dist p >>= UM.unsafeWrite dist u . (+c)
            U.mapM_ (uncurry $ dfs u)
                . U.filter ((/=p).fst)
                $ V.unsafeIndex tree u
    return dist

height :: Graph -> U.Vector Cost
height tree = U.zipWith max fromS fromT
  where
    !s = U.maxIndex $ shortestPath tree 0
    !fromS = shortestPath tree s
    !t = U.maxIndex fromS
    !fromT = shortestPath tree t

Measured memory_bytes: 11396
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define FORR(i, m, n) for(ll i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n)
#define MAX 100000
#define inf 1000000007
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
using graph = vector<vector<int>>;

int main() {
    //cin高速化
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, tmp;
  	ll s = 0;
    cin >> n;
    vll box(n+10, 0);
    vll ball(n, 0);
    REP(i, n){
        cin >> tmp;
        ball[i] = tmp;
        box[tmp] ++;
    }
  
    //すべてのボールのペアの出し方の和を先に格納
    REP(i, n+1){
        if(box[i] > 1){
            s += (box[i]*(box[i]-1))/2;
        }
    }

    //kの分だけ差し替えて出力
    REP(i, n){
        tmp = ball[i];
        if(box[tmp] > 2) cout << s - (box[tmp]*(box[tmp]-1))/2 + ((box[tmp]-1)*(box[tmp]-2))/2 << endl;
        else if(box[tmp] == 2) cout << s - (box[tmp]*(box[tmp]-1))/2 << endl;
        else cout << s << endl;
    }

	return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(int i = m;i >= n;--i)
#define INF INT_MAX/2
using namespace std;
using ll = long long;
using R = double;
using Data = pair<ll, vector<int>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 50;
struct edge { ll from; ll to; ll cost; };
typedef tuple<ll, ll, ll>T;
typedef pair<ll,ll>pll;

int N;
ll A[3010];
int vis[3010][3010];
ll memo[3010][3010];
ll dp(int L,int R) {
	if (L > R)return 0;
	if (vis[L][R])return memo[L][R];
	vis[L][R] = 1;
	int diff = N - (R - L + 1);

	ll res;
	if (diff % 2 == 0) {
		res = -inf;
		res = max(res,dp(L+1,R)+A[L]);
		res = max(res,dp(L,R-1)+A[R]);
	}
	else {
		res = inf;
		res = min(res,dp(L+1,R)-A[L]);
		res = min(res,dp(L,R-1)-A[R]);
	}
	return memo[L][R] = res;
}


int main(){
	cin >> N;
	rep(i, 0, N)cin >> A[i];

	cout << dp(0, N - 1) << endl;
	
	return 0;
}



Measured memory_bytes: 105472
#include <algorithm>
#include <map>
#include <vector>
#include <iostream>
#include <stdio.h>
#include <set>
#include <string>
#include <stack>
#include <stdlib.h>
#include <math.h>
#include <iomanip>
#include <iterator>

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<ll, ll> point;

#define PI 3.1415926535897932384626433832795

int main() {
    iostream::sync_with_stdio(false);
    string s; cin>>s;

    if (s.size()==2) {
        if (s[0]==s[1]) cout<<"1 2"<<endl;
        else cout<<"-1 -1"<<endl;
        return 0;
    }
    for (int i=0; i<s.size()-2; i++) {
        if ((s[i]==s[i+1])||(s[i]==s[i+2])||(s[i+1]==s[i+2])) {
            cout<<i+1<<" "<<i+3<<endl;
            return 0;
        }
    }
    cout<<"-1 -1"<<endl;
    return 0;
}


Measured memory_bytes: 512
package main

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

var (
	n   int
	tmp int
)

func main() {
	fmt.Scanln(&n)

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	a := make([]int, 0, n)

	for sc.Scan() {
		tmp, _ := strconv.Atoi(sc.Text())
		a = append(a, tmp)
	}

	if n == 1 {
		fmt.Println(a[0])
		os.Exit(0)
	} else if n == 2 {
		fmt.Println(a[1], a[0])
		os.Exit(0)
	}

	i := len(a) - 1
	for i >= 0 {
		fmt.Printf("%d ", a[i])
		i -= 2
	}
	if i == -2 {
		i = 1
	} else {
		i = 0
	}
	for i < len(a) {
		if i == len(a)-2 {
			fmt.Println(a[i])
			break
		}
		fmt.Printf("%d ", a[i])
		i += 2
	}

}

Measured memory_bytes: 7040
#include<iostream>
using namespace std;
int n,x,y,z;
long mod=1e9+7,dp[41][1<<17];
main()
{
	cin>>n>>x>>y>>z;
	int no=1<<z-1|1<<y+z-1|1<<x+y+z-1;
	dp[0][0]=1;
	long ans=1;
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<=10;j++)
		{
			for(int k=0;k<1<<17;k++)
			{
				int nxt=(k<<j|1<<j-1)&(1<<17)-1;
				if((nxt&no)!=no)(dp[i+1][nxt]+=dp[i][k])%=mod;
			}
		}
		(ans*=10)%=mod;
	}
	for(int i=0;i<1<<17;i++)ans=(ans-dp[n][i]+mod)%mod;
	cout<<ans<<endl;
}

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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n)　for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod 1e9 +7;

const double pi = acos(-1.0);

typedef string ss;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll x,ll y)
{
    x /= gcd(x,y);
    //y /= gcd(x,y);
    return (x*y);
}

#define WA printf("WA\n");
int main()
{
    ll n,m;
    cin >> n >> m;
    vs a(n),b(m);
    rep(i,n)cin >> a[i];
    rep(i,m)cin >> b[i];
    rep(i,n-m+1){
        rep(j,n-m+1){
            ll count=0;
            rep(k,m){
                rep(l,m){
                    if(b[k][l] == a[i+k][j+l])count++;
                }
            }
            if(count == m*m){
                cout << "Yes" << endl;
                return 0;
            }

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


Measured memory_bytes: 256
//---------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
//---------------------------------------------------------------
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define SIZE 100005
#define INF 1000000000000000LL
#define all(x) x.begin(),x.end()
using pint = pair<int,int>;
using vec = vector<int>;
using ll=long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
//---------------------------------------------------------------
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//---------------------------------------------------------------

//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

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

    double PI = acos(-1);

    double a,b,x;cin>>a>>b>>x;

    double area=x/a;
    auto theta = [&](double t){
        if(tan(t)<=b/a){
            return a*b - a*(a*tan(t))/2;
        }else{
            return b*(b/tan(t))/2;
        }
    };

    double l=0, r = PI/2;
    for(int i=0; i<10000; ++i) {
        double mid=(l+r)/2;
        if(theta(mid)>=x/a) l = mid;
        else r = mid;
    }

    cout<<fixed<<setprecision(10)<<l*180/PI<<endl;
}

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

using namespace std;

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

#define INF (INT_MAX/2)
#define PI (2*acos(0.0))
#define EPS (1e-8)

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;

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

void printResult(int sec){
  int h = sec / 3600;
  int m = (sec - h * 3600) / 60;
  int s = sec - h * 3600 - m * 60;
  printf("%02d:%02d:%02d\n", h, m, s);
}

int main(void){
  ios_base::sync_with_stdio(0);
  int h, m, s;
  while(cin >> h >> m >> s, h >= 0 && m >= 0 && s >= 0){
    int all_sec = 2 * 3600;
    int now_sec = h * 3600 + m * 60 + s;
    int rest_sec = all_sec - now_sec;
    int three_times_sec = rest_sec * 3;
    printResult(rest_sec);
    printResult(three_times_sec);
  }
  return 0; 
}

Measured memory_bytes: 1208
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def query(x):
        print(x)
        ret = input()
        if ret == "Vacant":
            sys.exit()
        return ret

    n = int(readline())

    l = 0
    r = n - 1

    op = {"Male": "Female", "Female": "Male"}

    ls = query(l)
    rs = query(r)

    while r - l > 1:
        mid = (l + r) // 2
        ms = query(mid)
        if (mid - l) % 2 == 0:
            if ls == ms:
                l = mid + 1
                ls = op[ms]
            else:
                r = mid - 1
                rs = op[ms]
        else:
            if ls == ms:
                r = mid - 1
                rs = op[ms]
            else:
                l = mid + 1
                ls = op[ms]
    query(l)
    query(r)


if __name__ == '__main__':
    main()


Measured memory_bytes: 62276
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

const ll mod=1e9+7;

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s;
    t=s;
    reverse(begin(s),end(s));
    if(s==t){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int n, m, i, s, tmp;
    int t[100]={}, p[100]={}, x[100]={};
    scanf("%d", &n);
    s = 0;
    for (i=0; i<n; i++){
        scanf("%d ", &t[i]);
        s += t[i];
    }
    
    scanf("%d", &m);
    for (i=0; i<m; i++){
        scanf("%d %d\n", &p[i], &x[i]);
    }
    
    for (int i=0; i<m; i++){
        tmp = s-t[p[i]-1]+x[i];
        printf("%d\n", tmp);
    }
    
    return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {
  @SuppressWarnings("resource")
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int W = sc.nextInt();
    int H = sc.nextInt();
    int N = sc.nextInt();
    // 塗りつぶされていない範囲のx,yを求める
    int maxX = W, minX = 0;
    int maxY = H, minY = 0;

    for (int n = 0; n < N; n++) {
      int x = sc.nextInt();
      int y = sc.nextInt();
      int a = sc.nextInt();

      if (a == 1) {
        minX = Math.max(minX, x);
      } else if (a == 2) {
        maxX = Math.min(maxX, x);
      } else if (a == 3) {
        minY = Math.max(minY, y);
      } else if (a == 4) {
        maxY = Math.min(maxY, y);
      }
    }

    int x = (maxX - minX) > 0 ? (maxX - minX) : 0;
    int y = (maxY - minY) > 0 ? (maxY - minY) : 0;
    System.out.println(x * y);
  }
}


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

long long a,b,n;
string ss;
int main(){
    cin>>n;
    vector<int>v(n+2,0);
    for (int i=1; i<=n; i++){
        cin>>v[i];
        b+=abs(v[i]-v[i-1]);
    }
    b+=abs(v[n]);
    for (int i=1; i<=n; i++){
        cout<<b-abs(v[i]-v[i-1])-abs(v[i]-v[i+1])+abs(v[i-1]-v[i+1])<<endl;
    }
}


Measured memory_bytes: 1664
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int a,b,c; cin>>a>>b>>c;
    if(a<c && c<b) cout<<"Yes"<<endl;
    else if(b<c && c<a) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 3540
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int b[100000];
 
int main() {

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n)    cin >> a[i];

    rep(i,n) {
        b[a[i]]++;
    }
    int ans = 0;
    rep(i,100000-1) {
        ans = max(ans, b[i] + b[i+1] + b[i+2]);
    }
    
    cout<< ans <<endl;

 return 0;
}

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

int main(){

	long long a,b,c;
	cin >> a >> b >> c;

	if(a == 0 && b == 0){

		cout << 1 << endl;
	}
	else if(a == 0){

		cout << b/c + 1 << endl;
	}
	else{

		cout << (b/c)-((a-1)/c) << endl;
	}
}

Measured memory_bytes: 256
def main():
  n = int(input())
  li = list(input())
  i = 0
  j = n-1
  ans = 0
  while(i < j):
    while(li[i] == "R" and i < j):
      i += 1
    while(li[j] == "W" and i < j):
      j -= 1
    if li[i] == "W" and li[j] == "R":
      li[i] = "R"
      li[j] = "W"
      ans += 1
  print(ans)    

if __name__ == '__main__':
  main()

Measured memory_bytes: 10500
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

bool removePair(vector<int>& c, int x, int y)
{
    int n = c.size();
    if(x >= n || y >= n) // 指定した位置にカードがない
        return false;
    if(c[x] != c[y]) // 指定した位置のカードの数字が異なる
        return false;
    c.erase(c.begin() + max(x,y));
    c.erase(c.begin() + min(x,y));
    return true;
}

map<vector<int>, int> memo;

int solve(const vector<int>& c)
{
    if(memo.find(c) != memo.end())
        return memo[c];

    int n = c.size();

    int ret = n;
    for(int i=0; i<n; ++i){
        vector<int> c2 = c;
        if(removePair(c2, i, i+4))
            ret = min(ret, solve(c2));
        if(i % 4 != 3){
            c2 = c;
            if(removePair(c2, i, i+1))
                ret = min(ret, solve(c2));
            c2 = c;
            if(removePair(c2, i, i+5))
                ret = min(ret, solve(c2));
        }
        if(i % 4 != 0){
            c2 = c;
            if(removePair(c2, i, i+3))
                ret = min(ret, solve(c2));
        }
    }

    return memo[c] = ret;
}

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

    while(--n >= 0){
        vector<int> c(20);
        for(int i=0; i<20; ++i)
            cin >> c[i];

        memo.clear();
        cout << solve(c) << endl;
    }

    return 0;
}

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

int main(){
  int N;
  string S;
  cin >> N >> S;
  int cnt =0;
  for (int i = 0; i < N-2; i++)
  {
    if (S.substr(i, 3)=="ABC") cnt ++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

	if (N % 2) {

		cout << N / 2 << "\n";
	}
	else {
		cout << (N - 1) / 2 << "\n";
	}
}


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

using namespace std;

const int maxn=100000+5;
int h[maxn],mem;
struct
{
    int v,next;
}e[maxn<<1];
void add(int u,int v)
{
    e[mem].v=v;
    e[mem].next=h[u];
    h[u]=mem++;
}
int sg[maxn];
void dfs(int u,int fa)
{
    sg[u]=0;
    for(int i=h[u];i+1;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u);
        sg[u]^=(sg[v]+1);
    }
}
int main() {
    int n;
    scanf("%d",&n);
    memset(h,-1,sizeof(h));mem=0;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,1);
    int ans=0;
    for(int i=h[1];i+1;i=e[i].next)
    {
        int v=e[i].v;
        ans^=sg[v];
    }
    printf("%s\n",sg[1]!=0?"Alice":"Bob");
    return 0;
}


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

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

  if(s=="Sunny")
  cout << "Cloudy" << endl;
  else if (s=="Cloudy")
  cout << "Rainy" << endl;
  else
  cout << "Sunny" << endl;
}

Measured memory_bytes: 3572
import java.util.Scanner;

public class Main{
    public static void main(String[] args) throws java.lang.Exception{
        Scanner sc = new Scanner(System.in);
        double r = sc.nextDouble();
        double a = (double)r*r*3.141592653589;
        double c = (double)(2*r)*3.141592653589;
        System.out.println(String.format("%.5f", a) + " " + String.format("%.5f", c));
    }
}


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

//
#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#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 UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) |= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

int N;
int a[101010], cont[101010];
set<int> st;

signed main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  sort(a, a + N);

  for (int i = 0; i < N; i++) {
    cont[i] = (N - (int)(lower_bound(a, a + N, a[i]) - a));
  }

  /*
  cout << endl;
  for (int i = 0; i < N; i++) {
    cout << cont[i] << endl;
  }
  */

  //for (int i = 1; i <= N; i++) cout << cont[i] << endl;

  int grundy = 0;
  for (int i = 0; i < N; i++) {
    if (EXIST(st, a[i])) continue;

    if (i > 0) {
      if ((a[i] - a[i - 1]) % 2) grundy ^= cont[i];
    }
    if (i == 0) {
      if (a[i] % 2) grundy ^= cont[0];
    }

    st.insert(a[i]);
  }

  if (grundy != 0) {
    cout << "first" << endl;
  } else {
    cout << "second" << endl;
  }

  return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>
#include <utility>
#include <sstream>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) x.begin(),x.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

int main(){
    int H,W;
    cin >> H >> W;

    vector<vector<char>> A(H,vector<char>(W)),hako(H,vector<char>(W)),ans(H,vector<char>(W));

    for(int i = 0;i < H;i++)
        for(int j = 0;j < W;j++)
            cin >> A.at(i).at(j);

    int genzita = 0,hight =0;
    for(int i = 0;i < H;i++){
        int count = 0;
        
        for(int j = 0;j < W;j++){
            if(A.at(i).at(j) == '.')
                count++;
        }

        if(count != W){
            for(int j = 0;j < W;j++){
                hako.at(hight).at(j) = A.at(i).at(j);
                
            }
            hight++;
        }else{
          genzita++;  
        }
    }

    /*for(int i = 0;i < hight;i++){
        for(int j = 0;j < W;j++){
            cout << hako.at(i).at(j);
        }
        cout << endl;
    }

    */

    int yoko = 0;
    for(int i = 0;i < W;i++){
        int count = 0;
        for(int j = 0;j < H-genzita;j++){
            if(hako.at(j).at(i) == '.')
                count++;
        }

        if(count != (H-genzita)){
            for(int j = 0;j < H-genzita;j++){
                ans.at(j).at(yoko) = hako.at(j).at(i);
            }
            yoko++;
        }
    }

    for(int i = 0;i < hight;i++){
        for(int j = 0;j < yoko;j++){
            cout << ans.at(i).at(j);
        }
        cout << endl;
    }


}

Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    double ans = 0;
    rep(i, n){
        double d;
        cin >> d;
        ans += (1 / d);
    }

    cout << (1 / ans) << endl;
}

Measured memory_bytes: 256
#include<unordered_map>
#include<utility>
template<typename T>
class UnionFind {
 public:
  void unite(const T& a, const T& b) {
    auto x = find(a), y = find(b);
    if(rank_[x] < rank_[y]) std::swap(x, y);
    parent_[y] = x;
    if(rank_[x] == rank_[y]) rank_[x] += 1;
  }
  T find(const T& x) {
    if(!parent_.count(x)) {
      rank_[x] = 1;
      return parent_[x] = x;
    }
    return (parent_[x] == x) ? x : (parent_[x] = find(parent_[x]));
  }
 private:
  std::unordered_map<T, T> parent_;
  std::unordered_map<T, int> rank_;
};

#include<bits/stdc++.h>

using Vertex = int;
struct Edge {Vertex from, to;};
using Graph = std::vector<std::vector<Edge>>;

// ?????£?????????????§£ O(|V| + |E|)
std::vector<std::vector<Vertex>> strongly_connected_component(const Graph& G) {
  std::vector<std::vector<Vertex>> scc;
  std::stack<Vertex> S;
  std::vector<bool> inS(G.size());
  std::vector<int> num(G.size()), low(G.size());
  int timer = 0;
  // Tarjan
  std::function<int(Vertex v)> dfs = [&](Vertex v){
    num[v] = low[v] = ++timer;
    S.push(v); inS[v] = true;
    for(const auto& e: G[v]) {
      if(!num[e.to])     low[v] = std::min(low[v], dfs(e.to));
      else if(inS[e.to]) low[v] = std::min(low[v], num[e.to]);
    }
    if(num[v] == low[v]) {
      scc.push_back(std::vector<Vertex>());
      while(true) {
        auto w = S.top(); S.pop(); inS[w] = false;
        scc.back().push_back(w);
        if(v == w) break;
      }
    }
    return low[v];
  };
  for(Vertex v = 0; v < G.size(); ++v) if(!num[v]) dfs(v);
  return scc;
}

using namespace std;

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

  Graph G(N);
  for(auto i = 0; i < M; ++i) {
    int s, t;
    cin >> s >> t;
    G[s].push_back({s, t});
  }

  auto scc = strongly_connected_component(G);

  UnionFind<int> S;
  for(auto v: scc) for(auto i: v) S.unite(v.front(), i);

  set<int> in, out;
  for(auto E: G) for(auto e: E) if(S.find(e.from) != S.find(e.to)) {
    in.emplace(S.find(e.to));
    out.emplace(S.find(e.from));
  }

  if(scc.size() == 1) cout << 0 << endl;
  else cout << max(scc.size() - in.size(), scc.size() - out.size()) << endl;
}

Measured memory_bytes: 6972
#include <bits/stdc++.h>
using namespace std;
const int N = 13, M = 1005, K = (1 << 12);
const int inf = 10000000;
int n, m, f[M][K], a[M], b[M], mask[M];
int main () {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &a[i], &b[i]);
		mask[i] = 0;
		for (int j = 0; j < b[i]; j++) {
			int x;
			scanf("%d", &x);
			mask[i] |= (1 << (x - 1));
		}
	}
	for (int i = 0; i < (1 << n); i++) f[0][i] = inf;
	f[0][0] = 0ll;
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < (1 << n); j++) f[i][j] = f[i - 1][j];
		for (int j = 0; j < (1 << n); j++) {
			f[i][j | mask[i]] = min(f[i][j | mask[i]], f[i - 1][j] + a[i]);
		}
	}
	if (f[m][(1 << n) - 1] >= inf / 2) printf("-1\n");
	else printf("%d\n", f[m][(1 << n) - 1]);
	return 0;
}

Measured memory_bytes: 16256
#include <iostream>
#include <string>
#include <sstream>  // istringstream
#include <vector>

using namespace std;

int main()
{
	int N = 0;
	std::string lineBuf;

	cin >> N;

	std::vector<int> vctA(N + 2);
#if 0
	cin >> lineBuf;
	istringstream iss(lineBuf);
	string s;
	while (iss >> s){
		cout << s;
	}
#else
	//istringstream iss(lineBuf);
	//string s;
	vctA[0] = 0;
	for (int i = 0; i < N; ++i){
		// int num = 0;
		cin >> vctA[i + 1];
	}
	vctA[N + 1] = 0;
	// std::vector<int> vctA2()
#endif

#if 1
	// 最初に全部回った金額を算出
	int sum = 0;
	int CorPrep = 0;// 1つ前の座標
	for (int i = 0; i < N; ++i){
		int curCor = vctA[i + 1];
		int money = std::abs(curCor - CorPrep);
		sum += money;
		CorPrep = curCor;
	}
	int lastMoney = std::abs(CorPrep); // - 0
	sum += lastMoney;
	// cout << sum << std::endl;

	CorPrep = 0;
	// int CorNext = vctA[2];
	int CorNext = 0;
	int CorCur = vctA[1];
	for (int i = 0; i < N; ++i){
		int CorNext = vctA[i + 2];
#if 0
		if (CorPrep <= CorCur && CorCur <= CorNext){
			cout << sum << std::endl;
		}
		else
#endif		
		if ((CorCur < CorPrep && CorCur < CorNext)
			|| (CorCur > CorPrep && CorCur > CorNext))
		{
			int money1 = std::abs(CorCur - CorPrep);
			int money2 = std::abs(CorCur - CorNext);

			
			if (money1 < money2){
				cout << sum - money1 * 2 << std::endl;
			}
			else {
				cout << sum - money2 * 2 << std::endl;
			}
		}
		else {
			cout << sum << std::endl;
		}
		CorPrep = CorCur;
		CorCur = CorNext;
	}

#else
	for (int j = 0; j < N; ++j){
		int sum = 0;
		int CorPrep = 0;// 1つ前の座標
		for (int i = 0; i < N; ++i){
			if (i == j){
				continue;
			}
			int money = std::abs(vctA[i] - CorPrep);
			sum += money;
			CorPrep = vctA[i];
		}
		int lastMoney = std::abs(CorPrep); // - 0
		sum += lastMoney;
		cout << sum << std::endl;
	}
#endif

	return 0;
}

Measured memory_bytes: 1664
N = int(input())
alph = {'a':'b','b':'c','c':'d','d':'e','e':'f','f':'g','g':'h','h':'i','i':'j','j':'k'}
result = ['a']
for i in range(N-1):
    s = []
    for j in result:
        for k in range(len(j)):
            s.append(j+j[k])
        s.append(j+alph[max(j)])
    result = s

result = list(set(result))
result.sort()
for j in result:
    print(j)

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

 int main()
{
    long long int A, B, s, t, u;
    bool a = true;
    cin >> A >> B;
    if(A%2!=0){
    s = A*100/8 + 1;
    u = 11;}
    else{
        s= A*100/8;
        u = 12;
    }
    t = B*10;
    for(int i = 0;i<=9;i++){
        for(int j = 0;j<=u;j++){
        if(t+i==s+j){
            cout << t + i << endl;
            a = false;
            break;
        }
        if(a == false){
            break;
        }
    }
    }
    if(a){
        cout << -1 << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int MOD = 998244353;
const double PI = acos(-1.0);
const double EXP = 1e-8;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
inline ll qpow(ll a, ll b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}
bool ok(string s, int l, int r)
{
    while (s[l] == s[r])
        ++l, --r;
    return l >= r;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll l;
    cin>>l;
    double ans;
    ans=pow(l/3.0,3);
    cout<<fixed<<setprecision(12)<<ans;
}


Measured memory_bytes: 256
def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

def solve():
  a,b = (int(i) for i in input().split())
  print(max([a+b,a*b,a-b]))


solve()
  
  

Measured memory_bytes: 2940
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    double pi = 3.1415926535897932384626433;    
    double a,b,h,m;
    cin >> a >> b >> h >> m;
    double theta;
    if( abs(6*m - (30*h+m/2)) > 180 ) theta = 360 - abs(6*m - (30*h+m/2));
    else theta = abs(6*m - (30*h+m/2));

    cout << fixed << setprecision(21) << sqrt(a*a + b*b -2*a*b*cos(theta*pi/180)) << endl;

    return 0;
}



Measured memory_bytes: 4228
import java.util.*;

public class Main {
  public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	String letters = "ACGT";
 
    char letter = scanner.next().charAt(0);
	for (int ix = 0; ix < letters.length(); ix++) {
      if (letters.charAt(ix) == letter) {
		System.out.println(letters.charAt(letters.length() - ix - 1)); 
      }
    }
  }
}

Measured memory_bytes: 23764
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <mutex>
#include <cmath>
#include <set>
#include <climits>

#define mod 1e9+7
#define mp make_pair
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
int main(){
	string S;
	int ans = 0;
    cin >> S;
	for(int i = 0; i < S.size() / 2; i++){
		if(S[i] == S[S.size()-1-i]) continue;
		ans++;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 384
short*z,a[2][99];n,m,i,p;main(c){for(;m=scanf("%d %[^\n] %[^\n]",&n,a,a+1)*n;printf(m>n?"NA\n":"%d\n",m))for(i=2;i--;m=c)for(c=p=0;z=p+a[c+i&1],c<m&&*z&2|n+~p;)p+=p>=n|*z&2?-1:*z&1&z[1]?1:!++c+2;}

Measured memory_bytes: 0
//ProblemD

#ifdef _MYPC
#include "mypc.h"
#endif // _MYPC

#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <memory>
#include <complex>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

//ProblemD

using ll = long long;

class Solve {
private:
	void solve() {
		int Q;
		cin >> Q;
		ll a, b;
		for (int qq = 0; qq < Q; qq++) {
			cin >> a >> b;
			ll p = a * b - 1;

			ll q = (ll)sqrt(p);
			while ((q + 1) * (q + 1) <= p) q = q + 1;
			while (q * q > p) q --;

			if (q == 0) {
				cout << 0 << endl;
				continue;
			}

			ll rst = 2 * q - 1;
			ll ne = q;
			if (q * (q + 1) <= p) {
				rst++;
				ne++;
			}

			auto uni = [&](ll x) -> ll {
				if (x <= q) return 1;
				ll s = p / x;
				if (s == 0) return 0;
				if (s + x > q + ne) return 0;
				if (p / s > x) return 0;
				return 1;
			};
			rst -= uni(a);
			rst -= uni(b);

			cout << rst << endl;
		}
	}

public:
	Solve() { solve(); }
};

int main(int argc, char* argv[]) {
	unique_ptr<Solve> solve = make_unique<Solve>();
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>

int main() {
    //入力
    int a,b,c;
    std::scanf("%d%d%d",&a,&b,&c);

    if(a < b && b < c) {
        std::printf("Yes");
    }
    else {
        std::printf("No");
    }
    std::printf("\n");

    return 0;
}


Measured memory_bytes: 2604
#include<bits/stdc++.h>
using namespace std;
int main(){
	string a,b,c;
    cin>>a>>b>>c;
	cout<<(char)((int)a[0]-'a'+'A')<<(char)((int)b[0]-'a'+'A')<<(char)((int)c[0]-'a'+'A')<<endl;
  	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string a,b;
  cin >> a >> b;
  if (a.at(0) == b.at(2) && a.at(1) == b.at(1) && a.at(2) == b.at(0)) {
  	cout << "YES\n";
  }else {
  	cout << "NO\n";
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#define sc(n) scanf("%d",&n)
#define sc2(x,y) scanf("%d %d",&x,&y)
#define fornt(i,n) for(i=0; i<n; ++i)
using namespace std;


int main ()
{
    int i,c=0;
  string s,t;
  cin>>s;
  cin>>t;
  fornt(i,s.size())
  {
      if(s[i]!=t[i])
      ++c;
  }
  printf("%d\n",c);
}


Measured memory_bytes: 3468
import sys
sys.setrecursionlimit(10**6)
def dfs(tree, n, ans):
    for i in tree[n]:
        ans[i] += ans[n]
        tree[i].remove(n)
        dfs(tree, i, ans)

n, q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n-1)]
px = [list(map(int,input().split())) for _ in range(q)]

g = [[] for _ in range(n)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
    g[ab[i][1]-1].append(ab[i][0]-1)

ans = [0]*n
for i in range(q):
    ans[px[i-1][0]-1] += px[i-1][1]
dfs(g, 0, ans)

print(*ans)

Measured memory_bytes: 300052
n = int(input())
s = input()
cnt = 0

for i in range(1, n):
    c = 0
    s1 = s[i:]
    s2 = s[:i]
    S = set(s1)

    for j in S:
        if j in s2:
            c += 1
    cnt = max(cnt, c)

print(cnt)

Measured memory_bytes: 9096
class ModCombination
    def initialize(max)
        @MOD = 10 ** 9 + 7
        @fact = [1, 1]
        @factinv = [1, 1]
        @inv = [0, 1]
        2.upto(max) do |i|
            @fact << @fact[i-1] * i % @MOD
            @inv << @MOD - @inv[@MOD % i] * (@MOD / i) % @MOD
            @factinv << @factinv[i-1] * @inv[i] % @MOD
        end
    end
    def com(n, k)
        return 0 if n < k
        return 0 if n < 0 || k < 0
        return @fact[n] * (@factinv[k] * @factinv[n-k] % @MOD) % @MOD
    end
end

x, y = gets.chomp.split(" ").map(&:to_i)
n = (2 * y - x) / 3
m = (2 * x - y) / 3

if (x+y) % 3 == 0 then
    max = 10 ** 6
    comb = ModCombination.new(max)
    puts comb.com(n+m, n)
else
    puts 0
end

Measured memory_bytes: 29228
#include <stdio.h>
 
#define GROUP_1_MAX 7
#define GROUP_2_MAX 4
#define GROUP_3_MAX 1
 
typedef struct {
  int group[GROUP_1_MAX];
} GROUP_t;
 
int checkNum( GROUP_t *a_pstGroup, int x, int y, int groupNum );
 
int main(){
  int x,y,ret1,ret2,ret3;
  GROUP_t stGroup1 = { 1, 3, 5, 7, 8, 10, 12 };
  GROUP_t stGroup2 = { 4, 6, 9, 11 };
  GROUP_t stGroup3 = { 2 };
  
  scanf( "%d", &x );
  scanf( "%d", &y );
  
  ret1 = checkNum( &stGroup1, x, y, GROUP_1_MAX );
  ret2 = checkNum( &stGroup2, x, y, GROUP_2_MAX );
  ret3 = checkNum( &stGroup3, x, y, GROUP_3_MAX );
  if( ( ret1 != 0 ) || ( ret2 != 0 ) || ( ret3 != 0 ) ) {
    printf( "%s\n", "Yes" );
  } else {
    printf( "%s\n", "No" );
  }
  
  return 0;
}
 
int checkNum( GROUP_t *a_pstGroup, int x, int y, int groupNum ) {
  int i, ret, x_count = 0, y_count = 0;
  
  for( i = 0; i < groupNum; i++ ){
    if( x == a_pstGroup->group[i] ){
      x_count = 1;
    }
    if( y == a_pstGroup->group[i] ){
      y_count = 1;
    }
  }
  if ( ( x_count == 1 ) && ( y_count == 1 ) ) {
    ret = groupNum;
  } else {
    ret = 0;
  } 
  
  return ret;
}


Measured memory_bytes: 2060
while True:
  n = int(input())
  if n == 0:break
  to = []
  fr = [[] for _ in range(n * n)]
  for i in range(n):
    line = list(map(int, input().split()))
    for j in range(n):
      x, y = line[2 * j:2 * j + 2]
      to.append(y * n + x)
      fr[y * n + x].append(i * n + j)
  
  order = []
  used = [False] * (n * n)
  def dfs(x):
    if used[x]:return
    used[x] = True
    dfs(to[x])
    order.append(x)
  
  for i in range(n * n):
    dfs(i)
  order.reverse()
  
  def dfs2(x, used, group):
    if used[x]:return False
    if x in group:return True
    group.append(x)
    ret = False
    ret = ret or dfs2(to[x], used, group)
    return ret
  
  used = [False] * (n * n)
  ans = 0
  for i in order:
    group = []
    if not used[i]:
      if dfs2(i, used, group):ans += 1
    for g in group:used[g] = True
  print(ans)
  


Measured memory_bytes: 8400
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
typedef long long int ll; 
typedef long double ld; 

#define MAX 3000
#define mod 1000000007

ll add(ll a,ll b)
{
	return (mod+(a+b)%mod)%mod;
}


int main()
{
	
  std::ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
	
	char c;
	cin>>c;
	
	if(c>='a' && c<='z')
	{
		cout<<'a'<<endl;
	}
	else{
		cout<<'A'<<endl;
	}
	
}















Measured memory_bytes: 3608
#include<iostream>
using namespace std;
#define R(i,n) for(int i=0;i<n;i++)
int n,a=1e9,c[2][20],p[1<<18][51];main(){cin>>n;int s=1<<n;R(i,n)cin>>c[0][i];R(i,n)cin>>c[1][i];fill(p[1],p[s],1e9);;R(B,s){int o=0,d[n];R(i,n)if(!(B&1<<i))d[i]=o++;R(i,n){int k=c[abs(i-n+o)%2][i];R(j,k+1)p[B|1<<i][k]=min(p[B|1<<i][k],p[B][j]+d[i]);}}R(i,51)a=min(a,p[s-1][i]);cout<<(a>1e8?-1:a);}

Measured memory_bytes: 52480
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) v.begin(), v.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main() 
{
  ll a, b; cin >> a >> b;
  if(a <= b)cout << 0 << endl;
  else cout << a-b << endl;
  system("pause");
}

Measured memory_bytes: 504
from heapq import heappush, heappop
INF = 10**15
def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    prev = [-1] * n
    d[s] = 0
    heappush(que, (0, s))
    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                prev[w] = v
                heappush(que, (d[w], w))
    return d, prev

n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    ai, bi, ci = map(int, input().split())
    ai, bi = ai-1, bi-1
    edges[ai].append((ci, bi))
    edges[bi].append((ci, ai))

q, k = map(int, input().split())
k -= 1
d, prev = dijkstra(k, edges)
ans = []
for i in range(q):
    xi, yi = map(int, input().split())
    xi, yi = xi-1, yi-1
    ans.append(d[xi]+d[yi])

for i in ans:
    print(i)

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

const ll INF = 1LL << 60;

ll A, B;
vector<string> c;

int main() {
    cin >> A >> B;
    c.resize(100);
    for (int i = 0; i < 100; i++) {
        if (i >= 50) {
            c[i] = string(100, '#'); 
        } else {
            c[i] = string(100, '.'); 
        }
    }

    // 奇数行目について # を 1つおきに塗っていく
    int cnt = 0;
    for (int i = 0; i < 50; i += 2) {

        if (cnt >= B - 1) break;

        for (int j = 0; j < 100; j += 2) {
            if (cnt >= B - 1) break;
            c[i][j] = '#';
            cnt++;
        }
    }

    cnt = 0;

    for (int i = 51; i < 100; i += 2) {
        if (cnt >= A - 1) break;
        for (int j = 0; j < 100; j += 2) {
            if (cnt >= A - 1) break;
            c[i][j] = '.';
            cnt++;
        }
    }

    cout << 100 << " " << 100 << endl;
    for (int i = 0; i < 100; i++) {
        cout << c[i] << endl;
    }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second
 
int main(int argc, char **argv) {
	int n;
	cin >> n;
	cout << (n <= 999 ? "ABC" : "ABD") << endl;
	return 0;
}
 

Measured memory_bytes: 256
N,M,K = map(int,input().split())
#follow = [[False for i in range(N)] for j in range(N)]
follow = [[] for _ in range(N)]
labels = [-1 for _ in range(N)]
edges = [0 for _ in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    A = A-1
    B = B-1
    follow[A].append(B)
    follow[B].append(A)
    edges[A] = edges[A] + 1
    edges[B] = edges[B] + 1

c = 0
for i in range(N):
    if (labels[i] == -1):
        s = []
        s.append(i)
        labels[i] = c
        while(len(s) != 0):
            u = s.pop()
            for i in range(len(follow[u])):
                if (labels[follow[u][i]] == -1):
                    labels[follow[u][i]] = c
                    s.append(follow[u][i])
        c += 1

groupV = [0]*(c+1)
for i in range(N):
    groupV[labels[i]] = groupV[labels[i]] + 1

for i in range(K):
    C,D = map(int,input().split())
    C = C-1
    D = D-1
    if (labels[C] != labels[D]) : continue
    edges[C] = edges[C] + 1
    edges[D] = edges[D] + 1

ans = ["0"]*N

for i in range(N):
    ans[i] = str(groupV[labels[i]] - 1 - edges[i])

print(" ".join(ans))


Measured memory_bytes: 31744
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 300010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, K;
ll dp[110][100010];
int A[MAX_N];

void solve() {
	cin >> N >> K;
	rep(i, 0, N) cin >> A[i];

	dp[0][0] = 1;
	rep(i, 0, N) {
		// debug(vl(dp[i], dp[i] + K + 1));
		rep(j, 0, K + 1) {
			int r = min(K, j + A[i]);
			ADD(dp[i + 1][j], dp[i][j]);
			ADD(dp[i + 1][r + 1], mod - dp[i][j]);
		}
		rep(j, 0, K) {
			ADD(dp[i + 1][j + 1], dp[i + 1][j]);
		}
	}
	cout << dp[N][K] << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 80256
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	vector<int> a(3);
	for (int i = 0; i < 3; i++)
		cin >> a[i];

	sort(a.begin(), a.end());

	cout << a[0] + a[1] << endl;

	return 0;
}



Measured memory_bytes: 256