akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

/**
 * Created by Reopard on 2014/07/06.
 */
public class Main{
    static Scanner sc = new Scanner(System.in);
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static char[][] general;

    public static void main(String[] args){

        char[][] black_area, white_area;
        int w, h, black, white;
        while((w = sc.nextInt()) != 0 | (h = sc.nextInt()) != 0){
            general = new char[h][w];
            black_area = new char[h + 2][w + 2];
            white_area = new char[h + 2][w + 2];
            for(int i = 0; i < h; i++) general[i] = sc.next().toCharArray();
            initArea(black_area, 'B');
            initArea(white_area, 'W');
            black = findAreaStock(black_area, 'B', 'W');
            white = findAreaStock(white_area, 'W', 'B');
            System.out.println(black + " " + white);
        }
    }

    static void initArea(char[][] area, char side){
        for(int i = 0; i < area[0].length; i++) area[0][i] = side;
        for(int i = 1; i <= area.length - 2; i++){
            area[i][0] = side;
            for(int j = 0; j < general[i - 1].length; j++) area[i][j + 1] = general[i - 1][j];
            area[i][area[i].length - 1] = side;
        }
        for(int i = 0; i < area[area.length - 1].length; i++) area[area.length - 1][i] = side;
    }

    static int findAreaStock(char[][] area, char side, char ob){
        int temp = 0;
        char[][] check_area;
        for(int i = 1; i <= area.length - 2; i++){
            for(int j = 1; j <= area[i].length - 2; j++){
                if(area[i][j] == side){
                    for(int k = 0; k < 4; k++){
                        check_area = copyArea(area);
                        if(checkStock(check_area, side, ob, j + dx[k], i + dy[k])){
                            temp += calcArea(area, side, j + dx[k], i + dy[k]);
                        }
                    }
                }
            }
        }
        return temp;
    }

    static boolean checkStock(char[][] area, char side, char ob, int x, int y){
        boolean temp = true;
        if(area[y][x] == side || area[y][x] == '-') return true;
        else if(area[y][x] == ob)  return false;
        else if(area[y][x] == '.'){
            area[y][x] = '-';
            for(int i = 0; i < 4; i++) temp &= checkStock(area, side, ob, x + dx[i], y + dy[i]);
        }
        return temp;
    }

    static int calcArea(char[][] area, char side, int x, int y){
        int count = 0;
        if(area[y][x] == side){
            return 0;
        }else if(area[y][x] == '.'){
            area[y][x] = ' ';
            count++;
            for(int i = 0; i < 4; i++){
                count += calcArea(area, side, x + dx[i], y + dy[i]);
            }
        }
        return count;
    }

    static char[][] copyArea(char[][] copying){
        char[][] temp = new char[copying.length][copying[0].length];
        for(int i = 0; i < copying.length; i++){
            for(int j = 0; j < copying[i].length; j++){
                temp[i][j] = copying[i][j];
            }
        }
        return temp;

    }
}

Measured memory_bytes: 153028
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

ll a[100010];

int main(){
    int n;
    cin >> n;
    rep(i, n) cin >> a[i];

    bool flag = true;

    if (a[n-1] != 2) flag = false;

    ll mx = 3, mn = 2;

    rrep(i, n - 1){
        ll p = a[i];
        ll nmx = mx / p * p;
        ll nmn = (mn + p - 1) / p * p;
        // cout << nmx << " " << nmn << endl;
        if (nmn > mx || nmx < mn) {
            flag = false;
            break;
        }
        mx = nmx + p - 1;
        mn = nmn;
    }

    if (flag) cout << mn << " " << mx << endl;
    else cout << -1 << endl;

    return 0;
}


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

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


void solve(long long H){
    long long ans = 1;
    for (long long h = H; h >= 1; h = floor(h/2)) {
        ans *= 2;
    }
    cout << ans-1 << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long H;
    cin >> H;
    solve(H);
}


Measured memory_bytes: 256
from sys import stdin

N = int(stdin.readline().rstrip())
data = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
f = False
for i in range(N):
    for j in range(i):
        if data[j] > data[i]:
            f = True
    if not f:
        ans += 1
    f = False

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
/*-----------------------*/
#define FAST        ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define endl        "\n"
#define ff          first
#define ss          second
#define cc(x)       cout<<#x<<"="<<x<<" ";
#define CC(x)       for(auto xx: x) cout<<xx<<" ";
#define ee          cout<<"\n";
#define ll          long long
#define ull         unsigned long long
#define pii         pair<ll,ll>
#define mp          make_pair
#define all(x)      x.begin(),x.end()
#define ps(x)       push(x)
#define psb(x)      push_back(x)
#define psf(x)      push_front(x)
#define pp          pop()
#define ppb         pop_back()
#define ppf         pop_front()
#define OK          cout<<"Ok"<<"\n";
#define TESTS       ll test;cin>>test;for(ll   tcase=1;tcase<=test;tcase++)
/*------------------------*/
#define MAX int(1e5)
int dp[2][10000+9];
int value[1000+9],weight[1000+9];


int main()
{
    FAST
    int n,k;
    ll h;
    cin>>h;
    ll x=log2(h)+1ll;
    ll mul=1ll;
    ll s=0ll;
    for(int i=0;i<x;i++)
    {
        s+=mul;
        mul=mul*2ll;
    }
    cout<<s<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

using namespace std;


int main(){
	double a,b,c,d,e,f,x,y;

	while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)!=EOF){
		x=(c*e-b*f)/(a*e-d*b);
		y=(a*f-c*d)/(a*e-b*d);
		if(x == 0)x=0;
		if(y == 0)y=0;
		printf("%.3lf %.3lf\n",x,y);
	}

    return 0;
}

