akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define len(x) (int)(x.size())
#define all(vs) vs.begin(), vs.end()
using ii = pair<int, int>;
using ll = long long;

int mod = 1e9+7;

int ext_gcd(int a, int b, int& x, int& y){
    if(b==0){
        x=1; y=0; return a;
    }
    else{
        int g = ext_gcd(b, a%b, y, x);
        y-=a/b*x; return g;
    }
}
int mod_inv(int a){
    int x, y;
    ext_gcd(a, mod, x, y);
    return (x%mod+mod)%mod;
}

#define MAXN 1000009
int fat[MAXN];
void init(){
    fat[0] = 1;
    for(int i=1; i<MAXN; ++i)
        fat[i]=(i*fat[i-1])%mod;
}
int comb(int a, int b){
	int num = fat[a];
	int den = (fat[a-b]*fat[b])%mod;
	return (num*mod_inv(den))%mod;
}
int32_t main(){
	init();
	ios::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	vector<int> vs(n+1);
	for(int i=1; i<=n; ++i) cin >> vs[i];
	sort(vs.begin()+1, vs.end());
	
	for(int i=1; i<=n; ++i) vs[i] += vs[i-1];
	int ans = 0;
	for(int i=0, z = n-k+1; z>0 ; ++i, --z){
		int sum = (vs[n]-vs[n-z]) - vs[z];
		sum%=mod;
		ans = (ans + (comb(k-2+i, k-2)*sum)%mod)%mod;
	}
	cout << ans << endl;
}


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

using namespace std;

vector<int>arr;
bool IsOK(int index, int key)
{
    if (arr[index] <= key) return true;
    else return false;
}
static int Binary_search(int key)
{
    int ok = -1;
    int ng = arr.size();
    while (abs(ok - ng) > 1)
    {
        int mid = ng + (ok - ng) / 2;

        if (IsOK(mid, key)) ok = mid;
        else ng = mid;
    }

    return ok;
}

int main() {
    while (true) {
        int n, m;
        cin >> n >> m;
        if (n == 0 && m == 0)break;
        vector<int> p(n);
        arr=vector<int>(0);
        for (int i = 0; i < n; i++)cin >> p[i];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                arr.push_back((i != n ? p[i] : 0) + (j != n ? p[j] : 0));
            }
        }
        sort(arr.begin(), arr.end());
        int ret = 0;
        for (int i = 0; i < arr.size() && arr[i] <= m; i++) {
            ret = max(ret, arr[i] + arr[Binary_search(m - arr[i])]);
        }
        cout << ret << endl;
    }
    return 0;
}


Measured memory_bytes: 7024
N = int(input())
A = list(map(int, input().split()))
maney = 1000
stock = 0

for i in range(N):
    if i == N-1:
        maney += stock * A[i]
        break
    if A[i] < A[i+1]:
        tmp_stock = maney // A[i]
        stock += tmp_stock
        maney -= tmp_stock * A[i]
    elif A[i] > A[i+1]:
        maney += stock * A[i]
        stock = 0
    else:
        pass

print(maney)


Measured memory_bytes: 9200
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		new Main().start();
	}
	int[] matchTo;
	boolean[] vis;
	ArrayList<Integer>[] g;
	@SuppressWarnings("unchecked")
	void start(){
		Scanner in = new Scanner(System.in);
		int x = in.nextInt();
		int y = in.nextInt();
		int e = in.nextInt();
		int[] xs = new int[e];
		int[] ys = new int[e];
		g = new ArrayList[x + y];
		for(int i = 0; i < x + y; i++){
			g[i] = new ArrayList<>();
		}
		for(int i = 0; i < e; i++){
			xs[i] = in.nextInt();
			ys[i] = in.nextInt() + x;
			g[xs[i]].add(ys[i]);
			g[ys[i]].add(xs[i]);
		}
		vis = new boolean[x + y];
		matchTo = new int[x + y];
		Arrays.fill(matchTo, -1);
		int match = 0;
		for(int i = 0; i < x; i++){
			Arrays.fill(vis, false);
			if(dfs(i))match++;
		}
		System.out.println(match);
		in.close();
	}
	boolean dfs(int v){
		if(v < 0)
			return true;
		for(int u : g[v]){
			if(vis[u])
				continue;
			vis[u] = true;
			if(dfs(matchTo[u])){
				matchTo[u] = v;
				matchTo[v] = u;
				return true;
			}
		}
		return false;
	}

}

