akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

class Dijkstra {
  using QItem = pair<int, int>;

 public:
  vector<int> minDistance(vector<array<int, 3>> edges, int n, int src) {
    vector<int> costs(n, -1);
    costs[src] = 0;

    // 各ノードの隣接ノードとその距離を初期化
    vector<map<int, int>> distances(n);
    for (auto &edge : edges) {
      int n1 = edge[0], n2 = edge[1], d = edge[2];
      distances[n1][n2] = d;
      distances[n2][n1] = d;
    }

    vector<bool> used(n, false);
    priority_queue<QItem, vector<QItem>, greater<QItem>> q;
    q.push({0, src});

    while (!q.empty()) {
      // 未確定で，コストの一番低いノードを選択する
      auto [min_cost, min_idx] = q.top();
      q.pop();

      // 選択したノードは確定とする
      used[min_idx] = true;

      // 選択したノードの隣接ノードについて，そのコストを再計算する
      auto dist = distances[min_idx];
      for (auto p : dist) {
        int new_cost = min_cost + p.second;
        if (costs[p.first] < 0 || costs[p.first] > new_cost) {
          costs[p.first] = new_cost;
          q.push({new_cost, p.first});
        }
      }
    }

    return costs;
  }
};

int main(int argc, const char *argv[]) {
  int h, w, ch, cw, dh, dw;
  cin >> h >> w >> ch >> cw >> dh >> dw;
  ch--, cw--, dh--, dw--;
  vector<string> maze(h);
  for (int i = 0; i < h; ++i) {
    cin >> maze[i];
  }

  vector<array<int, 3>> edges;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (maze[i][j] == '#') {
        continue;
      }

      int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
      int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
      for (int i2 = min_y; i2 <= max_y; ++i2) {
        for (int j2 = min_x; j2 <= max_x; ++j2) {
          if (i2 == i && j2 == j) {
            continue;
          }

          if (maze[i2][j2] == '#') {
            continue;
          }

          int dist = abs(i2 - i) + abs(j2 - j);
          int cost = dist <= 1 ? 0 : 1;
          // cout << i << ' ' << j << ' ' << i2 << ' ' << j2 << ' ' << cost
          // << '\n';
          edges.push_back({i * w + j, i2 * w + j2, cost});
          edges.push_back({i2 * w + j2, i * w + j, cost});
        }
      }
    }
  }

  Dijkstra d;
  vector<int> min_dists = d.minDistance(edges, h * w, ch * w + cw);
  int ans = min_dists[dh * w + dw];
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 615928
S = input()
addition = 0
for i in range(2 ** (len(S)-1)):
    a = ''.join([c + ('+' if j < len(S)-1 and (i & 2 ** j == 2 ** j) else '') for j, c in enumerate(S)])
    for k in a.split('+'):
        addition += int(k)
print(addition)

Measured memory_bytes: 3060
n = int(input())
s = [input() for _ in range(n)]
az = "abcdefghijklmnopqrstuvwxyz"
counts = {}

for v in az:
    counts[v] = 10**9
    for i in range(n):
        counts[v] = min(counts[v], s[i].count(v))

ans = ""
for k, v in sorted(counts.items()):
    ans += k*v