Measured memory_bytes: 2704
#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()
{
    ll n;
    ll k;
    cin >> n >> k;
    vl as(n);
    for(ll i=0; i<n; i++)
    {
        ll a;
        cin >> a;
        as.at(i) = a-1;
    }
    vl bs;
    ll cp = 0;
    vector<bool> np(n, false);
    while(!np.at(cp))
    {
        bs.push_back(cp);
        np.at(cp) = true;
        cp = as.at(cp);
    }
    
    auto itr = find(bs.begin(), bs.end(), cp);
    auto dist = distance(bs.begin(), itr);
    // for(auto b : bs)
    // {
    //     cout << b << endl;
    // }
    // cout << dist << endl;
    if(dist >= k) cout << bs.at(k) + 1 << endl;
    else
    {
        ll r = (k + 1 - dist + bs.size() - dist - 1) % (bs.size() - dist);
        cout << bs.at(dist + r) + 1 << endl;
    }
    
    return 0;
}


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

using namespace std;

using int64 = long long;
const int INF = 1 << 30;

int main()
{
  int A, B;
  string S;
  cin >> A >> B;
  cin >> S;
  for(int i = 0; i < S.size(); i++) {
    if(i != A) {
      if(!isdigit(S[i])) {
        cout << "No" << endl;
        return (0);
      }
    } else {
      if(S[i] != '-') {
        cout << "No" << endl;
        return (0);
      }
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int i, j, t, n, g, x[100000+1], d[100000];
int main(void) {
    cin >> t;
    for(i = 0; i < t; ++i){
        int sum = 0;
        cin >> n >> g;
        for(j = 0; j < n; ++j) {cin >> x[j];}
        for(j = 0; j+1< n; ++j) {d[j] = x[j+1]-x[j];}
        sort(d, d+n-1);
        for(j = 0; j < max(0,n-g);++j){sum += d[j];}
        cout << sum << endl;
    }
}


Measured memory_bytes: 3932
while True:
  n = int(input())
  if n == 0:break
  x = []
  for _ in range(n):
    lst = set(list(map(int, input().split()))[1:])
    x.append(lst)
  
  y = set(list(map(int, input().split()))[1:])
  
  ans = []
  for i, v in enumerate(x,start=1):
    if y - v == set():
      ans.append(i)
  
  if len(ans) == 1:
    print(ans[0])
  else:
    print(-1)


Measured memory_bytes: 6328
NONE = -1

class Node
	attr_accessor :p, :l, :r
	def initialize(p, l, r)
		@p = p; @l = l; @r = r
	end
end

$t = []

def preParse(u)
	return if u == NONE
	printf(" %d", u)
	preParse($t[u].l)
	preParse($t[u].r)
end

def inParse(u)
	return if u == NONE
	inParse($t[u].l)
	printf(" %d", u)
	inParse($t[u].r)
end

def postParse(u)
	return if u == NONE
	postParse($t[u].l)
	postParse($t[u].r)
	printf(" %d", u)
end

n = gets.to_i
0...n.times do |i|
	$t[i] = Node.new(NONE, NONE, NONE)
end
0...n.times do |i|
	v, l, r = gets.split.map &:to_i
	$t[v].l = l
	$t[v].r = r
	$t[l].p = v if l != NONE
	$t[r].p = v if r != NONE
end
root = 0
0...n.times do |i|
	root = i if $t[i].p == NONE
end

printf("Preorder\n")
preParse(root)
puts
printf("Inorder\n")
inParse(root)
puts
printf("Postorder\n")
postParse(root)
puts

Measured memory_bytes: 8668
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

const int N=1e5+5;
int n, vis[N], ans, cnt, x, y;
vector<int> pts[N], ony[N];
vector<int> adj[N];
set<int> ys;
void dfs(int u)
{
	vis[u]=1;
	cnt++;
	for(auto p: pts[u])
	{
		ys.insert(p);
	}
	for(auto v: adj[u])
	{
		if(!vis[v])
		{
			dfs(v);
		}
	}
}
signed main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cin >> x >> y;
		ony[y].pb(x);
		pts[x].pb(y);
	}
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < (int) ony[i].size()-1; j++)
		{
			adj[ony[i][j]].pb(ony[i][j+1]);
			adj[ony[i][j+1]].pb(ony[i][j]);
		}
	}
	for(int i = 0; i < N; i++)
	{
		if(!vis[i]) dfs(i);
		ans+=ys.size()*cnt;
		ys.clear();
		cnt=0;
	}
	cout << ans-n;
}

Measured memory_bytes: 17024
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	vector< pair<int,string> > sh(5);
	int s1,s2;
	string a[] = { "A" , "B" , "C" , "D" , "E"};
	REP(i,5){
	    cin >> s1 >> s2;
	    if(s1 == 0 && s2 == 0) break;
	    sh.PB( pair<int,string>(s1+s2, a[i] ));
	}
	if(s1 == 0 && s2 == 0) break;
	sort(RALL(sh));
	cout << sh[0].second << " " << sh[0].first << endl;
    }
    return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef pair<ll, ll> P;
struct edge{ll to,cost;};
const int inf = 1<<27;
const ll INF = 1LL<<60;
const int COMBMAX = 1001001;
const ll MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (ll)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (ll)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
ll mpow(ll a, ll n, ll mod = MOD){ll res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void YesNo(bool j){cout << (j ? "Yes" : "No") << endl; return;}
void yesno(bool j){cout << (j ? "yes" : "no") << endl; return;}
template<class T1, class T2> ll bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
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;}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}

