akhauriyash/Code-Regression huggingface dataset:
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

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

#define MOD 1000000007

void solve(int test_case) {
	int x,a,b;
	cin>>x>>a>>b;
	if(abs(x-a)<abs(x-b)) {
		cout<<"A";
	}else cout<<"B";
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3560
import sys

def output(x):
	count = 0
	for i in xrange(10):
		for j in xrange(10):
			for k in xrange(10):
				for l in xrange(10):
					if i+j+k+l == x:
						count += 1
	print count


if __name__ == "__main__":

	for i in sys.stdin:
		num = int(i)
		output(num)

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

using namespace std;

int main() {
	vector<int> nums;

	nums.resize(3);
	cin >> nums[0] >> nums[1] >> nums[2];

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

	int cnt = 0;
	while (nums[1] != nums[2]) {
		nums[0]++;
		nums[1]++;
		cnt++;
	}

	while (nums[0] < nums[1]) {
		nums[0] += 2;
		cnt++;
	}

	if (nums[0] > nums[1]) {
		nums[1]++;
		nums[2]++;
		cnt++;
	}

	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
int main() {
    int a,b,c;
    cin>>a>>b>>c;
    cout<<(b-a==c-b?"YES":"NO")<<endl;
}


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

#define all(a) (a).begin(), (a).end()
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;

int gcd(int a, int b){
	if(a<b)return gcd(b,a);
	if(b==0)return a;
	return gcd(b,a%b);
}



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

	int ans=a[0];
	for (int i = 1; i < n; ++i){
		ans=gcd(ans,a[i]);
	}

	cout<<ans<<endl;

}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int, int> P;
 
int main(){
  int n, r;
  cin >> n >> r;

  if(n>=10)   cout << r << endl;
  else		  cout << r+100*(10-n) << endl;

  return 0;
}

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


int main(){
  int i, j, X, flag = 0;
  cin >> X;
  
  int a, b, c, d, e, f;
  for(a = 0 ; a < 100 ; a++){
    for(b = 0 ; b < 50 ; b++){
      for(c = 0 ; c < 34 ; c++){
        for(d = 0 ; d < 25 ; d++){
          for(e = 0 ; e < 10 ; e++){
            f = X - (101*a + 102*b + 103*c + 104*d + 105*e);
            if(f < 0){
              break;
            }else if(f % 100 == 0 || 
                     f % 101 == 0 ||
                     f % 102 == 0 ||
                     f % 103 == 0 ||
                     f % 104 == 0 ||
                     f % 105 == 0   ){
              flag = 1;
              break;
            }
          }
        }
      }
    }
  }
  
  cout << flag << endl;
    
  
  return 0;
}

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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007


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

bool isp[55566];
vector<int> v;
void f(){
	isp[0] = true;
	isp[1] = true;
	for(int i = 2; i < 55566;i++){
		if(!isp[i]){
			v.PB(i);
			for(int j = 2*i;j < 55566;j +=i)isp[j] = true;
		}
	}
}
			

int main()
{
	int n;cin >> n;
	f();
	int cou = 0;
	vector<int> ans;
	REP(i,v.size()){
		if(v[i] % 5 == 1){
			ans.PB(v[i]);
			cou++;
			if(cou == n)break;
		}
	}
	REP(i,n){
		cout << ans[i];
		if(i != n-1)cout << ' ';
	}cout << endl;
	return 0;
}

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


class Program
{
    static void Main(string[] args)
    {
        Console.ReadLine();
        var H = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        var max = 0;

        for (int i = 0; i < H.Length; i++)
        {
            var count = 0;
            var pH = H[i];
            for (int j = i + 1; j < H.Length; j++)
            {
                if (pH >= H[j])
                {
                    pH = H[j];
                    ++count;
                }
                else
                {
                    break;
                }
            }

            if (max < count) max = count;
            i += count;
            if (max > H.Length - i - 2) break;
        }

        Console.WriteLine(max);
    }
}

Measured memory_bytes: 26204
//package EducationalDPContest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
        
        int[] nextIntArray(int n)
        {
        	int a[]=new int[n];
        	for(int i=0;i<n;i++)
        	{
        		a[i]=Integer.parseInt(next()); 
        	}
        	return a;
        }
    } 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader sc=new FastReader();
		int n=sc.nextInt();
		int k=sc.nextInt();
		int a[]=sc.nextIntArray(n);
		
		
		//Now we have two changing variables n and k;
		//for each i we have k choices;
		//I need to reach from 0 to end;
		int dp[]=new int[n+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		//cost to reach 0 will be 0 only;
		dp[0]=0;
		
		for(int i=0;i<n;i++)
		{
			//now to cost to reach 1; 
			//dp[i];
			//we can take k steps;
			//we are already at i;
			for(int j=i+1;j<=i+k;j++)
			{
				if(j<n)
				{
					int cost=Math.abs(a[j]-a[i])+dp[i];
					dp[j]=Math.min(dp[j],cost);
				}
			}
		}
		System.out.println(dp[n-1]);

	}
	
	

}