print(ans)


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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cout.precision(15);
    cout << fixed;
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<pair<int, int> > > g(n);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int x, y;
            cin >> x >> y;
            x--;
            g[i].push_back({x,y});
        }
    }

    int ans = 0;
    for (int msk = 0; msk < (1<<n); msk++) {
        bool ok = true;
        for (int i = 0; i < n; i++) {
            if ((msk >> i) & 1) {
                for (auto p : g[i]) {
                    int x = p.first;
                    int y = p.second;
                    if (((msk>>x)&1) != y) {
                        ok = false;
                    }
                }
            }
        }
        if (ok) {
            int cnt = __builtin_popcount(msk);
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
use strict;
use warnings;

my ($num, $tmp, @button);
my ($n, $r) = (1, 0);

while(<>){
	chomp;
	if($. == 1){
		$num = $_;
	}
	else{
		$button[$. - 1] = $_;
	}
}

while(1){
	if($button[$n] == 0){
		$r = -1;
		last;
	}
	elsif($button[$n] == 2){
		$r++;
		last;
	}
	else{
		$tmp = $button[$n];
		$button[$n] = 0;
		$n = $tmp;
		$r++;
	}
}

print $r;


Measured memory_bytes: 11008
"""
author : halo2halo
date : 15, Jan, 2020
"""

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M, C = map(int, readline().split())
B = np.array(readline().split(), dtype=np.int64)
A = [np.array(readline().split(), dtype=np.int64) for _ in range(N)]

A = A * B
ans = 0
for i in A:
    if sum(i) + C > 0:
        ans += 1
print(ans)


Measured memory_bytes: 12480
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <string>
#include <iostream>
#include <stack>
#include <tuple>
#include <map>
#include <cassert>

using namespace std;
typedef long long ll;

struct mint{
    static const long long MOD = 1000000007;

    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const{
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const {
        return mint(v) -= a;
    }

    mint pow(long long k) const {
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv(){return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

int main(){
    ll n, k;
    cin >> n >> k;
    if(k == 1){
        cout << n << endl;
        return 0;
    }
    for(int i = 0; i < k; ++i){
        if(i == 0){
            cout << n - k + 1 << endl;
            continue;
        }else if(i == k - 1 && ((n + 1) >= 2*k)){
            cout << mint::comb(n - k + 1, k).v << endl;
        }else if(i < k - 1 && (n - k + 1 >= i + 1)){
            mint tmp = mint::comb(k - 1, i);
            mint tmp2 = mint::comb(n - k - 1, i) * 2 
                + mint::comb(n - k - 1, i + 1) + mint::comb(n - k - 1, i - 1);
            ll ans = (tmp * tmp2).v;
            cout << ans << endl;
        }else{
            cout << 0 << endl;
        }
    }
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    set<char> s;
    rep(i, n) {
        char ss;
        cin >> ss;
        s.insert(ss);
    }
    if(s.size() == 3){
        cout << "Three" << endl;
    }
    else {
        cout << "Four" << endl;
    }


    // cout << "Hello, World" << endl;
}

Measured memory_bytes: 256
fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let t = (s.next().unwrap().parse::<i64>().unwrap(), s.next().unwrap().parse::<i64>().unwrap());
	let a = (s.next().unwrap().parse::<i64>().unwrap(), s.next().unwrap().parse::<i64>().unwrap());
	let b = (s.next().unwrap().parse::<i64>().unwrap(), s.next().unwrap().parse::<i64>().unwrap());
	let alen = a.0 * t.0 + a.1 * t.1;
	let blen = b.0 * t.0 + b.1 * t.1;
	if alen == blen {
		println!("infinity");
	} else {
		let (a, b) = if alen < blen {
			(b, a)
		} else {
			(a, b)
		};
		let ans = if a.0 > b.0 {
			0
		} else {
			let dif = (alen - blen).abs();
			let r = b.0 - a.0;
			2 * ((t.0 * r + dif - 1) / dif) + if t.0 * r % dif == 0 { 1 } else { 0 } - 1
		};
		println!("{}", ans);
	}
}

Measured memory_bytes: 4352
/************************* C *****************/
#include <iostream>
using namespace std;

int main()
{
	int N = 0, A = 0;
	cin >> N >> A;
	int x[N];
	for(int i = 0; i < N; i++){
		cin >> x[i];
	}
	long long dp[N + 1][N + 1][50 * N + 1];
	for(int j = 0; j < N + 1; j++){
		for(int k = 0; k < N + 1; k++){
			for(int s = 0; s < 50 * N + 1; s++){
				dp[j][k][s] = 0;
			}
		}
	}
	dp[0][0][0] = 1;
	for(int j = 1; j < N + 1; j++){ /* how many available cards */
		for(int k = 0; k < N + 1; k++){ /* how many cards to choose */
			for(int s = 0; s < 50 * N + 1; s++){ /* goal sum */
				if(x[j - 1] > s){
					dp[j][k][s] = dp[j-1][k][s];
				}else if(x[j - 1] <= s && k >= 1){
					dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]];
				}
			}
		}
	}
	long long ans = 0;
	for(int k = 1; k < N + 1; k++){
		ans += dp[N][k][A * k];
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 51072
import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	int N;
	int[] memo;

	Main(BufferedReader in) throws IOException {
		N = Integer.parseInt(in.readLine());
		memo = new int[N + 1];
		Arrays.fill(memo, 0);
	}

	void calc() {
		for (int i = 1; i <= N; ++i) {
			for (int j = i; j <= N; j += i) {
				memo[j]++;
			}
		}
		long count = 0;
		for (int i = 1; i <= N; ++i) {
			count += (long) i * (long) memo[i];
		}
		System.out.println(count);
	}

	void showResult() {
	}
}

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

using namespace std;

#define SORT(c) sort((c).begin(),(c).end())
#define ANS(ans) cout<<(ans)<<endl;
typedef vector<int> VI;


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



int main() {
	VI v(3);

	REP(i, 3) {
		cin >> v[i];
	}

	SORT(v);
	
	ANS(v[2] * 10 + v[1] + v[0]);





	return 0;
}



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

int main(){
  int N,tmp,c;
  vector<int> d;

  cin >> N;
  d = vector<int>(N, 0);
  for (int i = 0; i < N; i++) {
    cin >> d[i];
  }
  sort(d.begin(), d.end());

  tmp = d[0];
  c = 1;
  for (int i = 1; i < N; i++)
  {
    if(tmp != d[i]){
      c++;
      tmp = d[i];
    }
  }
  cout << c;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, t, ans = 0;
    cin >> n >> t;
    int tarr[n];
    for (int i = 0; i < n; i++)
    {
        cin >> tarr[i];
    }
    ans += t;
    for (int i = 1; i < n; i++)
    {
        ans += (t > tarr[i] - tarr[i - 1] ? tarr[i] - tarr[i - 1] : t);
    }

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

Measured memory_bytes: 1024
#include <iostream>
#include<string.h>
#include<algorithm>
#include<math.h>

using namespace std;

int main() {
	int N;
	cin >> N;
	int a[110];
	
	for (int i = 0; i < N; ++i)  a[i]=i+1;

	int c = 0;
	int c_MAX = -1;
	int a_MAX=-1;
	for (int i = 0; i < N; ++i) {

		while (true) {
			if (a[i] % 2 != 0)break;
			else a[i] = a[i] / 2;
			c = c + 1;
		}
		if (c > c_MAX) {
			c_MAX = c;
		}

		c = 0;
	}
	cout << pow(2,c_MAX) << endl;
	return 0;
}

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

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

bool check_p(ll k, ll mid, vector<ll> &b, vector<ll> &c){
    ll cnt = 0;
    ll r = 0, l = b.size() - 1;
    for(r = 0; r < l; r++){
        while(l > r && b[r] * b[l] > mid){l--;}
        if(l < 0){
            break;
        }
        cnt += l - r;
    }
    r = 0, l = c.size() - 1;
    for(r = 0; r < l; r++){
        while(l > r && c[r] * c[l] > mid){l--;}
        if(l < 0){
            break;
        }
        cnt += l - r;
    }
    return k <= cnt;
}

bool check_m(ll k, ll mid, vector<ll> &b, vector<ll> &c){
    ll cnt = 0;
    ll r = 0, l = c.size() - 1;
    for(r = 0; r < b.size(); r++){
        while(l >= 0 && b[r] * c[l] > mid){l--;}
        if(l < 0){
            break;
        }
        cnt += l + 1;
    }
    return k <= cnt;
}

int main(){
    ll n, k, ans = 0;
    cin >> n >> k;
    vector<ll> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(begin(a), end(a));
    vector<ll> b, c;
    ll cm = 0, cz = 0, cp = 0;
    for(int i = 0; i < n; i++){
        if(a[i] < 0){
            cm++;
            b.push_back(a[i]);
        }else if(a[i] == 0){
            cz++;
        }else{
            cp++;
            c.push_back(a[i]);
        }
    }
    ll m = k;
    m -= cm * cp;
    bool f;
    if(m <= 0){
        f = false;
    }else{
        m -= cz * (n - cz) + cz * (cz - 1) / 2;
        if(m <= 0){
            cout << 0 << endl;
            return 0;
        }else{
            f = true;
        }
    }
    if(f){
        k = m;
        reverse(begin(b), end(b));
    }else{
        reverse(begin(c), end(c));
    }
    ll ok, ng;
    if(f){
        ok = LINF;
        ng = 0;
    }else{
        ok = -1;
        ng = -LINF;
    }
    while(abs(ok - ng) > 1){
        ll mid = (ok + ng) / 2;
        if(f){
            if(check_p(k, mid, b, c)){
                ok = mid;
            }else{
                ng = mid;
            }
        }else{
            if(check_m(k, mid, b, c)){
                ok = mid;
            }else{
                ng = mid;
            }
        }
    }
    cout << ok << endl;
    return 0;
}


Measured memory_bytes: 4084
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MAX = 5100000;
ll gcd(ll a, ll b) {
    return (b==0) ? a : gcd(b, a%b);
}

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// 以下から
const int MAX_N = 100000;
struct Edge {
    int to;
    int id;
};


vector<int> to[100005];
int n;
vector<int> dist;
void dfs(int v, int d=0, int p=-1) {
    dist[v] = d;
    for (int u: to[v]) {
        if (u == p) continue;
        dfs(u, d+1, v);
    }
}

vector<int> calcDist(int s){
    dist = vector<int>(n);
    dfs(s);
    return dist;
}

//int main() {
//    ll a, b, k; cin >> a >> b >> k;
//    a -= k;
//    if (a < 0) {
//        b += a;
//    }
//    if (a < 0) a = 0;
//    if (b < 0) b = 0;
//
//    cout << a << ' ' << b << endl;
//}

int main() {
    ll x; cin >> x;
    while (true) {
        bool isOk = true;
        for (ll i=2; i * i <= x; i++) {
            if (x % i == 0) {
                isOk = false;
                break;
            }
        }
        if (isOk) {
            break;
        }
        x++;
    }
    cout << x << endl;
}

Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC_Training
{
    public class Program
    {
        static void Main(string[] args)
        {
            var nr = Console.ReadLine().Split(' ');
            var n = int.Parse(nr[0]);
            var dr = int.Parse(nr[1]);
            var ir = dr + 100 * (10 - n);
            Console.WriteLine(n >= 10 ? dr : ir);
        }
    }
}


Measured memory_bytes: 11092
#include<iostream>
#include<string>
using namespace std;
string s;
int main()
{
    cin>>s;
    long long len=s.size();
    if(s[0]==s[len-1])
    {
        if(len%2==1) 
        {
            cout <<"Second";
        }
        else 
        {
            cout <<"First";
        }
    }
    else
    {
        if(len%2==1)
        {
            cout << "First\n";
        }
        else
        {
            cout << "Second\n";
        }
    }
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
long long n,t,e,x[111111],mnp,pos,dp[111111];
multiset<long long> s;
int main()
{
	scanf("%lld%lld%lld",&n,&e,&t);
	for (long long i=1;i<=n;i++)
	{
		scanf("%lld",&x[i]);
	}
	dp[0]=0;
	mnp=1e18;
	pos=1;
	for (long long i=1;i<=n;i++)
	{
		s.insert(dp[i-1]);
		while(pos<=i)
		{
			if (2*(x[i]-x[pos])>t) 
			{
				mnp=min(mnp,dp[pos-1]-2*x[pos]);
				s.erase(s.find(dp[pos-1]));
				pos++;
			}
			else break;
		}
		dp[i]=min(*s.begin()+t,mnp+2*x[i]);
	}
	printf("%lld\n",dp[n]+e);
	return 0;
} 

Measured memory_bytes: 3840
#include <bits/stdc++.h>
#define PI acos(-1)
#define eq(x,y) (fabs((x)-(y)) < eps)
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define pb push_back
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define bump cout<<"bleh\n"
#define all(v) (v).begin(),(v).end()

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
const int nmax=1e5+10;
const int eps=1e-8;
const ll infll=1e15;


int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;

    if((a==b and b!=c) or (b==c and b!=a) or (c==a and a!=b))cout<<"Yes\n";
    else cout<<"No\n";



    return 0;
}


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

int main() {
   int n;
   cin >> n;
   int ans;
   if(n<10)
   ans=n;
   else if(n<100)
   ans=9;
   else if(n<1000)
   ans=n-90;
   else if(n<10000)
   ans=909;
   else if(n<100000)
   ans=n-9090;
   else 
   ans=90909;
   cout << ans << endl;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる



int main() {
  int n;
  cin >> n;
  int ans = 0;
  
  vector<int> p(n);
  rep(i,n){
    cin>>p[i];
  }
   
  int i=0;
  while(i!=1){
    ans++;
    i=p[i]-1;
    if(ans>n){
      ans = -1;
      break;
    }
  }
  
  cout << ans << endl;
  
}


Measured memory_bytes: 640
// CODE FESTIVAL 2016 qual C
// B - K個のケーキ / K Cakes

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int, int> PII;


int K, T;
priority_queue<PII> q;

int main() {

  int a, pre_t;
  PII p0, p1;

  scanf("%d%d", &K, &T);
  for (int i = 0; i < T; i++) {
    scanf("%d", &a);
    q.push(make_pair(a, i));
  }

  pre_t = -1;
  while (q.size() > 1) {
    p0 = q.top(); q.pop();
    p1 = q.top(); q.pop();
    if (pre_t == p0.second) {
      p1.first--;
      pre_t = p1.second;
    } else {
      p0.first--;
      pre_t = p0.second;
    }
    if (p0.first > 0) {
      q.push(p0);
    }
    if (p1.first > 0) {
      q.push(p1);
    }
  }

  printf("%d\n", (int)q.top().first - 1);

  return 0;

}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 998244353;
int N,A[MAXN];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a % b);
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) read(A[i]);
    sort(A + 1,A + N + 1);
    int ans = 1;
    for(int i = 1 ; i <= N ; ++i) ans = mul(ans,gcd(A[i],i - 1));
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


Measured memory_bytes: 640
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

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

fn f(x: i64) -> i64 {
    if x <= 0 { return 0; }
    match x % 4 {
        0 => x,
        1 => 1,
        2 => x + 1,
        3 => 0,
        _ => panic!(),
    }
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        a: i64,
        b: i64,
    }
    puts!("{}\n", f(b) ^ f(a - 1));
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int ans = a - b * 2;
		if(ans < 0) {
			ans = 0;
		}
		System.out.println(ans);

	}

}


Measured memory_bytes: 23764
/*
Loading:{
        https://codeforces.com/problemset/problem/1234/F
        https://atcoder.jp/contests/agc046/tasks/agc046_c
}
*/
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
ll a[305];
ll dp[305][305][305]; // id, used to donate, used to receive;
ll mod = 998244353; // fucking mod 1e9 + 7
ll n, k, cnt = 0;
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("GUARDS.INP", "r")){
                freopen("GUARDS.INP", "r", stdin);
                freopen("GUARDS.OUT", "w", stdout);
        }
        string s;
        cin >> s;
        n = s.length();
        cin >> k;
        ll cur = 0;
        ll cnt1 = 0;
        for (int i = s.length() - 1; i >= 0; i--){
                if (s[i] == '1') {
                        cur++;
                        cnt1++;
                }
                else {
                        cnt++;
                        a[cnt] = cur;
                        cur = 0;
                }
        }
        cnt++;
        a[cnt] = cur;
        //memset(dp, -1, sizeof(dp));
        k = min(k, cnt1);
        for (int i = a[1]; i >= max(0ll, a[1] - k); i--){
                dp[1][a[1] - i][0] = 1;
        }
        ll sum = a[1];
        for (int i = 1; i < cnt; i++){
                for (int j = 0; j <= sum; j++){
                        for (int t = 0; t <= j; t++){
                                dp[i + 1][j][t] = (dp[i + 1][j][t] + dp[i][j][t]) % mod;
                                for (int x = a[i + 1] - 1; x >= max(0ll, (a[i + 1] - (k - j))); x--){
                                        dp[i + 1][j + a[i + 1] - x][t] = (dp[i + 1][j + a[i + 1] - x][t] + dp[i][j][t]) % mod;
                                }
                                for (int x = a[i + 1] + 1; x <= a[i + 1] + (j - t); x++){
                                        dp[i + 1][j][t + x - a[i + 1]] = (dp[i + 1][j][t + x - a[i + 1]] + dp[i][j][t]) % mod;
                                }
                        }
                }
                sum += a[i + 1];
        }
        ll ans = 0;
        for (int i = 0; i <= k; i++) {
                ans = (ans + dp[cnt][i][i]) % mod;
                //cout << dp[cnt][i][i] << " ";
        }
        cout << ans;
}