int main(){
    ll N, P = 2019;
    string S; cin >> S;
    N = S.size();
    ll ans = 0;
    reverse(all(S));
    vector<ll> tb(P);
    vector<ll> dp(N + 1, 0);
    vector<ll> dp10(N + 1, 1);
    rep(i, N){
        dp10[i + 1] = (dp10[i] * 10) % P;
    }
    rep(i, N){
        dp[i + 1] = (dp[i] + dp10[i] * (S[i] - '0')) % P;
    }
    rep(i, N + 1){
        tb[dp[i]]++;
    }
    rep(i, P){
        ans += (tb[i] * (tb[i] - 1)) / 2;
    }
    // debug(dp);
    // debug(tb);
    // cout << accumulate(all(tb), 0LL) << endl;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6828
from collections import defaultdict
N, M = map(int, input().split())
D = defaultdict(int)
acd = set()
ac = 0
pen = 0
for i in range(M):
    p, S = input().split()
    p = int(p)
    if S == "WA":
        D[p] += 1
    else:
        if p not in acd:
            acd.add(p)
            ac += 1
            pen += D[p]
print(ac, pen)

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

#define N 100000

int main(void){
    ios::sync_with_stdio(false);
    vector<bool> prime(N+1,true);
    prime[0]=prime[1]=false;
    for (size_t i = 0; i <= sqrt(N); i++)
    {
        if (prime[i])
        {
            for (size_t j = 2; i*j <= N; j++)
            {
                prime[i*j]=false;
            }
        }
    }
    vector<int> likeCnt(N);
    for (size_t i = 1; i <= N; i++)
    {
        likeCnt[i]=likeCnt[i-1];
        if (i%2==1&&prime[i]&&prime[(i+1)/2])
        {
            likeCnt[i]++;
        }
    }
    /**************************************/
    int q;
    cin >> q;
    int l[q],r[q];
    for (size_t i = 0; i < q; i++)
    {
        cin >> l[i] >> r[i];
        cout << likeCnt[r[i]] - likeCnt[l[i]-1] << "\n";
    }
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    //*
    int a, b;
    cin >> a >> b ;
    //*/

    /*
    vector<int> vec(3);
    cin >> vec.at(0) >> vec.at(1) >> vec.at(2) ;

    sort(vec.begin(), vec.end());
    //*/
    
    //*
    if( a * 500 >= b ){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    //*/
    
    //cout << pow(a, 3) << endl;

    return 0; 
}


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

int h[6][6] = {
	{1,5,2,3,0,4},
	{3,1,0,5,4,2},
	{2,1,5,0,4,3},
	{4,0,2,3,5,1},
	{0,2,4,1,3,5},
	{0,3,1,4,2,5}
};

int s_to_i(string s){
	if( s == "North" ) return 0;
	if( s == "East" )  return 1;
	if( s == "West" )  return 2;
	if( s == "South" ) return 3;
	if( s == "Right" ) return 4;
	if( s == "Left" )  return 5;
	return -1;
}

void op(int dice[6], int dice_[6], string s){
	for(int i=0 ; i<6 ; i++ ){
		int j = s_to_i( s );
		dice_[i] = dice[ h[j][i] ];
	}
	for(int i=0 ; i<6 ; i++ ){
		dice[i] = dice_[i];
	}
}

int main(){
	int n;
	string s;
	
	while( cin >> n , n ){
		int dice[6] = {1,2,3,4,5,6};
		int dice_[6] = {0};
		int p=0;
		
		for(int i=0 ; i < n ; i++ ){
			cin >> s;
			op( dice , dice_ , s );
			p += dice[0];
		}
		cout << p+1 << endl;
	}
}

Measured memory_bytes: 0
D = gets.chomp.to_i
c = [0] + gets.chomp.split.map(&:to_i)
s = [0]
D.times{
  s.push ([0] + gets.chomp.split.map(&:to_i))
}

last_t = [0]
(1..26).each{
  last_t.push 0
}

score = 0

(1..D).each{ |d|
  scores = []
  (1..26).each{ |i|
    tmp_score = score
    tmp_score += s[d][i]
    (1..26).each{ |j|
      next if i == j
      tmp_score -= (c[j] * (d - last_t[j]))
    }
    if d < D
      d2 = d+1
      last_t2 = last_t.dup
      last_t2[i] = d
      scores2 = []
      (1..26).each{ |i2|
        scores2 = []
        tmp_score2 = tmp_score
        tmp_score2 += s[d2][i2]
        (1..26).each{ |j2|
          next if i2 == j2
          tmp_score2 -= (c[j2] * (d2 - last_t2[j2]))
        }
        scores2.push ([i2, tmp_score2])
      }
      tmp_score += scores2.sort{|a,b| a[1] <=> b[1]}[-1][1]
    end
    scores.push ([i, tmp_score])
  }
  i = scores.sort{|a,b| a[1] <=> b[1]}[-1][0]
  last_t[i] = d
  puts i
}


Measured memory_bytes: 14404
import fractions
N = int(input())
A = [int(i) for i in input().split()]

'''
'init(a)': 配列aで初期化。O(N)
'update(k,x)': a[k]をxに変更 O(logN)
'query(p,q)': [p,q)について "segfunc" したものを返す O(logN)
'ide_ele' : 単位元。
'''


def segfunc(x, y):
    return fractions.gcd(x, y)


def init(init_val):
    # set_val
    for i in range(N):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])