Measured memory_bytes: 50452
# !入力
# グラフの構築
# クエリの入力
# Kからの各点のの距離をdfs
# クエリの処理
from collections import deque
n=int(input())
edge=[[]for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  edge[a-1].append((b-1,c))
  edge[b-1].append((a-1,c))
q,k=map(int,input().split())
dist=[0]*n
seen=[False]*n
todo=deque([k-1])
while todo:
  par=todo.popleft()
  seen[par]=True
  for cld,cost in edge[par]:
    if dist[cld]==0:
      if seen[cld]==False:
        dist[cld]=dist[par]+cost
        seen[cld]=True
        todo.append(cld)

for i in range(q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])
  
  

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int tmp=0;
    int count=0;
    for(int i=0;i<n;i++){
        //cout << "tmp:" << tmp << endl;
        for(int j=0;j<n;j++){
            swap(a[i],a[j]);
            count=0;
            for(int k=0;k<n-1;k++){
                if(a[k]>a[k+1]){
                    tmp=0;
                    //cout << "if" << endl;
                    break;
                }
                count=k;
                //cout << "k:" << k << endl;
            }
            //cout << "count:" << count << endl;
            if(count==n-2){
                tmp=1;
                break;
            }
            swap(a[i],a[j]);    
        }
        if(tmp==1) break;
    }
    cout << (tmp ? "YES":"NO") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1000000000000000001
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  ll N, C;
  cin >> N >> C;
  vector<vector<ll>> D(C, vector<ll>(C));
  for (ll i = 0; i < C; ++i)
  {
    for (ll j = 0; j < C; ++j)
    {
      cin >> D.at(i).at(j);
    }
  }
  vector<vector<ll>> board(N, vector<ll>(N));
  for (ll i = 0; i < N; ++i)
  {
    for (ll j = 0; j < N; ++j)
    {
      ll temp;
      cin >> temp;
      board.at(i).at(j) = temp - 1;
    }
  }

  vector<vector<ll>> point(3, vector<ll>(C, 0));
  for (ll i = 0; i < C; ++i)
  {
    for (ll j = 0; j < N; ++j)
    {
      for (ll k = 0; k < N; ++k)
      {
        point.at((k + j + 2) % 3).at(i) += D.at(board.at(j).at(k)).at(i);
      }
    }
  }

  vector<vector<ll>> sort_point = point;
  for (ll i = 0; i < 3; ++i)
  {
    sort(sort_point.at(i).begin(), sort_point.at(i).end());
  }
  vector<vector<pll>> pos(3, vector<pll>(3));//point, color
  for (ll i = 0; i < 3; ++i)
  {
    for (ll j = 0; j < 3; ++j)
    {
      pos.at(i).at(j) = {sort_point.at(i).at(j), find(point.at(i).begin(), point.at(i).end(), sort_point.at(i).at(j)) - point.at(i).begin()};
      if (j == 0)
      {
        continue;
      }
      if (pos.at(i).at(j - 1).first == pos.at(i).at(j).first)
      {
        pos.at(i).at(j).second = find(point.at(i).begin() + pos.at(i).at(j - 1).second + 1, point.at(i).end(), sort_point.at(i).at(j)) - point.at(i).begin();
      }
    }
  }
  ll ans = INF;
  vector<ll> perm = {0, 1, 2};
  while (true)
  {
    map<ll, bool> already;
    ll temp = 0;
    for (ll i = 0; i < 3; ++i)
    {
      for (ll j = 0; j < 3; ++j)
      {
        if (already[pos.at(perm.at(i)).at(j).second])
        {
          continue;
        }
        already[pos.at(perm.at(i)).at(j).second] = true;
        temp += pos.at(perm.at(i)).at(j).first;
        break;
      }
    }
    ans = min(ans, temp);
    if (!next_permutation(perm.begin(), perm.end()))
    {
      break;
    }
  }
  // for (ll i = 0; i < 3; ++i)
  // {
  //   for (ll j = 0; j < 3; ++j)
  //   {
  //     cout << pos.at(i).at(j).first << ',' << pos.at(i).at(j).second << ' ';
  //   }
  //   cout << endl;
  // }
  cout << ans << endl;

}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()