Measured memory_bytes: 57032
N, M = map(int, input().split())
AB = []
for i in range(M):
    a, b = list(map(int, input().split()))
    AB.append([a, b])

AB.sort(key=lambda x:x[1])

cnt = 1
s = AB[0][1]
for a, b in AB[1:]:
    if s <= a:
        cnt += 1
        s = b
print(cnt)



Measured memory_bytes: 63832
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

#define int long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define f first
#define s second
#define sz(x) (int)x.size()
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=(int)l;i<=(int)r;++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.14159265358979323846

typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> oset;

// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

const int mod = 2019;
const int inf = 9e18;
const int N = 1005;

int i,n,p,pref=0,ans=0;
string s;

int power(int x,int y){
    int res=1;
    x%=p;
    while(y>0){
        if(y&1){
            res*=x;
            res%=p;
        }
        y>>=1;
        x*=x;
        x%=p;
    }
    return res;
}

void solve(){
    cin>>n>>p>>s;
    if(p!=2 && p!=5){
        map<int,int> mp;
        mp[0]++;
        for(i=0;i<n;++i){
            int sum=s[i]-'0';
            sum*=power(10,n-1-i);
            sum%=p;
            pref+=sum;
            pref%=p;
            ans+=mp[pref];
            mp[pref]++;
        }
    }
    else{
        for(i=0;i<n;++i){
            if((s[i]-'0')%p==0)
                ans+=i+1;
        }
    }
    cout<<ans;
}

