akhauriyash/Code-Regression huggingface dataset:
while true do
	h,w = gets.split.map(&:to_i)
	if h == 0 && w == 0
		break
	end
	r = "#" * w
	puts r
	t = 0
		while t < h-2
			puts "#" + "." * (w - 2) + "#"
			t = t + 1 
		end
	r = "#" * w
	puts r
	puts ""
end



Measured memory_bytes: 6960
bikkuri = [1]
mod = 10**9+7

for i in range(1,2*10**6+1000):
    bikkuri.append((bikkuri[-1]*i)%mod)
r1,c1,r2,c2 = map(int,input().split())

def F(r,c):
    tmp = (bikkuri[r+c+2]*pow(bikkuri[c+1],mod-2,mod)*pow(bikkuri[r+1],mod-2,mod) - 1)%mod
    return tmp

ans = (F(r2,c2)-F(r1-1,c2)-F(r2,c1-1)+F(r1-1,c1-1))%mod
print(ans)

Measured memory_bytes: 107368
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#define MAXN 200005
using namespace std;

int n, ans[MAXN];
struct A {int num, pos;} a[MAXN];

bool CMP(A x, A y)
{
    return x.num<y.num;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i].num), a[i].pos=i;
    sort(a+1, a+n+1, CMP);
    for(int i=1; i<=n; i++)
    {
        if(i<=n/2) ans[a[i].pos]=a[n/2+1].num;
        else ans[a[i].pos]=a[n/2].num;
    }
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}


Measured memory_bytes: 4480
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

cnt = 0
for i in range(N):
    cnt += A[i] //2
    if i < N-1 and A[i+1] > 0:
        A[i+1] -= A[i]%2
        cnt += A[i]%2

print(cnt)
    

