akhauriyash/Code-Regression huggingface dataset:
s = input()
q = int(input())
Q = [input().split() for _ in range(q)]

import collections
dq = collections.deque(s)

rev = 1
for i in Q:
    if i == ['1']:
        rev *= -1
    else:
        if (i[1] == '1' and rev == 1) or (i[1] == '2'and rev == -1):
            dq.appendleft(i[2])
        else:
            dq.append(i[2])

if rev == 1:
    print(''.join(dq))
else:
    print(''.join(dq)[::-1])


Measured memory_bytes: 44660
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    String alphabet = "abcdefghijklmnopqrstuvwxyz";

    String inputString = sc.next();
    char inputChar = inputString.charAt(0);

    for(int i = 0; i < alphabet.length(); i++){
      if( alphabet.charAt(i) == inputChar ){
        System.out.println( alphabet.charAt(i+1) );
        break;
      }
    }
  }
}

Measured memory_bytes: 21844
import java.util.*;
import java.math.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		while(sc.hasNextBigDecimal()){
			BigDecimal a=sc.nextBigDecimal(), b=sc.nextBigDecimal();
			int n=sc.nextInt();
			String d=a.divide(b,n+2,0).toPlainString();

			int i=0, ans=0;
			while(d.charAt(i) != '.') i++;
			while(n-- > 0) ans += d.charAt(++i) - '0';
			System.out.println(ans);
		}
	}
}

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

const int MOD = (int)1e9+7;

int main(){
	int N;
	cin >> N;
	vector<vector<int>> F(N,vector<int>(10));
	for(int i=0;i<N;i++){
		for(int j=0;j<10;j++){
			cin >> F.at(i).at(j);
		}
	}
	vector<vector<int>> P(N,vector<int>(11));
	for(int i=0;i<N;i++){
		for(int j=0;j<11;j++){
			cin >> P.at(i).at(j);
		}
	}

	int ans=-1e9;
	for(int bit=1;bit<(1<<10);bit++){
		int sum=0;
		for(int i=0;i<N;i++){
			int count=0;
			for(int j=0;j<10;j++){
				if((bit&(1<<j)) && F.at(i).at(j)==1)	count++;
			}
			sum+=P.at(i).at(count);
		}
		ans=max(ans,sum);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
a,b,c = gets.chomp.split(' ').map(&:to_i)
k = gets.chomp.to_i

m = [a, b, c].max
if m == a then
  puts (a * (2 ** k) + b + c).to_s
elsif m == b then
  puts (a + b * (2 ** k) + c).to_s
else
  puts (a + b + c * (2 ** k)).to_s
end

Measured memory_bytes: 1788
#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <cmath>
#define INF 100000000000
#define MOD 1000000007
#define ll long long int
//#define int long long int
using namespace std;

int main(){
   int n; cin>>n;
   int ans=0;
   vector <int> p; p.resize(n,0);
   for(int i=0;i<n;i++) cin>>p[i];

   for(int i=1;i<=n-1-1;i++){
       if(p[i-1] < p[i] and p[i] < p[i+1]){ans++;continue;}
          if(p[i-1] > p[i] and p[i] > p[i+1]){ans++;continue;}
   }

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



Measured memory_bytes: 256
use proconio::input;
use proconio::marker::Chars;
use proconio::marker::Usize1;
use std::collections::VecDeque;

fn main() {
    input! {
        h: usize,
        w: usize,
        ch: Usize1,
        cw: Usize1,
        dh: Usize1,
        dw: Usize1,
        maze: [Chars; h],
    }

    let mut dist = vec![vec![std::usize::MAX / 2; w]; h];
    if let Some(num) = bfs01((ch, cw), (dh, dw), &maze, &mut dist) {
        println!("{}", num);
    } else {
        println!("{}", -1);
    }
}

fn bfs01(
    start: (usize, usize),
    goal: (usize, usize),
    maze: &Vec<Vec<char>>,
    dist: &mut Vec<Vec<usize>>,
) -> Option<usize> {
    let height = maze.len();
    let width = maze[0].len();

    let dx = vec![1, 0, -1, 0];
    let dy = vec![0, 1, 0, -1];

    let mut que = VecDeque::new();
    que.push_back(start);
    dist[start.0][start.1] = 0;

    //xとyが通常の想定と逆（汗
    while !que.is_empty() {
        let current_pos = que.pop_front().unwrap();
        let x = current_pos.0 as i32;
        let y = current_pos.1 as i32;
        let d = dist[x as usize][y as usize];

        for i in 0..4 {
            let next_x = x + dx[i];
            let next_y = y + dy[i];
            if next_x < 0 || next_x >= height as i32 || next_y < 0 || next_y >= width as i32 {
                continue;
            }
            if maze[next_x as usize][next_y as usize] == '#' {
                continue;
            }
            if dist[next_x as usize][next_y as usize] <= d {
                continue;
            }
            dist[next_x as usize][next_y as usize] = d;
            que.push_front((next_x as usize, next_y as usize));
        }

        for i in -2..3 {
            for j in -2..3 {
                let next_x = x + i;
                let next_y = y + j;
                if next_x < 0 || next_x >= height as i32 || next_y < 0 || next_y >= width as i32 {
                    continue;
                }
                if maze[next_x as usize][next_y as usize] == '#' {
                    continue;
                }
                if dist[next_x as usize][next_y as usize] <= d + 1 {
                    continue;
                }
                dist[next_x as usize][next_y as usize] = d + 1;
                que.push_back((next_x as usize, next_y as usize));
            }
        }
    }

    let ans = dist[goal.0][goal.1];
    if ans == std::usize::MAX / 2 {
        return None;
    } else {
        return Some(ans);
    }
}


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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            Scanner cin = new Scanner();
            long Q = cin.Long();
            long H = cin.Long();
            long S = cin.Long();
            long D = cin.Long();
            long N = cin.Long();

            long[] price = { 8 * Q, 4 * H, 2 * S, D };
            Array.Sort(price);
            long ans = price[0] * (N / 2);
            N -= 2 * (N / 2);

            long[] rest_price = { 4 * Q, 2 * H, S };
            Array.Sort(rest_price);
            ans += N > 0 ? rest_price[0] : 0;
           
            Console.WriteLine(ans);
            Console.ReadLine();
        }
    }

    class Scanner //標準入力
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int Int()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = Int() + add;
            }
            return Array;
        }

        public long Long()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = Long() + add;
            }
            return Array;
        }

        public double Double()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = Double() + add;
            }
            return Array;
        }
    }
}