Measured memory_bytes: 43868
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <numeric>
#include <iomanip>
#include <climits>
#include <cstring>

using namespace std;

#define rep(i, n) for (int i=0;i<(int)(n);++i)
#define rep1(i, n) for (int i=1;i<=(int)(n);++i)
#define rrep(i, n) for (int i=(int)(n)-1;i>=0;--i)
#define rrep1(i, n) for (int i=(int)(n);i>=1;--i)
#define range(i, l, r) for (int i=l;i<(int)(r);++i)
#define rrange(i, l, r) for (int i=(int)(r)-1;i>=l;--i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;
using vpii=vector<pii>;
using ll=long long;

constexpr int TEN(int n){return n==0?1:10*TEN(n-1);}
bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}

constexpr int mod = 998244353;

int N, S;
int dp[3030][3030];

signed main()
{
	cin >> N >> S;
	vi a(N);
	rep(i, N) cin >> a[i];

	dp[0][0] = 1;

	for (int i = 0; i < N; ++i) {
		for (int s = S; s >= 0; --s) {
			dp[i + 1][s] += dp[i][s];
			dp[i + 1][s] %= mod;

			if (s + a[i] <= S) {
				dp[i + 1][s + a[i]] += dp[i][s];
				dp[i + 1][s + a[i]] %= mod;
			}
		}

		for (int s = S; s >= 0; --s) {
			dp[i + 1][s] += dp[i][s];
			dp[i + 1][s] %= mod;
		}
	}

	cout << dp[N][S] << endl;
}