Measured memory_bytes: 7072
#include <bits/stdc++.h>
#define maxn 1000010
#define modn 1000000007
int f[maxn],fac[maxn],sum[maxn],n,d,h,i,s=0,ans;
int power(int x,int y)
{
	int s=1,i=x;
	for (;y;y>>=1)
	{
		if (y&1) s=1LL*s*i%modn;
		i=1LL*i*i%modn;
	}
	return s;
}
int main()
{
	scanf("%d%d%d",&n,&h,&d);
	fac[1]=sum[1]=1;
	for (i=2;i<=n;i++)
	{
		fac[i]=1LL*fac[i-1]*i%modn;
		sum[i]=(sum[i-1]+fac[i])%modn;
	}
	f[0]=fac[n];
	s=f[0];
	for (i=1;i<=h;i++)
	{
		f[i]=1LL*s*sum[n]%modn;
		s=(s+f[i])%modn;
		if (i-d>=0) s=(s-f[i-d]+modn)%modn;
	}
	ans=1LL*f[h]*power(sum[n],modn-2)%modn;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 11904
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

K = int(input())
S = input()
if len(S) <= K:
    print(S)
else:
    print(S[:K] + "...")



Measured memory_bytes: 10840
#[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")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn main() {
    input!{
      n: usize,
      c: usize,
      stcs: [(usize, usize, usize); n],
    }
    let mut tbl = vec![vec![0; 100001]; c+1];

    for (s, t, c) in stcs {
        if tbl[c][s] == 2 {
            tbl[c][s] = 0;
        } else {
            tbl[c][s] = 1;
        }

        if tbl[c][t] == 1 {
            tbl[c][t] = 0;
        } else {
            tbl[c][t] = 2;
        }
    }

    let mut ans = 0;
    let mut d = 0;
    for t in 0..100001 {
        for c in 1..c+1 {
            if tbl[c][t] == 1 {
                d += 1;
            }
        }
        ans = max(ans, d);
        for c in 1..c+1 {
            if tbl[c][t] == 2 {
                d -= 1;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 22780
#include <cstdio>
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
	int n;
	long int num;
	long int sum = 0;
	long int max = -1000000;
	long int min = 1000000;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> num;
		if (min > num) min = num;
		if (max < num) max = num;
		sum += num;
	}

	printf("%ld %ld %ld\n", min, max, sum);

	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>

using namespace std;

int sod(int n) {
  int r = 0;
  while (n > 0) {
    r += n % 10;
    n /= 10;
  }
  return r;
}

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

  int ans = 1 << 10;
  for (int a = 1; a <= N / 2; ++a) {
    int b = N - a;
    int sum = sod(a) + sod(b);
    ans = min(ans, sum);
  }

  cout << ans << endl;

  return 0;
}


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

int main(){
  string str;
  cin>>str;
  int bob;
  cin>>bob;
int ans=str[0]-'0';
 int f;

  for(int i=1;i<str.size();i++){
    if(str[i]=='+')f=1;
    else if(str[i]=='*')f=2;
    if(str[i]>='0' && str[i]<='9'){
      if(f==1) ans+=(str[i]-'0');
      else if(f==2)ans*=(str[i]-'0');
    }
  }
  char ansf='I';
   if(ans==bob)ansf='L';
    ans=0;
  for(int i=1;i<str.size();i++){
    int multi=0;
    if(str[i]=='*'){
      multi+=((str[i-1]-'0')*(str[i+1]-'0'));
      str[i-1]='0',str[i+1]='0';
      while(1){
	i++;
	if(i>=str.size()) break;
	if(str[i]=='*')multi*=(str[i+1]-'0'),str[i+1]='0';
	else if(str[i]=='+') break;
      }
    }
    ans+=multi;
  }
      for(int i=0;i<str.size();i++)
	if(str[i]>='0' && str[i]<='9')ans+=(str[i]-'0');
    if(ans==bob && ansf=='L') ansf='U';
  else if(ans==bob)ansf='M';
  cout<<ansf<<endl;
  return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long a,b,c,k;
	cin>>a>>b>>c>>k;
	long long sum=0;
	if(k>=a) {
		sum+=a;
		k-=a;
		a=0;
	} else {
		cout<<k;
		return 0;
	}
//	cout<<k<<' ';
	if(k>=b) {
		k-=b;
		b=0;
	} else {
		cout<<sum;
		return 0;
	}
//	cout<<k<<' ';
	sum-=k;
	cout<<sum;
	return 0;
}

Measured memory_bytes: 3640
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std ;

#define MAXN 200007

int n ;
int a[ MAXN ] ;
long long prefsum[ MAXN ] ;
int prefxor[ MAXN ] ;

long long get_sum ( int l , int r ) {
    return ( prefsum[ r ] - prefsum[ l - 1 ] ) ;
}
long long get_xor ( int l , int r ) {
    return ( prefxor[ r ] ^ prefxor[ l - 1 ] ) ;
}


void input ( ) {
    scanf ( "%d" , &n ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
        prefsum[ i ] = ( prefsum[ i - 1 ] + a[ i ] ) ;
        prefxor[ i ] = ( prefxor[ i - 1 ] ^ a[ i ] ) ;
    }
}

void solve ( ) {
    long long ans = 0 ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        int l , r , mid ;
        l = i ;
        r = n ;
        while ( r - l > 3 ) {
            mid = ( l + r ) / 2 ;
            if ( get_sum ( i , mid ) == get_xor ( i , mid ) ) {
                l = mid ;
            }
            else {
                r = mid ;
            }
        }
        while ( get_sum ( i , r ) != get_xor ( i , r ) ) { r -- ; }
        ans += ( r - i + 1 ) ;
    }
    printf ( "%lld\n" , ans ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}


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

int main() {
string S;
  cin>>S;
  sort(S.begin(),S.end());
  if(S.at(0)=='a' && S.at(1)=='b' && S.at(2)=='c' ){
  cout<<"Yes";
  }
  else{
  cout<<"No";
  }
}


Measured memory_bytes: 256
/*
 this->author = Fuad Ashraful Mehmet, CSE-UAP
 Todo:
 lightoj : 1147,1101
*/
#include<bits/stdc++.h>
#define forn(i,n) for(int i=0;i<(int)n;++i)
#define all(o) (o).begin(),(o).end()
#define dbg(o)  cerr<<"at "<<__LINE__<<" response = "<<o<<endl;
using namespace std;

const int N=31;
typedef  long long ll;
int n,m,k;

void HalfDead()
{
      cin>>n;
      string s;
      cin>>s;

      int cost=0;
      int idx=n-1;
      
      for(int i=0;i<n;++i)
      {
            if(s[i]=='W')
            {
                  while(s[idx]=='W' and idx>i)idx--;
                  if(idx<=i)
                  {
                        break;
                  }
                  cost+=1;
                  swap(s[i],s[idx]);
            }
      }
      
      cout<<cost<<"\n";

}// end func
int main()
{
     ios_base::sync_with_stdio(0); cin.tie(nullptr);
      int tc=1;
      //cin>>tc;
      //scanf("%d",&tc);
      while(tc--)
      {
            HalfDead();
      }
      return 0;
}


Measured memory_bytes: 3704
N, K = [int(n) for n in input().split(" ")]
lst = [int(n) for n in input().split(" ")]

sum_max = 0
temp = 0

for i in range(K):
    temp += (lst[i]+1)/2
    sum_max = temp
for j in range(0,N-K):
        temp += (lst[j+K]-lst[j])/2
        if temp > sum_max:
            sum_max = temp
            
print(sum_max)

Measured memory_bytes: 24548
#[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)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $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")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn solve(n: usize, ws: &[usize], vs: &[usize]) -> usize {
    let mut dp = vec![0; n+1];
    for i in 0..ws.len() {
        for w in 0..n+1 {
            let cw = ws[i];
            if w + cw <= n {
                dp[w + cw] = max(dp[w + cw], dp[w] + vs[i]);
            }
        }
    }
    dp.into_iter().enumerate().map(|(i,v)| v + n - i).max().unwrap()
}

fn main() {
    input!{
      n: usize,
      a: [usize; 3],
      b: [usize; 3],
    }
    let m = solve(n, &a, &b);
    let ans = solve(m, &b, &a);
    println!("{}", ans);
}


Measured memory_bytes: 200956
#include<iostream>
using namespace std;using ll=long long;ll n,k,a=0,i,j,m=1e9+7,v[2<<20];ll f(ll k){return(k*(k+1)/2)%m;}main(){cin >> n >> k;for(i=0;i<n;i++)cin >> v[i];for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j)continue;if(v[i]>v[j]){if(i<j)a +=k;(a+=f(k-1))%=m;}}cout<<a<<endl;}

