akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

int main(){
	
	double a, b;
	
	cin >> a;
	
	while(true){
		if(cin.eof()){
			break;
		}
		cin >> b;
		
		if(a < 35.5 && b < 71){
			printf("AAA\n");
		}else if(a < 37.5 && b < 77){
			printf("AA\n");
		}else if(a < 40 && b < 83){
			printf("A\n");
		}else if(a < 43 && b < 89){
			printf("B\n");
		}else if(a < 50 && b < 105){
			printf("C\n");
		}else if(a < 55 && b < 116){
			printf("D\n");
		}else if(a < 70 && b < 148){
			printf("E\n");
		}else{
			printf("NA\n");
		}
		
		cin >> a;
	}
	
	return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
string s;
int main(void){
    int a,b,c;
    cin>>a>>b;
    if(a>b)a--;
    cout<<a<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PA pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e16+7;
const ll MOD=1e9+7;

int main(){
	ll N,M,ans=0;
	cin >> N >> M;
	priority_queue<PA> Q;
	FOR(i,0,N){
		ll a,b;
		cin >> a >> b;
		Q.push({-a,b});
	}
	FOR(i,0,M){
		PA x = Q.top();
		Q.pop();
		ans -= x.first;
		x.second--;
		if(x.second)Q.push(x);
	}
	cout << ans << endl;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n,k;cin>>n>>k;
    double p=0;
    for (int i=1;i<=n;i++) {
        int t=i,mul=1;
        while (t<k) {
            t*=2;
            mul*=2;
        }
        p+=1.0/mul;
    }
    cout<<fixed<<setprecision(10)<<p/n<<endl;
}

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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  string s;
  cin >> s;
  int n = s.size();
  ll ans = 0;
  ll w_cnt = 0;
  REP(i, n) {
    if (s[i] == 'W') {
      w_cnt++;
      ans += i;
    }
  }
  cout << ans - w_cnt * (w_cnt - 1) / 2 << endl;
  return 0;
}

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

int main(void){
    int n,min,max;
    while(1){
        scanf("%d %d %d",&n,&min,&max);
        if(n==0)
            break;
        int *map,i,summax=0,sumn;
        map=(int *)malloc(sizeof(int)*n);
        for(i=0;i<n;i++)
            scanf("%d",&map[i]);
        for(i=min;i<=max;i++){
            if(map[i-1]-map[i] >= summax){
                summax=map[i-1]-map[i];
                sumn=i;
            }
        }
        printf("%d\n",sumn);
    }
    return 0;
}

Measured memory_bytes: 716
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    cout << fixed << setprecision(10);
    
    int N; cin >> N;
    bool aflag = false, bflag = false;
    string S; cin >> S;

    int ans = 0;
    rep(i, N-2) {
        if (S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C') {
            ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import math

A,B=input().split()

# if isinstance(A,int):
#     A = int(A)
# else:
#     A = float(A)


if isinstance(B,int):
    B = int(B)
else:
    B = float(B)

print(math.floor(int(A)*B))

# 1000000000000000

Measured memory_bytes: 9196
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <numeric>

using namespace std;

#define ll long long
#define rep(i, n) for (i = 0; i < n; i++)

int main()
{
  int K;
  cin >> K;
  vector<vector<ll>> lunlun(19);
  for (int i = 1; i <= 9; i++)
  {
    lunlun[1].push_back(i);
  }
  int num_of_digits = 2;
  while (true)
  {
    for (ll lun : lunlun[num_of_digits - 1])
    {
      if (lun % 10 == 0)
      {
        lunlun[num_of_digits].push_back(lun * 10);
        lunlun[num_of_digits].push_back(lun * 10 + 1);
      }
      else if (lun % 10 != 9)
      {
        lunlun[num_of_digits].push_back(lun * 10 + (lun % 10 - 1));
        lunlun[num_of_digits].push_back(lun * 10 + lun % 10);
        lunlun[num_of_digits].push_back(lun * 10 + (lun % 10 + 1));
      }
      else
      {
        lunlun[num_of_digits].push_back(lun * 10 + 8);
        lunlun[num_of_digits].push_back(lun * 10 + 9);
      }
    }
    int num = K;
    for (vector<ll> lun_vec : lunlun)
    {
      if (num <= lun_vec.size())
      {
        cout << lun_vec[num - 1] << endl;
        return 0;
      }
      num -= lun_vec.size();
    }
    num_of_digits++;
  }
}


Measured memory_bytes: 3348
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

// reference: http://ir5.hatenablog.com/entry/20171209/1512821837

struct Scanner<'a> {
    cin: StdinLock<'a>,
}
 
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }
 
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }
 
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

use std::mem;
use std::cmp;

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let n: u32 = sc.read();
    let mut ans: u32 = 0;
    let mut mx: u32 = 0;
    for i in (0..n) {
        let a: u32 = sc.read();
        let b: u32 = sc.read();
        if a >= mx {
            mx = a;
            ans = a + b;
        }
    }
    println!("{}", ans);
}