using namespace std;
int INF = 1e9;
int N;
string S;
vector<int> black;
vector<int> white;
int main(){
    cin >> N >> S;
    
    int ans = INF;
    
    rep(i,N){
        if(S[i] == '#') black.pb(i);
        else white.pb(i);
    }
    
    rep(i,black.size()){
        auto itr = lower_bound(ALL(white),black[i]);
        int val = white.end() - itr;
        ans = min(ans,val+i);
    }    
    
    int n = black.size();
    ans = min(ans,n);
        

    cout << ans << endl;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define inf (ll)1e9
#define d(x) cerr<<#x<<"="<<x<<endl;

int a[100001],mina[100001];

int main(void){
    int n,t;
    int ans=0;
    cin>>n>>t;
    rep(i,n)cin>>a[i];
    int minv=inf;
    rep(i,n){
        if(a[i]<minv)minv=a[i];
        mina[i]=minv;
    }
    int maxv=0;
    rep(i,n){
        if(maxv<a[i]-mina[i]){
            ans=1;
            maxv=a[i]-mina[i];
        }
        else if(maxv==a[i]-mina[i])ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
import sys
import numpy as np

n = int(sys.stdin.readline())
ms = []
for i in range(n):
    ms += [int(sys.stdin.readline())]

total = sum(ms)
dp = np.zeros(total + 1, dtype=np.int64)
dp[0] = 1

for m in ms:
    dp[m:] = (dp[m:] * 2 + dp[:-m]) % 998244353
    dp[:m] = dp[:m] * 2 % 998244353

border = (total + 1) // 2
yo = sum(dp[border:]) % 998244353 * 3

if total % 2 == 0:
    dp2 = np.zeros(total // 2 + 1, dtype=np.int64)
    dp2[0] = 1
    for m in ms:
        dp2[m:] = (dp2[m:] + dp2[:-m]) % 998244353
    yo = yo - dp2[-1] * 3 % 998244353

print((3 ** n  - yo)% 998244353)


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

using namespace std;
using ll =long long;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#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;
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; }
using P = pair<int,int>;
//Write From this Line

int main()
{
	int n;
	cin >> n;
	vector<int> fact(101,0);
	For(i,1,n+1){
		int now = 2;
		int mul = i;
		while(mul != 1 && now <= 10 ){
			if(mul % now == 0){
				mul /= now;
				fact[now]++;
			} else {
				now += 1;
			}
		}
		if(mul != 1) fact[mul] ++ ;
	}
	int ni = 0,  yon = 0, juyon = 0, nijuyon = 0, nanayon = 0;
	rep(i,101){
		if(fact[i] >= 2){
			ni ++;
		}
		if(fact[i] >= 4) yon ++;
		if(fact[i] >= 14) juyon++;
		if(fact[i] >= 24) nijuyon ++;
		if(fact[i] >= 74) nanayon ++;
	}
	ll ans = 0;
	ans += max(0, (yon * (yon - 1) * (ni-2)) / 2);
	ans += max(0,(juyon) * (yon - 1));
	ans += max(0,(nijuyon) * (ni - 1));
	ans += nanayon;
	cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
int main() {
    char ch;
    int cnt[26] = {0};
    while(cin >> ch) {
        ch = tolower(ch);
        if(isalpha(ch)) ++cnt[ch-'a'];
    }
    for(int i = 0; i < 26; ++i) {
        printf("%c : %d\n", 'a' + i, cnt[i]);
    }
    return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORR(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)

#define CHMIN(a, b) (a) = min((a), (b))
#define CHMAX(a, b) (a) = max((a), (b))

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(),x.end()



int main() {
    int N,A,B,C,D;
    cin >> N >> A >> B >> C >> D;
    A--,B--,C--,D--;
    string s;
    cin >> s;

    bool ans = true;

    if(C==D){
        cout << "No" << endl;
        return 0;
    }

    if(C<D){
        int seq_rock = 0;

        for(int i=A;i<s.size();i++){ //石が2つ以上連続してないかチェック
          if(i==C)break;
          if(s[i]=='#'){
              seq_rock++;
              if(seq_rock>1){
                  ans = false;
                  break;
              }
          }
          else seq_rock=0;
        }

        seq_rock = 0;
        for(int i=B;i<s.size();i++){ //石が2つ以上連続してないかチェック
          if(i==D)break;
          if(s[i]=='#'){
              seq_rock++;
              if(seq_rock>1){
                  ans = false;
                  break;
              }
          }
          else seq_rock=0;
        }
    }

    if(C>D){
        int seq_rock = 0;

        for(int i=A;i<s.size();i++){ //石が2つ以上連続してないかチェック
          if(i==C)break;
          if(s[i]=='#'){
              seq_rock++;
              if(seq_rock>1){
                  ans = false;
                  break;
              }
          }
          else seq_rock=0;
        }

        seq_rock = 0;
        bool throughble = false;
        for(int i=B;i<s.size();i++){ //石が2つ以上連続してないかチェック
          if(i+1>=s.size())break;
          if(s[i-1]=='.'&&s[i+1]=='.'&&s[i]=='.'){
              throughble = true;

          }
          if(i==D)break;
          if(s[i]=='#'){
              seq_rock++;
              if(seq_rock>1){
                  ans = false;
                  break;
              }
          }
          else seq_rock=0;
        }

        if(!throughble)ans= false;

    }

    if(ans)cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}



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


int main(){
  int c[3][3];
  rep(i, 3){
    rep(j, 3){
      cin >> c[i][j];
    }
  }
  int f = 0;
  vector<vector<int>> co ={
    {1, 0}, {2, 1}, {0, 2}
  };
  rep(i, 3){
    int nx0 = co[i][0];
    int nx1 = co[i][1];
    int d1 = c[0][nx1] - c[0][nx0];
    int d2 = c[1][nx1] - c[1][nx0];
    int d3 = c[2][nx1] - c[2][nx0];
    if(d1 != d2 || d2 != d3 || d3 != d1) f = 1;
  }
  rep(i, 3){
    int ny0 = co[i][0];
    int ny1 = co[i][1];
    int d1 = c[ny1][0] - c[ny0][0];
    int d2 = c[ny1][1] - c[ny0][1];
    int d3 = c[ny1][2] - c[ny0][2];
    if(d1 != d2 || d2 != d3 || d3 != d1) f = 1;
  }
  if(f == 1) cout << "No" << endl;
  else cout << "Yes" << endl;
}


Measured memory_bytes: 3612
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("You can win")
    else:print("You will lose")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
n = ip()                                     #入力整数1つ
#a,b,c= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
## a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#k = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
s = a[0]
for i in range(1,n):
    s = s * a[i] // fractions.gcd(a[i], s)
b = 0
s-=1
for i in range(n):
    b+=s%a[i]
print(b)

Measured memory_bytes: 13832
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define xx first
#define yy second
 
#define pii pair <int, int >
#define pll pair < ll, ll >
#define xx first
#define yy second
#define vi vector < int >
#define vl vector < ll >
#define vp vector < pii >
 
#define inf  100000000
 
#define f(i, c, n) for(int i = c; i < n; i++)
#define fe(i, c, n) for(int i = c; i <= n; i++)
#define fr(i, n, c) for(int i = n - 1; i >= c; i--)
 
#define be(a) a.begin(), a.end()
#define vsort(a) sort(a.begin(), a.end())
#define mem(a) memset(a, 0, sizeof(a))
#define memn(a) memset(a, -1, sizeof(a))
#define srti(a, n) sort(a, a + n)
#define srtd(a, n) sort(a, a + n, greater<int>())
#define LB(a, x) (lower_bound(vbe(a), x) - a.begin())
#define UB(a, x) (upper_bound(vbe(a), x) - a.begin())
#define S " "
#define N "\n"

//cout << "Case " << ++cs << ": " <<
#define fast ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FILE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);


void solve() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	a += b;
	c += d;

	if(a > c) {
		cout << "Left" << N;
	} else if(a < c) {
		cout << "Right" << N;
	} else {
		cout << "Balanced" << N;
	}
}

int main() {
    // FILE;
    fast;
    // int t; cin >> t; while(t--)
    solve();
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
typedef     long long    ll;
typedef     vector<int> vi;
typedef     vector<long long> vl;
typedef     pair<int, int>pi;
typedef     pair<long long, long long>pl;
#define F   first
#define S   second
#define pb  push_back
#define     all(x)      x.begin() , x.end()
#define mp  make_pair
#define       FOR(i,a,b) for(i=a;i<=b;i++)
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)
int main()
{
   ll n,j,k,i,x,y,c=0;
   cin>>n>>k;
   int a[n+2];
   vi v;
   FOR(i,1,n)  cin>>a[i];
    FOR(i,k+1,n)
    {
      if(a[i]>a[i-k])  cout<<"Yes"<<endl;
      else cout<<"No"<<endl;
    }
}

Measured memory_bytes: 4388
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;
typedef vector<pair<int,int> > vp;

void split(vp &v,int x){
	int cnt=0,l,r;
	fr(i,v){
		l=i->first; r=i->second;
		if(x<=cnt+r-l+1){
			if(x==cnt+r-l+1)break;
			i=v.erase(i);
			v.insert(i,mp(l+x-cnt,r));
			v.insert(i,mp(l,l+x-cnt-1));
			break;
		}
		cnt+=r-l+1;
	}
}
void cut(vp &v,int x,int y){
	split(v,x); split(v,y);
	vp ret;
	int l,r,cnt=0;
	rep(i,v.size()){
		cnt+=v[i].second-v[i].first+1;
		if(cnt==x)l=i;
		if(cnt==y)r=i;
	}
	for(int i=r+1;i<v.size();i++)ret.pb(v[i]);
	for(int i=l+1;i<=r;i++)ret.pb(v[i]);
	for(int i=0;i<=l;i++)ret.pb(v[i]);
	v=ret;
}

int main()
{
	int n,m,p,q,r;
	while(scanf("%d",&n),n){
		vp taba;
		taba.pb(mp(1,n));
		
		scanf("%d",&m);
		scanf("%d%d%d",&p,&q,&r);
		
		rep(i,m){
			int x,y; scanf("%d%d",&x,&y);
			cut(taba,x,y);
		}
		if(p>1)split(taba,p-1); if(q<n)split(taba,q);
		int ans=0,cnt=0,a,b; bool plus=0;
		fr(i,taba){
			a=i->first; b=i->second;
			if(cnt+1==p)plus=1;
			if(plus){
				if(b<=r)ans+=b-a+1;
				else if(a<=r)ans+=r-a+1;
			}
			cnt+=b-a+1;
			if(cnt==q)break;
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1116
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#include <stdexcept>

using namespace std;

// type alias
using ll = long long;
using ull = unsigned long long;
using comp = complex<double>;

const ll MOD = 1000000007LL;
const double PI = 3.14159265358979323846;

//conversion
//------------------------------------------
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

// for loop
#define REP(i, n) for ((i) = 0;(i) < (ll)(n);(i)++)

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl
#define DEBUG(x) cerr << #x << " = " << (x) << " (l" << __line__ << ")" << " " << __file__ << endl

int solve() {
	string s;
	cin >> s;
	
	for (ll i = 0; i < s.size(); ++i) {
		if (s[i] == '?') s[i] = 'D';
	}

	cout << s << endl;

	return 0;
}

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

	solve();

	return 0;
}


Measured memory_bytes: 3772
package main

import (
	"fmt"
)

func main() {
	var N int
	fmt.Scanf("%d", &N)

	var MAX uint64
	MAX = 1000000000000000000
	var ans uint64
	ans = 1
	A := make([]uint64, N)
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &A[i])
	}
	for i := 0; i < N; i++ {
		if A[i] == 0 {
			fmt.Println(0)
			return
		}
	}
	for i := 0; i < N; i++ {
		v := A[i]
		// check ans * v > MAX : ans > MAX / v
		vv := ans * v
		if vv/ans != v {
			// overflow
			fmt.Println(-1)
			return
		}

		if vv > MAX {
			fmt.Println(-1)
			return
		}
		ans = vv
	}
	fmt.Println(ans)
}


Measured memory_bytes: 6328
#include <iostream>
#include <string>
#include <cstdlib>


int head,tail;
int n,q;


bool isFull(){
    return head==(tail+1)%(n+1);
}
bool isEmpty(){
    return head==tail;
}

void enqueue(int *time,std::string *queue,int t,std::string str){
    if(isFull()){
        std::cerr << "Size over!!\n";
        exit(1);
    }
    time[tail] = t;
    queue[tail] = str;
    if(tail==n){
        tail = 0;
    }else{
        tail++;
    }
}

int dequeue(int *time){
    if(isEmpty()){
        std::cerr << "Empty!!\n";
        exit(1);
    }
    int x = time[head];
    time[head] = -1;
    if(head==n){
        head = 0;
    }else{
        head++;
    }
    return x;
}

void initialize(int* sum1,std::string *queue,int *time){
    head = 0;
    tail = 0;
    std::string str;
    int t;
    for(int i=0;i<n;i++){
        std::cin >> str >> t;
        enqueue(time,queue,t,str);
        *sum1+=t;
    }
}

int main(){
    int sum1=0,sum2=0;
    int tmp;
    std::cin >> n >> q;
    std::string queue[n+1];
    int time[n+1];
    initialize(&sum1,queue,time);
    while(sum2<sum1){
        if(time[head]==-1){
            head++;
        }else if(time[head]<=q){
            tmp = head;
            sum2 += dequeue(time);
            std::cout << queue[tmp] << " " << sum2 << "\n";
        }else{
            enqueue(time,queue,dequeue(time)-q,queue[head]);
            sum2 += q;
        }
    }
    return 0;
}


Measured memory_bytes: 6036
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

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

    int n; cin>>n;
    vector<ll>h;
    rep(i,n){
        ll b; cin>>b;
        h.push_back(b);
    }
    
    int max_cnt = 0;
    int cnt = 0;

    for(int i=0; i<n-1; i++){
        if(h[i]>=h[i+1]){
            cnt++;
            if(max_cnt < cnt) max_cnt = cnt;
            continue;
        }
        cnt = 0;
    }
    
    cout << max_cnt << ln;
    return 0;
}

Measured memory_bytes: 1400
// E - Divisible Substring
#include <bits/stdc++.h>
using namespace std;
#define c2d(c) ((c)-'0') // char to digit

int main() {
	int N,P; string S; cin>>N>>P>>S;
	long long total = 0;
	if(10%P == 0){ // P={2,5}
		for(int i=0; i<N; ++i)
			if(c2d(S[N-1-i]) % P == 0) total += N - i;
	}
	else{
		reverse(S.begin(), S.end());
		vector<int> cnt(P, 0);
		int r = 0, ten = 1;
		cnt[r]++; // for half-open section
		for(char si:S){
			// n=count(r), nC2 = {n-1}C2 + {n-1}
			// {n-1} = count(r): previous of count up
			// ∴ total = total + {count of previous of count up}
			r = (r + c2d(si)*ten) % P;
			total += cnt[r];
			cnt[r]++;
			ten = ten * 10 % P;
		}
	}
	cout << total << endl;
}

Measured memory_bytes: 640
def main():
    N = int(input())
    A1 = list(map(int, input().split()))
    A2 = list(map(int, input().split()))
    ans = 0
    for i in range(N):
        tmp = sum(A1[:(i + 1)]) + sum(A2[i:])
        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
char a[504][504];
char b[2][504][504];
int main() {
	ios_base::sync_with_stdio(false);
	ll rlim,clim; cin>>rlim>>clim;
	for (ll r=0;r<rlim;r++) for (ll c=0;c<clim;c++) {
		cin>>a[r][c];
	}
	for (ll t=0;t<2;t++) for (ll r=0;r<rlim;r++) for (ll c=0;c<clim;c++) {
		b[t][r][c]=a[r][c];
	}
	for (ll k=0;;k++) {
		ll ox=k,oy=k;
		ll ex=rlim-k-1,ey=clim-k-1;
		if (ox>=ex||oy>=ey) break;
		//printf("ox:%lld ex:%lld oy:%lld ey:%lld\n",ox,ex,oy,ey);
		ll c=k&1;
		ll d=c^1;
		for (ll x=ox+1;x<=ex;x++) {
			b[c][x][oy]='#';
		}
		for (ll y=oy;y<=ey;y++) {
			b[c][ex][y]='#';
		}
		for (ll y=oy;y<=ey;y++) {
			b[d][ox][y]='#';
		}
		for (ll x=ox;x<ex;x++) {
			b[d][x][ey]='#';
		}
	}
	for (ll t=0;t<2;t++) {
		for (ll r=0;r<rlim;r++) {
			for (ll c=0;c<clim;c++) {
				cout<<b[t][r][c];
			}
			cout<<endl;
		}
		cout<<endl;
	}
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define int long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pii pair<int , int>
#define vi vector<int>
#define inf 1e18 //(10^18
#define pqmax priority_queue<int>
#define mii map<int , int>
#define ps(x, y) fixed<<setprecision(y)<<x
// double ans = 1.012345668992
//cout<<ps(ans , 6)
// ans = 1.012345 // 6 decimal places
#define pqmin priority_queue<int , vi , greater<int> >
#define mk(arr , n , type) type *arr = new type[n];
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
// 48->11000(4) (returns no. of zeros after first one)
#define mod 1000000007 //1e9 +7
#define w(t) int t; cin>>t;while(t--)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//shuffle(arr , arr +n , rng)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>pbds;
//pbds s;
//s.order_of_key(4);
//*s.find_by_order(4);
int32_t main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt" , "r", stdin);
	//freopen("output.txt" , "w", stdout);
#endif

	int k;
	cin >> k;
	int a , b;
	cin >> a >> b;
	int flag = 0;
	for (int i = a; i <= b; i++) {
		if (i % k == 0) {
			flag = 1;
		}
	}
	if (flag == 1) {
		cout << "OK" << "\n";
	}
	else {
		cout << "NG" << "\n";
	}


	return 0;


}





Measured memory_bytes: 3612
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int max = 0;
		int sum = 0;

		for(int i = 0; i < n; i++){
			int p = sc.nextInt();

			sum += p;
			max = Math.max(max, p);
		}

		System.out.println(sum - max/2);

	}

}


Measured memory_bytes: 23764
/* ****revpro**** */
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl	   '\n'
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)    
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mii	    map<ll,ll>
using namespace std;