def update(k, x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1], seg[k*2+2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num-1
    q += num-2
    res = ide_ele
    while q-p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele = 0

# num:n以上の最小の2のべき乗
num = 2**(N-1).bit_length()
seg = [ide_ele]*2*num

init(A)

# print(query(0, 2))

ans = 1
for i in range(N):
    if i == 0:
        ans = max(ans, query(1, N))
    elif i == N-1:
        ans = max(ans, query(0, N-1))
    else:
        ans = max(ans, fractions.gcd(query(0, i), query(i+1, N)))
print(ans)


Measured memory_bytes: 96232
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
from itertools import accumulate,permutations, combinations,combinations_with_replacement,product


def resolve():
    N=int(input())
    P=tuple(map(int,input().split()))
    Q=tuple(map(int,input().split()))

    anslist=list(permutations(range(1,N+1)))
    print(abs(anslist.index(P)-anslist.index(Q)))







resolve()

Measured memory_bytes: 44656
from math import radians,cos

a,b,h,m = map(int,input().split())
j = 30*h+(0.5)*m
f = 6*m
k = abs(j-f) if abs(j-f) <= 180 else 360-abs(j-f)
print((a**2+b**2-2*a*b*cos(radians(k)))**(0.5))

Measured memory_bytes: 9512
import java.util.Scanner;

/**
 * @author kmori
 *
 */
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		doIt();

	}

	public static void doIt(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		while(n != 0){
			int[] seq = new int[n];
			for(int i = 0; i < n; i++){
				seq[i] = sc.nextInt();
			}
			//iから始まる列の最大値
			int[] max = new int[n];
			max[n - 1] = seq[n - 1];
			int m = max[n - 1];
			for(int i = n - 2; i >= 0; i--){
				max[i] = seq[i];
				if(max[i + 1] > 0){
					max[i] += max[i + 1];
				}
				if(max[i] > m){
					m = max[i];
				}
			}
			System.out.println(m);
			n = sc.nextInt();
		}
	}

}

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

