akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
#define N 200005
ll fact[N], inv[N], finv[N];
void make()
{
	fact[0] = 1;
	fact[1] = 1;
	inv[1] = 1;
	finv[1] = finv[0] = 1;
	for(int i = 2; i < N; ++i)
	{
		fact[i] = fact[i - 1] * i % MOD;
		inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
		finv[i] = finv[i -1] * inv[i] % MOD;
	}
}

ll C(int a, int b)
{
	if(a < b || b < 0) return 0;
	return fact[a] * (finv[b] * finv[a - b] % MOD) % MOD;
}

ll exp(ll a, ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1)
			res = res * a % MOD;
		b >>= 1;
		a = a * a % MOD;
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	make();
	ll n, a, b, c;
	cin >> n >> a >> b >> c;

	ll ans = 0, pa = a * inv[a + b] % MOD, pb = b * inv[a + b] % MOD;
	ll powa[N], powb[N];
	powa[0] = 1, powb[0] = 1;

	for(int i = 1;i < N; ++i)
	{
		powa[i] = powa[i - 1] * pa % MOD;
		powb[i] = powb[i - 1] * pb % MOD; 
	}

	for (int i = 0; i < n; ++i)
	{
		ans += C(n + i - 1, i) * powa[i] % MOD * powb[n] % MOD * (i + n) % MOD;
		ans += C(n + i - 1, i) * powb[i] % MOD * powa[n] % MOD * (i + n) % MOD;
		ans %= MOD; 
	}
	ans = ans * inv[100 -c] % MOD *100 % MOD;
	cout << ans; 
	return 0;
}

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

using namespace std;
using ll = long long;

int main()
{
    ll m,n,i,total=0,cnt=0;
    cin >> n >> m;

    ll a[n];

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

    for(i=0; i<n; i++){
        if(a[i] * 4 * m >= total )
        cnt++;
    }

    if(cnt >= m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;

}

Measured memory_bytes: 3624
n=int(input())
a=list(map(int,input().split()))

i=0
b=[0]*n
while i<len(a):
    ii=n-i
    j=1
    temp=0
    while j*ii<=n:
        temp+=b[j*ii-1]
        j+=1
    if temp%2!=a[ii-1]:
        b[ii-1]=1
    else:
        b[ii-1]=0
    i+=1

result=[]
cnt=0
for index,item in enumerate(b):
    if item==1:
        cnt+=1
        result.append(str(index+1))
print(cnt)
if cnt>0:
    print(" ".join(result))




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

#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

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

typedef long long ll;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;

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

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

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int k;
    string s;
    cin>>k>>s;

    if(s.length() <= k)cout<<s<<endl;
    else{
        rep(i,k){
            cout<<s[i];
        }
        cout<<"..."<<endl;
    }


    //cout <<fixed<<setprecision(16)<< << endl;

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

    return 0;
}


Measured memory_bytes: 3628
#include <memory>
#include <map>
#include <cassert>
#include <array>
#include <iterator>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <array>
#include <numeric>

class Solution {
public:
    long long n;
    std::vector<std::vector<std::array<long long, 2>>> v;
    std::vector<long long> dist;
    std::vector<bool> visited;
    void dfs (long long cur, long long cur_dist)
    {
      dist[cur] = cur_dist;
      visited[cur] = true;
      for (auto &p : v[cur])
        {
          if (visited[p[0]])
            continue;

          dfs (p[0], cur_dist + p[1]);
        }
    }

    void solve(std::istream& in, std::ostream& out) {
      int a, b, c, d, e, f;
      in >> a >> b >> c >> d >> e >> f;
      std::vector<bool> w (f + 1), s (f + 1);
      w[0] = true;
      s[0] = true;
      for (int i = 0; i < f; ++i)
          {
            auto fill = [&](std::vector<bool> &target, int pos)
            {
                if (pos > f)
                    return;
                target[pos] = true;
            };
            if (w[i])
                {
                    fill (w, i + a * 100);
                    fill (w, i + b * 100);
                }
            if (s[i])
                {
                    fill (s, i + c);
                    fill (s, i + d);
                }
          }
        double max_dens = 0, best_v = 100 * a, best_s = 0;
        for (int i = 0; i <= f; ++i)
            { 
                if (!w[i])
                    continue;
                int j = std::max (std::min (i * (100 + e) / (100) - i, f - i), 0);
                while (!s[j])
                  --j;
                auto dens = (j + 0.) / (i + j);
                if (dens > max_dens)
                    {
                        max_dens = dens;
                        best_v = i + j;
                        best_s = j;
                    }
            }
        out << best_v << ' ' << best_s << '\n';
    }
};

void solve(std::istream& in, std::ostream& out)
{
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}

#include <iostream>