signed main(){
    fastio;
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
        cout<<endl;
    }
    return 0;
}


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

using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<double>;
using VVI = vector<VI>;
using VVL = vector<VL>;
using PI = pair<int, int>;
using PL = pair<ll, ll>;
using VPI = vector<PI>;
using VPL = vector<PL>;
using VS = vector<string>;

#define ln '\n'
#define REP(t, n) for (int t = 0; t < (n); ++t)
#define FOR(t, a, b) for (int t = (a); t <= (b); ++t)
#define FORR(t, a, b) for (int t = (a); t >= (b); --t)
#define ALL(c) (c).begin(), (c).end()

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll r, d, x;
    cin >> r >> d >> x;
    REP(i, 10) {
        x = r * x - d;
        cout << x << ln;
    }
    return 0;
}


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

using namespace std;
#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)
#define REV(i,a,b) REVV(i,a,b,1)
#define FOR(i,a) REP(i,0,(int)a-1)
#define FORD(i,a) REV(i,(int)a-1,0)
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FI first
#define SE second
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > pii;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;

const double EPS = 1e-9;
const double PI = acos(-1);
const ll INF = 1e15;
const ll MOD = 1e9 + 7;

ll addMod(ll a, ll b){
	return (a+b) % MOD;
}

ll mulMod(ll a, ll b){
	return (a*b) % MOD;
}