#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define N  100005
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;  
#define ordered_set tree<double, null_type,less<double>, rb_tree_	tag,tree_order_statistics_node_update> 
void solve()
{
	ll n;
	cin>>n;
	// cout<<n<<endl;
	ll sq=sqrt(n),ans=0;
	rep(i,2,sq+1){
		// cout<<"here";
		if(n%i==0){
			ll cnt=0;
			while(n%i==0){
				cnt++;
				n/=i;
			}
			rep(j,1,100){
				if(j*(j+1)/2>cnt){
					ans+=j-1;
					break;
				}
			}
		}
	}
	if(n!=1) ans++;
	cout<<ans<<endl;
}
signed main()
{
	
		/***********************************/
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    mt19937_64 generator (seed);

	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	// cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
		
	}
	TIME
	return 0;
}

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

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> p(N);
  for(int i = 0; i < N; i++){
    cin >> p.at(i);
  }
  sort(p.begin(), p.end());
  int result = 0;
  for(int i = 0; i < K; i++){
    result += p.at(i);
  }
  cout << result << endl;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const int INF=1e9;


int main(){
  int n;
  cin>>n;
  map<int,int> exist;
  rep(i,n){
    int a;
    cin >>a;
    if(exist[a]==1){
      cout<<"NO"<<endl;
      return 0;
    }
    exist[a]=1;
  }

  cout<<"YES"<<endl;
 
}


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