int main ()
{
  solve (std::cin, std::cout);
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long  arr[100100];
int main()
{
	long long n,c,k;
	while(~scanf("%lld%lld%lld",&n,&c,&k))
	{
		for(int i=1;i<=n;i++)
		scanf("%lld",&arr[i]);
		
		sort(arr+1,arr+1+n);
		
		long long ans = 0;
		long long t=1e9 + 10, r =0;
		for(int i=1;i<=n;i++)
		{
			t++;
			if(t>c)
			{
				ans++;
				t = 1;
				r = arr[i] + k;
			}
			else if(r < arr[i])
			{
				ans++;
				r = arr[i] + k;
				t = 1;
			}
			
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 896
#include <stdio.h>
int main(int argc, char *argv[])
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i,s=0;
		for(i=1;i<=n;i++)
		s+=i;
		printf("%d\n",s);
	}
	return 0;
}


Measured memory_bytes: 128
import sys
from collections import deque

# sys.stdin = open('d1.in')


def main():
    n = int(input())
    adj = [[] for u in range(n+1)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))

    d = [0] * (n+1)
    q, k = map(int, input().split())

    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        Q.extend([(v, u, dist+w) for v, w in adj[u] if v != parent])
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()


Measured memory_bytes: 50144
import java.io.*;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		
		int n=in.nextInt();List<Integer> A=new ArrayList<>();
		for(int i=0;i<n;i++) {
			//A[i]=Integer.parseInt(in.next());
			A.add(Integer.parseInt(in.next()));
		}
		
		
		PrintWriter out=new PrintWriter(System.out);
		A=partition(A);int r=A.get(A.size()-1);
		for(int i=0;i<A.size()-2;i++) {
			if(i==r)out.print("["+A.get(i)+"] ");
			else out.print(A.get(i)+" ");
		}
		out.println(A.get(A.size()-2));
		out.flush();

	}
	
	static List<Integer> partition(List<Integer> A){
		int r=A.size()-1,x=A.get(r),i=-1;
		
		if(A.get(0)<=x)i++;
		for(int j=1;j<r;j++) {
			if(A.get(j)<=x) {
				i++;
				Collections.swap(A, i, j);
			}
		}
		
		i++;
		
		if(i<r && A.get(i)>x) {
			Collections.swap(A, i, r);
		}
		A.add(i);
		return A;
	}

}



Measured memory_bytes: 70304
import java.io.*;
import java.math.*;
import java.util.*;
 
public class Main {
    private static boolean debug = false;
    private static boolean elapsed = false;
 
    private static PrintWriter _out = new PrintWriter(System.out);
    private static PrintWriter _err = new PrintWriter(System.err);
 
    private void solve(Scanner sc) {
        int N = sc.nextInt();
        int M = sc.nextInt();
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < N; ++i) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < M; ++i) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            list.get(a).add(b);
            list.get(b).add(a);
        }
 
        List<Integer> route = new ArrayList<>();
        route.add(0);
        _out.println(search(0, N, list, route, new HashSet<>()));
    }
    private int search(int cur, int N, List<List<Integer>> list, List<Integer> route, Set<List<Integer>> set) {
        if (route.size() >= N) {
            if (route.size() == N && !set.contains(route)) {
                set.add(new ArrayList<>(route));
                return 1;
            }
            return 0;
        }
 
        int res = 0;
 
        for (int next : list.get(cur)) {
            if (!route.contains(next)) {
                route.add(next);
                res += search(next, N, list, route, set);
                route.remove(route.size() - 1);
            }
        }
 
        return res;
    }
    private static BigInteger C(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        for (long i = r; i > 1; --i) {
            res = res.divide(BigInteger.valueOf(i));
        }
        return res;
    }
    private static BigInteger P(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        return res;
    }
    /*
     * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
     * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
     */
    public static void main(String[] args) {
        long S = System.currentTimeMillis();
 
        Scanner sc = new Scanner(System.in);
        new Main().solve(sc);
        _out.flush();
 
        long G = System.currentTimeMillis();
        if (elapsed) {
            _err.println((G - S) + "ms");
        }
        _err.flush();
    }
}

Measured memory_bytes: 24148
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  long long n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) {
    int b;
    cin >> b;
    a[i] = b - 1;
  }
  vector<int> flag(n, -1);
  int tmp = 0;
  int roop;
  int i = 0;
  while(k > 0) {
    //k--;
    //i++;
    //tmp = a[tmp];
    if(flag[tmp] == -1) flag[tmp] = i;
    else {
      roop = i - flag[tmp];
      break;
    }
    tmp = a[tmp];
    i++;
    k--;
  }
  //for(int i = 0; i < n; i++ ) {
  //  cout << flag[i] << " ";
  //}

  //cout << endl;
  //roop = i - flag[tmp];
  //cout << roop << endl;
  if(k == 0) {
    cout << tmp+1 << endl;
    return 0;
  }
  k %= roop;
  rep(j, k) {
    tmp = a[tmp];
  }
  cout << tmp+1 << endl;
}

Measured memory_bytes: 4848
#include<bits/stdc++.h>
using namespace std;
main()
{

int n,m;
cin>>n>>m;
int sum=0;
for(int i=0;i<m;i++)
{ int x;

    cin>>x;
    sum+=x;
}
if(sum>n)
    cout<<-1;
else
    cout<<n-sum;
}


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

#define int long long

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

int N;
string a, b;