ll fast(ll a, ll b){
	if(b == 0) return 1;
	ll tmp = fast(a,b/2);
	tmp = mulMod(tmp, tmp);
	if(b & 1) tmp = mulMod(tmp, a);
	return tmp;
}

/////////////////////////////////////////////////////////

const int N = 5000;

ll n,m,p;
ll dist[N + 5];
ll u[N + 5], v[N + 5], w[N + 5];
vi G[N + 5], G2[N + 5];
bool vis[N + 5][3];

void dfs(int u){
	vis[u][1] = true;
	for(auto v : G[u]){
		if(!vis[v][1]){
			dfs(v);
		}
	}
}

void dfs2(int u){
	vis[u][0] = true;
	for(auto v : G2[u]){
		if(!vis[v][0]){
			dfs2(v);
		}
	}
}

ll solve(){
	REP(i,1,n) dist[i] = INF;
	dist[1] = 0;
	FOR(j,n){
		FOR(i,m){
			if(vis[v[i]][0] && vis[u[i]][0] && vis[v[i]][1] && vis[u[i]][1] && dist[v[i]] > dist[u[i]] + w[i]){
				dist[v[i]] = dist[u[i]] + w[i];
				if(j == n-1 && vis[v[i]][0] && vis[v[i]][1]){
					return -1;
				}
			}
		}
	}
	if(dist[n] > 0) dist[n] = 0;
	return -dist[n];
}