using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int mi = 0, now = 0;
    for (int i = 0; i < n; i++) {
        now += s[i] == '(' ? 1 : -1;
        mi = min(mi, now);
    }

    cout << string(-mi, '(') << s << string(now - mi, ')') << endl;
    return 0;
}

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

using namespace std;

void Main() {
    string S;
    cin >> S;
    if (S == "SSS") {
        cout << 0 << endl;
    }
    else if (S == "RRR") {
        cout << 3 << endl;
    }
    else if (S == "RRS" || S == "SRR") {
        cout << 2 << endl;
    }
    else {
        cout << 1 << endl;
    }
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main()
{
    //assert(freopen("input.txt", "r", stdin));
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> v;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        v.push_back( x );
    }
    vector<int> v_s(v.begin(), v.end());
    sort(v_s.begin(), v_s.end());
    for(auto x : v){
        if(x != v_s[n-1])
            cout << v_s[n-1] << endl;
        else if(x == v_s[n-1])
            cout << v_s[n-2] << endl;

    }
    return 0;
}


Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll ceil(const ll a, const ll b) { return (a + b - 1) / b; }
int x[100][100];
int main(){
  ll n,w;
  cin >> n >> w;
  vector<ll>W(n),V(n);
  vector<priority_queue<ll>>WV(4);
  rep(i,n)cin >> W[i] >> V[i];
  ll a = *max_element(all(W));
  rep(i,n)if(a == W[i])a = W[i];
  rep(i,n)WV[abs(a - W[i])].push(V[i]);
  ll ans = 0;
  rep(i,1000000){
    ll A = 0,b = 0,c = 0,d = 0;
    if(WV[0].size() != 0)A = rand() % (WV[0].size() + 1);
    if(WV[1].size() != 0)b = rand() % (WV[1].size() + 1);
    if(WV[2].size() != 0)c = rand() % (WV[2].size() + 1);
    if(WV[3].size() != 0)d = rand() % (WV[3].size() + 1);
    if(A * a + b * (max(a - 1,0LL)) + c * (max(a - 2,0LL)) + d * (max(a - 3,0LL)) <= w){
      vector<priority_queue<ll>>WWV;
      WWV = WV;
      ll tmp = 0;
      rep(i,A){
        tmp += WWV[0].top();
        WWV[0].pop();
      }
      rep(i,b){
        tmp += WWV[1].top();
        WWV[1].pop();
      }
      rep(i,c){
        tmp += WWV[2].top();
        WWV[2].pop();
      }
      rep(i,d){
        tmp += WWV[3].top();
        WWV[3].pop();
      }
      ans = max(ans,tmp);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)
    {
        Reader r=new Reader();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int N=r.nextInt();
        String str=r.next();
        int K=r.nextInt();
        char key=str.charAt(K-1);
        solve(str, key, out);
        out.close();

    }
    static void solve(String str, char key, PrintWriter out)
    {
        String newStr="";
        for(int i=0; i<str.length(); i++)
        {
            if(str.charAt(i)!=key)
            {
                newStr+="*";
            }
            else
            {
                newStr+=str.charAt(i);
            }
        }
        System.out.println(newStr);

    }



    //Fast I/O class
    static class Reader
    {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            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;
        }
    }


}


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