Measured memory_bytes: 39140
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[]str = Console.ReadLine().Split();
		int A = int.Parse(str[0]);
		int B = int.Parse(str[1]);
		int C = int.Parse(str[2]);
		int K = int.Parse(Console.ReadLine());
		int ans = 0;
		while(B<=A){
			B *= 2;
			ans++;
		}
		while(C<=B){
			C *= 2;
			ans++;
		}
		string a = "No";
		if(ans<=K){
			a = "Yes";
		}
		Console.WriteLine(a);
	}
}

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a) ; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define sp system("pause")
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
const int N = (int) 1e5 + 10;
void TimeExecution() {
    cout << "\n\n===>> Time Execution: " << clock() / (double)1000 << " sec(s).";
}
int t;
vi st, ans;
void solve()
{
    queue<ll> q;
    q.push(3);
    q.push(5);
    q.push(7);
    while(!q.empty())
    {
        ll val = q.front();
        q.pop();
        if(val * 10 + 3 < INF)
        {
            q.push(val * 10 + 3);
            st.pb(val * 10 + 3);
            q.push(val * 10 + 5);
            st.pb(val * 10 + 5);
            q.push(val * 10 + 7);
            st.pb(val * 10 + 7);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    /*
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    */
    int n;
    cin >> n;
    st.pb(3);
    st.pb(5);
    st.pb(7);
    solve();
    FOR(i, 0, st.size() - 1)
    {
        int tmp = st[i];
        int ok = 0, ok2 = 0, ok3 = 0;
        while(tmp)
        {
            if(tmp % 10 == 3) ok = 1;
            if(tmp % 10 == 5) ok2 = 1;
            if(tmp % 10 == 7) ok3 = 1;
            tmp /= 10;
        }
        if(ok + ok2 + ok3 == 3) ans.pb(st[i]);
    }
    sort(all(ans));
    //FOR(i, 0, 12) cout << ans[i] << " ";
    FOR(i, 0, ans.size() - 1)
    {
        if(ans[i] > n)
        {
            cout << i;
            return 0;
        }
    }
    cout << ans.size();
    return 0;
}


Measured memory_bytes: 600
#include <stdio.h>

int main(void)
{
    int i = 1;
    int x;
    while(1) {
        scanf("%d", &x);
        if (x == 0) {
            break;
        } else {
            printf("Case %d: %d\n", i, x);
            ++i;
        }
    }
    return 0;
}

Measured memory_bytes: 1028
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する。
    built(array)   := arrayを初期値とするセグメント木を構築する O(N)。
    update(i, val) := i番目の要素をvalに変更する。
    get_val(l, r)  := 区間[l, r)に対する二項演算の畳み込みの結果を返す。
    """
    def __init__(self, n, op, e):
        """要素数、二項演算、単位元を引数として渡す
        例) 区間最小値 SegmentTree(n, min, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def build(self, array):
        """arrayを初期値とするセグメント木を構築する"""
        for i in range(self.n):
            self.node[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def update(self, i, val):
        """i番目の要素をvalに変更する"""
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res_l, res_r = self.e, self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.node[r], res_r)
            l, r = l >> 1, r >> 1
        return self.op(res_l, res_r)


ALPH = "abcdefghijklmnopqrstuvwxyz"
to_int = {char: i for i, char in enumerate(ALPH)}


n = int(input())
s = input()
q = int(input())
query = [list(input().split()) for i in range(q)]

init = [0] * n
for i, char in enumerate(s):
    init[i] = 1 << to_int[char]

op = lambda a, b: a | b
st = SegmentTree(n, op, 0)
st.build(init)

for i in range(q):
    if query[i][0] == "1":
        _, ind, char = query[i]
        ind = int(ind) - 1
        st.update(ind, 1 << to_int[char])
    else:
        _, l, r = query[i]
        l, r = int(l) - 1, int(r) 
        print(bin(st.get_val(l, r)).count("1"))


Measured memory_bytes: 84680
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9;
const int ZERO = 0;
const int MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

signed main() {
    int A,B,C;
    cin >> A >> B >> C;
    if(A + B + C >= 22) {
        cout << "bust" << endl;
    }
    else {
        cout << "win" << endl;
    }
}

Measured memory_bytes: 256
def main():
    L = int(input())
    ret = (L / 3) ** 3
    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


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

int kouyaku(int a,int b,int c)
{
  int kou;
  kou=__gcd(a,__gcd(b,c));
  return kou;
}

int main()
{
  int K;
  int64_t sum=0;
  cin >> K;
  for(int a=1; a<=K; a++)
  {
    for(int b=1; b<=K; b++)
    {
      for(int c=1; c<=K; c++)
      {
        sum+=kouyaku(a,b,c);
      }
    }
  }

cout << sum << endl;

}


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

using namespace std;

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

const int MAX_N=100;

int N;
int L[MAX_N*2];

int main(){
	cin>>N;
	REP(i,N*2){
		cin>>L[i];
	}
	sort(L,L+N*2);
	int ans=0;
	REP(i,N){
		ans+=L[i*2];
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int a, b;
    cin >> a >> b;
    cout << ((a * b % 2) ? "Yes" : "No") << endl;
}

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

int main(){

    int n;
    cin >> n;

    int sumMin = 100000000;
    for(int i = 1; i <= n / 2; i++){
        int sum = 0;
        int a = i;
        int b = n - i;
        while(b > 0){
            //cout << a << b << endl;
            sum += a % 10 + b % 10;
            b = b / 10;
            a = a / 10;
        }
        if(sum < sumMin) sumMin = sum;
    }

    cout << sumMin << endl;
}

Measured memory_bytes: 256
a,g,a_,a__,ac,ga,al=[0]*6+[1]
for i in range(int(input())):
    a__,a_,ac,ga,a,g,al=a_,a,a-ga,g,al,al-ac,(al*4-(a_+ac+ga+a__*3))%(pow(10,9)+7)
print(al)


Measured memory_bytes: 2940
use text_io::*;

fn main() {
    let a: f64 = read!();
    let b: f64 = read!();
    let h: f64 = read!();
    let m: f64 = read!();
    
    let x = m * 6.0;
    let y = (h % 12.0) * 30.0 + m / 2.0;
    
    let m = (x - y).abs().min(360.0 - (x - y).abs());
    
    let ans = (a * a + b * b - 2.0 * a * b * m.to_radians().cos()).sqrt();
    
    println!("{}", ans)
}


Measured memory_bytes: 3020
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
ll bit[200010], num;
string s;
ll cnt;

ll sum(ll i)
{
	ll s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add(ll i, ll x)
{
	while (i <= num)
	{
		bit[i] += x;
		i += i & -i;
	}
}

ll po(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2)
	{
		return po(x, y - 1) * x % mod;
	}
	else
	{
		ll yyy = po(x, y / 2);
		return yyy * yyy % mod;
	}
}

ll div(ll x)
{
	return po(x, mod - 2);
}

int main(void)
{
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == 'x')
		{
			cnt++;
		}
	}
	if (cnt < 8)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	int www;
	cin >> www;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define pp pair<int,int>
#define ll long long
#define ld long double
int inf=100000000;
ll INF=4000000000000000000;
ll MOD=1000000007;



int main() {
  ll a,b;
  cin >> a >> b;
  for (ll i=1;i<a+1;i++){
    ll h=i*a,u=0;
    u+=h/b;
    ll k=h%b;
    u+=k/a;
    u+=k%a;
    if (i<u) {cout << h << endl;return 0;}
  }
  cout << -1 << endl;
}



Measured memory_bytes: 3136
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int K = scanner.nextInt();
        int S = scanner.nextInt();

        int ret = 0;
        for (int x = 0; x <= K; x++)
            for (int y = 0; y <= K; y++) {
                int z = S - x - y;
                if (z<0)
                    break;
                if (z>K)
                    continue;
                ret++;
            }
        System.out.println(ret);
    }
}