Measured memory_bytes: 256
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

const ll INF = 1LL << 50;

const ll mod = 1000000007;

int main() {
  ll k, x;
  cin >> k >> x;

  if (500 * k >= x)
    puts("Yes");
  else
    puts("No");

  return 0;
}


Measured memory_bytes: 256
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target ("sse4")
#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define deb(x) cout << #x << " is " << x << "\n";

using namespace std;
using namespace __gnu_pbds;

const double PI = 2 * acos(0.0);
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<int> fact(9, 1);

int findRank(vector<int> &arr){
    if(arr.size() < 2)
        return 1;
    int n = arr.size();
    int ans = 0;
    for(int i = 0; i < n - 1; i++){
        int g = 0;
        for(int j = i + 1; j < n; j++){
            if(arr[j] < arr[i])
                g++;
        }
        ans += (g * fact[n - i - 1]);
    }
    return ans + 1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for(int i = 2; i <= 8; i++) 
        fact[i] = i * fact[i-1];
    int n;
    cin >>n;
    vector<int> p(n), q(n);
    for(int i = 0; i < n; i++)
        cin >>p[i];
    for(int i = 0; i < n; i++)
        cin >>q[i];
    int a = findRank(p);
    int b = findRank(q);
    cout <<abs(a - b);
    return 0;
}

Measured memory_bytes: 256
H,W,A,B = map(int, input().split())

if A == 0 and B == 0:
  for _ in range(H):
    print("".join("0" * W))
  exit(0)
  
ANS = []
cnt = B
roll = 0
for i in range(B):
  wk = ["1"] * A + ["0"] * (W-A)
  ANS.append(wk)
for i in range(H-B):
  wk = ["0"] * A + ["1"] * (W-A)
  ANS.append(wk)
  
for ans in ANS:
  print("".join(ans))



Measured memory_bytes: 16644
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1000000000
#define  pow(x) pow(10,(x)) 
typedef long long int LL;

int main(){
    int N;cin >> N;
    LL x,y; 
    vector<vector<pair<LL,LL>>> DP(N,vector<pair<LL,LL>>(N));
    vector<LL> X(N);
    vector<LL> Y(N);
    rep(k,N){
        cin >> X[k] >> Y[k] ;
    }

    rep(i,N){ // DP を作る(X[i]-X[j],Y[i]-Y[j])
        rep(j,N){

            if(i == j){
                DP[i][j] = make_pair(0,0);
                continue;
            }
            DP[i][j] = make_pair(X[i]-X[j],Y[i]-Y[j]);

        }
    }

    map<pair<LL,LL>,int> m;
    int max = 0;
    pair<LL,LL> zer = make_pair(0,0);
    rep(l,N){
        rep(p,N){
            if(DP[l][p] != zer){
                m[DP[l][p]]++;
                if(max < m[DP[l][p]]){
                    max = m[DP[l][p]];
                }
            }
            else{
                continue;
            }
        }
    }
    cout << N - max << endl;

}

Measured memory_bytes: 384
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n, a, b, c, d;
string s;