Measured memory_bytes: 13268
until ((n = gets.chomp.to_i) == 0)
    numbers = gets.chomp.split.map(&:to_i)
    mean = numbers.inject(:+) / n.to_f
    squares = numbers.map{|n| n ** 2}
    ss = squares.inject(:+)
    sd = Math.sqrt(ss / n.to_f - mean ** 2)
    printf("%.5f\n", sd)
end

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

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end())
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint=vector<int>;
using vvint=vector<vint>;
using pint=pair<int, int>;
using vpint=vector<pint>;
template<typename T> using priority_queue_rev=priority_queue<T, vector<T>, greater<T>>;
constexpr double pi = 3.1415926535897932384626433832795028L;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T1, typename T2> bool chmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> bool chmin(T1 &a, const T2 &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int A, B;
signed main() {
    cin >> A >> B;
    if (A >= 13) { cout << B << endl; }
    else if (A >= 6) { cout << B / 2 << endl; }
    else { cout << 0 << endl; }
}


Measured memory_bytes: 256
A = list(map(int , input().split()))
if A[0] == A[1] and A[0] != A[2]:
    print('Yes')
elif A[0] == A[2] and A[0] != A[1]:
    print('Yes')
elif A[1] == A[2] and A[1] != A[0]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include<cmath>
using namespace std;

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

    sort(a.begin(), a.end());
    int p = a[n-1];
    vector<long> b(n);
    double mm = INT_MAX;
    int q;
    for (int j = 0; j < n; ++j) {
        if(abs(a[j] - p/2.0) < mm) {
            mm = abs(1.0 * a[j] - p/2.0);
            q = a[j];
        }
    }
    cout << p << " " << q << endl;

    return 0;
}


Measured memory_bytes: 1792
def main():
    N = int(input())
    A = []
    A.append(list(map(int, input().split())))
    A.append(list(map(int, input().split())))
    max_sum = A[0][0] + sum(A[1])
    left_sum = max_sum
    for i in range(0, N-1):
        left_sum += A[0][i+1] - A[1][i]
        if left_sum > max_sum:
            max_sum = left_sum
    print(max_sum)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
package main

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

var (
	read  = bufio.NewReader(os.Stdin)
	write = bufio.NewWriter(os.Stdout)
)

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

func yesno(result bool) {
	if result {
		fmt.Fprintln(write, "Yes")
	} else {
		fmt.Fprintln(write, "No")
	}
}

func printansStr(result bool, a, b string) {
	if result {
		fmt.Fprintln(write, a)
	} else {
		fmt.Fprintln(write, b)
	}
}

func printansInt(result bool, a, b int) {
	if result {
		fmt.Fprintln(write, a)
	} else {
		fmt.Fprintln(write, b)
	}
}

func main() {
	defer write.Flush()

	var n int
	fmt.Fscan(read, &n)

	h := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(read, &h[i])
	}

	pre := int(1e9) + 1
	cnt := 0
	ans := 0
	for i := n - 1; i >= 0; i-- {
		if h[i] < pre {
			cnt = 0
		} else {
			cnt++
		}
		pre = h[i]
		if ans < cnt {
			ans = cnt
		}
	}
	fmt.Fprintln(write, ans)

}


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

int main(){
	int N;
	cin >> N;
	vector<int> A(N);
	for(int i = 1; i < N; i++)
		cin >> A.at(i);

	vector<int> X(N, 0);
	for(int i = 1; i < N; i++)
		X.at(A.at(i)-1)++;

	for(int i = 0; i < N; i++)
		cout << X.at(i) << endl;

	return 0;	
}

Measured memory_bytes: 4776
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll PowerOFPINnfactorial(ll n, ll p) { 
    ll ans = 0; 
  
    ll temp = p; 
  
    while (temp <= n) { 
  
        ans += n / temp; 
  
        temp = temp * p; 
    } 
    return ans; 
} 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    ll i,j,k,n,r;

    cin>>n;
    if(n%2!=0){
        cout<<0<<"\n";
    }
    else{
        n=n/2;
        r=PowerOFPINnfactorial(n,5);
        cout<<r<<"\n";
    }



    return 0;
}