Measured memory_bytes: 9808
n = int(input())
a = list(map(int,input().split()))
import sys

lim = [0]*(n+1)
aa = 0
for i in range(n+1):
    aa += a[n-i]
    lim[n-i] = aa
    
if n == 0:
    if a[0] != 1:
        print(-1)
        sys.exit()
    else:
        print(1)
        sys.exit()
        
if a[0] != 0:
    print(-1)
    sys.exit()
    
ha = [[0]*(n+1) for i in range(2)]
ha[0][0] = 1
ha[1][0] = 1
for i in range(n):
    ha[1][i+1] = min(ha[0][i]*2 , lim[i+1])
    ha[0][i+1] = ha[1][i+1] - a[i+1]
    if ha[0][i+1] <= 0 and i != n-1:
        print(-1)
        sys.exit()
    if ha[0][i+1] < 0 and i == n-1:
        print(-1)
        sys.exit()
        
print(sum(ha[1]))

Measured memory_bytes: 87368
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

struct Edge {
	int s;
	int e;
	int v;
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int l; cin >> l;
	l--;
	vector<bool> bits(20);
	int maxi = 0;
	FOR_LT(i, 0, 20) {
		if (l & (1 << i)) bits[i] = true;
		if (bits[i]) maxi = i;
	}

	if (l == 1) {
		cout << 2 << " " << 2 << endl;
		cout << "1 2 0" << endl;
		cout << "1 2 1" << endl;
		return 0;
	}

	vector<Edge> edges;
	int node = 1;
	int num = (1 << maxi);
	FOR_DW(i, maxi - 1, 0) {
		edges.push_back({ node, node + 1, 0 });
		edges.push_back({ node, node + 1, (1 << i) });
		if (bits[i]) {
			edges.push_back({ 1, node + 1, num });
			num += (1 << i);
		}
		node++;
	}
	edges.push_back({ 1, node, num});


	cout << (node) << " " << edges.size() << endl;
	for (auto e : edges) {
		cout << e.s << " " << e.e << " " << e.v << endl;
	}

	return 0;
}

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

using namespace std;
using ll =long long;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
#define leftunique(a) {sort((a).begin(),(a).end());(a).erase(unique((a).begin(),(a).end()),(a).end());}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
static const ll INF = 1LL << 60;
//Write From this Line

int main()
{
	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	vector<int> p(a);
	rep(i,a) cin >> p[i];
	vector<int> q(b);
	sort(p.rbegin(),p.rend());
	rep(i,b) cin >> q[i];
	sort(q.rbegin(),q.rend());
	vector<int> r(c);
	rep(i,c) cin >> r[i];
	sort(r.rbegin(),r.rend());

	vector<int> P;
	rep(i,x) P.push_back(p[i]);
	rep(i,y) P.push_back(q[i]);
	rep(i,c) P.push_back(r[i]);
	sort(P.rbegin(),P.rend());
	ll ans= 0 ;
	rep(i,x+y){
		ans += P[i];
	}
	cout << ans << endl;
}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18