int main(){
	cin >> n >> a >> b >> c >> d >> s;
	a--;
	b--;
	c--;
	d--;
	bool ans = true;
	for(ll i = b+1; i < d; i++){
		if(s[i] == '#' && s[i+1] == '#'){ans = false;}
	}
	for(ll i = a+1; i < c; i++){
		if(s[i] == '#' && s[i+1] == '#'){ans = false;}
	}
	if(c > d){
		ans = false;
        for(ll i = b; i <= d; i++){
        	if(s[i-1] == '.' && s[i] == '.' && s[i+1] == '.'){
        		ans = true;
        	}
        }	
	}
	if(ans){cout << "Yes" << endl;}
	else{cout << "No" << endl;}
	return 0;
}

Measured memory_bytes: 640
#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 ll Lmax=ll(1e18);
const ll Nmax=1e9;


// B貪欲法で決定する．
int main(){
  int d;
  cin>>d;
  vector<int> c(26);
  vector<vector<int>> s(d,vector<int>(26));
  vector<int> last(26);

  rep(i,26){
    cin>> c[i];
    last[i]=-1;
  }
  rep(i,d){//i日目
    int maxs=0;
    int jm=0;

    rep(j,26){
      cin>>s[i][j];
    }
  }

  ll ans=0;
  int t;
  rep(i,d){
    cin>>t;
    t--;
    last[t]=i;//最後に行われた日を更新
    ans+=s[i][t];
    rep(j,26){
      ans-=c[j]*(i-last[j]);
    }

    cout<<ans<<endl;



  }





}


Measured memory_bytes: 3680
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    Xs = [int(item) for item in input().split()]
    if N < M:
        Xs.sort()
        ds = [Xs[i] - Xs[i-1] for i in range(1, M)]
        ds.sort()
        # print(ds)
        print(sum(ds[:M-N]))

    else:
        print(0)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 21188
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		String[] s = saori.nextHayami().split("");
		String[] t = saori.nextHayami().split("");
		int[][] dp = new int[s.length+1][t.length+1];
		for(int i = 0;i < s.length;i++){
			for(int j = 0;j < t.length;j++){
				if(s[i].equals(t[j])){
					dp[i+1][j+1] = Math.max(dp[i][j] + 1, dp[i+1][j+1]);
				} else {
					dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
				}
			}
		}

		int i = s.length;
		int j = t.length;
		int len = dp[i][j];
		char[] c = new char[len];
		while(dp[i][j] != 0){
			if(dp[i][j] == dp[i][j-1]){
				j--;
			} else if(dp[i][j] == dp[i-1][j]){
				i--;
			} else {
				c[len-1] = s[i-1].charAt(0);
				len--;
				i--;
			}
		}
		String ans = String.valueOf(c);
		System.out.println(ans);

		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 81428
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;


void solve(long long N, std::vector<long long> a){
    ll cnt = 1;
    REP(i, N){
        if(a[i]==cnt){
            cnt ++;
        }
    }
    if(cnt == 1)
        cout << -1 << endl;
    else
        cout << N - cnt + 1<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1000000007; 
const int INF = 1000000000; //1e9
const int NIL = -1;
const long long LINF = 1000000000000000000; // 1e18
const long double EPS = 1E-10;

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






int main(){
    int N, A, mx; std::cin >> N >> A;
    mx = A;
    std::vector<int> x(N);
    for(int i(0); i < N; ++i){
        std::cin >> x[i];
        chmax(mx, x[i]);
    }
    //dp[i][j][k]: x[0],..,x[i-1]からj枚で和がk
    std::vector<std::vector<std::vector<long long>>> dp(N+1, 
     std::vector<std::vector<long long>>(N+1, 
     std::vector<long long>(N*mx + 1, 0)));
    dp[0][0][0] = 1;
    for(int i(1); i <= N; ++i){
        for(int j(0); j <= N; ++j){
            for(int k(0), k_len(N*mx); k <= k_len; ++k){
                dp[i][j][k] = dp[i-1][j][k];
                if(j && k >= x[i-1])
                    dp[i][j][k] += dp[i-1][j-1][k - x[i-1]];
            }
        }
    }
    long long ans(0);
    for(int i(1); i <= N; ++i){
        ans += dp[N][i][A*i];
    }
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 52224
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;

void solve() {
    int n;
    cin >> n;
    cout << 180*(n-2) << endl;
}

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

    solve();
    return 0;
}
 


Measured memory_bytes: 256
n = int(input())
lst = ['AC', 'WA', 'TLE', 'RE']
dic = {'AC': 0, 'WA': 0, 'TLE': 0, 'RE': 0}
for _ in range(n):
  s = input()
  dic[s] += 1
for judge in lst:
  print(judge, 'x', dic[judge])
  

Measured memory_bytes: 9088
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // 入力
        MyScanner sc = new MyScanner(System.in);
        int[] line1 = sc.nextIntArray();
        int A = line1[0];
        int B = line1[1];
        int C = line1[2];
        int X = line1[3];
        int Y = line1[4];

        // 初期化
        long minTotal = A * X + B * Y; // AをX枚とBをY枚買った場合の金額を最小としておく

        // 主処理
        // Cを1枚以上買う場合の金額を求める(上限枚数はXかYの小さい方の2倍まで)
        for (int i = 1; i <= Math.max(X, Y)*2; i++) {
            long total = A * (Math.max(0, X-i))+ B * (Math.max(0, Y-i)) + C * i * 2;
            // 最小の金額か判定する
            if (minTotal > total) {
                // 最小の金額を変更
                minTotal = total;
            }
        }

        // 出力
        System.out.println(minTotal);
    }

    static class MyScanner {
        BufferedReader br;
        // 標準入力から入力値を取得
        MyScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        // 標準入力を文字列で取得
        public String nextString() throws IOException {
            return br.readLine();
        }
        // 標準入力を文字列の配列で取得
        public String[] nextStringArray() throws IOException {
            return nextString().split(" ");
        }
        // 標準入力を数値で取得
        public int nextInt() throws IOException {
            return Integer.parseInt(nextString());
        }
        // 標準入力を数値の配列で取得
        public int[] nextIntArray() throws IOException {
            String[] strArr = nextStringArray();
            int[] intArr = new int[strArr.length];
            for(int i = 0; i < strArr.length; i++) {
                intArr[i] = Integer.parseInt(strArr[i]);
            }
            return intArr;
        }
    }

}