Measured memory_bytes: 256
require 'set'

N, M = gets.split.map(&:to_i)

s = Set.new
e = Set.new

M.times do |i|
  a, b= gets.split.map(&:to_i)
  s << b if a == 1
  e << a if b == N
end

puts ( s & e ).size > 0 ? "POSSIBLE" : "IMPOSSIBLE"

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

int main(){
  cin.tie(0);
 	ios::sync_with_stdio(false);
  int N;
  string S;
  cin >> N >> S;
  int idx = 0;
  int ans = 0;
  while(idx + 1 < N){
    if(S[idx] != S[idx + 1]){
      idx += 2;
      ans++;
    }else{
      idx++;
    }
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 3336
#include <iostream>
#include <cstdio>
using namespace std;
long long a, b, c;
int main() {
    cin >> a >> b >> c;
    if (c - (a + b) < 0) puts("No");
    else {
        if (4 * a * b < a * a + b * b + c * c - 2 * a * c - 2 * b * c + 2 * a * b) puts("Yes");
        else puts("No");
    }
    return 0;
}


Measured memory_bytes: 256
//There was and will always be only one Chester
//RIP legend
#include<bits/stdc++.h>
#define Nilesh ios_base::sync_with_stdio(false)
using namespace std;
int main()
{
    Nilesh;
   string a;
   cin>>a;
   int l=a.length();
   for(int i=0;i<l;i++)
   {
       if(i%2==0)
        cout<<a[i];
   }
}


Measured memory_bytes: 592
# ABC070C - Multiple Clocks
from fractions import gcd


def main():
    N = int(input())
    T = tuple(map(int, [input() for _ in range(N)]))
    ans = 1
    for i in T:
        ans = ans // gcd(ans, i) * i
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 5048
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
#include<functional>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

ll N = 100010;
ll bit[100010];
void add(ll a, ll w) {
	a++;
	for (ll x = a; x <= N; x += x & -x) bit[x] += w;
}
ll sum(ll a) {
	a++;
	ll ret = 0;
	for (ll x = a; x > 0; x -= x & -x) ret += bit[x];
	return ret;
}
// return the sum of [a, b)
ll sum(ll a, ll b) {
	ll ret = 0;
	if(b == 0) return 0;
	ret += sum(b - 1);
	if(a) ret -= sum(a - 1);
	return ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	vector<ll> cons(n, -1);
	REP(i, n) cons[i] = i;
	REP(i, m) {
		ll l, r;
		cin >> l >> r;
		l--; r--;
		cons[l] = max(cons[l], r);
	}
	ll tmp = -1;
	REP(i, n) {
		if(cons[i] > tmp) {
			tmp = cons[i];
		} else cons[i] = -1;
	}
	REP(i, n) if(s[i] == '1') add(i, 1);
	tmp = -1; // どこまで見た
	vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 0));
	dp[0][0] = 1;
	REP(i, n) {
		ll diff = 0;
		if(cons[i] != -1) {
			diff += sum(tmp + 1, cons[i] + 1);
			tmp = cons[i];
		}
		REP(j, n + 1) {
			dp[i][j] %= MOD;
			ll one = j + diff;
			if(one) dp[i + 1][one - 1] += dp[i][j];
			if(tmp - i + 1 > one) dp[i + 1][one] += dp[i][j];
		}
	}
	cout << dp[n][0] % MOD << endl;
	return 0;
}

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


Measured memory_bytes: 70784
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, A, B, C = read_values()
    res = "Yes\n"
    SS = [input().strip() for _ in range(N)]
    i = 0
    for i, S in enumerate(SS):
        if S == "AB":
            if A == 0 and B == 0:
                print("No")
                return

            if A == 1 and B == 1 and C == 0 and i != N - 1:
                T = SS[i + 1]
                if T == "AC":
                    res += "A\n"
                    A += 1
                    B -= 1 
                    continue

            if A >= B:
                res += "B\n"
                A -= 1
                B += 1
            else:
                res += "A\n"
                A += 1
                B -= 1

        elif S == "BC":
            if C == 0 and B == 0:
                print("No")
                return

            if A == 0 and B == 1 and C == 1 and i != N - 1:
                T = SS[i + 1]
                if T == "AC":
                    res += "C\n"
                    C += 1
                    B -= 1 
                    continue

            if C >= B:
                res += "B\n"
                C -= 1
                B += 1
            else:
                res += "C\n"
                C += 1
                B -= 1

        elif S == "AC":
            if A == 0 and C == 0:
                print("No")
                return

            if A == 1 and B == 0 and C == 1 and i != N - 1:
                T = SS[i + 1]
                if T == "AB":
                    res += "A\n"
                    A += 1
                    C -= 1 
                    continue

            if A >= C:
                res += "C\n"
                A -= 1
                C += 1
            else:
                res += "A\n"
                A += 1
                C -= 1

    print(res)


if __name__ == "__main__":
    main()