int main() {
    int n ;
    cin >> n ;
    vector<int> vec (n) ;
    rep(i, n) cin >> vec[i] ;
    int ans = 0 ;
    for(int i = 1 ; i < n -1 ; i++){
        int a = vec[i-1] ;
        int b = vec[i] ;
        int c = vec[i + 1] ;
        if((a > b && c < b) || (a < b && c > b)){
            ans++ ;
        }
    }
    cout << ans << endl ;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using pll = pair<ll, ll>;
using edge = pair<int, ll>;
using Graph = vector<vector<int>>; 
using WeightedGraph = vector<vector<edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int main(){
string s;cin >> s;
cout << s.front()<< s.size()-2<< s.back() << endl;
}


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

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

    vector<int> a(n);
    rep(i, n) {
        cin >> a.at(i);
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    vector<P> cards(m);
    rep(i,m) {
        cin >> cards.at(i).second >> cards.at(i).first;
    }
    sort(cards.begin(), cards.end());
    reverse(cards.begin(), cards.end());

    ll ans = 0;
    int j = 0, k = 0;
    rep(i, n) {
        if(k == m || a.at(j) >= cards.at(k).first) {
            ans += a.at(j);
            j++;
            continue;
        }
        int c = min(n-i, cards.at(k).second);
        ans += (ll)cards.at(k).first * c;
        k++;
        i += c-1;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1408
/*input
4
20 11 9 24
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ll long long 
#define ld long double
#define pii pair<int,int>
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define MP make_pair
const ll INF64=4e12;
const int INF=0x3f3f3f3f;
const ll MOD=998244353;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1){
            res=(res*a)%MOD;
        }
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
const ll maxn=1e6+5;
const ll maxlg=__lg(maxn)+2;
int arr[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n;
    int ans=0;
    REP(i,n){
        cin>>arr[i];
        ans^=arr[i];
    }
    REP(i,n){
        cout<<(ans^arr[i])<<' ';
    }
}

Measured memory_bytes: 4360
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

int main(){
    int N;cin>>N;
    priority_queue<int>pq;
    int tmp;
    rep(i,N){
        cin>>tmp;
        pq.push(tmp);
    }
    int sumA=0;
    int sumB=0;
    int judge=0;
    while(!pq.empty()){
        if(judge==0){
            sumA+=pq.top();
            pq.pop();
            judge=1;
        }else if(judge==1){
            sumB+=pq.top();
            pq.pop();
            judge=0;
        }
    }
    cout<<sumA-sumB<<endl;
}

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

typedef long long ll;
typedef pair<int,int> pii;
#define fore(i,ii,iii)for(int i=ii;i<iii;i++)
#define rfor(i,ii,iii)for(int i=iii-1;i>=ii;i--)
#define all(s) s.begin(),s.end()
#define sz(a) ((int)a.size())
#define pb push_back
#define mset(a,b) memset(a,b,sizeof(a))
#define fst first
#define snd second

const ll N=1e5+15;
int n,x,y;
vector<int>g[N],ch[N];
ll MOD;
ll s[N],d[N],r[N];

struct STree { // [cerrado-abierto)
	vector<ll> st;int n;
	STree(int n): st(4*n+5,1), n(n) {}
	void upd(int k, int s, int e, int p, ll v){
		if(s+1==e){st[k]=v;return;}
		int m=(s+e)/2;
		if(p<m)upd(2*k,s,m,p,v);
		else upd(2*k+1,m,e,p,v);
		st[k]=(st[2*k]*st[2*k+1])%MOD;
	}
	ll query(int k, int s, int e, int a, int b){
		if(s>=b||e<=a)return 1;
		if(s>=a&&e<=b)return st[k];
		int m=(s+e)/2;
		return (query(2*k,s,m,a,b)*query(2*k+1,m,e,a,b))%MOD;
	}
	void upd(int p, ll v){upd(1,0,n,p,v);}
	ll query(int a, int b){return query(1,0,n,a,b);}
}; // usage: STree st(n);st.upd(i,v);st.query(s,e);

void dfs1(int v,int pa) {
  s[v]=1;
  for(int i:g[v])if(i!=pa){
    ch[v].pb(i);
    dfs1(i,v);
    s[v]=(s[v]*(s[i]+1))%MOD;
  }
}

void dfs2(int v,int pa) {
  STree st(ch[v].size());
  fore(i,0,ch[v].size())st.upd(i,s[ch[v][i]]+1);
  fore(i,0,ch[v].size()) {
    ll a=st.query(0,i);
    ll b=st.query(i+1,ch[v].size());
    d[ch[v][i]]=((((d[v]+1)*a)%MOD)*b)%MOD;
    dfs2(ch[v][i],v);
  }
  r[v]=((d[v]+1)*st.query(0,ch[v].size()))%MOD;
}

int main() {
  scanf("%d %lld",&n, &MOD);
  fore(i,0,n-1) {
    scanf("%d %d", &x, &y);x--,y--;
    g[x].pb(y);
    g[y].pb(x);
  }
  dfs1(0,-1);
  dfs2(0,-1);
  fore(i,0,n)printf("%lld\n",r[i]);
}

Measured memory_bytes: 36992
#pragma GCC optimize("O4")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(1e9+7)
#define INF 1e17
#define int short
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }

int fpow(int b,int p)
{
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

int dp[5010][5010];



int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin>>n;
	string s; cin>>s;
	For(i,0,n){
		dp[i][n]=0;
		dp[n][i]=0;
	}
	int ans=0;
	for(int i=n-1;i>=0;i--){
		for(int j=n-1;j>=0;j--){
			if(i<j && s[i]==s[j]) dp[i][j]=min(dp[i+1][j+1]+1,j-i);
			else dp[i][j]=0;
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<"\n";
	//For(i,0,n) For(j,0,n){
	//	cout<<dp[i][j]<<" \n"[j==n];
	//}
	return 0;
}





























Measured memory_bytes: 49152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

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

    unordered_map<ll,int> mp;

    ll now = 0;
    ll ans = 0;

    mp[0]++;

    for(int i = 0; i < n; i++){
        now += a[i];
        ans += mp[now];
        mp[now]++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 12132
#include<iostream>
using namespace std;
int main(){
int n;
  cin >> n;
  int a[n];
  int ans = 0;
  for(int i = 0;i < n;i++) cin >> a[i];
  for(int i = 0;i < n;i++){
    for(int j = i+1;j < n;j++){
      ans += a[i]*a[j];
    }}
  cout << ans << endl;
}


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

int dig(int x, int y) {
    rep(i, y - 1) x /= 10;
    return x % 10;
}

int main() {
    string s;
    cin >> s;
    int num = stoi(s);
    
    int a = dig(num, 1) + 10 * dig(num, 2) ;
    int b = dig(num , 3) + 10 * dig(num, 4);

    if (a == 0) {
        if (b == 0 || b >= 13) cout << "NA";
        else cout << "MMYY";
    }

    else if (b == 0) {
        if (a >= 13) cout << "NA";
        else cout << "YYMM";
    }

    else if(a >= 13  && b >= 13) cout << "NA";

    else if (a >= 13 && b < 13) cout << "MMYY";

    else if (a < 13 && b >= 13) cout << "YYMM";

    else cout << "AMBIGUOUS";
}

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

using ll = long long int;
using P = std::pair<int, int>;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rag(con) std::begin(con), std::end(con)

int main()
{
    ll a, b, c, d;

    std::cin >> a >> b >> c >> d;

    if (a >= 0)
    {
        if (d <= 0)
            std::cout << a * d << std::endl;
        else
        {
            std::cout << b * d << std::endl;
        }
    }
    else if (b <= 0)
    {
        if (c >= 0)
            std::cout << b * c << std::endl;
        else
        {
            std::cout << a * c << std::endl;
        }
    }
    else
    {
        if (c >= 0)
            std::cout << b * d << std::endl;
        else if (d <= 0)
            std::cout << a * c << std::endl;
        else
        {
            std::cout << std::max(a * c, b * d) << std::endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3636
/*   ꧁༒☬महाकाल☬༒꧂ ꧁༒ঔमहाकालঔ༒꧂
                   
                   ঔৣ۝महाकालᴳᵒᵈ۝ঔৣ            
 
 */ 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops"
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T, typename cmp=less<T>> using oset =tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long 
#define mod 1000000007
#define MOD 998244353
#define inf 100000000000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _it iterator
#define all(_x) _x.begin(),_x.end()
#define f first
#define s second
#define pb push_back
#define ar array
#define ld long double
void mahakal(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
	#endif
}
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
char c[4]={'D' , 'R' , 'U' , 'L'};
const ll maxN=2e5+5;
ll n , m ;

void solve(){	

	cin>> n ;
	ll a[n+1];
	ll p[n+2]={0};
	for(ll i=1;i<=n ;i++)cin>>a[i];

	for(ll i=1;i<=n ;i++){
		p[i]=(p[i-1]+a[i])%mod;
	}
	ll ans =0;
	for(ll i=1;i<n ;i++){
		ans = (ans + a[i]*(p[n]-p[i]+mod)%mod)%mod;
	}

	cout<<ans<<endl;
}


int main(){
	//mahakal();
	fast;
	ll t =1 ;
	//cin>> t ; 
	while(t--)solve();
	//cerr << "\ntime taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl; 
	return 0;
}

Measured memory_bytes: 6788
#include<iostream>
#include<algorithm>
using namespace std;
int H,N;
long dp[10101];
main()
{
	cin>>H>>N;
	for(int i=1;i<=H;i++)dp[i]=1e18;
	for(int i=0;i<N;i++)
	{
		int A,B;cin>>A>>B;
		for(int j=0;j<H;j++)
		{
			int nxt=min(j+A,H);
			dp[nxt]=min(dp[nxt],dp[j]+B);
		}
	}
	cout<<dp[H]<<endl;
}


Measured memory_bytes: 384
package main

import (
  "fmt"
  "strconv"
)

func f(s string) int {
  tot := 0
  for _, d := range s {
    tot += int(d - '0')
  }
  return tot
}

func main() {
  var n int
  fmt.Scan(&n)
  ans := "No"
  if n % f(strconv.Itoa(n)) == 0 {
    ans = "Yes"
  }
  fmt.Println(ans)
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>

using namespace std;


int main() {
	long long n, c;
	cin >> n >> c;
	vector<long long> x{ 0 };
	vector<long long> v{ 0 };
	vector<long long> calmax1{ 0 };
	vector<long long> calmax2{ 0 };
	long long totalsushi = 0;
	for (int i = 0; i < n; ++i) {
		long long xi, vi;
		cin >> xi >> vi;
		x.push_back(xi);
		v.push_back(vi);
		totalsushi += vi;
		calmax1.push_back(max(totalsushi-xi, calmax1[i]));
		calmax2.push_back(max(totalsushi-2*xi, calmax2[i]));
	}

	long long result = 0;
	totalsushi = 0;
	for (int i = n; i > 0; --i) {
		totalsushi += v[i];
		result = max(result,
			max(calmax2[i - 1] + totalsushi - (c - x[i]),
				calmax1[i - 1] + totalsushi - (c - x[i]) * 2));
	}
	cout << max(result,calmax1[n]) << endl;


	return 0;
}


Measured memory_bytes: 3540
#include<cstdio>
#include<cstring>
using namespace std;

int h, w, k;
char s[300][301];
int a[300][301];
bool jdg[300];

int main() {
    scanf("%d %d %d", &h, &w, &k);
    for (int i = 0; i < h; i++) scanf("%s", s[i]);
    int num = 1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '#') {
                jdg[i] = true;
                break;
            }
        }
        if (!jdg[i]) continue;
        bool judge = false;
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '#') {
                if (!judge) judge = true;
                else num++;
            }
            a[i][j] = num;
        }
        num++;
    }
    for (int i = 0; i < h - 1; i++) {
        if (jdg[i] && !jdg[i + 1]) {
            jdg[i + 1] = true;
            for (int j = 0; j < w; j++) a[i + 1][j] = a[i][j];
        }
        if (jdg[h - i - 1] && !jdg[h - i - 2]) {
            jdg[h - i - 2] = true;
            for (int j = 0; j < w; j++) a[h - i - 2][j] = a[h - i - 1][j];
        }
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <utility>
#include <string>
#include <map>
#include <unordered_map>

using namespace std;

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

    vector< pair<int, int> > p(M);
    vector< int > Y(M);
    vector< int > app(N);
    vector< string > SN(M);
    //map< int, int > orig;
    unordered_map< int, int > orig;
    
    int P;
    for (i=0; i<M; i++){
        cin >> P;
        cin >> Y[i];
        p[i] = make_pair(Y[i], P);
        orig[Y[i]] = i;
    }

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

    int temp, num, j, index;
    for (i=0; i<M; i++){
        app[p[i].second]++;
        num = app[p[i].second];
        index = orig[p[i].first];
        string s1 = to_string(num); //build order
        string s2 = to_string(p[i].second); //num of pref.
        for (j=0; j<6-s2.size(); j++) SN[index].push_back('0');
        SN[index] += s2;
        for (j=0; j<6-s1.size(); j++) SN[index].push_back('0');
        SN[index] += s1;
        
    }

    for (i=0; i<M; i++){
        cout << SN[i] << '\n';
    }

}