Measured memory_bytes: 23124
import sys
import itertools
import math

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

while 1:
    N = int(readline())
    if N == 0:
        break
    A = [int(x) for x in readline().split()]
    m = sum(A)/N
    ans = 0
    for i in A:
        ans += (i - m) ** 2
    print((ans/N)**.5)



Measured memory_bytes: 5780
#include<stdio.h>
int sosuch();

int main(){
  int n,a,b,c,i,cnt=0,flag;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    cnt += sosuch();
  }
  printf("%d\n",cnt);
return 0;
}

int sosuch(){
  int a,b=1,c=3;
   scanf("%d",&a);
   if(a <= 3) {
     return 1;
   }
   if(a%2==0) return 0;
   while(1){
     if(a%c == 0){
       return 0;
     }
     b=c;
     c+=2;
     if(b*c >= a) return 1;
   }



}




Measured memory_bytes: 2044
#coding:utf-8

def cnt_five(n):
    i = 1
    cnt = 0
    while 5 ** i <= n:
        cnt += n // (5 ** i)
        i += 1
    return cnt

n = int(input())
if n % 2 != 0:
    print(0)
else:
    n //= 2
    print(cnt_five(n))
    
    

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define first first
#define second se
using namespace std;
typedef pair<int, int> P;
typedef vector<int> vi;

signed main(){
    int n, s;
    cin >> n >> s;
    vector<int> a(n + 10);
    int total = 0;
    bool f = false;
    rep(i, 0, n){
        cin >> a[i];
        total += a[i];
        if(a[i] >= s) f = true;
    }
    // if(total < s){
    //     o(0);
    //     return 0;
    // }
    // if(f){
    //     o(1);
    //     return 0;
    // }
    int l = 0, r = 1;
    int sum = a[0], ans = 1e8;
    rep(i, 0, n){
        while(r <= n && sum < s){
            sum += a[r++];
        }
        if(sum >= s){
            ans = min(ans, r - l);
        }
        sum -= a[l];
        l++;
        if(l >= r){
            r = l + 1;
            sum = a[l];
        }
    }
    cout << (ans == 1e8 ? 0 : ans) << endl;
}