using namespace std;


#define ll              long long
#define pb              push_back
#define nn           cout << "\n";



int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t,a,b,i,j,c,d,e,f,n,k,m,w;

    
      
    cin>>n>>k;
    
      int dp[n+5],ht[n+5];
      
    for(i=1;i<=n;i++)
    {
        cin>>a;
        ht[i]=a;

    }

    dp[n]=0;
    for(i=n-1;i>=1;i--)
    {
        dp[i]=INT32_MAX;
        for(j=1;j<=k&&(i+j)<=n;j++)
        {


        dp[i]=min(dp[i],(dp[i+j]+abs(ht[i]-ht[i+j])));
        }
    }

    cout<<dp[1]<<endl;
    return 0;
}


Measured memory_bytes: 4404
N = int(input())
A = [int(a) for a in input().split()]


L = [0]*61

for i in range(N):
    b = bin(A[i])
    for j in range(2, len(b)):
        if b[j] == "1":
            L[len(b)-j-1] += 1

ans = 0
mod = 10**9+7

for i in range(61):
    c = 2**i*(L[i]*(N-L[i]))
    ans += c
    ans %= mod
    
print(ans)

Measured memory_bytes: 122936
#include <iostream>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> as;
  for (int i = 0; i < n; ++i) {
    int a;
    std::cin >> a;
    as.push_back(a);
  }
  for (int i = 0; i < n; ++i) {
    int target = as[i];
    for (int j = 0; j < i; ++j) {
      if (as[j] > target) {
        as.erase(as.begin() + i);
        as.insert(as.begin() + j, target);
         break;
      }
    }
    for (int i = 0; i < n; ++i) {
      std::cout << as[i];
      if (i == n - 1)
        std::cout << std::endl;
      else
        std::cout << " ";
    }
  }
}