int main(){
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(vis,0,sizeof vis);
	cin >> n >> m >> p;
	FOR(i,m){
		cin >> u[i] >> v[i] >> w[i], w[i] = p - w[i];
		G[u[i]].PB(v[i]);
		G2[v[i]].PB(u[i]);
	}
	dfs(1); dfs2(n);
	cout << solve() << endl;
	return 0;
}

Measured memory_bytes: 896
n,T = map(int,input().split())

a = list(map(int,input().split()))
maxDiff = 0
curMin = a[0]
for i in range(n):
  if curMin > a[i]:
    curMin = a[i]
  if maxDiff < a[i] - curMin:
    maxDiff = a[i] - curMin

isCovered = False
count = 0

curMin = a[0]

for i in range(n):
  if curMin > a[i]:
    curMin = a[i]
    isCovered = False
  if maxDiff == a[i] - curMin:
    if not isCovered:
      count += 1
      isCovered = True

print(count)


Measured memory_bytes: 84840
#include <iostream>

const int MAXN = 112345;
long long a[MAXN];

int main() {
  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  long long ans = 0;
  for (int d = 1; 2*d < n-1; ++d) {
    int s = 0;
    int g = n-1;
    long long cur = 0;
    while(true) {
      int ns = s + d;
      int ng = g - d;
      if (ns >= n-1 || ng <= d || ns == ng || ns - ng == d)   break;
      cur += a[ns] + a[ng];
      ans = std::max(ans, cur);
      s = ns;
      g = ng;
    }
  }
  std::cout << ans << std::endl;
}

Measured memory_bytes: 1152
#include<stdio.h>
 
int main(void){
   int a;
   int h;
   int m;
   int s;
   
   scanf("%d",&a);
   h = a / 3600;
   m = (a % 3600) / 60;
   s = a % 60;
   printf("%d:%d:%d\n",h,m,s);
   return (0);
}



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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    ll N; cin >> N;
    ll A[N]; rep(i, N) cin >> A[i];
    // A[1]^A[2] + A[1]^A[3] + ... + A[1]^A[N] + A[2]^A[3] + ...
    // 桁に注目するとうまくいくことが多い(分配則が成り立つので)
    // 2^kの桁について(0,1)なるペアの個数*2^kを足せばいい
    ll ans = 0;
    ll cnt[62] = {};
    ll bit = 1ll;
    rep(i, N){
        bit = 1ll;
        rep(j, 62){
            if(bit == (A[i] & bit)) cnt[j]++;
            bit <<= 1;
        }
    }
    rep(i, 62){
        ll temp;
        temp = ((cnt[i]*(N-cnt[i])) % mod)*((1ll << i) % mod) % mod;
        ans = (ans + temp) % mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(__,v.size()){rep(_,v[__].size())cout<<" "<<v[__][_];cout<<endl;}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

signed main(){
	string s;
	cin>>s;
	int n=s.size(),MOD=1000000007;
	
	bool h=true;
	rep(i,n-1)if(s[i]==s[i+1])h=false;
	if(h){
		cout<<1<<endl;
		return 0;
	}
	s+=s.back();
	vi c(n+1),ren(n,inf);
	rep(i,n)c[i+1]=s[i]-'a'+1;
	rep(i,n)if(s[i]==s[i+1])ren[i]=i;
	rep(i,n-1)cmin(ren[n-i-2],ren[n-i-1]);
	rep(i,n)(c[i+1]+=c[i])%=3;

	vvi next(n+1,vi(3,n));
	for(int i=n-1;i>=0;i--){
		rep(j,3)next[i][j]=next[i+1][(j+3-(s[i]-'a'+1))%3];
		next[i][s[i]-'a'+1]=i;
	}
	vi dp(n+1);
	dp[0]=1;
	rep(i,n)if(dp[i]){
		rep(q,2){
			if(s[i]-'a'==q){
				(dp[i+1]+=dp[i])%=MOD;
				continue;
			}
			int to=ren[i]+1;
			to=next[to][(q+1-c[to]+c[i]+3)%3];
			if(to==n)continue;
			(dp[to+1]+=dp[i])%=MOD;
		}
	}
	int out=0;
	rep(i,n)if((c[n]+3-c[i+1])%3==0)(out+=dp[i+1])%=MOD;
	cout<<out<<endl;
}















Measured memory_bytes: 8192
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();	
       	for(int i=b-a+1;i<b+a;i++){
			System.out.print(i+" ");
        }
	}
	

}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int n;
    int x[109]={};
    int ans=99999999;
    int tmp=0;
    
    cin >> n;
    
    for(int i=1; i<=n; i++){
        
        cin >> x[i];
        
    }
    
    for(int i=1; i<=100; i++){
        
        tmp = 0;
        
        for(int j=1; j<=n; j++){
            
            tmp += pow(x[j]-i, 2);
            
        }
        
        ans = min(ans, tmp);
        
    }
    
    cout << ans << endl;
    
    return 0;
    
}

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