int main()
{
    int n,k,q,a;
    cin >> n >> k >> q;
    vector<int> x(n+1,0);
    for(int i = 0 ; i < q ; i += 1){
        cin >> a;
        x[a-1] += 1;
    }
    for(int i = 0 ; i < n ; i += 1){
        if(k-(q-x[i]) > 0){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 1024
#include<iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;

int main(void) {
	char n[4];
	bool flag = true;
	cin >> n;
	
	if(n[0] == n[1] && n[1] == n[2] && n[2] == n[0])cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

const ll MOD = 1e9 + 7;

int main() {
  int N;
  while (cin >> N) {
    vec<int, 2> G(N);
    for (int i = 0; i < N - 1; i++) {
      int x, y;
      cin >> x >> y;
      --x;
      --y;
      G[x].push_back(y);
      G[y].push_back(x);
    }
    vector<ll> g(N + 1, 0);
    g[0] = 1;
    for (int i = 2; i <= N; i += 2) {
      g[i] = g[i - 2] * (i - 1) % MOD;
    }
    vec<ll, 3> mem(N);
    function<int(int, int)> dfs = [&](int v, int p) {
      int sz = 1;
      vec<ll, 2> cur = make_v(sz + 1, 2, 0ll);
      cur[1][0] = 1;
      for (int u : G[v]) {
        if (u == p) continue;
        int chsz = dfs(u, v);
        vec<ll, 2> nxt = make_v(sz + chsz + 1, 2, 0ll);
        auto& ch = mem[u];
        for (int i = 1; i <= sz; i++) {
          for (int ip = 0; ip < 2; ip++) {
            for (int j = 1; j <= chsz; j++) {
              for (int jp = 0; jp < 2; jp++) {
                // 繋げる
                (nxt[i + j][(ip + jp) % 2] += cur[i][ip] * ch[j][jp] % MOD) %=
                    MOD;
                // 繋げない
                (nxt[i][(ip + jp + 1) % 2] +=
                 cur[i][ip] * ch[j][jp] % MOD * g[j] % MOD) %= MOD;
              }
            }
          }
        }
        cur = nxt;
        sz += chsz;
      }
      mem[v] = cur;
      return sz;
    };
    dfs(0, -1);
    auto& dp = mem[0];
    ll res = 0;
    for (int i = 1; i <= N; i++) {
      for (int ip = 0; ip < 2; ip++) {
        ll ways = dp[i][ip] * g[i] % MOD;
        if (ip % 2 == 0) {
          res = (res + ways) % MOD;
        } else {
          res = (res - ways + MOD) % MOD;
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 480792
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    // a + 2 * sqrt(a * b) + b < c
    // a + b > c  or 4ab < (c - a - b)^2
    auto d = c - a - b;
    if (d >= 0 && 4 * a * b < d * d) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100
int main(){

  int i,j,num;
  int minj,count=0;
  int A[N],tmp;

  scanf("%d",&num);
  
  for(i=0;i<num;i++){
    scanf("%d",&A[i]);
  }

 
  for(i=0;i<num;i++){
    minj=i;
    for(j=i;j<num;j++){
      if(A[j]<A[minj]){
	minj=j;
      }
    }
    if(A[i]!=A[minj]){
      count++;
    }
    tmp=A[minj];
    A[minj]=A[i];
    A[i]=tmp;
     
  }


for(i=0;i<num-1;i++){
  printf("%d ",A[i]);
 }
printf("%d\n",A[num-1]);
printf("%d\n",count);



return 0;
}



Measured memory_bytes: 2076
#include<bits/stdc++.h>
using namespace std;
int main(){
  map<char,bool>str;
  string mstr="abcdefghijklmnopqrstuvwxyz";
  for(int i=0;i<26;i++){
    str[(char)mstr[i]]=true;
  }
  string s;
  cin>>s;
  for(int i=0;i<s.size();i++){
    str[(char)s[i]]=false;
  }
  for(int i=0;i<26;i++){
    if(str[(char)mstr[i]]==true){
      cout<<mstr[i]<<endl;
      return 0;
    }
  }
  cout<<"None"<<endl;
  return 0;
}


Measured memory_bytes: 512
a, b, k = map(int, input().split())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

a_y = set(make_divisors(a))
b_y = set(make_divisors(b))
#print(a_y & b_y)
y = list(a_y & b_y)
y.sort(reverse=True)
print(y[k-1])



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

int n,c,a[31],b[31],dp[31][1<<16];

void solve(){
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;
	
	for(int i=0;i<n;i++){
		for(int j=0;j<(1<<16);j++){
			if(dp[i][j]<0)continue;
			int nj=(j|a[i]);
			for(int k=0;k<c;k++){
				int cal=(nj&b[k]);
				int pop=__builtin_popcount(cal);
				dp[i+1][nj-cal]=max(dp[i+1][nj-cal],dp[i][j]+pop);
			}
		}
	}
	
	int ans=0;
	for(int i=0;i<(1<<16);i++)ans=max(ans,dp[n][i]);
	cout<<ans<<endl;
}

int main(){
	while(cin>>n>>c,n){
		for(int i=0;i<n;i++){
			a[i]=0;
			for(int j=0;j<16;j++){
				int x;cin>>x;
				a[i]=(a[i]<<1)+x;
			}
		}
		for(int i=0;i<c;i++){
			b[i]=0;
			for(int j=0;j<16;j++){
				int x;cin>>x;
				b[i]=(b[i]<<1)+x;
			}
		}
		solve();
	}
	return 0;
}


Measured memory_bytes: 9112
//By Vlgd
#include<bits/stdc++.h>
#define EPS (1e-10)
#define equals(a,b) fabs((a)-(b))<EPS
using namespace std;
class Point{
public:
	double x,y;
	Point(double x=0,double y=0):x(x),y(y){}
	Point operator +(Point p){return Point(x+p.x,y+p.y);}
	Point operator -(Point p){return Point(x-p.x,y-p.y);}
	Point operator *(double a){return Point(a*x,a*y);}
	Point operator /(double a){return Point(x/a,y/a);}
	double norm(){return x*x+y*y;}
	double abs(){return sqrt(norm());}
	bool operator <(const Point &p){
		return x!=p.x?x<p.x:y<p.y;
	}
	bool operator ==(const Point &p){
		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
	}
};
class Circle{
public:
	Point c;
	double r;
	Circle(Point c=Point(),double r=0):c(c),r(r){}
};
typedef Point Vector;
struct Segment{Point p1,p2;};
typedef Segment Line;
Vector con(double r,double a){return Point(cos(r)*a,sin(r)*a);}
pair<Point,Point>CP(Circle c1,Circle c2){
	Vector p12=c2.c-c1.c;
	double dis=p12.abs();
	double alpha=acos((c1.r*c1.r+dis*dis-c2.r*c2.r)/(2*c1.r*dis));
	double beta=atan2(p12.y,p12.x);
	return make_pair(c1.c+con(beta+alpha,c1.r),c1.c+con(beta-alpha,c1.r));
}
main(){
	int cx,cy,r;
	scanf("%d%d%d",&cx,&cy,&r);
	Point p1(cx,cy);
	Circle c1(p1,r);
	scanf("%d%d%d",&cx,&cy,&r);
	Point p2(cx,cy);
	Circle c2(p2,r);
	pair<Point,Point>ans=CP(c1,c2);
	Point x1=ans.first,x2=ans.second;
	if(x2<x1) swap(x1,x2);
	printf("%.8lf %.8lf %.8lf %.8lf\n",x1.x,x1.y, x2.x,x2.y);
}   	


Measured memory_bytes: 3600
#include <stdio.h>
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
  int n, ans = 0, i;
  rep(i, 3) {
    scanf("%d", &n);
    ans += n;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 2688
using System;
using System.Linq;

class B
{
	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		var h = read();
		var l = read();

		var d = new int[h[0] + 1];
		for (int i = 0; i < h[0]; i++) d[i + 1] = d[i] + l[i];
		Console.WriteLine(d.TakeWhile(v => v <= h[1]).Count());
	}
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)
#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)
#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const int n_max = 1e5+10;

ll h, w;
ll h_max = 410, w_max = 410;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
vector<vector<ll>> is_moved(h_max, vector<ll>(w_max, 0));
vector<ll> cnt(2, 0);
void dfs(vector<string> &s, ll x, ll y){
    is_moved[x][y] = 1;
    if(s[x][y] == '.')cnt[0]++;
    else cnt[1]++;
    rep(i,4){
        ll nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || h <= nx)continue;
        if(ny < 0 || w <= ny)continue;
        if(is_moved[nx][ny])continue;
        if(s[nx][ny] == s[x][y])continue;
        dfs(s, nx, ny);
    }
}

int main(){
    cin >> h >> w;
    vector<string> s(h);
    rep(i,h)cin >> s[i];

    ll ans = 0;

    rep(i,h)rep(j,w){
        if(is_moved[i][j])continue;
        if(s[i][j] == '.')continue;
        fill(all(cnt), 0);
        dfs(s, i, j);
        ans += cnt[0] * cnt[1];

        // debug(i);debug(j);debug(ans);
    }

    cout << ans << endl;
}

Measured memory_bytes: 16768
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
using namespace std;



int main() {
	//cout << fixed << setprecision(10);
	
	
	long long int n, m=1, a[100][100] = {}, b[100005], c, d, k, cou = 0, one = 0, zero = 0,in;
	string str;
	cin >> str;
	n = str.length();
	while (m < n) {
		if (str[m] != str[m - 1]) {
			cou++;
		}

		m++;
	}
	cout << cou;
}


Measured memory_bytes: 512
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

G = []
i,j = 1,1
while i < 201:
    j = 1
    g0 = []
    while j < 201:
        g0.append(gcd(i,j))
        j += 1
    g0 = tuple(g0)
    G.append(g0)
    i += 1
n = int(input())
i = 1
j = 1
k = 1
ans = 0
while i < n+1:
    j = 1
    while j < n+1:
        k = 1
        p = G[i-1][j-1]
        while k < n+1:
            ans += G[k-1][p-1]
            k += 1
        j += 1
    i += 1
print(ans)

Measured memory_bytes: 9540
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        int[] a = new int[6];

        for(int i = 0; i < s.length; i++){
            a[i] = Integer.parseInt(s[i]);    
        }

        Dice dice = new Dice(a);

        int num = Integer.parseInt(br.readLine());

        for(int i = 0; i < num; i++){
            String[] input = br.readLine().split(" ");
            int top = Integer.parseInt(input[0]);
            int front = Integer.parseInt(input[1]);
            dice.setTop(top);
            dice.setFront(front);
            System.out.println(dice.RIGHT);
        }
        
    }
}

class Dice{
    int TOP,BOTTOM,LEFT,RIGHT,FRONT,BACK;

    Dice(int[] a){
        this.TOP = a[0];
        this.FRONT = a[1];
        this.RIGHT = a[2];
        this.LEFT = a[3];
        this.BACK = a[4];
        this.BOTTOM = a[5];
    }

    void setTop(int top){
        if(this.FRONT == top)           this.turnN();
        else if(this.RIGHT == top)      this.turnW();
        else if(this.LEFT == top)       this.turnE();
        else if(this.BACK == top)       this.turnS();
        else if(this.BOTTOM == top)    {this.turnN(); this.turnN();}
    }

    void setFront(int front){
        if(this.RIGHT == front)         this.turnL();
        else if(this.LEFT == front)     this.turnR();
        else if(this.BACK == front)    {this.turnR(); this.turnR();}
    }

    void turnS(){
        int tmp = this.TOP;
        this.TOP = this.BACK;
        this.BACK = this.BOTTOM;
        this.BOTTOM = this.FRONT;
        this.FRONT = tmp;
    }

    void turnN(){
        int tmp = this.TOP;
        this.TOP = this.FRONT;
        this.FRONT = this.BOTTOM;
        this.BOTTOM = this.BACK;
        this.BACK = tmp;
    }

    void turnW(){
        int tmp = this.TOP;
        this.TOP = this.RIGHT;
        this.RIGHT = this.BOTTOM;
        this.BOTTOM = this.LEFT;
        this.LEFT = tmp;
    }

    void turnE(){
        int tmp = this.TOP;
        this.TOP = this.LEFT;
        this.LEFT = this.BOTTOM;
        this.BOTTOM = this.RIGHT;
        this.RIGHT = tmp;
    }

    void turnL(){
        int tmp = this.FRONT;
        this.FRONT = this.RIGHT;
        this.RIGHT = this.BACK;
        this.BACK = this.LEFT;
        this.LEFT = tmp;
    }

    void turnR(){
        int tmp = this.FRONT;
        this.FRONT = this.LEFT;
        this.LEFT = this.BACK;
        this.BACK = this.RIGHT;
        this.RIGHT = tmp;
    }

}



Measured memory_bytes: 24276
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception{
		new Main(new Scanner(System.in), System.out, System.err).exec();
	}
	private final Scanner sc;
	private final PrintStream out, err;
	public Main(final Scanner sc, final PrintStream out, final PrintStream err) {
		this.sc = sc;
		this.out = out;
		this.err = err;
	}

	public void exec() throws Exception{
		final int N = sc.nextInt();
		final int[] L = new int[N];
		for(int i=0;i<N;i++) {
			L[i] = sc.nextInt();
		}
		int sum = 0;
		Arrays.sort(L);
		for(int a=0;a<N-2;a++) {
			for(int b=a+1;b<N-1;b++) {
				int ab = L[a]+L[b];
				for(int c=b+1;c<N;c++) {
					if(L[c]<ab) {
						sum++;
					}else {
						break;
					}
				}
			}
		}
		out.println(sum);
	}
}


Measured memory_bytes: 26380
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i = (int)(begin); i < (int)(end); i++)
#define rep(i, n) FOR(i, 0, n)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using namespace std;


int main(int argc, char const *argv[])
{
    unsigned N, M;
    cin >> N >> M;
    vector<int> ss(M);
    vector<int> cs(M);
    vector<int> num(N, -1);
    rep(i, M) {
        int s, c;
        cin >> s >> c;
        ss[i] = s;
        cs[i] = c;
    }
    // if(M == 0) {
    //     cout << static_cast<int>(pow(10, N-1)) << endl;
    //     return 0;
    // }
    rep(i, M) {
        int s = ss[i] - 1;
        int c = cs[i];
        if(num[s] == -1) {
            num[s] = c;
        } else if (num[s] != c) {
            cout << -1 << endl;
            return 0;
        } else {
            // Do nothing
        }
    }
    int ans = 0;
    if (N == 1 && num[0] <= 0) {
        cout << 0 << endl;
        return 0;
    }
    rep(j, N) {
        ans *= 10;
        if(j == 0) {
            if(num[j] == 0) {
                cout << -1 << endl;
                return 0;
            }
            if (num[j] == -1) {
                num[j] = 1;
            }
        } else if(num[j] == -1) {
            num[j] = 0;
        }
        ans += num[j];
    }
    cout << ans << endl;
    return 0;
}


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

typedef struct{
    long long B;
    long long C;
} Data;

int main(){
    long long N,M;
    long long sum1 = 0,answer = 0;
    int i,j;

    cin >> N >> M;

    vector<Data> data(M);
    vector<long long> A(N);

    for(i = 0; i < N; i++){
        cin >> A[i];
        sum1 += A[i];
    }

    for(j = 0; j < M; j++){
        cin >> data[j].B >> data[j].C;
    }

    sort(A.begin(), A.end());
    sort(data.begin(), data.end(), [](const Data &a, const Data &b){
        return a.C > b.C;
    });

    i = 0;//A
    j = 0;//data列
    int start = 0;

    for(j = 0; j < M; j++) {
        while ((A[i] < data[j].C)&&((i- start) < data[j].B)&&(i < N)){
            answer += data[j].C - A[i];
            i++;
        }
        start = i;
    }

    cout << sum1 + answer;

    return 0;
}

Measured memory_bytes: 2560
let () = Scanf.scanf " %s %s" @@ fun s t ->
  Printf.printf "%d\n" @@
  Array.fold_left min max_int @@
  Array.init (String.length s - String.length t + 1) @@ fun i ->
    Array.fold_left ( + ) 0 @@
    Array.init (String.length t) @@ fun j -> if s.[i + j] = t.[j] then 0 else 1

Measured memory_bytes: 5780
#include<bits/stdc++.h>
using namespace std;
typedef struct{
  int left;
  int right;
  int check;
}Player;
Player num[200005];
int n,m,q;
void lists(int x);
main(){
  cin>>n>>m>>q;
  int a;
  int out=0;
  num[0].right=1;
  num[0].left=n-1;
  num[0].check=1;
  for(int i=1;i<n-1;i++){
    num[i].left=i-1;
    num[i].right=i+1;
    num[i].check=1;
  }
  num[n-1].left=n-2;
  num[n-1].right=0;
  num[n-1].check=1;
  for(int i=0;i<m;i++){
    cin>>a;
    if(a%2==0){
      for(int j=0;j<a;j++){
	out=num[out].right;
      }
    }
    else{
      for(int j=0;j<a;j++){
	out=num[out].left;
      }
    }
    num[out].check=0;
    lists(out);
    out=num[out].right;
  }
  for(int i=0;i<q;i++){
    cin>>a;
    cout<<num[a].check<<endl;
  }
}
void lists(int x){
  num[num[x].left].right=num[x].right;
  num[num[x].right].left=num[x].left;
}

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

using namespace std;

const int INF = 1e9 + 3;
const int N = 2e5 + 3;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;

const double PI = acos(-1);



void solve() {
    int d, t, s;
    cin >> d >> t >> s;
    if (s * t >= d)
        cout << "Yes";
    else
        cout << "No";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    t = 1;
    while (t--) {
        solve();
    }
}

Measured memory_bytes: 3636
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int w=sc.nextInt();
    int[] val=new int[n];
    int[] weights=new int[n];
    for(int i=0;i<n;i++)
    {
      weights[i]=sc.nextInt();
      val[i]=sc.nextInt();
      
    }
    long[][] dp=new long[n+1][w+1];
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=w;j++)
      {
        if(j>=weights[i-1])
        {
          dp[i][j]=Math.max(dp[i-1][j],val[i-1]+dp[i-1][j-weights[i-1]]);
        }
        else
          dp[i][j]=dp[i-1][j];
      }
    }
    System.out.println(dp[n][w]);
  }
}
    