signed main() {
    cin >> N >> a >> b;
    int ans = 2 * N;
    for (int i = N - 1; i >= 0; i--) {
        if (a.substr(i) == b.substr(0, N - i)) {
            ans = N + i;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;

class Main {
	public static void main (String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int a = sc.nextInt();
	    int res=0;
	    res = res + 1000*(a/500);
	    a = a % 500;
	    res = res + 5*(a/5);
		System.out.println(res);
	}
}

Measured memory_bytes: 24020
#include <bits/stdc++.h>
#define For(i, a, b) for(register int (i) = (a); (i) <= (b); ++(i))
#define ForDown(i, a, b) for(register int (i) = (a); (i) >= (b); (i)--)
using namespace std;
int F() {
	register int x = 0, ch = getchar(), f = 0;
	while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
string s;
int ans;
int main() {
	cin >> s;
	if(s == "SUN") ans = 7;
	else if(s == "MON") ans = 6;
	else if(s == "TUE") ans = 5;
	else if(s == "WED") ans = 4;
	else if(s == "THU") ans = 3;
	else if(s == "FRI") ans = 2;
	else if(s == "SAT") ans = 1;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>


using namespace std;


int s[201];

int main(){


	int n,m;
	int i,j;


	while(1){

		loop:
		cin >> n >> m;

		if(n == 0 && m == 0){
			break;
		}

		int sum_T,sum_H;

		sum_T = sum_H = 0;

		for(i=0; i<n; i++){
			cin >> s[i];
			sum_T += s[i];
		}
		for(i=n; i<n+m; i++){
			cin >> s[i];
			sum_H += s[i];
		}

		for(i=0; i<n;i++){
			for(j=n; j<n+m; j++){
				if(sum_T - s[i] + s[j] == sum_H + s[i] - s[j]){
					cout << s[i] << " " << s[j] << endl;
					goto loop;
				}
			}
		}
		cout << -1 << endl;
	}
return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vector<ll> > vvl;
typedef vector<vector<P> > vvp;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  int n,k;
  cin >> n >> k;
  vector<int>d(n);
  rep(i,k){
    int m;
    cin >> m;
    rep(i,m){
      int x;
      cin >> x;
      d[x-1]=1;
    }
  }
  int cnt=0;
  rep(i,n){
    if(d[i]==0)cnt++;
  }
  cout << cnt << endl;
  return 0;     
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main()
{
  ifstream fIn("input.txt");
  if (fIn.is_open())
    cin.rdbuf(fIn.rdbuf());

  int n;
  string s;
  cin >> n;
  cin >> s;

  if (n % 2 != 0){
    cout << "No" << endl;
    return 0;
  }
  int h = n / 2;
  string a = s.substr(0, h);
  string b = s.substr(h,h);

  if(a == b){
    cout << "Yes" << endl;
    return 0;
  }
  
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
s = S()
n = len(s)
if s == list("keyence"):
    print("YES")
    quit()
for i in range(n):
    for j in range(i+1,n):
        if s[:i]+s[j:] == list("keyence"):
            print("YES")
            quit()
print("NO")
#B
"""
c = LIR(3)
v = [[] for i in range(4)]
for i in range(3):
    c[i][0] -= 1
    c[i][1] -= 1
    v[c[i][0]].append(c[i][1])
    v[c[i][1]].append(c[i][0])

for i in range(4):
    li = [True for i in range(4)]
    li[i] = False
    q = [i]
    c = 0
    while q:
        x = q.pop(-1)
        k = 0
        for j in v[x]:
            if li[j]:
                li[j] = False
                q.append(j)
                if k == 0:
                    c += 1
                    k += 1
    if c == 3:
        print("YES")
        quit()
print("NO")
"""

#C
"""
n = I()
ng = IR(3)
if n in ng:
    print("NO")
    quit()
ng.sort()
for i in range(100):
    b = n
    n -= 3
    if n in ng:
        while n in ng:
            n += 1
            if n == b:
                print("NO")
                quit()
if n <= 0:
    print("YES")
else:
    print("NO")
"""

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 39280
#include<iostream>

using namespace std ;

int main()

{
    int a,b ;

    cin>>a>>b  ;

    if(a==1 && b==2 ||a==2 &&b==1)
    {
        cout<<"3"<<endl ;
    }
    else if(a==1 && b==3 ||a==3 &&b==1)
    {
        cout<<"2"<<endl ;
    }

    else if(a==3 && b==2 ||a==2 &&b==3)
    {
        cout<<"1"<<endl ;
    }

    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e16;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)

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

void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll N, P;
    cin >> N >> P;
    string S;
    cin >> S;
    ll ans = 0;
    if(P==2){
        rep(i,N){
            if ((S[i] - '0') % 2 == 0) ans += i + 1;
        }
        cout << ans << endl;
        return 0;
    }else if(P==5){
        rep(i,N){
            ll a = S[i] - '0';
            if (a == 0 || a == 5) ans += i + 1;
        }
        cout << ans << endl;
        return 0;
    }

    reverse(all(S));
    ll ev = 0, d = 1;
    map<ll, ll> mp = {{0, 1}};
    rep(i,N){
        ev += (S[i] - '0') * d;
        ev %= P;
        ans += mp[ev];
        mp[ev]++;
        d *= 10;
        d %= P;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1044
import java.io.IOException;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) throws IOException {
		Scanner scanner = new Scanner(System.in);
		String aString = scanner.nextLine();
		String bString = scanner.nextLine();
		String cString = scanner.nextLine();

		int a=0;
		int b=0;
		int c=0;
		char start = 'a';
		while (true) {
			if(start=='a'){

				if(a==aString.length()){
					System.out.println("A");
					break;
				}
				start = aString.charAt(a);
				a++;
			}else if (start=='b') {

				if(b==bString.length()){
					System.out.println("B");
					break;
				}
				start = bString.charAt(b);
				b++;
			}else {

				if(c==cString.length()){
					System.out.println("C");
					break;
				}
				start = cString.charAt(c);
				c++;
			}

		}
	}
}


Measured memory_bytes: 21844
// Problem - Uppercase and Lowercase

import java.util.Scanner;
import java.lang.Character;

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

    // Input
    String str = sc.nextLine();
    String ans = "";
    for(int i=0; i<str.length(); i++){
      char tmp = str.charAt(i);
      if(Character.isUpperCase(tmp)){
        tmp = Character.toLowerCase(tmp);
      }else{
        tmp = Character.toUpperCase(tmp);
      }
      ans += tmp;
    }

    // Output
    System.out.println(ans);
  }
}



Measured memory_bytes: 31328
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((ll)(2e9))
#define pi (acos(-1))
#define M ((ll)(998244353))
#define NN ((ll)(1e4+2))
#define N ((ll)(1e5 + 5))
#define eps 0
#define log 20


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;

typedef tree < ll,  null_type,  less < ll >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
/// typedef tree < pair < ll,ll >,  null_type,  less < pair < ll,ll > >,  rb_tree_tag,  tree_order_statistics_node_update > o_setp;
/// o_set s;
/// s.order_of_key(k) : Number of items strictly smaller than k .
/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).

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

int main()
{
    int t;
    cin>>t;
    while(t--){
        ll a , b ,  c, d;
        cin>>a>>b>>c>>d;
        if(a<b || d<b){
            cout<<"No\n";
        }
        else{
            a %= b;
            d %= b;
            d = gcd(d,b);
            ll g = b-1-a;
            ll k = g/d;
            a += k*d;
            if(a>c){
                cout<<"No\n";
            }
            else cout<<"Yes\n";
        }
    }
    return 0;
}


Measured memory_bytes: 256
unittest
{
	assert( [ "1 3" ].parse.expand.solve == 2 );
	assert( [ "7 4" ].parse.expand.solve == 6 );
	assert( [ "5 5" ].parse.expand.solve == 5 );
}



import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto ab = input.front.split.to!( long[] );
	return tuple( ab[ 0 ], ab[ 1 ] );
}

auto solve( long a, long b )
{
	return ceil( ( a + b ) / 2f );
}


Measured memory_bytes: 256
//コンパイラ最適化用
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef pair<ll, ld> pld;
typedef pair<pii, int> ppiii;
typedef pair<pii, ll> ppiill;
typedef pair<pll, ll> ppllll;
typedef pair<pli, int> pplii;
typedef map<int, int> mii;
typedef deque<ll> dll;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqrll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvint;
typedef vector<vector<pll>> vvpll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define cin(x) cin >> x

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //入力
    ll H = 0, W =0, h = 0, w = 0; 
    cin(H);cin(W);cin(h);cin(w);

    //vll X(N);
    //REP(i,N) cin(X.at(i));

    ll ans = 0;
    
    ans = H*W - H*w -h*(W-w);


    //出力
    cout << ans << endl;
    //REP(i,N) cout << ans.at(i) <<endl;
  return 0;
}

Measured memory_bytes: 3648
//  cd Desktop/Atcoder
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define rep(i,n) for(i=0;i<(n);i++)
#define ll long long
#define ull unsigned long long
#define MOD 1000000007

int compare_smallorder(const void *a, const void *b){return *(int*)a - *(int*)b;}


int main(){
    int i,n,k,p[1002]={},ans=0;
    scanf("%d%d",&n,&k);
    rep(i,n) scanf("%d",&p[i]);
    qsort(p,n,sizeof(p[0]),compare_smallorder);
    rep(i,k) ans+=p[i];
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 1752
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    K, N, *A = map(int, read().split())

    A.sort()
    A.append(A[0] + K)
    B = [0] * N
    for i in range(N):
        B[i] = A[i + 1] - A[i]

    ans = K - max(B)

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 97800
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
 
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
 
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
 
ans=0
for i in range(n):
  ans+=a[i]*cmb(i,k-1,mod)
  ans%=mod
for i in range(n):
  ans-=a[i]*cmb(n-i-1,k-1,mod)
  ans+=mod
  ans%=mod
print(ans)

Measured memory_bytes: 20056
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

ll A[10000];

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

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

	ll ans = N;

	for (int i=0; i<M; i++) {
		ans -= A[i];
	}

	if (ans < -1) ans = -1;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3704
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
using Double = long double;

template<typename T1,typename T2> void chmin(T1 &a,T2 b){if(a>b) a=b;};
template<typename T1,typename T2> void chmax(T1 &a,T2 b){if(a<b) a=b;};

signed main(){
  Int n;
  const Double EPS = 1e-8;
  Int cnt=0;
  while(cin>>n,n){
    ++cnt;
    vector<Double> vx(n),vy(n);
    for(Int i=0;i<n;i++) cin>>vx[i]>>vy[i];

    const Double g=9.8;
    auto calc=[&](Int i,Double x){    
      Double t=x/vx[i];
      return vy[i]*t-g/2.0*t*t;    
    };

    Double x,y;
    cin>>x>>y;
  
    Double lb=calc(0,x);
    for(Int i=0;i<n;i++) chmin(lb,calc(i,x));
    if(y+EPS<lb){
      cout<<"No"<<endl;
      continue;
    }
    
    auto check=[&](Double m)->Double{
      Double res=0;
      for(Int i=0;i<n;i++){
	if(vy[i]<m*vx[i]) continue;
	res+=vx[i]*(vy[i]-m*vx[i])/9.8;
      }
      return res+EPS;
    };
    auto check2=[&](Double m)->Double{
      Double res=0;
      for(Int i=0;i<n;i++){
	if(vy[i]<m*vx[i]) continue;
	res+=calc(i,vx[i]*(vy[i]-m*vx[i])/9.8);
      }
      return res;
    };
    Double l=-1e9,r=1e9;
    for(Int k=0;k<100;k++){
      Double m=(l+r)/2;
      if(x<=check(m)) l=m;
      else r=m;
    }
    //cout<<l<<":"<<check(l)<<":"<<check2(l)<<endl;
    cout<<(y<=check2(l)?"Yes":"No")<<endl; 
  }
  
  return 0;
}




Measured memory_bytes: 3196
fn main() {
    let n:usize = readln();
    let a:Vec<i32> = readlns(n);
    let s = a.iter().sum();
    let x = a.into_iter().filter(|x| x%10 != 0).min();
    let ans = if s % 10 != 0 {
        s
    } else if let Some(x) = x {
        s - x
    } else {
        0
    };
    println!("{}", ans);
}

// --- template ---
pub trait FromLn {
    fn fromln(s: &str) -> Self;
}
pub fn readln<T: FromLn>() -> T {
    let mut buf = String::new();
    let _ = ::std::io::stdin().read_line(&mut buf).unwrap();
    T::fromln(buf.trim())
}
pub fn readlns<T: FromLn>(n: usize) -> Vec<T> {
    let mut vs = vec![];
    for _ in 0..n { vs.push(readln()); }
    vs
}
macro_rules! fromln_primitives {
    ($($t:ty),*) => { $(
        impl FromLn for $t {
            fn fromln(s: &str) -> $t {
                s.parse().unwrap()
            }
        }
    )* }
}
fromln_primitives!(String, bool, f32, f64, isize, i8, i16, i32, i64, usize, u8, u16, u32, u64);
impl<T> FromLn for Vec<T> where T: FromLn {
    fn fromln(s: &str) -> Vec<T> {
        s.split_whitespace().map(T::fromln).collect()
    }
}
impl FromLn for Vec<char> {
    fn fromln(s: &str) -> Vec<char> {
        s.chars().collect()
    }
}
macro_rules! fromln_tuple {
    ($($t:ident),*) => {
        impl<$($t),*> FromLn for ($($t),*) where $($t: FromLn),* {
            fn fromln(s: &str) -> ($($t),*) {
                let mut it = s.split_whitespace();
                let t = ($($t::fromln(it.next().unwrap())),*);
                assert_eq!(it.next(), None);
                t
            }
        }
    }
}
fromln_tuple!(A, B);
fromln_tuple!(A, B, C);
fromln_tuple!(A, B, C, D);
fromln_tuple!(A, B, C, D, E);
fromln_tuple!(A, B, C, D, E, F);

Measured memory_bytes: 4352
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define PII         pair<int, int>
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for(auto &x : a){
        cin >> x;
    }
    sort(ALL(a));
    int cnt = 0;
    for(int i = 0; x > 0 && i < n; i++){
        x -= a[i];
        cnt++;
    }
    cout << cnt - 1 + (x == 0);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
//#include <cmath>
//#include <cstdlib>
using namespace std;

int main(){
	string s;
	cin >> s;
	int a = 2000000, z = 0;
	for (int i = 0; i < s.size(); i ++) {
		if (s[i] == 'A' && a > i) a = i;
		if (s[i] == 'Z' && z < i) z = i;
	}
	cout << z - a + 1 << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;
long long m[100001];
long long A[100001];
int main(){
  int N;
  cin>>N;
  long long nord=1;
  long long answer=0;
  long long M=0;
  for(int i=0;i<=N;i++){
    cin>>A[i];
    M+=A[i];
  }
  for(int i=0;i<=N;i++){
    m[i]=M;
    M-=A[i];
  }
  for(int i=0;i<=N+1;i++){
    answer+=nord;
    if(i<=N) nord-=A[i];
    if(nord<0){
      cout<<-1<<endl;
      break;
    }
    if(i<N) nord=min(nord*2,m[i+1]);
    if(i==N+1) cout<<answer<<endl;
  }
  return 0;
}

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

using namespace std;
using LL = long long;

constexpr int N = 1e5 + 5;

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

    int a, b;
    cin >> a >> b;
    cout << a + b / 2 << endl;
}

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

using namespace std;
using ll=long long;
const ll mod = 1e9 + 7;
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};

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

int main() {
    int N,K;
    cin>>N>>K;
    vector<int> a(N,0);
    int maxn=0;
    for(int i = 0; i < N; ++i) {
      cin>>a[i];
      maxn=max(maxn,a[i]);
    }
    if(maxn<K){
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }
    int sdk=a[0];
    for(int i=1;i<N;i++){
        sdk=gcd(sdk,a[i]);
    }

    if(K%sdk==0) cout<<"POSSIBLE"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;

    return 0;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
class Program
{
	//static int[] dp;
	//static decimal[,,] dp;
	//static decimal N;
	static void Main(string[] args)
	{
			// 入力フェーズ
			//N = Decimal.Parse(Console.ReadLine()); // N皿ある
			string[] input = Console.ReadLine().Split(' '); // K,X
			int K = Int32.Parse(input[0]);
			int X = Int32.Parse(input[1]);

// X-K+1 から X+K-1までを出力する
			for(int i=X-K+1; i<=X+K-1; i++)
			{
				if(i==X+K-1)
				{
					Console.WriteLine(i + "");
				}
				else
				{
						Console.Write(i + " ");
				}
			}
    }


}


Measured memory_bytes: 13140
// template {{{

#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) loop(i, 0, n)
#define rloop(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define rrep(i, n) rloop(i, 0, n)
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T>
using max_pq = priority_queue<T, vector<T>, less<T>>;

template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

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

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(std::begin(c), std::end(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(std::begin(c), std::end(c)); }

template<typename T>
inline void unique(T &c){ std::sort(std::begin(c), std::end(c)); c.erase(std::unique(all(c)), std::end(c)); }

// }}}

int a, b, p;

template<typename T>
struct FenwickTree {
	FenwickTree(size_t n = 0): n(n), val(n + 1){}	
	
	void add(int k, T x){
		++k;
		while (k <= n){
			val[k] = (val[k] + x) % p;
			k += k & -k;
		}
	}

	T sum(int k){
		T res = 0;
		while (k > 0){
			res = (res + val[k]) % p;
			k -= k & -k;
		}
		return res;
	}

private:
	size_t n;
	vector<T> val;
};

using pr = pair<string, int>;

int main()
{
	while (cin >> a >> b >> p, a){
		vector<pr> v;
		loop(i, a, b + 1){
			v.eb(to_string(i), i - a + 1);
		}
		sort(v);
		FenwickTree<int> t(b - a + 10);
		t.add(0, 1);
		int res = 0;
		for (pr &a : v){
			res = (res + t.sum(a.se)) % p;
			t.add(a.se, t.sum(a.se));
		}
		cout << res << endl;
	}
}

Measured memory_bytes: 9564
#include<bits/stdc++.h>
using namespace std; 
#define all(c) c.begin(),c.end()
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define tr(container,it) \
for(auto it=container.begin();it!=container.end();++it)
typedef long long ll ; 
typedef vector<int> vi;
#define mod 1000000007

int main()
{
 //freopen("input.txt","r",stdin);
 //freopen("output.txt","w",stdout);
 //  ios::sync_with_stdio(0);
// cin.tie(0);
ll n,w;
cin>>n>>w;
vi a(n),b(n);
for(ll i=0;i<n;++i)
cin>>a[i]>>b[i];
vector<vector<ll>>dp(n+1,vector<ll>(100001,1e18+5));
REP(i,0,n)
dp[i][0]=0;
for(ll i=1;i<=n;++i){
    for(ll j=1;j<=accumulate(all(b),0ll);++j){
       // dp[i][j]=dp[i][j-1];
        dp[i][j]=min(dp[i][j],dp[i-1][j]);
     if(j-b[i-1]>=0)
        dp[i][j]=min(dp[i][j],dp[i-1][j-b[i-1]]+a[i-1]);
       // cout<<dp[i][j]<<" ";
    }//cout<<'\n';

}
ll best=0;

for(ll j=1;j<=accumulate(all(b),0ll);++j){
    if(dp[n][j]<=w)
    {
        best=max(best,j);
    }
}

cout<<best;
    return 0;
}

Measured memory_bytes: 83232
#include<bits/stdc++.h>
using namespace std;
char in[200050];
int R[26][200050];
int L[26][200050];
int pos[200050];
int main() 
{
	scanf("%s", in + 1);
	int N = strlen(in + 1), i, j;
	for (i = 0; i < 26; i++) 
	{
		for (j = 1; j <= N; j++) 
		{
			L[i][j] = L[i][j - 1];
			if (in[j] == 'a' + i) L[i][j] = j;
		}
		R[i][N + 1] = N + 1;
		for (j = N; j >= 1; j--) 
		{
			R[i][j] = R[i][j + 1];
			if (in[j] == 'a' + i) R[i][j] = j;
		}
	}
 
	int p = N+1, len = 0;
	pos[0] = N + 1;
	while (1) 
	{
		len++;
		int mn = N + 1;
		for (i = 0; i < 26; i++) mn = min(mn, L[i][p - 1]);
		pos[len] = mn;
		if (mn == 0) break;
		p = mn;
	}
	
	for (i = len-1, j = 1; i >= 0; i--) 
	{
		for (int k = 0; k < 26; k++) 
		{
			int p = R[k][j];
			if (pos[i] <= p) 
			{
				j = p + 1;
				printf("%c", 'a' + k);
				break;
			}
		}
	}
	return !printf("\n");
}

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

int main(){
  string S;
  cin>>S;
  int R=0,B=0;
  for(int i=0;i<S.size();++i){
    if(S[i]=='0') ++R;
    else ++B;
  }

  cout<<2*min(R,B)<<endl;
}


Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

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

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

  int need = 0;

  while (b <= a) {
    b <<= 1;
    ++need;
  }

  while (c <= b) {
    c <<= 1;
    ++need;
  }

  cout << (need <= k ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 3656
// Author - Kartikeya Gupta
// Problem Link - https://atcoder.jp/contests/dp/tasks/dp_e

#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <typeinfo>
#include <sstream>
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define I insert
#define pb push_back
#define F first
#define S second
#define br "\n"
#define repi(i, a, b) for (ll i = a; i < b; i++)
#define repj(j, a, b) for (ll j = a; j < b; j++)
#define vi vector<int>
#define pii pair<int, int>
#define vpii vector<pii>
#define mod 1000000007
#define lim 100001
#define pi 3.14159265

using namespace std;

ll factorial(ll n)      {    return (n == 1 || n == 0) ? 1 : n * factorial(n - 1); }
ll gcd(ll a, ll b)      {    if (a == 0)  return b; else return gcd(b % a, a);}
ll power(ll a, ll n)    {    if (n == 1) return a;else if (n == 0) return 1; else{ ll r = power(a, n / 2);if (n % 2 == 0)    return r * r;    else    return r * a * r;}}
ll nCr(ll n, ll r)      {    return ((factorial(n)) / (factorial(n - r) * factorial(r))); }
double precise(double n){    return floor(pow(10, 250) * n) / pow(10, 250);}

ll calculate(ll w,ll n, ll weights[], ll value[], vector<vll>& rec){
    if((w==0) or (n==-1)){
        return 0;
    }
    if(rec[w][n]!=-1){
        return (rec[w][n]);
    }
    ll weight = weights[n];
    if(weight>w){
        return  rec[w][n] = calculate(w, n - 1, weights,value,rec);
    }
    else{
    return rec[w][n] = max(calculate(w, n - 1, weights, value, rec), value[n] + calculate(w - weight, n-1, weights, value, rec));
    }
}

void solve(){
    ll n;
    cin >> n;
    string s;
    cin >> s;
    int pl=0, pr=n-1;
    /*while(pl<n){
        if(s[pl]=='W')
            break;
        else
            pl++;
    }
    if(pl==n){
        cout << 0;
        return;
    }
    while(pr>-1){
        if(s[pr]=='R')
            break;
        else
            pr++;
    }
    if(pr==-1){
        cout << 0;
        return;
    }*/
    ll ans = 0;
    while (pl < pr)
    {
        if(s[pl]=='R' and s[pr]=='W'){
            pl++;
            pr--;
            continue;
        }
        if(s[pr]=='W'){
            pr--;
            continue;
        }
        if(s[pl]=='R'){
            pl++;
            continue;
        }
        else{
            pl++;
            pr--;
            ans++;
        }
        }
        cout << ans << endl;
}

int main()
{    
/*#ifndef ONLINE_JUDGE
    // for getting input from input.
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif*/
    ll t;
	t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	//cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
	return 0;
}


Measured memory_bytes: 3724
#include<bits/stdc++.h>
using namespace std;
int main(){
    long double a,b,x;cin>>a>>b>>x;
    if((b/2)<(x/(a*a))){
        cout<<fixed<<setprecision(10)<<atan((b-(x/(a*a)))/(a/2.000)) *180.000/M_PI<<endl;
    }
    else{
        cout<<fixed<<setprecision(10)<<atan(b/((2.000*x)/(a*b))) *180.000/M_PI<<endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;
 int n, q, k;
vector<pair<int, int> > g[100010];
ll ans[100010];
bool vis[100010];
int main(){
  	scanf("%d", &n);
  	for(int i=0; i<n-1; i++){
    	int a, b, c;
      	scanf("%d%d%d", &a, &b, &c);
      	g[a].push_back(make_pair(b,c));
      	g[b].push_back(make_pair(a,c));
    }
    scanf("%d%d", &q, &k);
  vis[k] = true;
  ans[k] = 0;
  queue<int> bfs;
  bfs.push(k);
  while(bfs.size()){
  		int x = bfs.front(); bfs.pop();
    	vis[x] = true;
    	for(auto pp : g[x]){
        	if(!vis[pp.first]){
              	ans[pp.first] = ans[x] + pp.second;
            	bfs.push(pp.first);
            }
        }
  }
  
  
  for(int i=0; i<q; i++){
  	int x, y;
    scanf("%d%d", &x, &y);
    printf("%lld\n", ans[x] + ans[y]);
  }
	return 0;
}

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

int cmpnum(const void * n1, const void * n2) {
	if (*(long *)n1 > *(long *)n2)
	{
		return 1;
	}
	else if (*(long *)n1 < *(long *)n2)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void) {

  long n;
  scanf("%ld", &n);
  long a[n],b[n];
  for (long i = 0; i < n; i++) {
    scanf("%ld %ld", &a[i], &b[i]);
  }
  qsort(a, n, sizeof(long), cmpnum);
  qsort(b, n, sizeof(long), cmpnum);
  long min,max,ans;
  if (n%2 == 1) {
    min = a[(n-1)/2];
    max = b[(n-1)/2];
    ans = max-min+1;
  } else {
    min = a[n/2]+a[n/2-1];
    max = b[n/2]+b[n/2-1];
    ans = max-min+1;
  }
  printf("%ld\n", ans);

  return 0;
}

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


int main(){
  string s;
  cin >> s;
  int n,i;
  n=s.size();
  string ans;
  for(i=0;i<n;++i){
    if(s[i]=='0'){
      ans+=s[i];
    }else if(s[i]=='1'){
      ans+=s[i];
    }else{
      if(!ans.empty()){
        int len=ans.size();
        ans=ans.erase(len-1,1);
      }else{
        continue;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [10**10]*(H+1)
dp[0] = 0
for i in range(H):
    for ab in AB:
        a,b = ab[0], ab[1]
        idx = i+a if i+a < H else H
        dp[idx] = min(dp[idx], dp[i]+b)
print(dp[H])


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

#define ld long double
#define ll long long int
#define ull unsigned long long int
#define vi vector<int>
#define vl vector<ll>
#define vvi vector< vector<int> >
#define vvl vector< vector<ll> >
#define repd(i, a, b) for (int i=(a);i<(b);i++)
#define rep(i, n) repd(i,0,n)
#define ALL(v) v.begin(), v.end()
#define INF 1e9

using namespace std;

/**
 * calculate GCD(greatest common divisor)
 * @param a
 * @param b
 * @return
 */
unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

/**
 * change minimum
 * @tparam T
 * @param a
 * @param b
 * @return bool
 */
template<class T>
inline bool changeMinimum(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * change maximum
 * @tparam T
 * @param a
 * @param b
 * @return bool
 */
template<class T>
inline bool changeMaximum(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * output answer
 * @tparam T
 * @param answer
 * @return
 */
template<typename T>
T output(T answer) {
    cout << answer << endl;
    return 0;
}

/** ----from here ---------------------------------------------------------- */

string S;
int M;
int ans;

int cal(int n) {

    // cout << n << endl;
    if (n < 0) return 1;
    if (n % 2 == 1) {
        return cal(--n);
    }
    string first, second;

    /**
     * forループだとTLE
     */
//    for (int i = 0; i < n; ++i) {
//        if (i < n / 2) {
//            first += S[i];
//        }
//        if (i >= n / 2) {
//            second += S[i];
//        }
//    }
    /**
     * substrなどを使うことでループを計算量を減らす
     */
    first = S.substr(0, (n / 2));
    second = S.substr((n / 2), (n / 2));
    if (first == second) {
        ans = n;
        return 1;
    } else { return cal(--n); }
}

int main() {
    cin >> S;
    M = S.length();
    //int ans = cal(M - 1);
    cal(M - 1);
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <stack>
using namespace std;

void calculate(stack<int> &st, char c) {
    int b = st.top();
    st.pop();
    int a = st.top();
    st.pop();
    switch (c) {
        case '+':
            st.push(a + b);
            break;
        case '-':
            st.push(a - b);
            break;
        case '*':
            st.push(a * b);
            break;
    }
};

int main() {
    stack<int> st;        
    char s[10];

    while(scanf("%s", s) != EOF) {
        if (s[0] == '+' || s[0] == '-' || s[0] == '*') {
            calculate(st, s[0]);
        } else {
            st.push(atoi(s));
        }
    }
    printf("%d\n", st.top());
}


Measured memory_bytes: 2736
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define _max(_x, _y) ((_x)>(_y)?(_x):(_y))
#define _min(_x, _y) ((_x)>(_y)?(_y):(_x))

int main(void)
{
  int N, H, index;
  int ans = 0;
  int max_height = 0;
  scanf("%d", &N);
  for (index = 0; index < N; ++index) {
    scanf("%d", &H);
    if (H >= max_height) {
      ans++;
      max_height = H;
    }
  }
  printf("%d\n", ans);
  
  return 0;
}

Measured memory_bytes: 128