Measured memory_bytes: 256
import java.util.*;
public class Main {

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      String s = sc.next();
      StringBuilder sb = new StringBuilder();
      for(int i = 0; i < s.length(); i++) {
        int charNum = s.charAt(i) - 'A';
        charNum = (charNum + n) % 26 + 'A';
        sb.append((char)charNum);
      }
      System.out.println(sb.toString());
  }
}

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

constexpr int mod = 1e9 + 7;

template <class T> inline bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <class T> inline bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

struct edge {
    int to, num;
};

int n, m, a[100009], b[100009], out[100009];
vector<edge> e[100009];
bool visit[100009], use[100009];

void dfs(int x) {
    visit[x] = true;
    rep(i, e[x].size()) {
        if(!visit[e[x][i].to]) {
            use[e[x][i].num] = true;
            dfs(e[x][i].to);
        }
    }
}

void dfs2(int x, int par = 0) {
    visit[x] = false;
    rep(i, e[x].size()) {
        if(visit[e[x][i].to]) {
            dfs2(e[x][i].to, x);
        }
    }
    if(par == 0) return;
    if(out[x] & 1) {
        out[x]++;
        cout << x << " " << par << endl;
    } else {
        out[par]++;
        cout << par << " " << x << endl;
    }
}

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

    cin >> n >> m;
    if(m & 1) {
        cout << -1 << endl;
        return 0;
    }
    rep(i, m) {
        cin >> a[i] >> b[i];
        e[a[i]].push_back({b[i], i});
        e[b[i]].push_back({a[i], i});
    }

    dfs(1);

    rep(i, m) {
        if(!use[i]) {
            out[a[i]]++;
            cout << a[i] << " " << b[i] << endl;
        }
    }

    dfs2(1);

    return 0;
}

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

using namespace std;
#define MAXN 22
const int mod = 1e9 + 7;

int dp[1 << 22][MAXN], n, a[MAXN][MAXN];

int solve(int mask, int i){
    if (dp[mask][i] != -1)  return dp[mask][i];
    if (i == 0) {
        if (mask == ((1 << n) - 1))
            return dp[mask][i] = 1;
        return dp[mask][i] = 0;
    }
    int res = 0;
    for (int j = 1; j <= n; j++){
        if (a[i][j] == 1 && !(mask & (1 << (j-1)))){
            res = (res + solve(mask | (1 << (j-1)), i - 1) ) % mod;
        }
    }
    return dp[mask][i] = res;
}

int main(){
    cin >> n;
    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)
        cin >> a[i][j];
    cout << solve(0, n) << '\n';
    return 0;
}

Measured memory_bytes: 360704
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