Measured memory_bytes: 2144
N = int(input())
MAX = 3501
for i in range(1,MAX):
  for j in range(1,MAX):
    chi = N*i*j
    mom = 4*i*j - N*i - N*j
    if mom <= 0:
      continue
    if chi%mom == 0:
      ans = [i,j,chi//mom]
      print(*ans)
      exit()
    
    

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

int main(void){
	int n, m;
	cin >> n >> m;
	vector<int> l(m), r(m);
	vector<int> ans(n+2);
	for(int i = 0; i < m;++i){
		cin >> l[i] >> r[i];
		ans[l[i]]++;
		ans[r[i]+1]--;
	}
	int ret = 0;
	for(int i = 1; i <= n; ++i){
		ans[i] += ans[i-1];
		if(ans[i]==m){
			ret++;
		}
	}
	cout << ret << endl;
	return 0;
}

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

int n;
int main()
{
	cin >> n;
	cout << 24 - n + 24;
//	for (i = 0; i < n; i++) {
//		scanf ("%d", &a[i]);
//		s += a[i];
//	}
//	cout << s'
//    cout << "Hello world!" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	bool c = 0, f = 0;
	for (int i = 0; i < (int) s.length(); ++ i) {
		if (c && s[i] == 'F') f = 1;
		if (s[i] == 'C') c = 1;
	}
	puts(f ? "Yes" : "No");
}



Measured memory_bytes: 256
//#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <atcoder/all>
using namespace atcoder;
//using mint = modint998244353;
//using mint = modint1000000007;
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//using i128 = __int128_t;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
constexpr char ln = '\n';
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
inline int topbit(int x) {return x == 0 ? -1 : 31-__builtin_clz(x);}
inline int topbit(long long x) {return x == 0 ? -1 : 63-__builtin_clzll(x);}
inline int botbit(int x) {return x == 0 ? 32 : __builtin_ctz(x);}
inline int botbit(long long x) {return x == 0 ? 64 : __builtin_ctzll(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
inline int kthbit(long long x, int k) {return (x>>k)&1;}
inline void print() {cout << "\n";}
template<class T>
inline void print(const vector<T> &v) {
    for (auto itr = v.begin(); itr != v.end(); ++itr) cout << *itr << " ";
    print();
}
template<class T, class... Args>
inline void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
#ifdef MINATO_LOCAL
#define dump(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
inline void debug() {cerr << endl;}
template<class T>
inline void debug(const vector<T> &v) {
    for (auto itr = v.begin(); itr != v.end(); ++itr) cerr << *itr << " ";
    debug();
}
template<class T, class... Args>
inline void debug(const T &x, const Args &... args) {
    cerr << x << " ";
    debug(args...);
}
#else
#define dump(x) void(0)
inline void debug() {}
template<class T> inline void debug(const vector<T> &v) {}
template<class T, class... Args> inline void debug(const T &x, const Args &... args) {}
#endif
struct Fast_ios {Fast_ios() {cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);};} fast_ios;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void solve() {
    ll n,m,a,b; cin >> n >> m >> a >> b;
    cout << floor_sum(n,m,a,b) << ln;
}
int main() {
    int Q; cin >> Q;
    while (Q--) {
        solve();
    }
}


Measured memory_bytes: 3676
/*#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>*/
#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
const ll mod = 1e9 + 7;
ll dx[4] = {1,0,-1,0};
ll dy[4] = {0,1,0,-1};

int main(){
    ll k,s;
	cin >> k >> s;
	ll ans=0;
	rep(i,k+1)rep(j,k+1){
		ll z = s - i - j;
		if(0 <= z && z <= k) ans++;
	}
	cout << ans << endl;
	return 0;
}  


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int 
#define pb push_back 
int main() 
{
    ll n ;
    cin >> n ;
    vector<ll> dis(n,0) ;
    vector<ll>hig ;
    for(ll i =0 ; i < n ; i++)
    {
        ll a ;
        cin >>a ;

        hig.pb(a) ;
        
    }
    
    dis[n-2]= abs(hig[n-1] - hig[n-2]) ;
    
    
    for( ll i = n-3 ; i >= 0 ;i--)
    {
        dis[i] = min(dis[i+1] + abs(hig[i+1] - hig[i]) , dis[i+2] + abs(hig[i+2] - hig[i]) ) ;
    }
    
    cout<< dis[0] ;
    return  0; 
}

Measured memory_bytes: 2168
function Main(input){
  var inp = input.split('\n');
  var c1 = inp[0].split(' ').map(n => { return parseInt(n.trim())});
  var c2 = inp[1].split(' ').map(n => { return parseInt(n.trim())});
  var c3 = inp[2].split(' ').map(n => { return parseInt(n.trim())});

/*
       y[0] y[1] y[2]
  x[0]   1    0   1
  x[1]   2    1   2
  x[2]   1    0   1
*/

  // 二次配列にする
  var C = [];
  C[0] = c1;
  C[1] = c2;
  C[2] = c3;

  var x = []; // 縦列見出し
  var y = []; // 横行見出し
  x[0] = 0; // xは打ち消されてしまうのでなんでも良い。0とする

  // y横行の値を決める
  for(var i = 0; i < 3; i++){
    y[i] = C[0][i] - x[0];
  }

  // x縦列の値を求める
  for(var i = 0; i < 3; i++){
    x[i] = C[i][0] - y[0];
  }

  // 検算する
  var good = true;
  for(var i = 0; i < 3; i++){
    for(var j = 0; j < 3; j++){
      if(x[i] + y[j] !== C[i][j]){
        good = false;
      }
    }
  }

  if(good){
    console.log('Yes');
  } else {
    console.log('No');
  }

}
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 7372
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<tuple>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
int main(){
    int n,x,t;
    cin >> n >> x >> t;
    int counter=1;
    while(counter*x<n){
        counter++;
    }
    cout << counter*t << endl;
}

Measured memory_bytes: 3628
#include<iostream>
using namespace std;
int main(){
  int H,W;
  cin>>H>>W;
  char  a[H+1][W+1];
  for(int i=0;i<H;i++){
    for(int k=0;k<W;k++){
      cin>>a[i][k];
    }
  }
  char ans[H+2][W+2];
  for(int i=0;i<H+2;i++){
    for(int k=0;k<W+2;k++){
      ans[i][k]='#';
    }
  }
  for(int i=1;i<H+1;i++){
    for(int k=1;k<W+1;k++){
      ans[i][k]=a[i-1][k-1];
    }
  }
  for(int i=0;i<H+2;i++){
    for(int k=0;k<W+2;k++){
      cout<<ans[i][k];
    }
    cout<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<cstdio>
#include<unordered_set>
using namespace std;

int main()
{
	string str;
	cin >> str;
	int i, x, y;
	x = y = -1;
	for (i = 0; i < str.size(); i++) {
		if (x >= 0 && str[i] == 'F') {
			y = i;
			break;
		}
		else if (str[i] == 'C') {
			x = i;
		}
	}
	if (y > 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

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

int n,mx,mn,cnt[110];

int main()
{
#ifdef h10
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
#endif
	int i,x;
	scanf("%d",&n);
	mx=0; mn=n;
	for (i=1;i<=n;i++)
	{
		scanf("%d",&x);
		cnt[x]++;
		mx=max(mx,x);
		mn=min(mn,x);
	}
	bool flag=1;
	flag&=mn==(mx+1)/2;
	for (i=mn+1;i<=mx;i++)
		flag&=cnt[i]>=2;
	flag&=cnt[mn]==(mx&1)+1;
	puts(flag?"Possible":"Impossible");
}


Measured memory_bytes: 256
import bisect
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    for j in range(i+1, N):
        t = L[i] + L[j]
        idx = bisect.bisect_left(L, t)
        ans += max(0, idx-j-1)
print(ans)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
 
signed main(){
 
	lli n,l;
	cin>>n>>l;

	vector<lli> a(n);
	for(lli i=0;i<n;i++){
		a[i] = l+i;
	}
	lli sum=0;
	lli ans=100000000000000;
	lli ansIndex=-1;
	REP(i,0,n){
		sum+=a[i];
		if(ans>abs(a[i])){
			ans = abs(a[i]);
			ansIndex=i;
		}
	}
	cout<<sum-a[ansIndex]<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
 
 
using namespace std;
using ll = long long;
using ull = unsigned long long;
 
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
 
#define REP(i, n) for(ll i = 0; i < n; i++)
 
 
 
int main() {
	ll n, k, q;
	cin >> n >> k >> q;
	vector<ll> a(n);
	REP(i, n){
		cin >> a[i];
	}
 
	ll ans = INF;
	REP(i, n){
		vector<ll> tmp;
		multiset<ll> ms;
		REP(j, n + 1){
			if(j == n || a[j] < a[i]){
				sort(tmp.begin(), tmp.end());
				REP(l, (ll)tmp.size() - k + 1){
					ms.insert(tmp[l]);
				}
				tmp.clear();
			}
			else{
				tmp.push_back(a[j]);
			}
		}
		if(ms.size() < q) continue;
		auto itr = ms.begin();
		REP(j, q - 1) itr++;
		ans = min(ans, *itr - a[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
function main(input) {
  const args = input.split(' ');
  const A = args[0];
  const B = args[1];
  const C = args[2];
  const culc = Math.floor(B / A);
  console.log(Number(C) < culc ? C : culc);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

using namespace std;

const int maxn = 3010;

int n, a[maxn], ind[maxn];
int dp[maxn], l[maxn], e;

struct Edge {
	int v, x;
} E[maxn << 1];

bool cmp(int x, int y) {
	return a[x] < a[y];
}

inline void addEdge(int u, int v) {
	E[e].v = v; E[e].x = l[u]; l[u] = e++;
}

int main() {
	memset(l, -1, sizeof(l));
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) ind[i] = i;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sort(ind+1, ind+n+1, cmp);
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%d%d", &u, &v);
		addEdge(u, v);
		addEdge(v, u);
	}
	for (int _ = 1; _ <= n; _++) {
		int i = ind[_];
		for (int p = l[i]; p >= 0; p = E[p].x) {
			int v = E[p].v;
			if (a[v] < a[i]) {
				if (!dp[v]) {
					dp[i] = 1;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dp[i]) {
			printf("%d ", i);
		}
	}
	puts("");
	return 0;
}

Measured memory_bytes: 384
n, k = map(int,input().split())
array = list(map(int,input().split()))

box = [0]*200000

for item in array:
  box[item-1] += 1
  
box.sort(reverse=True)

cnt = 0
for i in range(k):
  cnt += box[i]
  
print(n-cnt)

Measured memory_bytes: 25644
#include<bits/stdc++.h>
using namespace std;
int main(){
  	int n;
  	long long a, min=1000000, max=-1000000, total=0;
  	cin >>n;
	for(int i=0; i<n; i++){
      	cin >>a;
      	if(max<a) max = a;
      	if(min>a) min = a;
      	total += a;
    }
  	cout << min << " " << max << " " << total << endl;
}


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

H,W=map(int,input().split())
MAP=[input().strip() for i in range(H)]

Y=[[0]*W for i in range(H)]
T=[[0]*W for i in range(H)]

count=0

for i in range(H):
    count=0
    for j in range(W):
        if MAP[i][j]=="#":
            count=0
        else:
            count+=1
            Y[i][j]=count

for i in range(H):
    for j in range(W-2,-1,-1):
        if Y[i][j]==0:
            continue
        Y[i][j]=max(Y[i][j],Y[i][j+1])

for i in range(W):
    count=0
    for j in range(H):
        if MAP[j][i]=="#":
            count=0
        else:
            count+=1
            T[j][i]=count

for i in range(W):
    for j in range(H-2,-1,-1):
        if T[j][i]==0:
            continue
        T[j][i]=max(T[j][i],T[j+1][i])

ANS=0
for i in range(H):
    for j in range(W):
        ANS=max(ANS,Y[i][j]+T[i][j]-1)

print(ANS)


Measured memory_bytes: 119516
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a=0,b=1000000000;
  cin >> n;
  int l[n];
  for(int i=0;i<n;i++){
    cin >> l[i];
    a=max(a,l[i]);
    b=min(b,l[i]);
  }
  cout << a-b;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;
typedef long long ll;

int main() {
    ll N,M;
    cin >> N >> M;
    vector<int> csum(N+1,0);
    for(int i=0;i<N;i++) {
        cin >> csum[i+1];
        csum[i+1]%=M;
    }
    for(int i=1;i<=N;i++){
        csum[i]+=csum[i-1];
        csum[i]%=M;
    }

    sort(csum.begin(),csum.end());
    vector<ll> num;
    ll tmp=csum[0];
    ll ct=1;
    for(int i=1;i<=N;i++){
        if(tmp==csum[i]){
            ct++;
            if(i==N) num.push_back(ct);
        }
        else{
            num.push_back(ct);
            ct=1;
        }

        tmp=csum[i];
    }
    ll ans=0;
    for(int i=0;i<num.size();i++) {
        //cout << i << " " << num[i] << endl;
        ans+=num[i]*(num[i]-1)/2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    if (b == 1) {
        cout << 0 << endl;
        return 0;
    }
    int i = 0;
    while (a + (a - 1) * i < b) {
        i++;
    }
    cout << i + 1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>

int main() {
	int n, mult2 = 0, mult4 = 0, a[100000];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
		mult2 += ((a[i] & 1) ^ 1);
		mult4 += (a[i] % 4 == 0);
	}
	bool can = false;
	if (n / 2 <= mult4)
		can = true;
	else if (n - mult4 * 2 <= (mult2 - mult4))
		can = true;
	printf("%s\n", (can ? "Yes" : "No"));
}

Measured memory_bytes: 512
n,d=map(int,input().split())
x=[]
for i in range(n):
    x.append(list(map(int,input().split())))
ans=0


for i in range(n-1):
    for j in range(i+1,n):
        d2=0
        for l in range(d):
            d2+=(x[i][l]-x[j][l])**2
        d2=int(d2)
        for k in range(1,d2//2+2):
            if d2==k**2:
                ans+=1
                break

print(ans)



Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include<string>
#include<cmath>
#include<stack>
#include <vector>
#include<queue>
#include <random>
#include <cstdint>
#include <bitset>
#include <iomanip>
using namespace std;

int main() {
	char s[52][52];
	int h, w;
	cin >> h >> w;
	fill(s[0], s[52], '.');
	for (int i = 1; i < h+1; i++) {
		for (int j = 1; j<w + 1; j++) {
			cin >> s[i][j];
		}
	}
	for (int i = 1; i < h + 1; i++) {
		for (int j = 1; j<w + 1; j++) {
			if (s[i][j] == '.'||s[i-1][j]=='#'|| s[i + 1][j] == '#' || s[i][j + 1] == '#' || s[i][j - 1] == '#' ) {
				continue;
			}
			else {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int a, b, mult1, mult2;
  scanf("%d %d", &a, &b);

  mult1=a*b*a;
  mult2=a*b*b;

  if( (mult1%2)!=0 || (mult2%2)!=0)
    printf("Yes\n");
  else
    printf("No\n");
  return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
Int dist[300][300], cnt[300][300];
const Int INF = 1e18;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, L; cin >> N >> M >> L;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = cnt[i][j] = INF;
        }
    }
    for (int i = 0; i < N; i++) {
        dist[i][i] = 0;
        cnt[i][i] = 0;
    }
    for (int i = 0; i < M; i++) {
        int a, b, c; cin >> a >> b >> c; a--, b--;
        dist[a][b] = dist[b][a] = c;
    }
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dist[i][j] <= L) {
                cnt[i][j] = min(cnt[i][j], 1LL);
            }
        }
    }
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cnt[i][j] = min(cnt[i][j], cnt[i][k] + cnt[k][j]);
            }
        }
    }
    int Q; cin >> Q;
    for (int i = 0; i < Q; i++) {
        int s, t; cin >> s >> t; s--, t--;
        if (cnt[s][t] < INF) {
            cout << cnt[s][t] - 1 << '\n';
        } else {
            cout << -1 << '\n';
        }
    }
    return 0;
}


Measured memory_bytes: 1920
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
S1 = LS2()
S2 = LS2()
mod = 10**9+7

A = []
a = 0
while a < N:
    if S1[a] == S2[a]:
        a += 1
        A.append(1)
    else:
        a += 2
        A.append(2)

ans = 1
for i in range(len(A)):
    if i == 0:
        if A[i] == 1:
            ans *= 3
        else:
            ans *= 6
    else:
        if A[i] == 1 and A[i-1] == 1:
            ans *= 2
        if A[i] == 2 and A[i-1] == 1:
            ans *= 2
        if A[i] == 2 and A[i-1] == 2:
            ans *= 3
        ans %= mod

print(ans)

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

int vary(string x, string y){
	int n, c = 0;
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());


	for(int i=0; i < x.size(); i++){
		if(i==0 || i>0 && x[i] != x[i-1]){
			for(int j=0; j < y.size(); j++){
				if(j==0 || j>0 && y[j] != y[j-1]){
					if(x[i] == y[j]) c++;
				}
			}
		}
	}
	return c;
}





int main(){
	int n, ans=0, count;
	string s;
	cin >> n >> s;

	for(int i=1; i<n; i++){
		string x, y;
		x = s.substr(0, i);
		y = s.substr(i);
		count = vary(x, y);
		ans = max(ans, count);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
#define INF 100000000
#define MOD 1000000007

int main()
{
	int n, m, x, ip = 1;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		ip *= 2;
	}
	x = (1900 * m + 100 * (n - m)) * ip;

	cout << x << endl;

	return (0);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[100009],minx = (1 << 30);
int main(){
      // #ifndef ONLINE_JUDGE
      //  // for getting input from input.txt
      //  freopen("input.txt", "r", stdin);
      //  // for writing output to output.txt
      //  freopen("output.txt", "w", stdout);
      // #endif
	   int n,k;
     cin>>n>>k;
     for (int i = 0; i < n; ++i)
     {
       cin>>a[i];
     }
     sort(a,a+n);
     for (int i = 0; i <= n-k; ++i)
     {
       minx = min(minx, (a[i+k-1] - a[i]));
     }
     cout<<minx;
	return 0;
}


Measured memory_bytes: 768
n = 0
S = input()
for i in range(0,len(S)):
    if i==0:
        if S[i]=="R":
            n += 1
    if i==1:
        if S[i]=="R":
            n += 1
        else:
            n = 0
    if i==2:
        if S[i]=="R":
            n += 1
        else:
            continue
    if S == "RSS":
        n = 1
print(n)

Measured memory_bytes: 9060
n,m,x,y=map(int,input().split())
xn=list(map(int,input().split()))
yn=list(map(int,input().split()))
xn.sort()
yn.sort()
z=yn[0]
if x<z<y and xn[-1]<z and yn[0]>=z:
    print("No War")
else:
    print("War")


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

void solve(std::string AtCoder, std::string s, std::string Contest){
    cout << AtCoder[0] << s[0] << Contest[0] << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::string AtCoder;
    std::cin >> AtCoder;
    std::string s;
    std::cin >> s;
    std::string Contest;
    std::cin >> Contest;
    solve(AtCoder, s, Contest);
    return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
    ost<<"{"<<p.first<<","<<p.second<<"}";
    return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
    ost<<"{";
    for(int i=0;i<v.size();i++){
        if(i)ost<<",";
        ost<<v[i];
    }
    ost<<"}";
    return ost;
}

const int INF=100100100100100100ll;

signed main(){
    int N,M;
    scanf("%lld%lld",&N,&M);
    int L=-INF;
    int R=INF;
    rep(i,N){
        int l,r;
        scanf("%lld%lld",&l,&r);
        chmax(L,l);
        chmin(R,r);
    }
    cout<<max(0ll,R-L+1)<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ff first
#define ss second 
using ii = pair<int, int>;

vector<ii> adj_list[MAXN];
int color[MAXN];

int main(){
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    memset(color, -1, sizeof color);
    for(int i=1; i<n; ++i){
        int a, b, w;
        cin >> a >> b >> w;
        adj_list[a].push_back({b, w});
        adj_list[b].push_back({a, w});
    }
    stack<int> q;
    for(int u=1; u<=n; ++u){
        if((int)adj_list[u].size()==1){ 
            q.push(u);
        }
    }
    while(not q.empty()){
        int u = q.top(); q.pop();
        
        for(auto x:adj_list[u]){
            int v = x.ff, w = x.ss;
            if(w%2==0){
                if(color[u]==-1 and color[v]==-1){
                    color[u] = 0;
                    color[v] = 0;
                    q.push(v);
                }
                else if(color[u]!=-1 and color[v]==-1){
                    color[v] = color[u];
                    q.push(v);
                }
                else if(color[u]==-1 and color[v]!=-1){
                    color[u] = color[v];
                }
            }
            else{
                if(color[u]==-1 and color[v]==-1){
                    color[u] = 0;
                    color[v] = 1;
                    q.push(v);
                }
                else if(color[u]!=-1 and color[v]==-1){
                    color[v] = (color[u]+1)%2;
                    q.push(v);
                }
                else if(color[u]==-1 and color[v]!=-1){
                    color[u] = (color[v]+1)%2;
                }
            }
        }
    }
    for(int i=1; i<=n; ++i)
        cout << color[i] << "\n";
}   


Measured memory_bytes: 7040
#include <iostream>
#include <cstdio>
#include <complex>
#include <vector>
using namespace std;

typedef complex<double> P;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

double area(vector<P> p){
	int n = p.size();
	double res = 0.0;

	rep(i,n){
		res += p[i].real() * p[(i+1)%n].imag() - p[(i+1)%n].real() * p[i].imag();
	}
	return fabs(res/2);
}

double cross(P a, P b){
	return (a.real() * b.imag() - a.imag() * b.real());
}

P intersection_l(P a1, P a2, P b1, P b2){
	P a = a2 - a1;
	P b = b2 - b1;
	return a1 + a * cross(b, b1-a1) / cross(b, a);
}

int main(void){
	int n;

	while(cin>>n && n){
		P v[n+2][n+2];

		v[0][0] = P(0,0);
		v[0][n+1] = P(1,0);
		v[n+1][0] = P(0,1);
		v[n+1][n+1] = P(1,1);

		REP(i,1,n+1) { v[0][i].imag() = 0;   cin>>v[0][i].real(); }
		REP(i,1,n+1) { v[n+1][i].imag() = 1; cin>>v[n+1][i].real(); }
		REP(i,1,n+1) { v[i][0].real() = 0;   cin>>v[i][0].imag(); }
		REP(i,1,n+1) { v[i][n+1].real() = 1; cin>>v[i][n+1].imag(); }

		REP(i,1,n+1){
			REP(j,1,n+1){
				v[i][j] = intersection_l(v[0][j],v[n+1][j],v[i][0],v[i][n+1]);
			}
		}

		double ans = 0.0;
		rep(i,n+1){
			rep(j,n+1){
				vector<P> p;
				p.push_back(v[i][j]);
				p.push_back(v[i+1][j]);
				p.push_back(v[i+1][j+1]);
				p.push_back(v[i][j+1]);
				ans = max(ans,area(p));
			}
		}
		printf("%.6lf\n",ans);
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun Jun 21 21:11:30 JST 2020
 **/

signed main() {
    Int n;
    std::cin >> n;
    std::map<Int, Int> mp;
    Int sum = 0;
    REP(i, n) {
        Int x;
        std::cin >> x;
        mp[x]++;
        sum += x;
    }
    Int Q;
    std::cin >> Q;
    REP(q, Q) {
        Int b, c;
        std::cin >> b >> c;
        mp[c] += mp[b];
        sum += (c - b) * mp[b];
        std::cout << sum << "\n";
        mp[b] = 0;
    }
}


Measured memory_bytes: 9536
# -*- coding: utf-8 -*-
import bisect

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
B_list = list(map(int, input().rstrip().split()))
C_list = list(map(int, input().rstrip().split()))
#-----

A_list.sort()
B_list.sort()
C_list.sort()

cnt=0
for i in B_list:
    ind_A = bisect.bisect_left(A_list, i)
    ind_C = bisect.bisect_right(C_list, i)
    cnt +=  ind_A * (N - ind_C)

print(cnt)


Measured memory_bytes: 23360
INF = 10**30
def solve(n, x, d):
  if d == 0:
    if x == 0:
      return 1
    else:
      return n+1
  D={}
  for k in range(n+1):
    l = k*x + (k-1)*k//2 * d
    r = k*x + (n*k - k*(k+1)//2)*d
    c = k*x % d
    if not c in D:
      D[c] = [];
    l = (l-c)//d
    r = (r-c)//d
    if l > r:
      l, r = r, l
    D[c].append((l, r))
  res = 0
  for v in D.values():
    threshold = -INF
    for l,r in sorted(v):
      l = max(l, threshold)
      res += max(0, r-l+1)
      threshold = max(threshold, r+1)
  return res

n, x, d = map(int, input().split())
print(solve(n, x, d))


Measured memory_bytes: 83540
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
using namespace std;

typedef long long ll;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int s[102][20000];
int t[102][52];
int now[102];
bool wait[102];

int main(){
  int n,m;

  while(cin>>n>>m,n||m){
    rep(i,n) for(int j=0;cin>>t[i][j],t[i][j];j++);

    queue<int> q;
    memset(s,-1,sizeof(s));
    memset(now,0,sizeof(now));
    memset(wait,0,sizeof(wait));

    int ans = 0;

    //0 : '*', 1 : '.', 2 : '-'
    rep(j,m){
      bool flg = false;
      rep(i,n){
        if(s[i][j] == 1){
          flg = true;
        }
      }

      rep(i,n){
        if(s[i][j] != -1) continue;

        if(now[i] % 2 == 0){
          for(int k=j;k<j+t[i][now[i]];k++){
            s[i][k] = 0;
          }
          now[i]++;
        }
        else if(flg){
          ans++;
          if(!wait[i]){
            q.push(i);
            wait[i] = true;
          }

          s[i][j] = 2;
        }
        else{
          if(!wait[i]){
            q.push(i);
            wait[i] = true;
          }
          if(q.front() == i){
            q.pop();
            wait[i] = false;
            flg = true;
            for(int k=j;k<j+t[i][now[i]];k++){
              s[i][k] = 1;
            }
            now[i] = (t[i][now[i]+1] == 0 ? 0 : now[i]+1);
          }
          else{
            ans++;
            s[i][j] = 2;
          }
        }
      }
    }

    cout<<ans<<endl;
  }
}

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

template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}

const int N = 2007;
int cnt[3][N][N], pre[3][N][N], suf[3][N][N];

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k; cin >> n >> k;
	vector<pair<int, pair<int, char>>> a(n);
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		char z; cin >> z;
		int dx = x / k;
		int dy = y / k;
		bool t = z == 'W';
		t ^= (dx & 1);
		t ^= (dy & 1);
		x %= k;
		y %= k;
		cnt[t][x][y]++;
	}
	for (int t = 0; t < 2; t++) {
		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				pre[t][i + 1][j + 1] = pre[t][i + 1][j] + pre[t][i][j + 1] - pre[t][i][j] + cnt[t][i][j];
			}
		}
		for (int i = k - 1; i >= 0; i--) {
			for (int j = k - 1; j >= 0; j--) {
				suf[t][i][j] = suf[t][i + 1][j] + suf[t][i][j + 1] - suf[t][i + 1][j + 1] + cnt[t][i][j];
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			for (int t = 0; t < 2; t++) {
				ans = max(ans, pre[t][i][j] + suf[t][i][j] + (pre[t ^ 1][k][k] - pre[t ^ 1][i][j] - suf[t ^ 1][i][j]));
			}
		}
	}
	cout << ans << '\n';
}


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

int main() {
	long long x;	cin >> x;
	long long ans = 0;
	ans += x / 500 * 1000;
	x %= 500;
	ans += x / 5 * 5;
	x %= 5;
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		in.nextLine();
		int max = 0;
		while (in.hasNextLine()) {
			int n = 0;
			for (char c : in.nextLine().toCharArray()) {
				if (c == '1') {
					n++;
				}
			}
			max = Math.max(n, max);
		}
		System.out.println(max);
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int Q, q, a, b;
ll res;
multiset<int>st;

int main() {
	cin >> Q;
	--Q;
	cin >> q >> a >> res;
	st.insert(a);
	auto it = st.begin();
	while (Q--) {
		cin >> q;
		if (q == 1) {
			cin >> a >> b;
			res += b;
			res += abs(*it - a);
			if (st.size() & 1) {
				st.insert(a);
				if (*it > a) {
					--it;
				}
			}
			else {
				st.insert(a);
				if (*it <= a) {
					auto it2 = it;
					++it2;
					res -= *it2 - *it;
					++it;
				}
			}
		}
		else {
			cout << *it << sp << res << endl;
		}
	}
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{ 
  vector<ll> v(5);
  for(int i=0; i<5; i++) cin >> v[i];
  for(int i=0; i<5; i++) if(v[i]==0) {
    cout<<i+1<<endl; return 0;
  }
  return 0;
}


Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define llinf 1e17
#define nllinf -4e18
 
#define vll vector<ll>
#define sll set<ll>
#define pll pair<ll,ll> 
#define vpll vector<pair<ll,ll > >
 
#define repup(a,b,i) for(i=a;i<=b;i++)
#define repdown(a,b,i) for(i=b; i>=a; i--)
#define repupx(a,b,i,x) for(i=a;i<=b;i+=x)
	
#define repit(v,it) for(it=v.begin(); it!=v.end(); it++)
#define itall(v) v.begin(),v.end()
#define pb push_back
#define pf push_front
#define mp make_pair
#define fr first
#define sc second
 
#define err(n) cout<<n<<" ";
#define t1 cout<<",";
 
ll MOD= 1e9 +7;


int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll i,j,k;

ll n,m;cin>>n>>m;
char a[n][m];
repup(0,n-1, i){
	repup(0,m-1,j){
		cin>>a[i][j];
	}
}
ll dp[n+4][m+4];
dp[0][0]=1;
repup(1,n-1,i){
	if(dp[i-1][0]&&a[i][0]!='#')dp[i][0]= 1;
	else dp[i][0]=0;
}
repup(1,m-1,i){
	if(dp[0][i-1]&&a[0][i]!='#')dp[0][i]= 1;
	else dp[0][i]=0;
}
repup(1,n-1,i){
	repup(1,m-1,j){
		if(a[i][j]=='#')dp[i][j]=0;
		else{
			dp[i][j]=0;
			if(dp[i-1][j])dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
			if(dp[i][j-1])dp[i][j]=(dp[i][j]+dp[i][j-1])%MOD;
		}
	}
}
cout<<dp[n-1][m-1];
}

Measured memory_bytes: 9088
#include <iostream>
#define REP(i, n) for(int i = 0; i < (n); ++i)
using ll = long long;
using namespace std;

constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 22;


ll n, a[MAX][MAX];

ll dp[22][1 << 22];

int main() {
	cin >> n;
	REP(i, n) REP(j, n) cin >> a[i][j];

	dp[0][0] = 1;
	REP(i, n) { // 男
		REP(bit, 1 << n) { // bit: 女の状態
			if (__builtin_popcount(bit) != i) continue;
			REP(j, n) { // j人目の女
				if ((bit >> j & 1) == 0 && a[i][j] == 1) {
					dp[i + 1][bit | (1 << j)] += dp[i][bit];
					dp[i + 1][bit | (1 << j)] %= MOD;
				}
			}
		}
	}

	cout << dp[n][(1 << n) - 1];
	return 0;
}

Measured memory_bytes: 321792
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch ChangingACharacter | diff ChangingACharacter.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address ChangingACharacter.cpp && ./a.out

/*
 
 5/19/2019
 
 5:01-
 
 */

int N,K;
string S;

void solve() {
  S[K-1]=tolower(S[K-1]);
  cout<<S<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
  cin>>N>>K>>S;
  solve();
  
  return 0;
}


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

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v),v.end()));
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	char a,b;
	cin >> a >> b;
	if (a == 'H') {
		cout << b << endl;
	}
	else {
		if (b == 'H')cout << 'D' << endl;
		else cout << 'H' << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

typedef long long ll;

ll N, X;
vector<ll> b, l, u;
vector<tuple<ll, ll, ll, ll>> v;

bool C(ll Y){
    ll sm = 0;
    ll M = Y / X;
    ll R = Y % X;
    for(int i=0; i<N; i++){
        ll a2, b2, l2, u2;
        tie(a2, b2, l2, u2) = v[i];
        if(i < N-M) sm += l2*(-b2);
        else sm += u2*(X-b2);
    }
    if(R == 0)
        return sm >= 0;

    for(int i=0; i<N; i++){
        ll a2, b2, l2, u2;
        tie(a2, b2, l2, u2) = v[i];
        ll sm2 = sm;

        if(i < N-M){
            sm2 -= l2*(-b2);
            if(R >= b2) sm2 += u2*(R-b2);
            else sm2 += l2*(R-b2);
            if(sm2 >= 0) return true;
        }
        if(i == N-M-1){
            sm += u2*(X-b2) - l2*(-b2);
        }
        if(i >= N-M){
            sm2 -= u2*(X-b2);
            if(R >= b2) sm2 += u2*(R-b2);
            else sm2 += l2*(R-b2);
            if(sm2 >= 0) return true;
        }
    }
    return false;
}

int main(){
    cin >> N >> X;
    b.resize(N);
    l.resize(N);
    u.resize(N);
    v.resize(N);

    for(int i=0; i<N; i++)
        cin >> b[i] >> l[i] >> u[i];

    bool ok = true;
    for(int i=0; i<N; i++)
        if(b[i] > 0)
            ok = false;
    if(ok){
        cout << 0 << endl;
        return 0;
    }

    for(int i=0; i<N; i++){
        v[i] = make_tuple(u[i]*X-(u[i]-l[i])*b[i], b[i], l[i], u[i]);
    }
    sort(v.begin(), v.end());

    ll ub = N*X;
    ll lb = 0;
    while(ub - lb > 1){
        ll mid = (lb + ub) / 2;
        if(C(mid)) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
    return 0;
}

Measured memory_bytes: 5760
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, j, k, n, ans = 0, l, t = 0, h = 0;
  scanf("%lld%lld%lld", &n, &k, &l);
  ll a[n];
  for(i = 0; i < n; ++i) {
    scanf("%lld", &a[i]);
    if(a[i] > t) t = a[i];
  }
  while( 1 ) {
    ll now = (t + h) / 2, sum = 0, las = -1, cnt = 0;
    for(i = 0; i < n; ++i) {
      while(cnt < k && las < n) {
        las++;
        if(a[las] <= now) ++cnt;
      }
      sum += n - las;
      if(a[i] <= now) --cnt;
    }
    if(sum >= l) t = now;
    else h = now;
    if(t - h == 1) break;
  }
  printf("%lld\n", t);
  return 0;
}


Measured memory_bytes: 4260
#include <stdio.h>

int main(){
  
  int N, X, T;
  int Batch = 0;
  scanf("%d %d %d", &N, &X, &T);

	while (N > 0){
		N -= X;
		Batch++;	
	}
  
  printf("%d", T * Batch);
  
  return 0;
}

Measured memory_bytes: 1716
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll x; cin >> x;
  cout << 9 - (x-200)/200 << endl;
  
  
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <stdio.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;

int main() {
	int k, a, b;
	cin >> k;
	cin >> a >> b;
	bool ans = false;

	for (int i = a; i <= b; i++) {
		if (i % k == 0) {
			ans = true;
			break;
		}
	}

	if (ans) {
		cout << "OK" << endl;
	}
	else {
		cout << "NG" << endl;
	}
}

Measured memory_bytes: 3064
#include <stdio.h>

int main()
{
	int deb = 100000;
	int n;
	int i;

	scanf("%d", &n);
	i = 0;
	for(i = 0; i < n; i++){
		deb *= 1.05;
		while(deb % 1000 != 0) deb++;
	}
	printf("%d\n", deb);
	return 0;
}

Measured memory_bytes: 0