akhauriyash/Code-Regression huggingface dataset:
/*
    Code written by Talant I.D.
*/

#include <bits/stdc++.h>

using namespace std;

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

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);

inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}

inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i += 2)
        if(n%i == 0) return false;
    return true;
}

int main(){
    do_not_disturb

    int n, i;
    cin >> n;
    set <string> st;
    for(i = 0; i < n; i++){
        string s;
        cin >> s;
        st.insert(s);
    }
    cout << st.size();

    return 0;
}


Measured memory_bytes: 19156
#include<vector>
#include<cstdio>
#include<queue>
#include<algorithm>
#define MN 410001
#define ll long long
using namespace std;

int n,m,w[MN],c[MN];
long long f[MN],ans=9e18;
long long sqr(long long x){return x*x;}
inline void Min(long long &x,long long v){if(x>v) x=v;}
inline ll work(int p){
	ll ans=0;
	for (int i=n,j=0,k=0;i;i--){
		ans+=1LL*c[k]*w[i];
		j++;
		if (j==p) j=0,k++;
	}
	ans+=1LL*p*m;
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&w[i]);
	c[0]=5;
	for (int i=1;i<=n;i++) c[i]=i*2+3;
	int l=1,r=n,mid1,mid2;
	while(l<r-10){
		int u=(r-l)/3;
		mid1=l+u;mid2=r-u;
		if (work(mid1)<work(mid2)) r=mid2;else l=mid1;
	}
	l-=10;r+=10;
	if (l<1) l=1;if (r>n) r=n;
	for (int i=l;i<=r;i++) Min(ans,work(i));
	printf("%lld\n",ans+1LL*n*m);
}

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+1];
	long long s=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s+=a[i];
		s--;
	}
	cout<<s;
 } 

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

#define int long long
//#define double long double

#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define ALL(v) (v).begin(), (v).end()

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

using pi = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vvb = vector<vb>;

const int INF = 1e18;
const int MOD = 1e9+7;

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

vi node;

int root(int x)
{
    if(node[x] == x) return x;
    return node[x] = root(node[x]);
}

void unite(int x, int y)
{
    int rx = root(x);
    int ry = root(y);
    node[rx] = ry;
}

bool same(int x, int y)
{
    return root(x) == root(y);
}

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    using edge = tuple<int, int, int>;
    int V, E; cin >> V >> E;
    node.resize(V);
    REP(i, V) node[i] = i;
    vector<edge> edges(E);
    REP(i, E)
    {
        int s, t, d; cin >> s >> t >> d;
        edges[i] = edge(d, s, t);
    }
    sort(ALL(edges));

    int ans = 0;
    REP(i, E)
    {
        if(!same(get<1>(edges[i]), get<2>(edges[i])))
        {
            ans += get<0>(edges[i]);
            unite(get<1>(edges[i]), get<2>(edges[i]));
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 5212
from copy import deepcopy
import itertools


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


N = read()
P = []
for _ in range(N):
    P.append(read())

dic = {}
for p in P:
    if p in dic.keys():
        dic[p+1] = dic[p] + 1
        del dic[p]
    else:
        dic[p+1] = 1

print(N - max(dic.values()))



Measured memory_bytes: 35468
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define REP(i, n) for ( int i = 0; i < (n); i++ )
 
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int N;
  cin >> N;

  int sum = 0;
  vector<int> A(N);
  REP(i, N) {
    cin >> A[i];
    sum += A[i];
  }

  int ans = 1e10;
  int now = 0;
  REP(i, N) {
    now += A[i];
    // cout << now-(sum-now) << endl;
    if ( (double)now <= (double)sum/2 ) ans = min({ans, abs(sum-2*now)});
    if ( (double)now >= (double)sum/2 ) ans = min({ans, abs(now-(sum-now))});    
  }

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


Measured memory_bytes: 4756
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
constexpr auto INF = INT_MAX >> 1;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	int a, b;
	cin >> a >> b;

	V<string> s(100,"");
	rep(i, 50)rep(j, 100)s[i] += '#';
	rep(i, 50)rep(j, 100)s[50 + i] += '.';
	a--;b--;

	int pa = a / 50, qa = a % 50;

	rep(i, pa)rep(j, 50)s[2 * i][2 * j] = '.';
	rep(i, qa)s[48][2 * i] = '.';


	int pb = b / 50, qb = b % 50;

	rep(i, pb)rep(j, 50)s[99-2 * i][2 * j] = '#';
	rep(i, qb)s[51][2 * i] = '#';

	cout << 100 << " " << 100 << endl;
	rep(i, 100)cout << s[i] << endl;

}

Measured memory_bytes: 256
n = int(input())
t,a = map(int,input().split())
h = list(map(int,input().split()))
# print(n,t,a)
# print(h)
temperture = [ t - h[i] * 0.006 for i in range(n)]
# print(temperture)
tmp = abs(a - temperture[0])
ans = 0
for i in range(n):
    if tmp > abs(a - temperture[i]):
        tmp = abs(a -temperture[i])
        ans = i

print(ans+1)


Measured memory_bytes: 3064
n, m = map(int, input().split())

lst = [[] for i in range(3*n+1)]
dist = [-1 for i in range(3*n+1)]
for i in range(m):
    u, v = map(int, input().split())
    lst[u].append(v+n)
    lst[u+n].append(v+2*n)
    lst[u+2*n].append(v)

s, t = map(int, input().split())

next = lst[s]
next_next = []
not_empty = True
cost = 1
while not_empty:
    not_empty = False
    for i in next:
        if dist[i] == -1:
            dist[i] = cost
            next_next.extend(lst[i])
            not_empty = True
    next = next_next.copy()
    next_next = []
    cost += 1

if dist[t] != -1:
    print(dist[t]//3)
else:
    print(-1)

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

#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, list) for(auto i : list)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define fi first
#define se second
#define mp make_pair

using namespace std;

using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<double>;
using vs = vector<string>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;

const int INF = 1e9;
const int MOD = 1e9+7;

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

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

bool isPrime(ll n)
{
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0) return false;
    }
    return true;
}

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll A, B; cin >> A >> B;
    ll g = gcd(A, B);
    ll ans = 1;
    for(ll i = 2; i * i <= g; i++)
    {
        if(g % i == 0) ans++;
        while(g % i == 0) g /= i;
    }
    if(g > 1) ans++;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;