Measured memory_bytes: 3620
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      	int a = sc.nextInt();
      	int b = sc.nextInt();
      	if(a >9  || b> 9){
			System.out.println("-1");
        }else System.out.println(a*b);
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define SUM(x) ((x)*(x+1)/2)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int D;
    cin >> D;
    vector<int> c(26);
    for (int i = 0; i < 26; i++)
        cin >> c[i];
    vector<vector<int>> s(D, vector<int>(26));
    for (int i = 0; i < D; i++)
        for (int j = 0; j < 26; j++)
            cin >> s[i][j];

    vector<int> t(D);
    {
        vector<int> last(26, 0);
        for (int i = 1; i <= D; i++) {
            int mx = -1000000000, ti = 0;
            for (int k = 0; k < 26; k++) {
                int sd = s[i-1][k];
                for (int l = 0; l < 26; l++) {
                    if (l == k)
                        continue;
                    sd -= c[l] * (i - last[l]);
                }
                if (sd > mx) {
                    mx = sd;
                    ti = k;
                }
            }
            last[ti] = i;
            t[i-1] = ti+1;
        }
    }
    
    int score = 0;
    {
        vector<int> last(26, 0);
        for (int i = 1; i <= D; i++) {
            score += s[i-1][t[i-1]-1];
            last[t[i-1]-1] = i;
            for (int j = 0; j < 26; j++)
                score -= c[j] * (i - last[j]);
        }
    }
    int m = 200000;
    mt19937 mt((int)time(0));
    for (int i = 0; i < m; i++) {
        int d = mt() % D + 1, q = mt() % 26 + 1;
        int p = t[d-1];
        t[d-1] = q;
        
        int score2 = 0;
        vector<int> last(26, 0);
        for (int i = 1; i <= D; i++) {
            score2 += s[i-1][t[i-1]-1];
            last[t[i-1]-1] = i;
        for (int j = 0; j < 26; j++)
            score2 -= c[j] * (i - last[j]);
        }
        if (score < score2)
            score = score2;
        else
            t[d-1] = p;
    }
    
    for (int i = 0; i < D; i++)
        cout << t[i] << endl;
    
    //cout << "score:" << score << endl;
    
    return 0;
}


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#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; }
//Write From this Line

int main()
{
	int d;
	cin >> d;
	vector<int> c(26);
	rep(i,26) cin >> c[i]; 
	vector<vector<int>> s(d,vector<int>(26));
	rep(i,d) rep(j,26) cin >> s[i][j];
	int count = 1;
	rep(i,d){
		cout << count << endl;
		count ++;
		if(count == 27) count = 1;
	}
}


Measured memory_bytes: 3680
import math

def radi(n):
	return n * math.pi / 180

def resolve():
	a, b, h, m = map(int, input().split())
	hd = radi(h*30+30*(m/60))
	md = radi(360*(m/60))
	hx = a * math.cos(hd)
	hy = a * math.sin(hd)
	mx = b * math.cos(md)
	my = b * math.sin(md)
	x = abs(hx - mx)
	y = abs(hy - my)
	v = math.sqrt(x**2 + y**2)
	print(v)
resolve()

Measured memory_bytes: 9412
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        int[] n = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int[] a = new int[n[0]];
        for(int i = 0; i < n[1]; i++)
        {
            int[] s = Read.Ints();
            a[s[0]-1]++;
            a[s[1]-1]++;
        }
        bool f = true;
        for(int i = 0; i < n[0]; i++)
        {
            if (a[i] % 2 != 0)
            {
                f = false;break;
            }
        }
        Console.WriteLine(f?"YES":"NO");
    }
    public static Boolean uso() { return false; }
    public static bool IsPrime(long n)
    {
        if (n < 2) return false;
        if (n == 2) return true;

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

}
public static class Read
{
    public static void outl(string n = "") { Console.WriteLine(n); return; }
    public static int Int()
    {
        return int.Parse(Console.ReadLine());
    }
    public static int[] Ints()
    {
        return Console.ReadLine().Split().Select(int.Parse).ToArray();
    }
    public static string Str() { return Console.ReadLine(); }
    public static string[] Strs() { return Console.ReadLine().Split(); }
}

Measured memory_bytes: 17624
import java.util.*;

class Main {

    static void solve (int n, ArrayList<Integer> data) {
        ArrayList<Integer> max = new ArrayList<Integer>();
        max.add(data.get(0));
        for (int i = 1; i < n; i++) {
            if (max.get(i-1) > 0)   max.add(max.get(i-1) + data.get(i));
            else                    max.add(data.get(i));
        }

        System.out.println( Collections.max(max) );
    }

    public static void main (String [] args) {

        Scanner sc = new Scanner(System.in);

        while (true) {
            
            int n = sc.nextInt();
            if (n == 0) break;

            ArrayList<Integer> data = new ArrayList<Integer>();

            for (int i = 0; i < n; i++) {
                data.add(sc.nextInt());      
            }

            solve(n, data);
        }

    }
}