Measured memory_bytes: 13860
#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);++i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    ll N,K;
    cin >> N >> K;
    vector<P> V(N);
    rep(i,0,N){
        ll a,b;
        cin >> a >> b;
        V[i] = P(b,a-1);
    }
    sort(V.rbegin(), V.rend());
    vector<int> cnt(N),used,unused;
    ll sum = 0, maxi = 0, kind = 0;
    rep(i,0,K){
        int k = V[i].second;
        maxi += V[i].first;
        if(!cnt[k])kind++;
        else used.push_back(V[i].first);
        cnt[k]++;
    }
    rep(i,K,N){
        int k = V[i].second;
        if(!cnt[k])unused.push_back(V[i].first);
        cnt[k]++;
    }
    reverse(unused.begin(), unused.end());
    sum = maxi;
    maxi += kind * kind;
    //cout << maxi << " " << kind << endl;
    rep(i,kind,INF){
        if(used.size() == 0 || unused.size() == 0)break;
        //cout << unused.back() << "," << used.back() << endl;
        sum += unused.back() - used.back();
        maxi = max(maxi, sum + (i+1) * (i+1) );
        unused.pop_back();
        used.pop_back();
        //cout << sum << " " << sum + (i+1) * (i+1) << endl;
    }
    cout << maxi << endl;
}