Measured memory_bytes: 17328
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<map>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
#define sort(s) sort(s.begin(),s.end())
#define r(s) reverse(s.begin(),s.end())
#define please return
constexpr auto AC = 0;
using namespace std;
int main(){
	int a, b, ans;
	cin >> a >> b;
	ans = max(a - b, max(a + b, a * b));
	cout << ans << endl;
		please AC;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(v) v.begin(), v.end()
#define ll long long
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<long long>;
using vvll = vector<vll>;

//snippets:tmp,cl,cvl,cs,co,coy,con,cov

int main(){
    ll n;
    cin >> n;
    ll m;
    cin >> m;
    ll count=0;
    ll a;
    rep(i,m){
        cin>>a;
        count+=a;
    }
    if(count<=n) cout<<n-count<<endl;
    else cout<<-1<<endl;
}

Measured memory_bytes: 3636
N = int(input())
A = list(map(int, input().split()))+[0]

su = 0
ans = 0
right = 0

for left in range(N):
    while (left == right or su+A[right] == su^A[right]) and right < N:
        su += A[right]
        right += 1
    ans += right-left
    su -= A[left]
print(ans)

Measured memory_bytes: 32192
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <math.h>
#include <cmath>
#include <numeric>
#include <iomanip>


#define log(x) cout<<x<<endl
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
using namespace std;


// <<fixed<<setprecision(6)<<


int gcd(lint x, lint y){
  return y==0 ? x:gcd(y,x % y);
}


int combi(int n, int r){
  int num = 1;
  for(int i = 1; i <= r; i++){
    num = num * (n - i + 1) / i;
  }
  return num;
}


int main(){
  int n;
  cin>>n;
  vector<int> l;
  for(int i=0;i<n;i++){
    int j;
    cin>>j;
    l.pb(j);
  }
  sort(all(l),greater<int>());
  int count=1;
  int result=0;
  for(int i=0;i<n;i++){
    if(l[i]>=count){
      result++;
    }
    else{
      break;
    }
    count++;
  }
  cout<<result<<endl;

}



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

ll pri[101010];
class ABCount{
    public:
    vector<ll>v;
    set<pair<ll, ll> >S;
    ll makeFlg;
    ll Inf;
    ABCount(ll inf = 1145141919){
        Inf = inf;
        makeFlg = 0;
    }
    void push(ll a){
        v.push_back(a);
    }
    void make(){
        makeFlg = 1;
        S.clear();
        sort(v.begin(), v.end());
        for(ll i = 0; i < v.size(); i++){
            S.insert(pair<ll, ll>(v[i], i));
        }
        S.insert(pair<ll,ll>(Inf, v.size()));
    }
    ll count(ll a, ll b){
        if(a > b)return 0;
        if(makeFlg == 0)make();
        return (*S.upper_bound(pair<ll,ll>(b, Inf))).second - (*S.lower_bound(pair<ll,ll>(a, 0))).second;
    }
};
int main(){
    for(ll i = 2; i < 101010; i++)pri[i] = 1;
    for(ll i = 2; i * i < 101010; i++){
        for(ll j = i + i; j < 101010; j += i)pri[j] = 0;
    }
    ABCount abc;
    for(ll i = 2; i + 1 < 101010; i++){
        if(pri[i] && pri[(i + 1)/2])abc.push(i);
    }
    ll Q;
    cin >> Q;
    for(ll i = 0; i < Q; i++){
        ll l , r;
        cin >> l >> r;
        cout << abc.count(l, r) << endl;
    }
    
    
    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
  string w;
  cin >> w;
  int cnt = 0;
  bool flag = true;
  for (int j=0;j<w.length();j++) {
    for (int i = 0; i < w.length(); i++) {
      if (w[j] == w[i]) cnt++;
    }

    if (cnt % 2 != 0) {
      flag = false;
      break;
    }
  }

  if (flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
  public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);
     int scnt = 0;
     int tcnt = 0;
     String X = sc.next();
     for (int i = 0 ; i < X.length(); i++) {
        if (X.charAt(i) == 'S') {
          scnt++;
        } else if (scnt > 0 && X.charAt(i) == 'T') {
          scnt--;
        } else {
          tcnt++;
        }
     }
     System.out.println(scnt + tcnt);
  }
}


Measured memory_bytes: 26296
/*
                ____________    ______________       __
               / _________  /\ /_____   _____/\     / /\
              / /\       / /  \\    /  /\    \ \   / /  \
             / /  \_____/ /   / \__/  /  \____\/  / /   /
            / /   /    / /   /    /  /   /       / /   /
           / /   /    / /   /    /  /   /       / /   /
          / /   /    / /   /    /  /   /       / /   /
         / /___/____/ /   /    /  /   /       / /___/________
        /____________/   /    /__/   /       /______________/\
        \            \  /     \  \  /        \              \ \
         \____________\/       \__\/          \______________\/
           ___       ___               ___    __________
          /  /\     /  /\             /  /\  /_______  /\
         /  /__\___/  /  \           /  /  \ \      /  /  \
        /____    ____/   /          /  /   /  \____/  /   /
        \   /   /\   \  /          /  /   /       /  /   /
         \_/   /  \___\/ ___      /  /   /       /  /   /
          /   /   /     /  /\    /  /   /       /  /   /
         /   /   /     /  /__\__/  /   /       /  /___/____
        /___/   /     /___________/   /       /___________/\
        \   \  /      \           \  /        \           \ \
         \___\/        \___________\/          \___________\/
       
          A FAN OF FIZZYDAVID
           
*/