template<int MOD>
struct mod_int {
	static const int Mod = MOD;
	unsigned x;
	mod_int() : x(0) { }
	mod_int(int sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	mod_int(long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	mod_int &operator+=(mod_int that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator-=(mod_int that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator*=(mod_int that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	mod_int &operator/=(mod_int that) { return *this *= that.inverse(); }

	mod_int operator+(mod_int that) const { return mod_int(*this) += that; }
	mod_int operator-(mod_int that) const { return mod_int(*this) -= that; }
	mod_int operator*(mod_int that) const { return mod_int(*this) *= that; }
	mod_int operator/(mod_int that) const { return mod_int(*this) /= that; }

	mod_int inverse() const {
		long long a = x, b = MOD, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		return mod_int(u);
	}
};

using mint = mod_int<1000000007>;

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

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int R, C, ai, aj, bi, bj;
	cin >> R >> C >> ai >> aj >> bi >> bj;
	vector<vector<int>> d(R, vector<int>(C, -1));
	vector<vector<mint>> dp(R, vector<mint>(C));
	queue<pii> q;
	q.emplace(ai, aj);
	d[ai][aj] = 0;
	dp[ai][aj] = 1;
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second; q.pop();
		for (int i = 0; i < 4; i++) {
			int tx = x + dx[i], ty = y + dy[i];
			if (0 <= tx && tx < R && 0 <= ty && ty < C) {
				if (d[tx][ty] == -1) {
					d[tx][ty] = d[x][y] + 1;
					q.emplace(tx, ty);
				}
				if (d[tx][ty] == d[x][y] + 1) {
					dp[tx][ty] += dp[x][y];
				}
			}
		}
		int tx[] = { 0, R - 1, x, x };
		int ty[] = { y, y, 0, C - 1 };
		for (int i = 0; i < 4; i++) {
			if (tx[i] != x || ty[i] != y) {
				if (d[tx[i]][ty[i]] == -1) {
					d[tx[i]][ty[i]] = d[x][y] + 1;
					q.emplace(tx[i], ty[i]);
				}
				if (d[tx[i]][ty[i]] == d[x][y] + 1) {
					dp[tx[i]][ty[i]] += dp[x][y];
				}
			}
		}
	}
	cout << d[bi][bj] << ' ' << dp[bi][bj].get() << endl;
	return 0;
}



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

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

  for (int i = 1; i <= n; ++i) {
    if (i % 3 == 0) {
      cout << " " << i;
      continue;
    }
    int x = i;
    while (x != 0) {
      if (x % 10 == 3) {
        cout << " " << i;
        break;
      }
      x /= 10;
    }
  }
  cout << endl;
  return 0;
}



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

int ts[200010];

int main(){
	int n, t;
	scanf("%d%d", &n, &t);
	for(int i = 0; i < n; i++)
		scanf("%d", &ts[i]);
	long ans = t;
	for(int i = 0; i + 1 < n; i++) {
		int time = ts[i+1] - ts[i];
		ans += (time > t) ? t : time;
	}
	printf("%ld\n", ans);
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int32 n;
  cin >> n;
  vector<int32> p(n),q(n);
  REP(i,n)cin >> p[i];
  REP(i,n)cin >> q[i];
  int32 i = 0;
  vector<int32> perm;
  REP(i,n)perm.pb(i+1);
  int32 a = -1, b = -1;
  do{
    if(p == perm)a = i;
    if(q == perm)b = i;
    i++;
  }while(next_permutation(ALL(perm)));
  ANS(abs(a-b));
  return 0;
}

Measured memory_bytes: 256
n=int(input())
t=list(map(int,input().split()))
m=int(input())
drink=[]
all=sum(t)
for i in range(m):
  drink.append(list(map(int,input().split())))
for j in range(m):
  if drink[j][0]<=n:
    print(all-t[drink[j][0]-1]+drink[j][1])
  else:
    print(all)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,a,b;
    cin>>x>>a>>b;
    if(a-b>=0)
    {
        cout<<"delicious"<<endl;
    }
    else if(x>=abs(b-a))
    {

        cout<<"safe"<<endl;
    }
    else
        cout<<"dangerous"<<endl;
}


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

typedef long long ll;

using namespace std;

long long gcd(long long a , long long b){
    return (a%b == 0)?b:gcd(b,a%b);
}

int main(){
    int N;
    cin >> N;
    vector<pair<int,int>> sche(N);
    for(int i = 0; i < N; i++){
        int a , b;
        cin >> a >> b;
        sche[i] = make_pair(b,a);
    }
    sort(sche.begin(),sche.end());
    int time = 0;
    for(int i = 0; i < N; i++){
        time += sche[i].second;
        if(time > sche[i].first){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
	ll x,y,ans=0;
  	cin>>x>>y;
  	while(x <=y){
    	ans++;
      	x = x*2;
    }
  	cout<<ans<<"\n";
	return 0;
}

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

struct StoreInfo {
	int price;
	int num;
};

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

	std::vector<StoreInfo> list(N);
	for(auto &e : list) {
		std::cin >> e.price >> e.num;
	}

	// 値段で高い順にソート
	std::sort(list.begin(), list.end(), [](const auto &a, const auto &b) {
		return a.price > b.price;
	});

	long long result = 0;
	int rest = M;
	while(rest > 0) {
		// 不足分　または　在庫全部
		const int numBuy = std::min(rest, list.back().num);

		// 購入
		result += (long long)list.back().price * numBuy;
		rest -= numBuy;

		// この店はもう必要ない。
		list.pop_back();
	}

	std::cout << result << std::endl;

	return 0;
}


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

int main(){
    string s;
    cin>>s;
    int f = 0, e = s.size()-1;
    for(; f<s.size()-1; ++f){
        if(s[f] == 'A'){break;}
    }
    for(; e>=0; --e){
        if(s[e] == 'Z'){break;}
    }

    cout << e-f+1 << endl; return 0;
}

Measured memory_bytes: 640