Measured memory_bytes: 12000
using System;
using System.Linq;

    class Program
    {
        static void Main(string[] args)
        {
            var AB = Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).ToList();
            if(AB[0]== AB[1])
            {
                Console.WriteLine(AB[0] + AB[1]);
                return;
            }
            var max = Math.Max(AB[0], AB[1]);
            Console.WriteLine(2*max-1);
        }
    }

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

using lint = int64_t;
#define bit(n) ((lint)1 << n);
const int INF = 1e9;
const lint LINF = 1e18;

const lint MOD = 1e9 + 7;
// const lint MOD = 998244353;

class IoSetup {
    public:
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
        cerr << fixed << setprecision(12);
    }
} iosetup;

int main() {
    int x, a;
    cin >> x >> a;
    if (x < a) {
        cout << 0 << endl;
    } else {
        cout << 10 << endl;
    }

    return 0;
}

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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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

// const int INF = 1001001001;
// long long max => LLONG_MAX

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int a, b, c; cin >> a >> b >> c;
    if(b-a == c-b) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	ll n, a, b, c, d;
	cin>>n>>a>>b>>c>>d;
	ll t = abs(b-a);
	rep(k1, n){
		ll k2 = n-1-k1;
		ll lb = c*k1-d*k2;
		ll ub = d*k1-c*k2;
		if(lb<=t && t<=ub){
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)	for(int i=a;i<b;i++)
using namespace std;

void solve(){
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	cout<<max(A*B,C*D);
}

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

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

/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
int main() {
	int A, B;
	cin >> A >> B;
	cout << (A - 1) * (B - 1);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <functional>
#include <cmath>
#include <numeric>

using namespace std;

struct mo {
    int n, q, width;
    vector<int> ql, qr, qi;
    int ptr = 0, nl = 0, nr = 0;

    mo(int n, int q) : n(n), q(q), width(n / sqrt(q)), ql(q), qr(q), qi(q) {}

    // [l, r)
    void insert(int l, int r) { ql[ptr] = l; qr[ptr] = r; ptr++; }

    void build() {
        ptr = 0;
        iota(qi.begin(), qi.end(), 0);
        sort(qi.begin(), qi.end(), [&](int i, int j) {
            if (ql[i] / width != ql[j] / width) return ql[i] < ql[j];
            else {
                if ((ql[i] / width) % 2 == 0) return qr[i] < qr[j];
                else return qr[i] > qr[j];
            }
        });
    }

    int process() {
        int i = qi[ptr++];
        while (ql[i] < nl) add(--nl);
        while (nr < qr[i]) add(nr++);
        while (nl < ql[i]) del(nl++);
        while (qr[i] < nr) del(--nr);
        return i;
    }

    void add(int i);
    void del(int i);
};

vector<int> a, cnt;
int sum = 0;

inline void mo::add(int i) { if (cnt[a[i]]++ == 0) sum++; }
inline void mo::del(int i) { if (--cnt[a[i]] == 0) --sum; }

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

    int n, q;
    cin >> n >> q;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i], a[i]--;

    mo query(n, q);

    for (int i = 0; i < q; ++i) {
        int ql, qr;
        cin >> ql >> qr;
        ql--;
        query.insert(ql, qr);
    }
    query.build();

    cnt.resize(n);
    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        int idx = query.process();
        ans[idx] = sum;
    }

    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}


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

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

  uint64_t num[N+1];
  num[0]=2,num[1]=1;
  for(int i=2;i<N+1;i++){
    num[i]=num[i-1]+num[i-2];
  }
  cout << num[N] << endl;
}

Measured memory_bytes: 256
import math

n = int(input())
ans = [0]*n
max = int(math.sqrt(max(n,1)))+1

for x in range(1,max):
  for y in range(1,max):
    for z in range(1,max):
      ns = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if ns <= n:
        ans[ns-1] += 1
for a in range(n):
  print(ans[a])