#include<bits/stdc++.h>

#define HEAP priority_queue
#define rep(i,n) for(int i=0;i<(n);i++)
#define per(i,n) for(int i=(n)-1;i>=0;i--)
#define forn(i,l,r) for(int i=(l);i<=(r);i++)
#define nrof(i,r,l) for(int i=(r);i>=(l);i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define X first
#define Y second
#define eps 1e-20
#define pi 3.1415926535897932384626433832795
#define orz int
#define yjz main
#define fizzydavid return
#define ak 0
#define la ;
#define debug puts("OK");
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()

using namespace std;

typedef long long LL;
typedef double flt;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int iinf=1e9+7;
const LL linf=1ll<<60;
const flt dinf=1e10;

template <typename T>
inline void scf(T &x)
{
	bool f=0; x=0; char c=getchar();
	while((c<'0' || c>'9') && c!='-') c=getchar();
	if(c=='-') { f=1; c=getchar(); }
	while(c>='0' && c<='9') { x=x*10+c-'0'; c=getchar(); }
	if(f) x=-x; return;
}

template <typename T1,typename T2>
void scf(T1 &x,T2 &y) { scf(x); return scf(y); }

template <typename T1,typename T2,typename T3>
void scf(T1 &x,T2 &y,T3 &z) { scf(x); scf(y); return scf(z); }

//---------------------------head----------------------------

const int N=2e5+100;

int n,n2;
int a[N],b[N];

inline bool check(int mid)
{
	forn(i,1,n2) b[i]=(a[i]>=mid);
	forn(i,1,n-1)
	{
		if(b[n-i]==b[n-i+1]) return b[n-i];
		if(b[n+i-1]==b[n+i]) return b[n+i];
	}
	return b[1];
}

orz yjz()
{
	scf(n); n2=(n<<1)-1;
	forn(i,1,n2) scf(a[i]);
	int l=1,r=n2;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid)) l=mid+1; else r=mid-1;
	}
	printf("%d\n",r);
	fizzydavid ak la
}

Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main(){
  int n;
  long long int a[100001], b[100000], sum=0;
  cin >> n;
  for(int i=0; i<n+1; i++)cin >> a[i];
  for(int i=0; i<n; i++)cin >> b[i];
  for(int i=0; i<n; i++){
    if(a[i] >= b[i]){
      sum += b[i];
    }else{
        sum += a[i];
        b[i] -= a[i];
        if(a[i+1]>=b[i]){
            sum += b[i];
            a[i+1] -= b[i];
        }else{
            sum += a[i+1];
            a[i+1] = 0;
        }
    }
  }
  cout << sum << endl;
  return 0;
}
  

Measured memory_bytes: 1792
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#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(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
//typedef ll 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-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n;
	cin>>n;
	string q="MARCH";
	vi co(5);
	rep(i,n){
		string a;
		cin>>a;
		rep(j,5)if(a[0]==q[j])co[j]++;
	}
	ll out=0;
	rep(i,5)loop(j,i+1,5)loop(k,j+1,5)out+=(ll)co[i]*co[j]*co[k];
	cout<<out<<endl;
}












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();
        
        if(N >= 3200) {
            System.out.println(s);
        }else {
            System.out.println("red");
        }
    }
}

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


int main(void) {
    using namespace std;

    long a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    long s = 0;
    int aa, bb, cc, dd;
    double den = -1, g = 0, h = 0;
    for(aa=0; s <= f; aa++, s += 100*a) {
        for(bb=0; s <= f; bb++, s += 100*b) {
            for(cc=0; s <= f; cc++, s += c) {
                for(dd=0; s <= f; dd++, s += d) {
                    if((aa*a + bb*b)*e >= cc*c + dd*d) {
                        if(1.0*(cc*c+dd*d)/s > den) {
                            den = 1.0*(cc*c+dd*d)/s;
                            g = s;
                            h = cc*c + dd*d;
                        }
                    }
                }
                s -= d*dd;
            }
            s -= c*cc;
        }
        s -= 100*b*bb;
    }
    s -= 100*a*aa;

    cout << g << ' ' << h << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define elif else if
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;
#define int long long

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;

const int arr=2e5+10;
const int ar=2e3+10;
const ld pi=acos(-1);
const ld eps=1e-10;
const ll md=1e9+7;

///---program start---///

int t[arr];
int x[arr];
int y[arr];

main()
{
    #ifdef I_love_Maria_Ivanova
        files("barik");
        freopen("debug.txt","w",stderr);
    #endif

    int n;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>t[i]>>x[i]>>y[i];
    }
    for (int i=1;i<=n;i++){
        int dist=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
        if (dist>t[i]-t[i-1]){
            return cout<<"No"<<"\n", 0;
        }
        if (dist%2!=(t[i]-t[i-1])%2){
            return cout<<"No"<<"\n", 0;
        }
    }
    cout<<"Yes"<<"\n";
}


Measured memory_bytes: 3584
H, W = [int(i) for i in input().split()]
while (H != 0) and (W != 0):
    e = '#' * W
    m = ('\n' + '#' + '.' * (W-2) + '#') * (H-2)
    print('{0}{1}\n{0}\n'.format(e, m))
    H, W = [int(i) for i in input().split()]