Measured memory_bytes: 2568
#include<iostream>
#include<string>

using namespace std;

int gcd(int a, int b);

int main(){
    int k;
    cin >> k;
    int sum = 0;
    for (int a = 1; a <= k; a++){
        for (int b = 1; b <= k; b++){
            for(int c = 1; c <= k; c++){
                sum += gcd(a, gcd(b, c));
            }
        }
    }

    cout << sum << endl;
    return 0;
}

int gcd(int a, int b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}

Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}



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

  ll N ; cin >> N;
  vector<ll>A;
  
  rep(i,N){
    ll inp; cin >> inp;
    A.pb(inp);
  }
  sort(all(A));
  
  vector<ll> B;
  rep(i,N){
    ll num = (i+1);
    ll l = num-1;
    ll r = N-num;
    B.pb(abs(r-l));
  }

  sort(all(B));
  rep(i,A.size()){
    if(A[i] != B[i]){
      N=0;
      break;
    }
  }
  if(N==1){cout << 1 << endl; return 0;}
  N/=2;

  ll ans = 0;
  rep(i,N){
    if(i==0) ans = 1;
    ans *= 2;
    ans %= 1000000007;
  }

  cout << ans << endl;

  
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 2548
#include <stdio.h>

#define XLEN_MAX 1000

char x[XLEN_MAX + 1];