typedef pair<P,P> L;

const double EPS = 1e-7;

double dot(P a, P b){ return real(conj(a)*b); }
double cross(P a, P b){ return imag(conj(a)*b); }

int ccw(P a, P b, P c){
  b -= a;
  c -= a;
  if(cross(b,c) > EPS) return 1;
  if(cross(b,c) < -EPS) return -1;
  if(dot(b,c) < -EPS) return 2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}

P proj(P p, L l){
    return l.first + dot(p - l.first, l.second - l.first) / norm(l.second - l.first) * (l.second - l.first);
}

P reflect(P p, L l){
  return p + (proj(p,l) - p) * 2.0;
}

bool isIntersect(L s1, L s2){
  return ( ccw(s1.first,s1.second,s2.first) * ccw(s1.first,s1.second,s2.second) <= 0 &&
           ccw(s2.first,s2.second,s1.first) * ccw(s2.first,s2.second,s1.second) <= 0 );
}

P crossPoint(L l, L m){
  double A = cross(l.second - l.first, m.second - m.first);
  double B = cross(l.second - l.first, l.second - m.first);
  if(fabs(A) < EPS && fabs(B) < EPS) return m.first;
  else if(fabs(A) >= EPS) return m.first + B / A * (m.second - m.first);
}

L refL(L a,L b){
  return L(reflect(a.first,b),reflect(a.second,b));
}

int n;
L m[5];
int dm[5];
P g,s;
double ans;

double check(int d){
  vector<L> gm[8];
  L tp[5],tm[5];
  P gg=g;
  
  for(int i=0;i<n;i++)tp[i]=m[i];
  bool ff=0;
  if(d==2&&dm[0]==1&&dm[1]==0)ff=1;
  for(int i=0;i<d;i++){

    for(int j=0;j<n;j++){

      if(dm[i]==j) tm[i]=tp[j];
      else if(!i||dm[i-1]!=j)gm[i].push_back(tp[j]);

    }

    for(int j=0;j<n;j++)tp[j]=refL(tp[j],tm[i]);
    gg=reflect(gg,tm[i]);
  }
 
  for(int i=0;i<n;i++)
    if(!d||dm[d-1]!=i)gm[d].push_back(tp[i]);

  L sg=L(s,gg);
  double res=abs(s-gg);

  vector<P> v;

  v.push_back(s);
  for(int i=0;i<d;i++){
    if(!isIntersect(sg,tm[i]))res=1e9;
    v.push_back(crossPoint(sg,tm[i]));
  }
  
  v.push_back(gg);
  double dd=0;
  for(int i=0;i<=d;i++){
    L ww=L(v[i],v[i+1]);
    dd+=abs(v[i]-v[i+1]);
    for(int j=0;j<(int)gm[i].size();j++)
      if(isIntersect(ww,gm[i][j]))res=1e9;
  }
  if(abs(dd-res)>EPS)res=1e9;
  return res;
}

void dfs(int pr,int d){
  ans=min(ans,check(d));
  if(d==5)return;
  for(int i=0;i<n;i++){
    if(pr==i)continue;
    dm[d]=i;
    dfs(i,d+1);
  }
}