Measured memory_bytes: 5644
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD 1000000007
#define MOD2 998244353
#define MOD3 1000000009
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
//ifstream cinn("in.in");ofstream coutt("out.out");
int poww(const int &a,int b,const int &m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;}
int ceil(const int &a,const int &b){return (a+b-1)/b;}
////Read:
//Check corner cases, n==1;
//
////Some function:
//__builtin_popcountll(), is_sorted(),


signed main(){
    FASTER;
    int n,d;cin>>n>>d;
    int cnt=0;
    for(int i=0;i<n;i++){
        int x,y;cin>>x>>y;
        cnt+=(x*x+y*y<=d*d);
    }
    cout<<cnt;
}



Measured memory_bytes: 3692
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
a.sort()
m = sum(a) / n
if n % 2 == 0:
  print(2*sum(a[n//2+1:])-2*sum(a[:n//2-1])-a[n//2-1]+a[n//2])
else:
  print(max(2*sum(a[n//2+1:])-2*sum(a[:n//2-1])-a[n//2-1]-a[n//2],2*sum(a[n//2+2:])-2*sum(a[:n//2])+a[n//2]+a[n//2+1]))

Measured memory_bytes: 7504
from collections import deque
def main():
    H,W = map(int, input().split())
    road = [[False]*W for _ in range(H)]
    arrived = [[False]*W for _ in range(H)]
    que = deque([]) # BFS:appendleftとpopでキュー
    origWhite = 0
    for i in range(H):
        c = input()
        for j in range(W):
            if c[j]=='.':
                road[i][j] = True
                origWhite += 1
            else:
                que.append((i,j))
                arrived[i][j] = True

    if origWhite<=0:
        print(0)
        return

    directions = [(1,0),(0,1),(-1,0),(0,-1)] # 東西南北に移動可能
    depth = [[0]*W for _ in range(H)]
    while que:
        x1,y1 = que.pop()
        for dx,dy in directions:
            x2,y2 = x1+dx,y1+dy
            # 枠外
            if x2<0 or H<=x2 or y2<0 or W<=y2:
                continue
            # 壁
            if not road[x2][y2]:
                continue
            # 探索済み
            if arrived[x2][y2]:
                continue
            que.appendleft((x2,y2))
            arrived[x2][y2] = True
            origWhite -= 1
            depth[x2][y2] = depth[x1][y1]+1
            if origWhite<=0:
                print(depth[x2][y2])
                return


main()


Measured memory_bytes: 99800
N = int(input())
l,r,lr = 0,0,0
ans = 0
for i in range(N):
    s = input()
    if s[0] == "B" and s[-1] == "A":
        lr += 1
    elif s[0] == "B":
        l += 1
    elif s[-1] == "A":
        r += 1
    for j in range(len(s)-1):
        string = s[j]+s[j+1]
        if string == "AB":
            ans += 1
if lr > 0:
    ans += lr-1
    if l>0 and r>0:
        ans += 2
        l -= 1
        r -= 1
        ans += min(l,r)
    elif (r == 0 or l == 0) and not (r==l==0):
        ans += 1
else:
    ans += min(l,r)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
    string a,b ,inp;
    int c,d;
    cin >> a>>b>>c>>d>>inp;
    if(inp == a){
        cout<< c-1 << " " << d;
    }
    else{
        cout<< c << " " << d-1;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <ctype.h>
#include <string.h>

using namespace std;

int main(){
  string a, b, c, str;
  cin >> a >> b >> c;
  str += toupper(*a.c_str());
  str += toupper(*b.c_str());
  str += toupper(*c.c_str());
  cout << str << endl;
}

Measured memory_bytes: 256
import math
from functools import reduce


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def lcm(numbers):
    return reduce(lcm_base, numbers, 1)


def solve():
    N, M = [int(x) for x in input().split()]
    S = input()
    T = input()

    L = lcm([N, M])
    ic, jc = 0, 0
    i, j = ic * L // N + 1, jc * L // M + 1
    ans = L
    while ic < N and jc < M:
        # print(i, j, ic, jc, S[ic], S[jc])
        if i == j:
            if S[ic] != T[jc]:
                ans = '-1'
                break
            ic += 1
            jc += 1
            i = ic * L // N + 1
            j = jc * L // M + 1
        elif i < j:
            ic += 1
            i = ic * L // N + 1
        elif i > j:
            jc += 1
            j = jc * L // M + 1
    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 74436
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;

typedef long long ll;

#define MOD 1000000007

const int MAX = 2000001;
ll fac[MAX], finv[MAX], inv[MAX];

int main(int argc, char **argv)
{
    int X, Y;
    cin >> X >> Y;
    // a: (i+1, j+2), b: (i+2, j+1)
    // a + 2b = X, 2a + b = Y
    int a = (2 * Y - X) / 3;
    int b = (2 * X - Y) / 3;
    if (a + 2 * b != X || 2 * a + b != Y) {
        cout << 0 << endl;
    }
    else if (a == 0 && b == 0) {
        cout << 1 << endl;
    }
    else {
        // calculate (a+b) C (a) mod (10^9 +7)
        int s = a + b;
        //ll fac[s + 1], finv[s + 1], inv[s + 1];
//        ll *fac, *finv, *inv;
//        fac = new ll[s+1];
//        finv = new ll[s+1];
//        inv = new ll[s+1];
        fac[0] = 1; fac[1] = 1;
        finv[0] = 1; finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i <= s; ++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;
        }
        cout << (fac[s] * (finv[a] * finv[b] % MOD) % MOD) << endl;
//        delete[] fac;
//        delete[] finv;
//        delete[] inv;
    }
    return 0;
}


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

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define mst(ss,b) memset(ss,b,sizeof(ss));
#define dbg(x) cout << #x << "= " << x << endl;
typedef pair <int, int> pii;
const int inf = 0x3f3f3f3f;
const ll INF = (1LL<<62)-1;
const ll mod = 1e9+7;
const int N = 1e5+5;

int n;
vector<int>E[N];
int sz[N], dep[N], fa[N], ed, sum;

void dfs1(int u, int pre, int d){
    sz[u] = 1;
    dep[u] = d;
    for(auto v:E[u]){
        if(v == pre)continue;
        fa[v] = u;
        dfs1(v, u, d+1);
        sz[u] += sz[v];
    }
}

void dfs2(int u){
    if(dep[u] == ed){
        sum = sz[u];
        return ;
    }
    dfs2(fa[u]);
}

int  main(){
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].pb(v);
        E[v].pb(u);
    }

    dfs1(1, -1, 0);
    ed = dep[n]/2+1;
    dfs2(n);
    if(n-sum > sum)puts("Fennec");
    else puts("Snuke");
    return 0;
}


//    lower_bound()
//    __builtin_popcount()
//    ios::sync_with_stdio(false);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    const double eps=1e-12;
//    #pragma comment(linker,"/STACK:102400000,102400000")



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


int main() {
  int A;
  cin >> A;
  int B;
  cin >> B;
  int C;
  cin >> C;
  int X;
  cin >> X;
  
  int count = 0;
  for (int a = 0; a <= A; a++) {
    for (int b = 0; b <= B; b++) {
      for (int c = 0; c <= C; c++) {
        int total = a*500 + b*100 + c*50;
        if (X == total) count++;
      }
    }
  }
  cout << count << endl;
}  


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

int
main(void)
{
    int h[10];
    int idx1, idx2, idx3 = -1;
    int temp_h = 0;
    int i;

    for (i = 0; i < 10; i++)
        scanf("%d", h + i);

    /* 1 ????????????????±±?????¢??? */
    for (i = 0; i < 10; i++) {
        if (h[i] > temp_h) {
            temp_h = h[i];
            idx1 = i;
        }
    }

    /* 2 ????????????????±±?????¢??? */
    temp_h = 0;
    for (i = 0; i < 10; i++) {
        if (i == idx1) continue;

        if (h[i] > temp_h) {
            temp_h = h[i];
            idx2 = i;
        }
    }

    /* 3 ????????????????±±?????¢??? */
    temp_h = 0;
    for (i = 0; i < 10; i++) {
        if (i == idx1 || i == idx2) continue;

        if (h[i] > temp_h) {
            temp_h = h[i];
            idx3 = i;
        }
    }

    printf("%d\n%d\n%d\n", h[idx1], h[idx2], h[idx3]);

    return 0;
}

Measured memory_bytes: 600
import java.util.*;

public class Main {

    private static  Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        // write your code here

        int n = sc.nextInt();

        int[][] dp = new int[n + 1][3];

        for (int i = 1; i <= n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][2])  + a;
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][2])  + b;
            dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][1])  + c;
        }

        System.out.println(Math.max(Math.max(dp[n][0], dp[n][1]), dp[n][2]));
    }
}