Measured memory_bytes: 125516
n = int(input())
lst = list(map(int, input().split()))


MOD = 10 ** 9 + 7

rev = []

i = 0
for _ in range(n)[::-1]:
    i += lst[_]
    i %=  MOD
    rev.append(i)
    
lst= lst[0:n-1]
rev = rev[0:n-1]

ans = 0
for _ in range(n-1):
    ans += lst[_] * rev[n-(_+2)]
    ans %= MOD
    
print(ans)

Measured memory_bytes: 31484
#include <bits/stdc++.h>
using namespace std;
 
 int main(){
   int a,b,c,d;
   cin >> a >> b >> c >>d;
   if (a+b<c+d){
     cout << "Right" << endl;
   }
   else if (a+b>c+d){
     cout << "Left" << endl;
   }
   else {
     cout << "Balanced" << endl;
   }
 }
  

Measured memory_bytes: 256
import statistics
from collections import Counter
N = int(input())
A = [list(map(int, input().split(" "))) for i in range(N)]
xMIN = []
xMAX = []



for i in range(N):
    xMIN.append(A[i][0])

for j in range(N):
    xMAX.append(A[j][1])


if N % 2 != 0:
    medianMIN = statistics.median(xMIN)
    medianMAX = statistics.median(xMAX)
    print(int(medianMAX-medianMIN+1))