Measured memory_bytes: 3084
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
 
int main() {
  int a,b,c,d,e;cin >> a >> b >> c >> d >> e;
  int k;cin >> k;
  if(e-a>k){
      cout << ":(" << endl;
  }else{
      cout << "Yay!" << endl;
  }
}

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

using ll = long long;

int main() {
    int n; cin >> n;
    int t = n;
    int sn = 0;
    while(t) {
        sn += t % 10;
        t /= 10;
    }
    cout << (n % sn == 0 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
#define INF 10000000000000001
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound
#define vc vector
#define vll vector<long long>
#define pll pair<long long,long long> 
#define pb push_back
#define all(v) v.begin(),v.end()
#define T ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define MAX 100005
typedef long long ll;
typedef long double ld;
using namespace std;
void dfs(int src,vector<int>adj[],int vis[],int dp[])
{
	vis[src]=1;
	for(auto j:adj[src]){
		if(vis[j]==0)
		{
			dfs(j,adj,vis,dp);
		}
		dp[src]=max(dp[src],1+dp[j]);
	}
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n,m,x,y;
    cin>>n>>m;
    vector<int> adj[n+1];
    rep(i,0,m)
    {
    	cin>>x>>y;
    	adj[x].pb(y);
    }
    int dp[n+1]={0},vis[n+1]={0},mx=INT_MIN;
    rep(i,1,n+1)
    {
    	if(vis[i]==0)
    	{
    		dfs(i,adj,vis,dp);
    	}
    }
    rep(i,1,n+1)
    {
    	//cout<<dp[i]<<" ";
    	mx=max(mx,dp[i]);
    }
    cout<<mx<<endl;
}

Measured memory_bytes: 9984
#include <stdio.h>

int main(void){
   int a,b,c=0,n;
   while(scanf("%d %d",&a,&b)!=EOF){
   c=a+b;
   n=1;
   while(c>=10){
      c=c/10;
      n++;
   }
   printf("%d\n",n);
   }
  return 0;
}

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

#define mod 1000000007
#define ll long long

ll bow(ll x, ll y) {
  ll res = 1;
  for (ll i = 1; i <= y; ++i) {
    res = res * x % mod;
  }
  return res;
}

void solve() {
  ll x;
  cin >> x;
  cout << 1 - x << endl;
}

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

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define show(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define show(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<62;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

struct node{
    vector<node*> cld;
    int mini;
    node():mini(inf){}
};

node* parse(string s){
    node *v=new node;
    {
        bool f=true;
        rep(i,1,s.size()-1) if(!isdigit(s[i])){
            f=false;
            break;
        }
        if(f){
            v->mini=stoi(s.substr(1,s.size()-2));
            return v;
        }
    }
    int d=0,l;
    rep(i,1,s.size()-1){
        if(s[i]=='['){
            if(!d) l=i;
            ++d;
        }
        if(s[i]==']'){
            if(d==1) v->cld.push_back(parse(s.substr(l,i-l+1)));
            --d;
        }
    }
    return v;
};

int dfs(node *v){
    if(!v->cld.size()) return (v->mini+1)/2;
    vector<int> val;
    for(auto c:v->cld) val.push_back(dfs(c));
    sort(val.begin(),val.end());
    int res=0;
    rep(i,0,(val.size()+1)/2) res+=val[i];
    return res;
}

void solve(){
    string s;
    cin >> s;
    cout << dfs(parse(s)) << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    int n;
    cin >> n;
    rep(i,0,n) solve();
    return 0;
}

Measured memory_bytes: 5432
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  long long int a[3*N];
  for(int i = 0; i < 3*N; ++i){
    cin >> a[i];
  }
  sort(a, a+3*N);
  long long int ans = 0;
  for(int i = 1; i <= N; ++i){
    ans += a[3*N-2*i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vs = vector<string>;
using vd = vector<double>;
using ul = unsigned long;
 
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

int main()
{
  cin.tie( 0 );
  ios::sync_with_stdio( false );
  
  string s;cin>>s;
  int n=s.size()/2;
  int ans=0;
  rep(i,n){
    s=s.substr(0,s.size()-2);
    string l=s.substr(0,s.size()/2);
    string r=s.substr(s.size()/2,s.size()/2);
    if(l==r){
      ans=s.size();
      break;
    }
  }
  cout(ans);
  return 0;
}

Measured memory_bytes: 256
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn main() {
    let n = read::<u32>();

    for i in 1..n+1 {
        let mut x = i;
        if x %3 == 0 {
            print!(" {}", i);
        } else {
            while x > 0 {
                if x %10 == 3 {
                    print!(" {}", i);
                    break;
                }
                x /= 10;
            }
        }
    }
    println!("");
}



Measured memory_bytes: 5020
/// Containers Start
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// C Header Files
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <math.h>
#include <stdio.h>
/// Containers End

using namespace std;

/// Math Start
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define EPS (1e-7)
#define INF (0x3f3f3f3f)
/// Math End

/// Extra Start
#define nn '\n'
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define sz(a) int((a).size())
#define space " "
#define All(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
/// Extra End

#define rep(i, n) for (int i = 0; i < n; i++)
#define Cini(a)                                                                \
    int a;                                                                     \
    cin >> a;
#define Cinii(a, b)                                                            \
    int a, b;                                                                  \
    cin >> a >> b;
#define Ciniii(a, b, c)                                                        \
    int a, b, c;                                                               \
    cin >> a >> b >> c;
#define Cins(s)                                                                \
    string s;                                                                  \
    cin >> s;
#define Cinss(s1, s2)                                                          \
    string s1, s2;                                                             \
    cin >> s1 >> s2;
#define Cinc(c)                                                                \
    char c;                                                                    \
    cin >> c;
/// Functions End


/// Debug Start
#define deb(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << '\t' << #y << ": " << y << endl;
#define deb3(x, y, z)                                                          \
    cout << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": "   \
         << z << endl;
/// Debug End

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

/**>>>>>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<<<<**/

/// template


signed main(void) {
    cin.sync_with_stdio(false);
    cin.tie(0);
    Cinii(N,K);
    vector<int> h(N);
    rep(i, N) cin >> h[i];
    int ansCount =0;
    rep(i,N)if(h[i]>=K)ansCount++;
    cout << ansCount << nn;
    return 0;
}

Measured memory_bytes: 640