int main(){
  while(cin>>n,n){
    double x1,y1,x2,y2;
    for(int i=0;i<n;i++){
      cin>>x1>>y1>>x2>>y2;
      m[i]=L(P(x1,y1),P(x2,y2));
    }
    cin>>x1>>y1>>x2>>y2;
    g=P(x1,y1),s=P(x2,y2);
    ans=1e9;
    dfs(-1,0);
    printf("%f\n",ans);
  }
  return 0;
}

Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
long long n, h[1000200], dp[1000020], k;
long long fun(long long n)
{
    if (n <= 1)
        return 0;
    if (dp[n] != -1)
        return dp[n];
    dp[n] = fun(n - 1) + abs(h[n - 1] - h[n]);
    for (long long x = n - 1; x >= n - k && x > 0; x--)
        dp[n] = min(dp[n], fun(x) + abs(h[n] - h[x]));
    return dp[n];
}
int main()
{
    long long x, y, z, i, j;
    cin >> n >> k;
    memset(dp, -1, sizeof(dp));
    for (x = 1; x <= n; x++)
        cin >> h[x];
    long long ans = fun(n);
    cout << ans << endl;
}

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

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

    int res = 1;
    int trd = 0;
    for(int i = 0; i<N - 1; i++) {
        if(trd == 1 && A[i] > A[i + 1]) {
            res++;
            trd = 0;
        } else if(trd == -1 && A[i] < A[i + 1]) {
            res++;
            trd = 0;
        } else if(trd == 0 && A[i] < A[i + 1]) {
            trd = 1;
        } else if(trd == 0 && A[i] > A[i + 1]) {
            trd = -1;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 640
from itertools import combinations as C

N = int(input())
L = list(map(int, input().split()))
L = list(C(L, 3))
ans = 0
for l in L:
    l = list(l)
    l.sort()
    #print(l)
    if l[0] == l[1] or l[1] == l[2] or l[0] == l[2]:
        continue
    if l[0] + l[1] > l[2]:
        ans += 1
        
print(ans)

Measured memory_bytes: 20588
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

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

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int p;
	cin >> p;
	int x = a * p;
	int y = b;
	if(p > c){
		y += (p - c) * d;
	}

	cout << min(x, y) << endl;

	return 0;
}

Measured memory_bytes: 3204
#include<stdio.h>
#include<string.h>
#define M 1046527
#define NIL (-1)
#define L 14
char H[M][L]; 
 // 文字から数値に変換
int getChar(char ch){
    if ( ch == 'A' ) return 1;
    else if ( ch == 'C' ) return 2;
    else if ( ch == 'G' ) return 3;
    else if ( ch == 'T' ) return 4;
    else return 0;
}
 // 文字列から数値へ変換して key を生成する
long long getKey(char str[]){
    long long sum = 0, p = 1, i;
    for ( i = 0; i < strlen(str); i++ ) {
        sum += p*(getChar(str[i]));
        p *= 5;
    }
    return sum;
}
int h1(int key){
    return key % M;
}
int h2(int key){
    return 1+(key % (M-1));
}
int find(char str[]){
    long long key, i, h;
    key = getKey(str); // 文字列を数値に変換
    for ( i = 0;; i++ ) {
        h = (h1(key) + i * h2(key)) % M;
        if(strcmp(H[h],str) == 0 ){
            return 1;
        }else if(strlen(H[h]) == 0){
            return 0;
        }
    }
    return 0;
}
int insert(char str[]){
    long long key, i, h;
    key = getKey(str); // 文字列を数値に変換 
    for(i = 0; ; i++){
        h = (h1(key) + i * h2(key)) % M;
        if(strcmp(H[h],str) == 0 ){
            return 1;
        }else if(strlen(H[h]) == 0){
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}
int main(){
    int i, n, h;
    char str[L],com[9];
    for(int i=0;i<M;i++){
        H[i][0] = '\0';
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s%s",com,str);
        if(com[0]== 'i'){
            insert(str);
        }else{
            if(find(str)){
                printf("yes\n");
            }else{
                printf("no\n"); 
            }
        }
    }
    return 0;
}
         


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

int main() {
	// your code goes here
	double r;
	cin>>r;
	double c;
	c=2*3.141592653589793238*r;
	cout<<fixed<<setprecision(2)<<c<<endl;
	return 0;
}


Measured memory_bytes: 3788
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

class Main{

	public static void calc_railway(ArrayList<Integer> list){
		double x=0,l=0,v1,v2,ln=0;
		
		for(int i=0;i<10;i++){
			l += (double)list.get(i);
		}
		v1 = (double)list.get(10);
		v2 = (double)list.get(11);
		
		x = (v1*l)/(v1+v2);
		
		for(int i=0;i<10;i++){
			ln += list.get(i);
			if(ln >= x){System.out.println(i+1); break;}
		}
	}
	

	public static void rail_way(ArrayList<Integer> list){
		ArrayList <Integer> inp = new ArrayList<Integer>();
		
		for(int i=0;i<list.size()/12;i++){
			for(int j=0;j<12;j++){
				inp.add(list.get(i*12+j));
			}
			calc_railway(inp);
			inp.clear();
		}

	}
		
	public static void main(String args[]) throws IOException{
		String str;
		ArrayList <Integer> inp = new ArrayList<Integer>();

		Scanner scan = new Scanner(System.in);

		while(scan.hasNext()){
			str = scan.next();
			String [] strAry = new String[str.length()];
			strAry = str.split(",");
			for(int j=0;j<strAry.length;j++){
				Pattern p = Pattern.compile("[0-9]*");
				Matcher m = p.matcher(strAry[j]);
				if(m.find()){
					int x = Integer.valueOf(m.group(0)).intValue();
					inp.add(x);
				}
			}
		}
		rail_way(inp);
	}
}

Measured memory_bytes: 11000
#include <bits/stdc++.h>
using namespace std;
#include <math.h> 
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n,k;
	cin>>n>>k;
	if(n==k){
		cout << "Yes";
	}
	else{
		cout << "No";
	}
	// your code goes here
	return 0;
}

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

using namespace std;

int main(int argc, const char *argv[]) {
  int a, b, k;
  cin >> a >> b >> k;

  int cnt = 0, ans;
  for (int i = max(a, b); i >= 1; --i) {
    if (a % i == 0 && b % i == 0) {
      cnt++;

      if (cnt == k) {
        ans = i;
        break;
      }
    }
  }

  cout << ans << '\n';
  return 0;
}

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

typedef long long ll;

const ll M=1000000007;

ll dp[2002];

int main()
{
    ll s;
    cin>> s;
    dp[0]=1;
    for(int i=1;i<=s;i++){
        for(int j=3;j<=i;j++){
            dp[i]+=dp[i-j];
            if(dp[i]>=M) dp[i]-=M;
        }
    }
    cout<< dp[s] <<endl;
    return 0;
}

Measured memory_bytes: 3640
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::*,
    std::{cmp::*, collections::*, convert::*, iter::*, marker::*, mem::*, ops::*},
};
fn main() {
    input! {//
        n:i64,
        x:i64,
        MOD:i64,
    }
    let mut a = x;
    let mut v = vec![];
    v.push(a);
    let mut dup = 0;
    for k in 2..=1234124111 {
        a = (a * a) % MOD;
        if v.contains(&a) {
            dup = a;
            break;
        }
        v.push(a);
    }
    let ln = v.len() as i64;
    let mut ans = 0i64;
    let mut tt = 0i64;
    let mut dd = 0i64;
    if n < ln {
        ans = v.iter().take(n as usize).fold(0, |sum, x| sum + x);
        println!("{}", ans);
        return;
    }
    dd = v.iter().fold(0, |sum, x| sum + x);
    ans += dd;
    let n = n - ln;
    let mut a = dup;
    let mut v = vec![];
    v.push(a);
    for ll in 1.. {
        a = (a * a) % MOD;
        if v.contains(&a) {
            break;
        }
        v.push(a);
    }
    // dbg!(&v);
    let ln = v.len() as i64;
    if n < ln {
        ans += v.iter().take(n as usize).fold(0, |sum, x| sum + x);
        println!("{}", ans);
        return;
    }
    for (i, &x) in v.iter().enumerate() {
        let i = (i) as i64;
        ans += x * ((n - i + ln - 1) / ln);
        // let fl = n / ln;
        // if fl * (i) * ln < n {
        //     ans += x * (fl + 1);
        // } else {
        //     ans += x * fl;
        // }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2732
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;

  vector<vector<int>> W(n);
  int sz=1;
  for(int i=0;i<n;i++){
    sz*=3;
    W[i].resize(sz);
  }

  // k-th digit of v in ternary representation
  vector<int> po(n+1,1);
  for(int i=0;i<n;i++) po[i+1]=po[i]*3;
  auto digit=[&](int i,int j){
    return (j/po[i])%3;
  };

  for(int j=0;j<sz;j++)
    for(int i=0;i<n;i++)
      W[i][j%W[i].size()]=digit(i,j);

  int flip=0;
  auto query=[&](int i,int j){
    int val=W[i][j%W[i].size()];
    return (flip?3-val:val)%3;
  };
  auto update=[&](int i,int j,int val){
    W[i][j%W[i].size()]=(flip?3-val:val)%3;
  };

  auto rumba=[&](){
    int s=0,d=1;
    for(int i=0;i<n;i++){
      int x=(query(i,s+d*0)+1)%3;
      int y=(query(i,s+d*1)+1)%3;
      int z=(query(i,s+d*2)+1)%3;
      update(i,s+d*0,x);
      update(i,s+d*1,y);
      update(i,s+d*2,z);
      if(x==0) s+=d*0;
      if(y==0) s+=d*1;
      if(z==0) s+=d*2;
      d*=3;
    }
  };

  string t;
  cin>>t;

  for(char c:t){
    if(c=='S') flip^=1;
    if(c=='R') rumba();
  }

  vector<int> ans(sz,0);
  for(int j=0;j<sz;j++)
    for(int i=0;i<n;i++)
      ans[j]+=query(i,j)*po[i];

  for(int j=0;j<sz;j++){
    if(j) cout<<' ';
    cout<<ans[j];
  }
  cout<<newl;
  return 0;
}


Measured memory_bytes: 9492
#include <string>
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    string a,b;
    cin >> a >> b;
    string c;
    for (int i = a.length() - 1;i >= 0;i--) c.push_back(a[i]);
    if (b == c) printf("YES\n");
    else printf("NO\n");
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
mod = 13

s = input()

num_digits = len(s)

dp = [[0 for _ in range(mod)] for _ in range(num_digits)]
if s[0] == '?':
    dp[0] = [1 for _ in range(10)] + [0 for _ in range(10, 13)]
else:
    dp[0][int(s[0])] = 1

for i, c in enumerate(s[1:]):
    if c == '?':
        targets = range(10)
    else:
        targets = [int(c)]

    for j in targets:
        for k in range(mod):
            dp[i + 1][(k * 10 + j) % mod] += dp[i][k]

    for k in range(mod):
        dp[i + 1][k] %= int(10**9 + 7)

print(dp[-1][5])

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

int main() {
	string s;
	getline(cin, s);
	string suffix = s;
	smatch m;

	for (auto i = s.cbegin();
		 regex_search(i, s.cend(), m, regex("apple|peach"));
		 i = m[0].second) {
		cout << m.prefix() << (m.str()[0] == 'a' ? "peach" : "apple");
		suffix = m.suffix();
	}
	cout << suffix << endl;
}


Measured memory_bytes: 3064
N = int(input())
h = list(map(int, input().split()))
h_max = 100

cnt = 0
while True:
    decrease_cnt = 0
    for j in range(N):
        if h[j] > 0:
            h[j] -= 1
            decrease_cnt += 1
        elif decrease_cnt > 0:
            break
    if decrease_cnt == 0:
        print(cnt)
        break
    else:
         cnt += 1




Measured memory_bytes: 3060
#include <stdio.h>

int main(){
    int n;
    int a = 1000;
    scanf("%d", &n);
    
    if (n <= 1000){
        printf("%d\n", 1000 - n);
    }
    
    else{
        while (1){
            a += 1000;
            if (n <= a){
                printf("%d\n", a - n);
                break;
            }
        }
    }
    

    return 0;
}


Measured memory_bytes: 1732
#include<bits/stdc++.h>
#define rep(i,m) for(long long i=0; i<m; i++)
#define per(i,m) for(long long i=m-1; i>=0; i--)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define ROF(i,n,m) for(long long i=m-1; i>=n; i--)
#define SORT(v,n) do{sort(v,v+n);reverse(v,v+n);}while(0)
#define all(x) (x).begin(),(x).end()
#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
typedef pair<ll, ll> LP;

ll POW(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW(x*x,n/2)%MOD;
  return x%MOD*POW(x,n-1)%MOD;
}

ll POW2(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW2(x*x,n/2);
  return x*POW2(x,n-1);
}

ll POW3(ll x,ll n,ll m){
  x%=m;
  if(n==0)return 1;
  if(n%2==0)return POW3(x*x,n/2,m)%m;
  return x*POW3(x,n-1,m)%m;
}

ll gcd(ll u, ll v) {
  ll r;
  while (0 != v) {
    r = u % v; u = v; v = r;
  }
  return u;
}

ll lcm(ll u, ll v) {
  return u*v/gcd(u,v);
}
 
ll KAI(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI(m-1)%MOD;
}
 
ll KAI2(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI2(m-1);
}

ll extGCD(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extGCD(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
 
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}
 
ll modinv(ll a) {
    ll x, y;
    extGCD(a, MOD, x, y);
    return mod(x, MOD);
}
 
ll COM(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI(m)%MOD*modinv(KAI(n)%MOD*KAI(m-n)%MOD)%MOD;
}

ll COM2(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI2(m)/KAI2(n)/KAI2(m-n);
}

ll DEC(ll x,ll m,ll n)//xのm進数でのx^nの位の値
{
  return x%POW(m,n+1)/POW(m,n);
}

ll keta(ll x,ll n)//xのn進数での桁数
{
  if(x==0)return 0;
  return keta(x/n,n)+1;
}

ll DIV(ll x,ll n)//x!のnで割り切れる回数
{
  if(x==0)return 0;
  return x/n+DIV(x/n,n);
}

ll ORD(ll x,ll n)//xのnで割り切れる回数
{
  if(x==0)return INF;
  if(x%n!=0)return 0;
  return 1+ORD(x/n,n);
}

ll SGS(ll x,ll y, ll m)//1+x+…+x^(y-1)をmで割った余り
{
  if(y==0)return 0;
  if(y%2==0){
    return (1+POW3(x,y/2,m))*SGS(x,y/2,m)%m;
  }
  return (1+x*SGS(x,y-1,m))%m;
}

ll SSGS(ll x,ll y,ll m)//Σ[k=1→y](1+x+…+x^(k-1))をmで割った余り
{
  if(y==0)return 0;
  if(y==1)return 1;
  if(y%2==0){
    return (SSGS(x,y/2,m)*(POW3(x,y/2,m)+1)%m+SGS(x,y/2,m)*y/2%m)%m;
  }
  return (SSGS(x,y-1,m)*x%m+y)%m;
}

int main()
{
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  printf("%lld",b-b/c-b/d+b/lcm(c,d)-(a-1-(a-1)/c-(a-1)/d+(a-1)/lcm(c,d)));
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int H, A;
	scanf("%d %d", &H, &A);
	
	if(H % A == 0)
	{
		printf("%d", H / A);
	}
	else
	{
		printf("%d", H / A + 1);
	}
	
	return 0;
}

Measured memory_bytes: 3192
import collections
n=int(input())
v=[int(i) for i in input().split()]
p=v
u=v[0::2]
q=p[1::2]
U= collections.Counter(u)
Q= collections.Counter(q)
a=n/2-U.most_common()[0][1]
b=n/2-Q.most_common()[0][1]
if(a==0)and(b==0)and(U.most_common()[0][0]==Q.most_common()[0][0]):
  print(int(n/2))
else:
  if(U.most_common()[0][0]==Q.most_common()[0][0]):
    if(U.most_common()[1][1]<Q.most_common()[1][1]):
      b=n/2-Q.most_common()[1][1]
    else:
      a=n/2-U.most_common()[1][1]
  print(int(a+b))


Measured memory_bytes: 19040
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
use std::str::FromStr;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input {(source=$s:expr,$($r:tt)*) => {let mut iter=$s.split_whitespace(); let mut next=||{iter.next().unwrap()}; input_inner! {next,$($r)*}};($($r:tt)*) => {let stdin=std::io::stdin();let mut bytes=std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next=move||->String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()}; input_inner! {next,$($r)*}};}
#[allow(unused_macros)]
macro_rules! input_inner {($next:expr) => {}; ($next:expr,) => {}; ($next:expr,$var:ident:$t:tt$($r:tt)*) => {let $var=read_value!($next,$t); input_inner! {$next$($r)*}};}
#[allow(unused_macros)]
macro_rules! read_value {($next:expr,($($t:tt),*)) => {($(read_value! ($next,$t)),*)}; ($next:expr, [$t:tt; $len:expr]) => {(0..$len).map(|_|read_value! ($next,$t)).collect::<Vec<_>>()}; ($next:expr,chars) => {read_value! ($next,String).chars().collect::<Vec<char>>()}; ($next:expr,usize1) => {read_value! ($next,usize)-1}; ($next:expr,$t:ty) => {$next().parse::<$t>().expect("Parse error")};}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

#[allow(dead_code)]
const MAX: usize = 100006;
#[allow(dead_code)]
const INF_U32: u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32: i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64: u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64: i64 = 1 << 62;
#[allow(dead_code)]
const MOD: i64 = 1e9 as i64 + 7;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(unused_imports)]
use std::f64;


fn main() {
    input!{n:usize, k:i64, a:[(i64,i64);n]};
    let mut a = a;
    a.sort();

    let mut idx = 0i64;
    for i in 0..n {
        idx += a[i].1;
        if idx >= k {
            println!("{}", a[i].0);
            return();
        }
    }

}

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

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast")

using namespace std;
using ll = long long;

// MACRO
// for loop
#define REP(i, n) for (ll i = 0; i < ll(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= ll(b); i--)

// for vector
#define ALL(x) x.begin(), x.end()
#define SIZE(x) ll(x.size())
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort(ALL(x), greater<int>())
#define RSORTS(x) sort(ALL(x), greater<string>())
#define FIND(x, n) find(ALL(x), n)
#define VFOR(e, x) for (auto &e : x)

// Constant
const ll INF = 1000000000000; // 10^12:  ∞
const int MOD = 1000000007;   // 10^9+7: Congruence ceremony MOD
const int MAXR = 100000;      // 10^5:   Array Max Range
const char EL = '\n';         // newline

// alias
#define EB emplace_back // push as last element
#define PP pop_back     // pop last element
#define MP make_pair    // pair constractor
#define F first         // first element of pair
#define S second        // second element of pair

// change max/min
template <class T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
  if (b < a)
  {
    a = b;
    return 1;
  }
  return 0;
}