else:
    medianMIN_LOW = statistics.median_low(xMIN)
    medianMIN_HIGH = statistics.median_high(xMIN)
    medianMAX_LOW = statistics.median_low(xMAX)
    medianMAX_HIGH = statistics.median_high(xMAX)
    print((medianMAX_LOW+medianMAX_HIGH)-(medianMIN_LOW+medianMIN_HIGH)+1)


Measured memory_bytes: 52580
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

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

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


int main(){
	
	int n;
	cin>>n;
	vector<vector<int> > comp(n,vector<int>(n));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>comp[i][j];
		}
	}
	vector<long long> dp(1<<n);
	dp[0]=1;
	int count=0;
//	for(int m=0;m<n;m++){
		for(int i=0;i<(1<<(n));i++){
			int m = __builtin_popcount(i);
			for(int w=0;w<n;w++){
				if((i&(1<<w))==0 && comp[m][w]==1){
					int j= (i|(1<<w));
					dp[j]+=dp[i];
					dp[j]%=1000000007;
				}
				
			}
		}
//	}
	
	cout<<dp[(1<<n)-1]%1000000007;
	
}

Measured memory_bytes: 19596
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int main() {
	int t,n;
	cin>>t;
	int i;
	for(i=0;i<t;i++){
		cin>>n;
		int j;
		int maxa=0,maxb=0;
		int pr=in();
		for(j=1;j<n;j++){
			int nw=in();
			if(pr<nw)chmax(maxa,nw-pr);
			else chmax(maxb,-nw+pr);
			pr=nw;
		}
		cout<<maxa<<" "<<maxb<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
S=input()
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]=(dp[i+1][(10*k+j)%13]+dp[i][k])%MOD
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]=(dp[i+1][(10*k+a)%13]+dp[i][k])%MOD
print(dp[len(S)][5]%MOD)