Measured memory_bytes: 9244
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  long long ans=0;
  long long last=0;
  while(N--)
  {
    long long X;
    cin>>X;
    if(X<last)
    {
      ans+=last-X;
      X=last;
    }
    last=X;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3592
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;
typedef pair<char[10], int> process;
int main()
{
    int n, q;
    queue<process> Q;
    int total_time = 0;
    scanf("%d %d", &n, &q);

    for ( int i = 0; i < n; i++ ) {
	process p;
	scanf("%s %d", p.first, &p.second);
	Q.push( p );
    }

    while( !Q.empty() ) {
	int exe_time;
	process p = Q.front(); Q.pop();
	exe_time = min( p.second, q );
	p.second -= exe_time;
	total_time += exe_time;
	if ( p.second > 0 ) {
	    Q.push( p );
	}
	else {
	    printf("%s %d\n", p.first, total_time);
	}


    }

    return 0;
}

Measured memory_bytes: 1800
N = int(input())
L = (sorted([int(l) for l in input().split()]))
cnt = 0
for i in range(len(L)):
  for j in range(i+1,len(L)):
    if L[i] == L[j]:
      continue
    for k in range(j+1,len(L)):
      if L[i] == L[k] or L[j] == L[k]:
        continue
      if L[i]+L[j]>L[k] and L[i]+L[k]>L[j] and L[j]+L[k]>L[i]:
        cnt+=1

print(cnt)

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

int main() {	
	int a, b;
	cin >> a >> b;
	if (a * b == 15) {
		cout << "*" << endl;
	}
	else if (a + b == 15) {
		cout << "+" << endl;
	}
	else {
		cout << "x" << endl;
	}

	return 0;
}


Measured memory_bytes: 3588
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);

    int n;
    String[] time;
    int[] in;
    int[] out;
    int atOsaki;
    int outOsaki;

    void run(){
	while(sc.hasNext()){
	    n = sc.nextInt();
	    if(n!=0){
		atOsaki = 0;
		outOsaki = 0;
		in = new int[n];
		out = new int[n];
		solve();
		System.out.println(atOsaki+outOsaki);
	    }
	}
    }

    void solve(){
	for(int i=0; i<n; i++){
	    time = sc.next().split(":");
	    out[i] = 
		Integer.parseInt(time[0])*3600 +
		Integer.parseInt(time[1])*60 +
		Integer.parseInt(time[2]);
	    time = sc.next().split(":");
	    in[i] =
		Integer.parseInt(time[0])*3600 +
		Integer.parseInt(time[1])*60 + 
		Integer.parseInt(time[2]);
	    //System.out.println("*"+out[i]+" "+in[i]);
	}
	Arrays.sort(out);
	Arrays.sort(in);

	int Idx = 0;
	int Odx = 0;
	while(Idx<in.length || Odx<out.length){
	    //System.out.println(outOsaki+" "+atOsaki);
	    if(Odx==out.length){
		arrive();
		Idx++;	 
	    }
	    else if(out[Odx] < in[Idx]){
		leave();
		Odx++;
	    }
	    else{
		arrive();
		Idx++;
	    }
	}
    }

    void leave(){
	if(atOsaki>0) atOsaki--;
	outOsaki++;
    }

    void arrive(){
	outOsaki--;
	atOsaki++;
    }
}
		

Measured memory_bytes: 77676
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<math.h>
#define rep(i,n) for(int i = 0;i<(int)(n);i++);
using namespace std;
using ll = long long;
const ll INF = 100100100100100;


int main() {
	ll N, K;
	cin >> N >> K;
	vector<ll> A(N);
	for(int i = 0;i<N;i++) cin >> A[i];//K - 1こずつ1が増える
	if ((N - 1) % (K - 1) != 0) {
		cout << (N - 1) / (K - 1) + 1 << endl;
	}
	else cout << (N - 1) / (K - 1) << endl;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Data.SqlTypes;
using System.IO.Pipes;
using System.Linq;

class Program
{ 
	public static int Main()
	{
    Scanner cin = new Scanner();
	  while (true)
	  {
	    int n = cin.nextInt(), m = cin.nextInt();
	    if (n == 0 && m == 0)
	    {
	      break;
	    }
      int[] step = new int[n];
	    for (int i = 0; i < n; i++)
	    {
	      step[i] = cin.nextInt();
	    }
	    int[] num = new int[m];
	    for (int i = 0; i < m; i++)
	    {
	      num[i] = cin.nextInt();
	    }
	    int ans = 0, now = 0;
	    for (int i = 0; i < m; i++)
	    {
	      now += num[i];
	      if (now + 1 >= n)
	      {
	        ans = i + 1;
	        break;
	      }
	      now += step[now];
	      if (now + 1 >= n)
	      {
	        ans = i + 1;
	        break;
	      }
	    }
	    Console.WriteLine(ans);
	  }
	  return 0;
	}

}

class Scanner {
	string[] s;
	int i;

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

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

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

	public int nextInt() {
		return int.Parse(next());
	}

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

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

}

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

int main(void) {

	// TODO: submit前にprintf-debugの削除確認！
	int R;
	
	cin >> R;
	// >> 
	if(R<1200) cout << "ABC";
	else if(R<2800) cout << "ARC";
	else cout << "AGC";
	
	// cout << "[deb: val ]" << val <<endl;
	return 0;
}



Measured memory_bytes: 256