// optimize in/out
#define OPTIMIZE_CIN_COUT() \
  cin.tie(0);               \
  ios::sync_with_stdio(false);

template <typename... Args>
void input(Args... args)
{
  for (int &e : {args...})
  {
    cin >> e;
  }
}
#define INPUT1(a) \
  int a = 0;      \
  cin >> a;
#define INPUT2(a, b) \
  int a = 0;         \
  int b = 0;         \
  cin >> a >> b;
#define INPUT3(a, b, c) \
  int a = 0;            \
  int b = 0;            \
  int c = 0;            \
  cin >> a >> b >> c;
#define INPUTS(s) \
  string s = "";  \
  cin >> s;

#define INPUTA(n, a) \
  int n = 0;         \
  cin >> n;          \
  vector<int> a(n);  \
  REP(i, n)          \
  {                  \
    cin >> a[i];     \
  }
#define INPUTB(x, y, b)                     \
  int x = 0, y = 0;                         \
  cin >> x >> y;                            \
  vector<vector<int>> b(y, vector<int>(x)); \
  REP(i, y)                                 \
  {                                         \
    REP(j, x)                               \
    {                                       \
      cin >> b[i][j];                       \
    }                                       \
  }

int main()
{
  OPTIMIZE_CIN_COUT();

  INPUT1(X);
  if (X >= 30)
  {
    cout << "Yes";
  }
  else
  {
    cout << "No";
  }

  // INPUT2(A, B);
  // INPUT3(A, B, C);
  // INPUTS(S);
  // INPUTA(N, A);
  // INPUTB(X, Y, B);
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;

long long solve(int N, vector<int> L, vector<int> R)
{
    vector<pair<int,int>> tmp;
    for (int i=0; i<N; i++)
        tmp.push_back(make_pair(R[i], -L[i]));
    sort(tmp.begin(), tmp.end());
    for (int i=0; i<N; i++)
        R[i] = tmp[i].first,
        L[i] = -tmp[i].second;

    vector<int> L2, R2;
    L2.push_back(L[0]);
    R2.push_back(R[0]);
    int maxL = L[0];
    for (int i=1; i<N; i++)
    {
        if (L[i] > maxL)
        {
            L2.push_back(L[i]);
            R2.push_back(R[i]);
            maxL = L[i];
        }
    }
    int N2 = (int)L2.size();

    long long ans = 0;
    if (N2==1)
    {
        ans = R[0]-L[0]+1LL + R[N-1]-L[N-1]+1LL;
    }
    else
    {
        for (int i=0; i<N2-1; i++)
            ans = max(ans,
                max(0LL, R2[0]-L2[i]+1LL) +
                max(0LL, R2[i+1]-L2[N2-1]+1LL));
    }

    for (int i=0; i<N; i++)
        ans = max(ans, R[i]-L[i]+1LL);

    multiset<int> LS, RS;
    for (int i=0; i<N; i++)
    {
        LS.insert(L[i]);
        RS.insert(R[i]);
    }
    for (int i=0; i<N; i++)
    {
        LS.erase(LS.find(L[i]));
        RS.erase(RS.find(R[i]));

        ans = max(ans,
            max(0LL, R[i]-L[i]+1LL)+
            max(0LL, *RS.begin()-*LS.rbegin()+1LL));

        LS.insert(L[i]);
        RS.insert(R[i]);
    }

    return ans;
}

long long naive(int N, vector<int> L, vector<int> R)
{
    long long ans = 0;

    for (int b=1; b<(1<<N)-1; b++)
    {
        int l1 = 1;
        int r1 = 1000000000;
        int l2 = 1;
        int r2 = 1000000000;

        for (int i=0; i<N; i++)
        {
            if (b>>i&1)
            {
                l1 = max(l1, L[i]);
                r1 = min(r1, R[i]);
            }
            else
            {
                l2 = max(l2, L[i]);
                r2 = min(r2, R[i]);
            }
        }
        ans = max(ans, max(r1-l1+1LL, 0LL)+max(r2-l2+1LL, 0LL));
        //cout<<b<<" "<<ans<<endl;
    }
    return ans;
}

int main()
{
    //*
    int N;
    cin>>N;
    vector<int> L(N), R(N);
    for (int i=0; i<N; i++)
        cin>>L[i]>>R[i];

    cout<<solve(N, L, R)<<endl;
    /*/

    while (true)
    {
        int N = 6;
        vector<int> L(N), R(N);
        for (int i=0; i<N; i++)
        {
            while (true)
            {
                L[i] = rand()%10+1,
                R[i] = rand()%10+1;
                if (L[i]<=R[i])
                    break;
            }
        }

        long long ans1 = solve(N, L, R);
        long long ans2 = naive(N, L, R);
        if (ans1 != ans2)
        {
            cout<<ans1<<" "<<ans2<<endl;
            cout<<N<<endl;
            for (int i=0; i<N; i++)
                cout<<L[i]<<" "<<R[i]<<endl;
            break;
        }
    }
    //*/
}

/*
3
2 8
9 9
3 5

3
4 7
2 6
1 10
*/



Measured memory_bytes: 12916
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <ctype.h>

#define  NUMBER 3

int main( void )
{
    int  nPrice[NUMBER];
    int  i,j;
    int  tmp;
    
    scanf( "%d %d %d" , &nPrice[0], &nPrice[1], &nPrice[2]);

    for ( i = 0; i < NUMBER - 1 ; i++)
    {
        if ( nPrice[i] > nPrice[i+1] )
        {
            tmp         = nPrice[i];
            nPrice[i]   = nPrice[i+1];
            nPrice[i+1] = tmp;
        }
    }

    printf("%d", nPrice[0] + nPrice[1]);
    printf("\n");

    return ( 0 );

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr ll mod = 1e9+7;
int main(){ 
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  ll res = 0;
  for (int d = 0; d < 60 ; d++) {
    ll odd = 0, even = 0;
    for (int i = 0; i < n; i++) {
      if (1 & (a[i] >> d)) odd++;
      else even++;
    }
    ll sum = ((even * odd) % mod * ((1LL<<d) % mod)) % mod;
    (res += sum) %= mod;
  }
  cout << res << endl;
  return 0;
} 

Measured memory_bytes: 2560
#include<stdio.h>
#include<iostream>
using namespace std;


int main()
{	
	int x,i;

	i = 0;
	while (cin >> x)
	{
		i = i++;
			if (x == 0)
		{
			return 0;
		}
		
		cout << "Case " <<i <<": " << x <<endl;
	
	}
	return 0;
}

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

int main() {
    int a, b, c, x, cnt = 0;
    cin >> a >> b >> c >> x;

    for (int i = 0; i <= a; i++)
    {
        int A = 0, B = 0, C = 0;
        A = 500 * i;
        for (int j = 0; j <= b; j++)
        {
            B = 100 * j;
            for (int k = 0; k <= c; k++)
            {
                C = 50 * k;
                if (x == A + B + C) cnt++;
            }
            
        }
        
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // 整数スキャン（複数）
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // n個の整数のスキャン
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // 文字列スキャン
    /*
    string s;
    cin >> s;
    */

    // n個の文字列スキャン
    /*
    vector<string> slist;
    rep(i,n){
        string s;
        cin >> s;
        slist.push_back(s);
    }
    */

int main() {
    int n;
    scanf("%d",&n);
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    ll a[n] = {};
    int a1=0;
    int a2=0;
    int a3=0;
    rep(i,n){
        scanf("%lld",&a[i]);
        if(a[i]<=x){
            a1++;
        }else if(a[i]<=y){
            a2++;
        }else{
            a3++;
        }
    }


    int ans = 99999;
    mins(ans,a1);
    mins(ans,a2);
    mins(ans,a3);
    cout << ans << endl;
    return 0;
}
 
 


Measured memory_bytes: 256
/**
 * author:    Ziel
 * created:   19.04.2020 16:44:21
**/

// ~zaletaet~

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#define fi first
#define se second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const ll N = 1e5 + 123, MOD = 1e9 + 7, oo = 1e9 + 9, INF = 1e18 + 9;
const double EPS = 1e-9, PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	int n;
	cin >> n;
	
	string str;
	cin >> str;
	deque<char> s;
	for (int i = 0; i < n; i++) {
		s.pb(str[i]);
	}
	
	while (true) {
		bool neg = false;
		int bal = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == '(') bal++;
			else {
				bal--;
				if (bal < 0) neg = true;
			}
		}
		
		if (neg) s.push_front('(');
		else {
			if (bal > 0) s.pb(')');
			else break;
		}
		n = sz(s);
	}
	
	for (char c: s) cout << c;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+99,M=61e4;
inline int min(const int&a,const int&b){return a<b?a:b;}
struct graph{
	struct edge{int to,next,f;}e[M<<1];
	int h[N],cur[N],xb;
	inline void addedge(int x,int y,int z){
		e[++xb]=(edge){y,h[x],z};h[x]=xb;
		e[++xb]=(edge){x,h[y],0};h[y]=xb;
	}
	int S,T,d[N],n;
	inline bool bfs(){
		static int q[N];int t=0,w=1;q[1]=S;
		memset(d+1,0,n<<2);d[S]=1;
		for(;t<w;){
			int u=q[++t];
			for(int i=h[u];i;i=e[i].next)if(e[i].f && !d[e[i].to])
				d[e[i].to]=d[u]+1,q[++w]=e[i].to;
		}
		return d[T];
	}
	int dfs(int x,int f){
		if(x==T)return f;
		int ans=0,&i=cur[x],t;
		for(;i;i=e[i].next)if(e[i].f && d[e[i].to]==d[x]+1){
			if(t=dfs(e[i].to,min(f,e[i].f))){
				ans+=t,e[i].f-=t;e[i^1].f+=t;f-=t;
				if(!f)break;
			}
		}
		return ans;
	}
	inline int dinic(int s,int t){
		int ans=0;S=s;T=t;
		for(;bfs();ans+=dfs(s,1<<30))memcpy(cur+1,h+1,n<<2);
		return ans;
	}
}g;
int n,i,j,fa[N],bel[N],u1[N],v1[N];
vector<int>v[N],vv[N];
void dfs(int x){
	auto t=v[x];v[x].clear();
	for(int y:t)if(!fa[y])fa[y]=x,dfs(y);
}
int main(){
	scanf("%d",&n);
	g.n=n*2;g.xb=1;
	for(i=2;i<=n;++i)g.addedge(n-2+i,g.n,1);
	for(i=1;i<n;++i){
		scanf("%d",&j);vv[i].resize(j);
		for(int&x:vv[i]){scanf("%d",&x);if(x>1)g.addedge(i,n-2+x,1);}
		g.addedge(g.n-1,i,1);
	}
	if(g.dinic(g.n-1,g.n)<n-1){puts("-1");return 0;}
	for(i=1;i<n;++i){
		for(j=g.h[i];g.e[j].f;j=g.e[j].next);
		int x=g.e[j].to-(n-2);bel[x]=i;
//cerr<<x<<' '<<i<<endl;
		for(int y:vv[i])if(y!=x)v[y].push_back(x);
	}
	dfs(1);
	for(i=1,j=0;i<=n;++i)j+=!fa[i];
	if(j>1){puts("-1");return 0;}
	for(i=2;i<=n;++i)u1[bel[i]]=i,v1[bel[i]]=fa[i];
//	for(i=1;i<=n;++i)if(fa[i])printf("%d %d\n",i,fa[i]);
	for(i=1;i<n;++i)printf("%d %d\n",u1[i],v1[i]);
	return 0;
}

Measured memory_bytes: 38528
#include "bits/stdc++.h"
using namespace std;

int main() {
	int M, F, R;
	for (int a = 0; ; a++) {
		cin >> M >> F >> R;
		if (M == -1 && F == -1 && R == -1) break;
		if (M == -1 || F == -1) cout << "F";
		else if (M + F >= 80) cout << "A";
		else if (M + F >= 65) cout << "B";
		else if (M + F >= 50) cout << "C";
		else if (M + F >= 30) {
			if (R >= 50) cout << "C";
			else cout << "D";
		}
		else cout << "F";
		cout << endl;
	}
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll a,b,c,x;
  cin >> a >> b >> c >> x;
  ll ans=0;
  rep(i,a+1) {
    rep(j,b+1) {
      rep(k,c+1) {
        ll s=i*500+j*100+k*50;
        if(x==s) ans++;
      }
    }
  }
  pr(ans);
}

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


Measured memory_bytes: 256
n=int(input())
A=list(map(int,input().split()))
s=sum(A)
q=int(input())
from collections import Counter
a=Counter(A)
r=[0]*q
for i in range(q):
	b,c=map(int,input().split())
	s+=(c-b)*a[b]
	a[c]+=a[b]
	a[b]=0
	r[i]=s
for i in r:print(i)

Measured memory_bytes: 26964
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

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

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;

static inline ll mod(ll x, ll m)
{
    ll y = x % m;
    return (y >= 0 ? y : y+m);
}

// }}}

int N, K;
int a[100];
bool dp[100001];

void solve()
{
    dp[0] = false;
    REP (i, K+1) {
        REP (j, N) {
            if (i + a[j] <= K) dp[i+a[j]] |= !dp[i];
        }
    }
    cout << (dp[K] ? "First" : "Second") << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    REP (i, N) cin >> a[i];
    solve();
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 384
package main

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

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func absFloat64(a float64) float64 {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func minFloat64(a, b float64) float64 {
	if a > b {
		return b
	} else {
		return a
	}
}

func str2Int(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

//Main
var sc = bufio.NewScanner(os.Stdin)

var A, B int

func main() {
	sc.Split(bufio.ScanWords)
	A, B := nextInt(), nextInt()

	fmt.Println(A * B)
}


Measured memory_bytes: 1752
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }
    let mut s = 0usize;
    for &ai in &a {
        s ^= ai;
    }
    let mut result = vec![];
    for &ai in &a {
        result.push(ai ^ s);
    }
    println!(
        "{}",
        result
            .iter()
            .map(|x| format!("{}", x))
            .collect::<Vec<_>>()
            .join(" ")
    );
}


Measured memory_bytes: 20968