akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

struct node *root,*NIL;


void insert(int k){
  struct node *y =NIL;
  struct node *x =root;
  struct node *z;

  z = (struct node*)malloc(sizeof(struct node));
  z->key =k;
  z->left =NIL;
  z->right =NIL;
  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x=x->left;
    }else{
      x=x->right;
    }
  }
  z->parent=y;
  if(y==NIL)root=z;
  else if(z->key < y->key)y->left=z;
  else y->right=z;
}

void inorder(struct node *u){
  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(struct node *u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }else{
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}



Measured memory_bytes: 25136
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[105],pre[105],nxt[105],last[105],ans[105],top;
void solve(int x)
{
	if(x!=0)printf("%d\n",a[x]);
	for(int i=nxt[x]-1;i>x;i--)
	  if(a[i]==a[x]+1)
		solve(i);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=n;i>=1;i--)
	{
		int now=0;
		for(int j=1;j<=i;j++)
		  if(a[j]==j)
			now=j;
		if(!now)
		{
			printf("-1\n");
			return 0;
		}
		ans[i]=now;
		for(int j=now;j<=i;j++)
		  a[j]=a[j+1];
	}
	for(int i=1;i<=n;i++)
	  printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 128
n=int(input())
s=input()
c=s.count
m=c('R')*c('G')*c('B')
for i in range(n):
  for j in range(i+2,n,2):
    if s[i]!=s[i+j>>1]!=s[j]!=s[i]:
      m-=1
print(m)


Measured memory_bytes: 73788
#!/usr/bin/env python3
from itertools import accumulate, product

while True:
    n, m = map(int, input().split())
    if n == 0:
        exit()
    h = [int(input()) for _ in range(n)]
    w = [int(input()) for _ in range(m)]

    hs = [0] + list(accumulate(h))
    ws = [0] + list(accumulate(w))

    dic = {}
    for l, r in product(range(m + 1), range(m + 1)):
        if l >= r:
            continue
        dw = ws[r] - ws[l]
        dic[dw] = dic[dw] + 1 if dw in dic else 1

    ans = 0
    for l, r in product(range(n + 1), range(n + 1)):
        if l >= r:
            continue
        dh = hs[r] - hs[l]
        if dh in dic:
            ans += dic[dh]

    print(ans)



Measured memory_bytes: 35040
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14 100兆
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(){
  ll N;
  cin >> N;
  const auto &res = prime_factorize(N);
  ll ans = 0;
  for(auto p : res){
    ll e = 1;
    while(true){
      if(e * (e+1) / 2 <= p.second){
        e++;
      }
      else{
        e--;
        break;
      }
    }
    ans += e;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
H,W=[int(s) for s in input().split()]
lamp=[input() for _ in range(H)]
#Lを計算
L=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][0]=="#" :  L[i][0]=0
  else: L[i][0]=1
  for j in range(1,W):
    if lamp[i][j]=="#" : L[i][j]=0
    else: L[i][j]=L[i][j-1]+1
#Rを計算
R=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][W-1]=="#" :  R[i][W-1]=0
  else: R[i][W-1]=1
  for j in range(1,W):
    if lamp[i][W-1-j]=="#" : R[i][W-1-j]=0
    else: R[i][W-1-j]=R[i][W-j]+1
#Uを計算
U=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[0][j]=="#" :  U[0][j]=0
  else: U[0][j]=1
  for i in range(1,H):
    if lamp[i][j]=="#" : U[i][j]=0
    else: U[i][j]=U[i-1][j]+1
#Dを計算
D=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[H-1][j]=="#" :  D[H-1][j]=0
  else: D[H-1][j]=1
  for i in range(1,H):
    if lamp[H-1-i][j]=="#" : D[H-1-i][j]=0
    else: D[H-1-i][j]=D[H-i][j]+1
ls=[]
for i in range(H):
  for j in range(W):
    ls.append(L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(max(ls))

Measured memory_bytes: 325568
import itertools


n = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
X = list(range(1, n+1))

pattern = list(itertools.permutations(X))
pattern.sort()

a = pattern.index(P)
b = pattern.index(Q)

print(abs(a-b))

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

int main(int argc, char const *argv[])
{
    int H, W;
    
    cin >> H >> W;
    vector<vector<char>> a(H+2, vector<char>(W+2));


    for(int i = 0; i< H+2; i++){
        for(int j = 0; j < W+2 ; j++){
            a.at(i).at(j) = '#';
        }
    }

    char input;

    for(int i = 1; i< H+1; i++){
        for(int j = 1; j < W+1 ; j++){
            cin >> input;
            a.at(i).at(j) = input;
        }
    }

    for(int i = 0; i< H+2; i++){
        for(int j = 0; j < W+2 ; j++){
            cout << a.at(i).at(j);
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool wall[10000][10000][4];
char str[10001];

const int U = 0;
const int R = 1;
const int D = 2;
const int L = 3;

char dirchar[] = "URDL" ;
int righthand(int x) {return (x+1)%4;}
int lefthand(int x) {return (x+3)%4;}
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

int main() {
  bool firsttime = true;
  int width, height=0;
  int dir = R, x = 0, y = 0, i,j,k;

  while (true) {
    scanf("%9999s\n", str);

    if (firsttime) {
      width = strlen(str)+1;
      firsttime = false;
    }

    for (i = 0; i<width; i++)
      wall[i][height][R] = wall[i+1][height][L] = (str[i] == '1');

    if (scanf("%10000s\n", str) == -1)
      break;

    for (i=0; i<width; i++)
      wall[i][height][D] = wall[i][height+1][U] = (str[i] == '1');

    height++;
  }

  firsttime = true;
  while (true) {
    int nextdir;

    if (!firsttime && x == 0 && y == 0)
      break;

    for (nextdir = lefthand(dir); !wall[x][y][nextdir]; nextdir = righthand(nextdir))
      ;

    //    printf("\n(%d, %d) %c (%d, %d, %d, %d) ", x, y, dirchar[dir], wall[x][y][0], wall[x][y][1], wall[x][y][2], wall[x][y][3]);

    putchar(dirchar[nextdir]);
    x += dx[nextdir];
    y += dy[nextdir];
    dir = nextdir;
    firsttime = false;
  }

  puts("");
  return 0;
}

Measured memory_bytes: 552
n, m, x, y = gets.split(" ").map(&:to_i)
x_s = gets.split(" ").map(&:to_i)
y_s = gets.split(" ").map(&:to_i)
nums = []

i = x + 1
while i <= y
  nums << i
  i += 1
end

if nums.empty?
  puts "War"
  exit
end

nums.each do |n|
  if x_s.max < n && y_s.min >= n
    puts "No War"
    exit
  end
end

puts "War"

Measured memory_bytes: 1916
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <fstream>

using namespace std;

const int N = 100005;
int n, a[N], dp[N][2];

int rec(int i, bool p)
{
	if (i == n - 1) return 0;
	if (i > n - 1) return 1e9;

	int& dp = ::dp[i][p];

	if (dp != -1) return dp;

	return dp = min(rec(i+1,0) + abs(a[i]-a[i+1]), abs(a[i] - a[i + 2])  + rec(i+2,1));
}

int main()
{

	cin >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++)
	{
		scanf("%d", a + i);
	}

	printf("%d", rec(0, 0));
}

Measured memory_bytes: 3712
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int n,ans=1000000000,k,q,a[2000],x;
    vector<int> v1,v2;
    scanf("%d %d %d",&n,&k,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++){
        v2.clear();
        v1.clear();
        for(int j=0;j<n;j++){
            if(a[j]<a[i]){
                sort(v1.begin(),v1.end());
                x=(int)v1.size();
                for(int l=0;l<=x-k;l++){
                    v2.push_back(v1[l]);
                }
                v1.clear();
            }
            else{
                v1.push_back(a[j]);
            }
            if(j==n-1){
                sort(v1.begin(),v1.end());
                x=(int)v1.size();
                for(int l=0;l<=x-k;l++){
                    v2.push_back(v1[l]);
                }
                v1.clear();
            }
        }
        if(v2.size()>=q){
            sort(v2.begin(),v2.end());
            ans=min(ans,v2[q-1]-v2[0]);
        }
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

ll D, c[33], s[444][33], t[444], last[33] = {};
set<ll> s1[33], s2[33];

// vector<ll> score(ll t[]) {
//     ll i, j, sc = 0;
//     vector<ll> v;
//     v.pb(0);
//     for (i = 1; i <= D; i++){
//         sc += s[i][t[i]];
//         last[t[i]] = i;
//         for (j = 1; j <= 26;j++)
//             sc -= c[j] * (i - last[j]);
//         v.pb(sc);
//     }
//     return v;
// }

ll cost(ll k, ll dis){
    return k * dis * (dis - 1) / 2;
}

ll eval(ll d, ll q){
    ll bq = t[d];
    ll b = *s1[bq].upper_bound(d);
    ll a = *s2[bq].upper_bound(-d);
    ll sc = 0;
    sc -= s[d][bq];
    sc += s[d][q];
    ll l = d + a, r = b - d;
    sc += cost(c[bq], l);
    sc += cost(c[bq], r);
    sc -= cost(c[bq], l + r);
    b = *s1[q].upper_bound(d);
    a = *s2[q].upper_bound(-d);
    l = d + a, r = b - d;
    sc -= cost(c[q], l);
    sc -= cost(c[q], r);
    sc += cost(c[q], l + r);
    return sc;
}

int main(){
    ll i, j;
    cin >> D;
    for (i = 1; i <= 26;i++)
        cin >> c[i];
    for (i = 1; i <= D;i++)
        for (j = 1; j <= 26;j++)
            cin >> s[i][j];
    for (i = 1; i <= 26; i++){
        s1[i].insert(D + 1);
        s2[i].insert(0);
    }
    for (i = 1; i <= D;i++){
        ll ma = -1e15, p;
        for (j = 1; j <= 26; j++){
            if(c[j]*(i-last[j])+s[i][j]>ma){
                ma = c[j] * (i - last[j]) + s[i][j];
                p = j;
            }
        }
        t[i] = p;
        last[p] = i;
    }
    for (i = 1; i <= D;i++){
        s1[t[i]].insert(i);
        s2[t[i]].insert(-i);
    }
    random_device rnd;
    mt19937 mt(rnd());
    uniform_int_distribution<> rand365(1, 365);
    ll INF = 1e9;
    double start_temp = 3000, end_temp = 0;
    ll turn = 500000;
    for (i = 0; i < turn; i++){
        ll ma = -1e15, p;
        ll d = rand365(mt);
        for (j = 1; j <= 26; j++){
            if(j!=t[d]){
                ll sc = eval(d, j);
                if(sc > ma){
                    ma = sc;
                    p = j;
                }
            }
        }
        double temp = start_temp + (end_temp - start_temp) * i / turn;
        double prob = exp(ma / temp);
        if (prob > (rand() % INF) / (double)INF){
            s1[t[d]].erase(d);
            s2[t[d]].erase(-d);
            s1[p].insert(d);
            s2[p].insert(-d);
            t[d] = p;
        }
    }
    for (i = 1; i <= D;i++)
        cout << t[i] << endl;
}

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

#define all(x) x.begin(),x.end()
#define pb(x) emplace_back(x)
#define forn(i,N) for(int i=0;i<N;i++)

using namespace std;
using ll=long long int;
using ld=long double;

int main() {
//freopen("input.txt","rt",stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N;
cin>>N;
cout<<(N>=30 ? "Yes" : "No")<<endl;
return 0;
}


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

namespace AtCoder.Abc
{
    // 問題:
    class A_161_ABCSwap
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数配列の入力
            var array = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

            int a = array[0];
            int b = array[1];
            int c = array[2];

            Console.WriteLine(c + " " + a + " " + b);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 28240
def smaller(x, y):
	if x < y: return x
	else: return y

def calc(a, b, c, d):
	if b < c: return 0
	else: return smaller(b, d) - c

A, B, C, D = map(int, raw_input().split())

if A > C:
	tmp1 = A
	tmp2 = B
	A = C
	B = D
	C = tmp1
	D = tmp2

print calc(A, B, C, D)

Measured memory_bytes: 2568
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100000;

int main() {
	string s;
	cin >> s;
	int ans = 0;
	stack<char> S;
	rep(i, s.size()) {
		if((!S.empty()) && (s[i] != S.top())) {
			ans += 2;
			S.pop();
		}
		else {
			S.push(s[i]);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 512
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() throws IOException{
		String[] s = br.readLine().split(" ");
		int n = s.length;
		ArrayList<String> list = new ArrayList<String>();
		for (int i=0; i<n; i++) {
			s[i] = s[i].replaceAll(",","").replaceAll("\\.","");
			if (2 < s[i].length() && s[i].length() < 7) {
				list.add(s[i]);
			}
		}

		for (int i=0; i<list.size()-1; i++) {
			out.print(list.get(i) + " ");
		}
		out.println(list.get(list.size()-1));
	}

	public static void main(String[] args) throws Exception {
		long start = System.currentTimeMillis();

		solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		br.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 24740
import math

def next_sunuke(N):
    D = math.ceil(math.log(N,10) + 1)
    z = str(N)
    zx = [int(z[:1]) for z in z]
    Z = N / sum(zx)
    ret_val = N
#    print(Z)
    ret_vals = [ret_val]
    for d in range(0, D):
        x = ( (10 ** (d + 1)) * math.floor((N / (10 ** (d+1))) + 1 ) ) - 1
#        print(x)
        w = str(x)
        sx = [int(w[:1]) for w in w]
        y = x / sum(sx)
#        print(x,w,sx,sum(sx),y)
        if y == Z:
            Z = y
            ret_vals.append(x)
        elif y < Z:
            Z = y
            ret_vals = []
            ret_vals.append(x)
        #print(min(ret_vals))

#    print(ret_vals)
    return min(ret_vals)

K = int(input())
n = 1
for i in range(1,K+1):
    print(next_sunuke(n))
    n = next_sunuke(n) + 1


Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define square(x) pow(x,2.0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define max_queue(x) priority_queue<x>
#define min_queue(x) priority_queue<x, vector<x>, greater<x>>
#define big_sort(v) sort(all(v), [](int a, int b) { return a > b; })//大きい順にソート
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
using vd = vector<long double>;
#define co(x) cout << x << endl;
#define cins(n,v) rep(i,n){cin >> v.at(i);}
#define couts(v) rep(i,v.size()){cout << v.at(i) << endl;}
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
/*
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
*/
int main() {
  string s,t;
  ll ans=1e9,dif=0;
  cin >> t>>s;
  rep(i,t.size()-s.size()+1){
    dif=0;
    rep(j, s.size()){
      if(s[j]!=t[i+j]) dif++;
    }
    ans=min(ans,dif);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define CC(n,m) ((LL)fac[(n)+(m)]*ifac[n]%mo*ifac[m]%mo)

const int N=1e6;
const int maxn=N+10;
const int mo=998244353;

int row,line,sum,Ans;
int n,m,fac[maxn],ifac[maxn];

int power(int x,int k)
{
	int res=1;
	while (k)
	{
		if (k&1) res=(LL)res*x%mo;
		x=(LL)x*x%mo;
		k>>=1;
	}
	return res;
}

int F(int n,int m,int x,int y)
{
	/*
	if (m-y<0) puts("#3");
	if (n-x<0)
	{
		puts("#4");
		printf("%d %d %d %d\n",n,m,x,y);
	}
	*/
//	if (x>N||y>N||n-x>N||m-y>N) printf("...");
	if (x>=0&&y>=0)
		return CC(x,y)*CC((n)-(x),(m)-(y))%mo;
	else
		return CC((n)-(x),(m)-(y))%mo;
}

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i;
	fac[0]=1;
	for (i=1;i<=N;i++)
		fac[i]=(LL)fac[i-1]*i%mo;
	ifac[N]=power(fac[N],mo-2);
	for (i=N;i>=1;i--)
		ifac[i-1]=(LL)ifac[i]*i%mo;

	scanf("%d%d",&n,&m);

	if (n>m) swap(n,m);

	for (i=1;i<=n+m;i++)
	{
//		if (i==1)
//		{
//			row=CC(n,m-1);
//			line=CC(n-1,m);
//		}
//		else
			if (i<=n*2+1)
			{
				if (i&1)
				{
//3 : n,m-2,1,0
//5 : n,m-2,2,1
					(row+=F(n,m-2,i>>1,(i>>1)-1))%=mo;

					if (i<=n*2)

					(line+=F(n-2,m,(i>>1)-1,i>>1))%=mo;
//					if (i==n*2+1)
					if (i==1)
					{
//						printf("+=F(%d,%d,%d,%d)\n",n,m-2,i>>1,(i>>1)-1);
					}
				}
				else
				{
					(row+=mo-F(n-1,m-1,(i>>1)-1,(i>>1)-1))%=mo;
					(line+=mo-F(n-1,m-1,(i>>1)-1,(i>>1)-1))%=mo;
				}
			}
		(sum+=row)%=mo;
		(sum+=line)%=mo;
		(Ans+=(LL)sum*power(i,mo-2)%mo)%=mo;
//		printf("%d : %d %d\n",i,row,line);
	}
	Ans=(LL)Ans*power(CC(n,m),mo-2)%mo;
	printf("%d\n",Ans);
}


Measured memory_bytes: 8192
using System;
using System.Collections.Generic;
using System.Linq;

namespace C
{
	class Program
	{
		static void Main()
		{
			var line1 = Console.ReadLine();
			var line2 = Console.ReadLine();

			var line1Splited = line1.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
			var line2Splited = line2.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);

			var N = Int64.Parse(line1Splited[0]);
			var M = Int64.Parse(line1Splited[1]);

			if (N >= M) {
				Console.WriteLine("0");
				Environment.Exit(0);
			}

			var X = new List<Int64>();
			foreach (var token in line2Splited) {
				X.Add(Int64.Parse(token));
			}

			X.Sort();

			var L = new List<Int64>();
			foreach (var item in X.Select((value, index) => new {value, index})) {
				var i = item.index;
				var x = item.value;
				
				if (i >= 1)
					L.Add(X[i] - X[i - 1]);
			}

			L.Sort();
			L.Reverse();

			Int64 sumL = 0;
			for (int i = 0; i < N - 1; i++) {
				sumL += L[i];
			}

			Console.WriteLine(X.Max() - X.Min() - sumL);
		}
	}
}

Measured memory_bytes: 28508
# 2019/08/08
# 高速改良版

def mod(n):
    return n%(10**9+7)

def fac(n):
    res=1
    for i in range(1,n+1):
        res=mod(res*i)
    return res

n,m=map(int,input().split())
diff=abs(n-m)
if diff>1:ans=0
elif diff==0:
    ans=mod(2*fac(n)*fac(m))
else:
    ans=mod(fac(n)*fac(m))
print(ans)

Measured memory_bytes: 3064
n,x=map(int,input().split())
A=list(map(int,input().split()))

cnt=0
for i in range(n-1):
    point=A[i]+A[i+1]
    cnt +=max(0,point-x)
    if point>x:A[i+1]=max(0,x-A[i])

print(cnt)

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

typedef long long ll;
typedef pair<int,int>P;
#define INF (1e9)
#define EPS (1e-7)
#define MOD ((ll)1e9+7)
#define REP(i,n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,k,n) for(int i = (k); i < (int)(n); i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define pb push_back
#define vec vector<int>


/*--------------------------------------------*/
/*ll factorial(ll);
void list_Prime(ll);
ll divisor(ll);*/
/*--------------------------------------------*/


int main(){
    string s;cin>>s;
    vec a(27,0);
    int flag=1;
    REP(i,(int)s.size())a[s[i]-'a']++;
    //REP(i,27)printf("i=%d,%d",i,a[i]);
    REP(i,26)if(a[i]>1)flag=0;
    cout<<(flag?"yes":"no")<<endl;
}



/*--------------------------------------------*/
/*
ll factorial(ll n){
    if(n==1)return 1;
    return n*factorial(n-1);
}


void list_Prime(ll n){//n以下の素数を全て見つける
    ll Limit=(int)sqrt((double)n);
    for(ll i=2;i<=n;i++)prime[i]=1;//最初はみんな素数かも
    //素数の整数倍を消していく(ルートnまで)
    for(ll i=2;i<=Limit;i++){
        if(prime[i]){
            for(ll j=2*i;j<=n;j++){
                if(j%i==0){
                    prime[j]=0;                
                }
            }
        }
    }
}

ll divisor(ll n){
    for(ll i=2;i<=n;i++){
        ll d=1;
        ll tmp=i;
        while(tmp>0){
            d++;
            while(tmp%d==0){
                prime[i]++;
                tmp/=i;
            }
        }
    }
    ll sum=1;
    for(ll i=2;;i<=n;i++){
        sum*=(prime[i]+1)/MOD;
    }    
    cout<<"sum="<<sum<<endl;

    return sum%MOD;
}
*/


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

const int MOD=1000000007;

int main() {
  int n;
  cin>>n;
  ll ans=1;
  rep(i, n) {
    ans*=(i+1);
    ans%=MOD;
  }
  cout<<ans<<endl;
}


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

x1=-(-a//0.08)
x2=-(-(a+1)//0.08)-1
y1=-(-b//0.10)
y2=-(-(b+1)//0.10)-1

if x1<=y1 and y1<=x2:
    print(int(y1))

elif y1<=x1 and x1<=y2:
    print(int(x1))


else:
    print(-1)

Measured memory_bytes: 38384
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <vector>
using namespace std;

struct Card{char suit,value;};

void print_table(struct Card A[],int N){
  for(int i=0;i<N;i++){
    cout << (i==0 ? "" : " ") << A[i].suit << A[i].value;
  }
  cout << endl;
}

void SelectionSort(struct Card A[],int N){
  int minj;
  Card buf;
  for(int i=0;i<N;i++){
    minj = i;
    for(int j=i;j<N;j++){
      if(A[minj].value>A[j].value){
        minj = j;
      }
    }
    if(i != minj){
      buf = A[i];
      A[i] = A[minj];
      A[minj] = buf;
      //sw++;
    }
  }
  //return sw;
}

void BubbleSort(struct Card A[], int N){
  Card buf;
  for(int i=0;i<N;i++){
    for(int j=N-1;j>=i+1;j--){
      if(A[j-1].value>A[j].value){
        buf = A[j];
        A[j] = A[j-1];
        A[j-1] = buf;
      }
    }
  }
}

bool isStable(struct Card A1[],struct Card A2[],int N){
  for(int i= 0;i<N;i++){
    if(A1[i].suit!=A2[i].suit){
      return false;
    }
  }
  return true;
}

int main(){
  int N;
  bool b;
  Card A1[100],A2[100];
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> A1[i].suit >> A1[i].value;
  }
  for(int i=0;i<N;i++){
    A2[i] = A1[i];
  }
  BubbleSort(A1,N);
  SelectionSort(A2,N);
  b = isStable(A1,A2,N);

  print_table(A1,N);
  cout << "Stable" << endl;
  print_table(A2,N);
  if(b){
    cout << "Stable" << endl;
  }else{
    cout << "Not stable" << endl;
  }
  return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

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

    int ans;
    if(N%1000 == 0) ans = 0;
    else ans = 1000 - N%1000;
    cout << ans << endl;
}

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

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 1e-9;

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

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

	cin >> N >> M;
	multiset<pair<int, int>>ms;
	for (int i = 0; i < M; i++) {
		cin >> L >> R;
		ms.insert({ R,L });
	}
	R = 0;
	int ans = 0;
	for (auto i : ms) {
		if (i.second > R) {
			ans++;
			R = i.first - 1;
		}
	}
	cout << ans << endl;
	return 0;
}


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

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)

using namespace std;

const int N = 100000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 31;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const double eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

/*
 * Problem A
 * @author citizen11
 * Good Integer
 */
int main()
{
	int n;
	cin >> n;

	int prev = -1;
	int count = 0;
	int max = 0;

	while (n > 0) {
		int rem = n % 10;
		if (prev == rem) count++;
		else count = 1;
		if (count > max) max = count;
		prev = rem;
		n /= 10;
	}

	if (max >= 3) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

MOD = 10**9
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

N = input()
if '7' in N: print('Yes')
else : print('No')


Measured memory_bytes: 9048
import bisect
from collections import defaultdict
N = int(input())
S = list(input())
Q = int(input())

dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        if S[b] == c:
            continue
        else:
            dict[S[b]].remove(b)
            idx = bisect.bisect_left(dict[c], b)
            dict[c].insert(idx, b)
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            if len(value)>0:
                x1 = bisect.bisect_left(value, b)
                x2 = bisect.bisect_right(value, c)
                if x2 - x1 > 0:
                    char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)


Measured memory_bytes: 126700
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define SZ size()
#define FOR(i, a, n) for(long long (i) = (a); (i) < (n); (i)++)
#define REP(i, n) FOR((i), 0, (n))
#define SHOW(v) cout << (v) << endl
#define SHOW2(a, b) cout << (a) << " " << (b) << endl
#define SHOW3(a, b, c) cout << (a) << " " << (b) << " " << (c) << endl
#define GET(v) cin >> (v)
#define GET2(a, b) cin >> (a) >> (b)
#define GET3(a, b, c) cin >> (a) >> (b) >> (c)
#define MOD 1000000007
template<class T> void GETV(T &v) { REP(i, v.size()) { GET(v[i]); } }
template<class T> void SHOWV(T &v) { REP(i, v.size()) { SHOW(v[i]); } }

typedef long long ll;

struct xyz {
    int p;
    ll y;
    int ind;
    int num;
};

int main()
{
    int n, m;
    GET2(n, m);
    
    vector<xyz> v(m);
    REP(i, m) {
        GET2(v[i].p, v[i].y);
        v[i].ind = i;
    }
    
    sort(ALL(v), [](const xyz &a, const xyz &b) {return a.y < b.y;});
    
    int a[n + 1];
    REP(i, n + 1) {
        a[i] = 0;
    }
    
    REP(i, m) {
        a[v[i].p]++;
        v[i].num = a[v[i].p];
    }
    
    sort(ALL(v), [](const xyz &a, const xyz &b) {return a.ind < b.ind;});
    
    REP(i, m) {
        cout << setw(6) << setfill('0') << v[i].p;
        cout << setw(6) << setfill('0') << v[i].num << endl;
    }
    
    return 0;
}



Measured memory_bytes: 4224
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(void)
{
    int n,i,a[200][3],j,b[200],d,l;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		for(j=0;j<3;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(i=0;i<n;i++){
		b[i]=0;
	}
	for(j=0;j<3;j++){
	    for(i=0;i<n;i++){
			d=0;
			for(l=0;l<n;l++){
			    if(a[i][j]==a[l][j]){
				    d++;
				}
			}
			if(d<2) b[i]+=a[i][j];
		}
	}
	for(i=0;i<n;i++){
	    printf("%d\n",b[i]);
	}
	return 0;
}

Measured memory_bytes: 2700
#include <bits/stdc++.h>
#include <unordered_map>
#define fast
#define mem(ara, a) memset(ara, a, sizeof(ara))
#define fo freopen("output.txt", "w", stdout)
#define fi freopen("bruh.txt", "r", stdin)
#define int long long
#define sp " "
#define pb push_back
#define ff first
#define sz(x) x.size();
#define len(x) x.length();
#define ss second
#define vi vector<int>
#define double long double
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define F(i, a, n) for (int i = a; i < n; i++)
#define Fr(i, n, a) for (int i = n; i >= a; i--)

long long inf = 2e18;
long long minf = -inf;

using namespace std;

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  int ans;
  if (k % 2 == 0)
  {
    int f = (n) / k;
    ans = (f * f * f);
    f=(n+k/2)/k;
    ans += (f * f * f);
  }
  else
  {
    int f = n / k;
    ans = (f * f * f);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        new Main().run();
    }

    FastScanner sc;

    void run() {
        sc = new FastScanner();
        String s = sc.next();
        System.out.print(s.substring(0, 4));
        System.out.print(" ");
        System.out.print(s.substring(4));
        System.out.print("\n");
        
    }

}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Measured memory_bytes: 8144
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main(){

    double x1, y1, x2, y2;
double ans;
    cin>>x1>>y1>>x2>>y2;
cout<<fixed<<setprecision(10);
   ans=sqrt(abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2)); 
cout<<ans<<endl;
}


Measured memory_bytes: 3284
/*
Author : Xinyuan
*/
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef long long int ll;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
ll powmod(ll a, ll b) {
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
int nxt() {
    int x;
    scanf("%d", &x);
    return x;
}

struct S {
    int w, s, v;
    void read() {
        cin >> w >> s >> v;
    }
    bool operator<(const S& b) const {
        return w + s < b.w + b.s;
    }
};

int main() {
    int n = nxt();
    vector<S> in(n);
    int MAX_S = 20123;
    REP(i, n)
    in[i].read();
    sort(all(in));
    vector<ll> dp(MAX_S + 1);
    for (S block : in) {
        for (int w = min(block.s, MAX_S - 1); w >= 0; --w) {
            dp[w + block.w] = max(dp[w + block.w], dp[w] + block.v);
        }
    }
    ll answer = 0;
    REP(i, MAX_S + 1)
    answer = max(answer, dp[i]);
    printf("%lld\n", answer);
    return 0;
}


Measured memory_bytes: 3796
from collections import defaultdict


def main():
    n, m = map(int, input().split())
    cs = defaultdict(list)
    for i in range(m):
        p, y = map(int, input().split())
        cs[p].append((y, i))

    res = []
    for p in cs.keys():
        cs[p].sort()
        for j, (y, i) in enumerate(sorted(cs[p])):
            res.append((i, "{:06d}{:06d}".format(p, j + 1)))

    for t in sorted(res):
        print(t[1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 52420
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
//printf("%.10f\n", N);
/*
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
    */
int main(){
    ll A,B,C;
    cin >> A>> B>>C;
    if(A == B && B == C && A % 2 == 0)cout << -1 << endl;
    else{
        ll cnt = 0;
        while(A % 2 == 0 && B % 2 == 0 && C % 2 == 0){
            ll a = A;
            ll b = B;
            A = B / 2 + C / 2;
            B = C / 2 + a / 2;
            C = a / 2 + b / 2;
            cnt++;
        }
        cout << cnt << endl;
    }
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val s = readLine()!!
    val (x, y) = readLine()!!.split(" ").map(String::toInt)
    val ds = s.split("T").map { it.length }
    val dxs = ds.withIndex().filter { it.index % 2 == 0 }.map { it.value }
    val dys = ds.withIndex().filter { it.index % 2 == 1 }.map { it.value }
    val xSet = calculateSet(dxs[0], dxs.slice(1 until dxs.size))
    val ySet = calculateSet(0, dys)
    println(if (x in xSet && y in ySet) "Yes" else "No")
}

fun calculateSet(init: Int, ds: List<Int>): Set<Int> {
    return ds.fold(setOf(init), { current_set, d ->
        current_set.toList().map { listOf(it - d, it + d) }.flatten().toSet()
    })
}

Measured memory_bytes: 119720
#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e5 ;
const int INF = 1e9 + 1e5 + 2;
const int mod= 1e9+7;
#define eps 1e-15
typedef long long ll;
int main()
{
    string s;

    cin>>s;

    bool a=0,b=0;
    for (int i=0; i<3; ++i)
    {
        if (s[i]=='B' && s[i+1]=='A')
            a=1;
        if (s[i]=='A' && s[i+1]=='B')
            a=1;
    }
    a?cout<<"Yes":cout<<"No";








}


Measured memory_bytes: 256
#include <algorithm>
#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()
#define ll long long
#define ld long double
#define INF 1000000000000000000
typedef pair<ll, ll> pll;

// i番目まで選んだ時、合計jで、枚数kの時があるか
ll dp[55][2505][55];

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

    int N, A;
    cin >> N >> A;
    vector<ll> x(N);
    rep(i, N) { cin >> x[i]; }

    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;

    rep(i, N) {
        rep(j, 2505) {
            rep(k, N) {
                // i番目を選ぶ
                dp[i + 1][j + x[i]][k + 1] += dp[i][j][k];
                // i番目を選ばない
                dp[i + 1][j][k] += dp[i][j][k];
            }
        }
    }

    ll ans = 0;
    rep(j, 2505) {
        for (int k = 1; k <= N; k++) {
            if (j == k * A)
                ans += dp[N][j][k];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 62804
#include <bits/stdc++.h>
using namespace std;
#define mid ((s + e) / 2)
#define makefast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define comp(x) (lower_bound(vec.begin(), vec.end(), x) - vec.begin())
#define lc (v * 2)
#define rc (v * 2 + 1)
long long M = 1e9 + 7;
//>>>>>>>>>>>>>>>>>>>>>>>

#define int long long

const int N = 1e5 + 7;

int d[N];
int n, sz[N];
map <int, int> who;
vector <int> ad[N];
int sm = 0;

void dfs(int v, int p = 0, int dis = 0) {
	sm += dis;
	for (auto u: ad[v])
		if (u != p)
			dfs(u, v, dis + 1);
}

int32_t main() {
	makefast;
	cin >> n;
	set <int> s;
	for (int i = 1; i <= n; i++) {
		cin >> d[i];
		who[d[i]] = i;
		s.insert(-d[i]);
		sz[i] = 1;
	}
	while (s.size() > 1) {
		int dis = -*s.begin();
		s.erase(-dis);
		int v = who[dis];
		dis += 2 * sz[v] - n;
		if (!who[dis]) {
			cout << -1;
			return 0;
		}
		int u = who[dis];
	//	cout << v << " <> " << u << " " << dis << endl;
		ad[v].push_back(u);
		ad[u].push_back(v);
		sz[u] += sz[v];
	}
	dfs(1);
	if (d[1] != sm) {
		cout << -1;
		return 0;
	}
	for (int i = 1; i <= n; i++)
		for (auto j: ad[i])
			if (i < j)
				cout << i << ' ' << j << '\n';


}


Measured memory_bytes: 23172
#include<bits/stdc++.h>
#define ull unsigned long long
# define ll long long
# define mod 1000000007LL 
using namespace std;
int main()
{
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll arr[n];
    for(int i=0;i<n;i++)
    cin>>arr[i];
    sort(arr,arr+n,greater<ll>());
    ll sum=arr[0];
    ll count=0;
    ll index=1;
    for(int i=0;i<n-2;i++)
    {
        if(count==0 || count==1)
        {
        sum+=arr[index];
        count++;
        }
        else
        {
            count=1;
            index++;
            sum+=arr[index];

        }
        

    }
    cout<<sum;


    
    return 0;
}

Measured memory_bytes: 5204
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define MAX_V 400010
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<typename A, size_t NNN, typename T>
void Fill(A (&array)[NNN], const T &val){
    fill( (T*)array, (T*)(array+NNN), val );
}
#define INF 1e9+7
#define LLINF 1e18+7
ll MOD=1e9+7;
#define N 3000000
ll n,m,k;
ll a[N];
ll b[N];
ll dp[N][2];
vec G[N];
void dfs(int x,int p){
    ll ans=1;
    rep(i,G[x].size()){
        if(G[x][i]!=p){
            dfs(G[x][i],x);
            ans=(ans*((dp[G[x][i]][0]+dp[G[x][i]][1])%MOD))%MOD;
        }
    }
    dp[x][0]=ans;
    ans=1;
    rep(i,G[x].size()){
        if(G[x][i]!=p)ans=(ans*dp[G[x][i]][0])%MOD;
    }
    dp[x][1]=ans;
}
int main(){
    n=in();
    rep(i,n-1){
        int x=in(),y=in();
        G[x].pb(y);G[y].pb(x);
    }
    dfs(1,0);
    cout<<(dp[1][0]+dp[1][1])%MOD;
    return 0;
}

Measured memory_bytes: 84096
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

long long mod_pow(long long a, long long b) {
	long long res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}

	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

//↑template↑


int main() {
	long long a, b, ans = INF, k[105], l[105];
	cin >> a >> b;
	for (int i = 0; i < a; ++i) {
		cin >> k[i] >> l[i];
		if (l[i] <= b) ans = min(ans, k[i]);
	}
	if (ans == INF) cout << "TLE" << endl;
	else cout << ans << endl;
}

Measured memory_bytes: 256
#include "iostream"
#include "iomanip"
#include "math.h"

using namespace std;

static const double rad60 = 60.0 * 3.141592 / 180.0;

struct Pos {
	double x, y;
};

void solve( int n, int d, Pos start, Pos end ) {

	Pos p[5];

	p[0].x = start.x;
	p[1].x = ( end.x + start.x*2 ) / 3;
	p[3].x = ( end.x*2 + start.x ) / 3;
	p[4].x = end.x;

	p[0].y = start.y;
	p[1].y = (end.y + start.y*2) / 3;
	p[3].y = (end.y*2 + start.y) / 3;
	p[4].y = end.y;

	p[2].x = (p[3].x - p[1].x)*cos(rad60) - (p[3].y - p[1].y)*sin(rad60) + p[1].x;
	p[2].y = (p[3].x - p[1].x)*sin(rad60) + (p[3].y - p[1].y)*cos(rad60) + p[1].y;

	if (n == d + 1) {
		for (int i = 0; i < 4; i++) {
			cout << fixed << setprecision(8) << p[i].x << " "
				 << fixed << setprecision(8) << p[i].y << endl;
		}
	}
	else {
		for (int i = 0; i < 4; i++) {
			solve(n, d + 1, p[i], p[i + 1]);
		}
	}
	
}

int main() {

	int n;
	cin >> n;

	Pos s, e;

	s.x = 0;
	s.y = 0;
	e.x = 100;
	e.y = 0;
	if (n == 0) {
	cout << fixed << setprecision(8) << s.x << " " 
		 << fixed << setprecision(8) << s.y << endl;
	cout << fixed << setprecision(8) << e.x << " " 
		 << fixed << setprecision(8) << e.y << endl;

	}
	else {
		solve(n, 0, s, e);

		cout << fixed << setprecision(8) << e.x << " "
			 << fixed << setprecision(8) << e.y << endl;
	}
	return 0;
}

Measured memory_bytes: 1248
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.D
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var C = ReadText();

            var l = 0;
            var r = (int)N - 1;
            var count = 0;
            while (l < N && r >= 0 && l <= r)
            {
                while (C[l] != 'W' && l != r)
                {
                    l++;
                }
                while (C[r] != 'R' && l != r)
                {
                    r--;
                }

                if (l == r) break;

                count++;
                l++;
                r--;
            }

            return count;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 28240