Measured memory_bytes: 61916
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

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

    cout << ((a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) ? "Possible" : "Impossible") << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long[] A = new long[N];
		for(int i = 0; i < N; i++) A[i] = sc.nextInt();
		Arrays.sort(A);

		int small = 0, big = N - 1;
		long ans1 = 0, ans2 = 0;
		// a1 > a2 < a3 > a4 ...
		for(int i = 1; i < N - 1; i++) {
			if(i % 2 == 1) {
				ans1 -= 2 * A[small];
				small++;
			}else {
				ans1 += 2 * A[big];
				big--;
			}
		}
		ans1 += A[big] + ((N % 2 == 0) ? -A[small] : A[small]);

		// a1 < a2 > a3 < a4 ...
		small = 0; big = N - 1;
		for(int i = 1; i < N - 1; i++) {
			if(i % 2 == 0) {
				ans2 -= 2 * A[small];
				small++;
			}else {
				ans2 += 2 * A[big];
				big--;
			}
		}
		ans2 += -A[small] + ((N % 2 == 0) ? A[big] : -A[big]);

		System.out.println(Math.max(ans1, ans2));
	}
}

Measured memory_bytes: 60596
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>

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

using namespace std;
using ll = long long;
using ull = unsigned long long;

ll func(ll A, ll B, ll x) {
    // return (A * x) / B - A * (x / B);
    return A * (x % B) / B;
}

int main() {
    ll A; cin >> A;
    ll B; cin >> B;
    ll N; cin >> N;

    ll ans;
    if (N < B - 1) {
        ans =  func(A, B, N);
    } else {
        ans =  func(A, B, B - 1);
    }

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


Measured memory_bytes: 3632
//Littleboy123 Template 1.7
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

//pragmas

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")t
// #pragma GCC optimization ("unroll-loops")


typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef unsigned long long int ull;
typedef long double ld;
typedef unsigned long long ull;

const long double pi = acos(-1.0);

#define FOR(a,b,c) for(int (a)=(b);(a)<(c);++(a))
#define FORE(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define FORN(a,b,c) for(int (a)=(b);(a)>(c);--(a))
#define FORNE(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define TC(n) cout << "Case #" << (n) << ": "
#define DEBUG(x) cout << "DEBUG " << #x << ' ' << x << '\n';
#define MEM(a,b) memset((a), (b), sizeof((a)))
#define MAX(a,b) (a) = max((a), (b))
#define MIN(a,b) (a) = min((a), (b))
#define nl '\n'
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>

void init(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void infile(){
    freopen("walk.in", "r", stdin);
}

void outfile(){
    freopen("output.txt", "w", stdout);
}

ll modex(ll a, ll b, ll mod){
    if(b == 0)
        return 1;
    if(b == 1)
        return a;
    ll tmp = modex(a, b/2LL, mod);
    tmp = (tmp * tmp) % mod;
    if(b & 1LL)
        tmp = (tmp * a) % mod;
    return tmp;
}

ll ex(ll a, ll b){
    if(b == 0)
        return 1;
    if(b == 1)
        return a;
    ll tmp = ex(a, b/2LL);
    tmp = (tmp * tmp);
    if(b & 1LL)
        tmp = (tmp * a);
    return tmp;
}

//End of template

int main(){
    init();

    string s;
    cin >> s;
    if(s[s.length()-1] == 's'){
        cout << s << "es\n";
    }
    else{
        cout << s << "s\n";
    }
    return 0;
}


Measured memory_bytes: 3660
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
d = IL()

d.sort()

P(d[N//2]-d[N//2-1])

Measured memory_bytes: 52512