Measured memory_bytes: 95324
#include<stdio.h>
int b[1000];
int c[1000];
int d[1000];
int e[1000];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++)scanf("%d%d%d%d",b+i,c+i,d+i,e+i);
		int p,q,r,s;
		scanf("%d%d%d%d",&p,&q,&r,&s);
		bool ok=false;
		for(int i=0;i<a;i++){
			if(c[i]<=p&&d[i]<=q&&e[i]<=r&&4*c[i]+9*d[i]+4*e[i]<=s){
				ok=true;
				printf("%d\n",b[i]);
			}
		}
		if(!ok)printf("NA\n");
	}
}

Measured memory_bytes: 1056
import java.util.Scanner;

public class Main {
    public static void main(String []args){
        Scanner in = new  Scanner(System.in);
        int N = in.nextInt();
        int [][]dp = new int[3][N + 1];
        int [][]A = new int[3][N + 1];
        for(int i = 1; i <= 2; i++){
            for(int j = 1; j <= N; j++){
                A[i][j] = in.nextInt();
            }
        }
        for(int i = 1; i <= 2; i++){
            for(int j = 1; j <= N; j++){
                dp[i][j] = Math.max(dp[i - 1][j] , dp[i][j - 1]) + A[i][j];
            }
        }
        System.out.println(dp[2][N]);
    }
}


Measured memory_bytes: 22100
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
a = na()
a = a + a
a.sort(reverse=True)
print(sum(a[1:n]))


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

const int MAX = 510000;
const int MOD = 1000000007;

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;
    }
}

long long 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;
}