int solve(void){
	int a,b;
	char *s;
	a = b = 0;
	s = x;
	while(*s){
		b += (int)(*s - '0');
		s++;
		a ^= 1;
	}
	if((((b - 1) / 9) & 1) ^ a){
		puts("Audrey wins.");
	}else{
		puts("Fabre wins.");
	}
	return 0;
}

int main(void){
	int i;
	int n;
	scanf("%d", &n);
	i = n;
	while(n--){
		scanf("%s", x);
		solve();
	}
	return 0;
}

Measured memory_bytes: 584
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 10;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> prime(MAX_N, 1);
    prime[0] = prime[1] = 0;
    for(int i = 2; i < MAX_N; i++)
    {
        for(int j = 2 * i; j < MAX_N; j += i) prime[j] = 0; 
    }
    vector<int> like2017 = prime;
    for(int i = 0; i < MAX_N; i++)
    {
        if(not prime[i]) continue;
        if(not prime[(i + 1) / 2]) like2017[i] = 0;
    }
    vector<int> sum(MAX_N + 1, 0);
    for(int i = 2; i <= MAX_N; i++) sum[i] = sum[i - 1] + like2017[i];
    int Q; cin >> Q;
    for(int i = 0; i < Q; i++)
    {
        int l, r; cin >> l >> r;
        cout << sum[r] - sum[l - 1] << endl;
    }
    return 0;
}



Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

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

long long lcm(long long a,long long b){
	long long g=gcd(a,b);
	return a/g*b;
}

int main(){
	LL n,t[111]={};
	cin>>n;
	FOR(i,0,n){
		cin>>t[i];
	}
	LL ans=t[0];
	FOR(i,1,n){
		ans=lcm(ans,t[i]);
	}
	cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
  int n=0,ans;
  cin >>n;
  while(n!=-1){
    ans=0;
    if(n>30){
      ans+=(n-30)*160;
      n=30;
    }
    if(n>20){
      ans+=(n-20)*140;
      n=20;
    }
    if(n>10)
      ans+=(n-10)*125;
    cout <<4280-(ans+1150)<<endl;
    cin>> n;
  }
  return 0;
}



Measured memory_bytes: 3084
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<iomanip>
#include<bitset>
using ll=long long;


int main(){
  int n,k;
  cin >> n >> k;
  int r,s,p;
  cin >> r >> s >> p;
  string t;
  cin >> t;
  vector<ll>x(n);
  rep(i,n){
    if(t[i]=='r')x[i]=p;
    else if(t[i]=='s')x[i]=r;
    else if(t[i]=='p')x[i]=s;
  }
  for(int i=k;i<n;i++){
    if(t[i]==t[i-k]){x[i]=0;t[i]='n';}
  }
  ll sum=0;
  rep(i,n)sum+=x[i];
  cout << sum << endl;


}


Measured memory_bytes: 1280
n,m=map(int,input().split())
sc=[list(map(int,input().split())) for i in range(m)]

ans=[-1 for i in range (n)]
fail=0

for i in range(m):
    ss=sc[i][0]
    cc=sc[i][1]
    aa=ans[ss-1]
    if aa==-1:
        ans[ss-1]=cc
    elif aa!=cc:
        fail=-1

if n>1:
    if ans[0]==0:
        fail=-1
    elif ans[0]==-1:
        ans[0]=1
    answer=0
    
    for i in range (n):
        if ans[i]==-1:
            ans[i]=0
        answer*=10
        answer+=ans[i]
else:
    if ans[0]==-1:
        answer=0
    else:
        answer=ans[0]
    

if fail==-1:
    print(-1)
else:
    print(answer)
    

Measured memory_bytes: 38384
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n;
string a,b;
int x,y;
string u;

int main(){

	cin >> a;
	n = a.size();
	for ( int i = 0; i < n; i++ ) cout << "x";
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
    typedef long long int lli;
    #define MAX 1001000
    #define MOD 1000000007
    #define endl "\n"
    lli arr[MAX];
    lli N;
    lli M;
    lli Q;
    int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        lli t;
        t = 1;
        while(t--){
            lli A,B, N;
            cin>>A>>B>>N;
            lli f = min(B-1,N);
            double x = (double)f/B;
            cout<<floor(A*x);
            
        }
    }

Measured memory_bytes: 3808
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin>>s>>t;
    vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
    for(int i=1;i<s.size()+1;i++){
        for(int j=1;j<t.size()+1;j++){
            if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int i=s.size();
    int j=t.size();
    string res="";
    while(i!=0 && j!=0){
        if(dp[i][j]==dp[i-1][j]) i--;
        else if(dp[i][j]==dp[i][j-1]) j--;
        else if(dp[i][j]==dp[i-1][j-1]+1){
            res+=s[i-1];
            i--;
            j--;
        }
    }
    reverse(res.begin(),res.end());
    cout<<res<<endl;
}

Measured memory_bytes: 35584