int main() {
    int N, K;
    cin >> N >> K;
    COMinit();

    for (int i = 1; i <= K; i++) {
        if (N - K + 1 < i) {
            cout << 0 << endl;
            continue;
        }

        cout << (COM(N - K + 1, i) * COM(K - 1, i - 1)) % MOD << endl;
    }

    return 0;
}

Measured memory_bytes: 12160
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
G_t=[list(x) for x in list(zip(*G))]
def Check(G,H,W):
  Paired_y=[False]*H
  for y1 in range(H):
    if Paired_y[y1]:
      continue
    for y2 in range(H):
      if y1==y2 or Paired_y[y2]:
        continue
      Paired_x=[False]*W
      for x1 in range(W):
        if Paired_x[x1]:
          continue
        for x2 in range(W):
          if x1==x2 or Paired_x[x2]:
            continue
          if G[y1][x1]==G[y2][x2] and G[y1][x2]==G[y2][x1]:
            Paired_x[x1]=True
            Paired_x[x2]=True
            break
      if W%2==1:
        if Paired_x.count(False)==1:
          r=Paired_x.index(False)
          if G[y1][r]==G[y2][r]:
            Paired_y[y1]=True
            Paired_y[y2]=True
            break
      else:
        if Paired_x.count(False)==0:
          Paired_y[y1]=True
          Paired_y[y2]=True
          break
  if H%2==1:
    if Paired_y.count(False)==1:
      return True
    else:
      return False
  else:
    if Paired_y.count(False)==0:
      return True
    else:
      return False
  
if Check(G,H,W) and Check(G_t,W,H):
  print("YES")
else:
  print("NO")

      
      
        
                         
      
    


Measured memory_bytes: 39664
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x7f7f7f7f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline bool xr(bool x,bool y){
	return x==y?0:1;
}
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
ull ksm(ull a,ull b){
    ull ans=1,base=a;
    while(b){
        if(b&1){
            ans*=base;
	    }
	    base*=base;
	    b>>=1;
	}
    return ans;
}
ll gcd(ll a,ll b){
    if(b) return gcd(b,a%b);
    return a;
}
bool prm(int k){
    if(k<2) return 0;
    if(k==2||k==3) return 1;
    if(k%6!=1&&k%6!=5) return 0;
    for(int i=5;i<=sqrt(k);i+=6)
        if(k%i==0||k%(i+2)==0) return 0;
    return 1;
}
int n,a,b;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
    cin>>n;if(n==1){
    	cout<<"Hello World\n";
    	return 0;
	}
	else{
		cin>>a>>b; cout<<a+b<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <set>
#include <map>
#include <deque>
#define WMAX 10000
#define HMAX 10000

//コメントアウトするとdebug()を実行しない
#define DEBUG

using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef pair<int ,int > P;
typedef long long ll;

int sx,sy,tx,ty,X,Y,ans = 0,dp[HMAX][WMAX];
static const int dx[8] = {0,1,1,1,0,-1,-1,-1},
					dy[8] = {1,1,0,-1,-1,-1,0,1};

void solve(){
	for (int i = 0; i < Y; ++i)
		cout << 'U';
	for (int i = 0; i < X; ++i)
		cout << 'R';
	for (int i = 0; i < Y; ++i)
		cout << 'D';
	for (int i = 0; i < X+1; ++i)
		cout << 'L';
	for (int i = 0; i < Y+1; ++i)
		cout << 'U';
	for (int i = 0; i < X+1; ++i)
		cout << 'R';
	cout << "DR";
	for (int i = 0; i < Y+1; ++i)
		cout << 'D';
	for (int i = 0; i < X+1; ++i)
		cout << 'L';
	cout << "U\n";
}

void answer(){
	cout << ans << "\n";
}

int main(){
	cin >> sx >> sy >> tx >> ty;
	X = tx-sx;
	Y = ty-sy;
	solve();
	// answer();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAXNUM 111111
vector<int> e[MAXNUM],te[MAXNUM];
int isok[MAXNUM],dis[MAXNUM];
void dfs(int now,int p,int d)
{
    dis[now]=d;
    for(int k:e[now])if(k!=p)
    {
        if(!dis[k])isok[now]^=1,te[now].push_back(k),dfs(k,now,d+1);
        else if(dis[k]<d)isok[now]^=1,printf("%d %d\n",now,k);
    }
}
void dfs2(int now,int p)
{
    for(int k:te[now])
        dfs2(k,now),isok[now]^=isok[k];
    if(p&&!isok[now])printf("%d %d\n",p,now);
    else if(p)printf("%d %d\n",now,p);
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    if(m&1)printf("-1\n");
    else{
        int a,b;
        for(int i=1;i<=m;i++)
            scanf("%d%d",&a,&b),e[a].push_back(b),e[b].push_back(a);
    }
    dfs(1,0,1),dfs2(1,0);
}

Measured memory_bytes: 23040
N, X, Y = map(int,input().split())
l = [0]*(N-1)
for i in range(1,N):
    for j in range(i+1,N+1):
        d=min(j-i,abs(X-i)+1+abs(Y-j),abs(Y-i)+1+abs(X-j))
        l[d-1] += 1
for k in range(N-1):
    print(l[k])

Measured memory_bytes: 3444