akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
const ll MAX_N=10000;
ll N;
vector<ll> G[MAX_N];
bool used[MAX_N];
ll c[MAX_N],var[MAX_N],indeg[MAX_N];
typedef pair<ll,ll> P;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>N;
	REP(i,N-1){
		ll a,b;
		cin>>a>>b;
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	REP(i,N){
		cin>>c[i];
	}
	sort(c,c+N);
	priority_queue<P,vector<P>,greater<P> > pque;
	REP(i,N){
		pque.push(P(G[i].size(),i));
		indeg[i]=G[i].size();
	}
	ll inx=0;
	while(!pque.empty()){
		P p=pque.top();
		pque.pop();
		if(used[p.second])continue;
		used[p.second]=true;
		var[p.second]=c[inx++];
		for(auto e:G[p.second]){
			indeg[e]--;
			pque.push(P(indeg[e],e));
		}
	}
	ll ans=0;
	REP(i,N){
		for(auto e:G[i]){
			ans+=min(var[i],var[e]);
		}
	}
	ans/=2;
	cout<<ans<<endl;
	REP(i,N){
		if(i)cout<<' ';
		cout<<var[i];
	}
	cout<<endl;
		
}

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

const int MOD = 1000000007;

typedef long long ll;

vector<int> g[100005];

ll n,k;
ll ans=1;

void dfs(int node,int par)
{
	int left = k-1;
	if(par!=0)
		left--;
	
	for(auto i:g[node])
	{
		if(i==par)
			continue;
		if(left<=0)
		{
			ans=0;
			return;
		}
		ans*=left;
		ans = ans%MOD;
		left--;
		dfs(i,node);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin>>n>>k;
	
	for(int i=0;i<n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	ans = k;
	
	dfs(1,0);
	
	cout<<ans%MOD;
}

Measured memory_bytes: 10368
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <climits>
int main()
{
    long D,N;
    std::cin >> D >> N;
    long m=std::pow(100,D);
    if(N==100){
        N++;
    }
    std::cout << N*m << std::endl;
    return 0;
}

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

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> h(n);
    rep(i, 0, n) cin >> h[i];
    sort(h.begin(), h.end());

    int ans = h[n - 1];
    for (int i = 0; i + k - 1 < n; i++)
        ans = min(ans, h[i + k - 1] - h[i]);
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main()
{
  long long n, a, b;
  cin >> n >> a >> b;
  long long cnt = n / (a + b);
  long long ans = cnt * a;
  if (n % (a+b) >= a) ans += a;
  else ans += n % (a+b);
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
S = input()

if len(S) == 1:
    print(1)
    exit()

ans = 1
tmp1 = S[0]
tmp2 = ""

for i in range(1,len(S)):
    tmp2 += S[i]
    if tmp1 == tmp2:
        continue
    else:
        ans += 1
        tmp1 = tmp2
        tmp2 = ""

print(ans)

Measured memory_bytes: 3500
def resolve():
	n, m = map(int, input().split())
	a, b = [-1]*n, [-1]*n
	c, d = [-1]*m, [-1]*m
	ans = []
	for i in range(n):
		a[i], b[i] = map(int, input().split())
	for i in range(m):
		c[i], d[i] = map(int, input().split())
	for i in range(n):
		low_i = -1
		low_v = float('inf')
		for j in range(m):
			v = abs(a[i] - c[j]) + abs(b[i] - d[j])
			if v < low_v:
				low_v = v
				low_i = j
		ans.append(low_i+1)
	for i in ans:
		print(i)
resolve()

Measured memory_bytes: 39280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)2003;
const int MAXS = (int)2e5 + 3;
const int infint = (int)1e9 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e17;
int n, a[MAXS], b[MAXS];
int add(int a, int b)
{
	int c = a + b;
	if(c >= MOD)
		c -= MOD;
	if(c < 0)
		c += MOD;
	return c;
}
int mul(int a, int b)
{
	int c = 1LL * a * b % MOD;
	return c;
}
int pwr(int a, int b)
{
	if(b == 0)
		return 1;
	if(b == 1)
		return a;
	int c = pwr(a, b / 2);
	c = mul(c, c);
	if(b % 2)
		c = mul(c, a);
	return c;
}
int dp[2 * MAXN][2 * MAXN], fact[4 * MAXN], facrev[4 * MAXN];
int inv(int p)
{
	return pwr(p, MOD - 2);
}
int C(int n, int k)
{
	int ans = fact[n];
	ans = mul(ans, facrev[k]);
	ans = mul(ans, facrev[n - k]);
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
		dp[MAXN - a[i]][MAXN - b[i]]++;
	}
	for (int i = 0; i < 2 * MAXN; i++)
		for (int j = 0; j < 2 * MAXN; j++)
		{
			if(i)
				dp[i][j] = add(dp[i][j], dp[i - 1][j]);
			if(j)
				dp[i][j] = add(dp[i][j], dp[i][j - 1]);
		}
	
	
	fact[0] = 1;
	for (int i = 1; i < 4 * MAXN; i++)
		fact[i] = mul(fact[i - 1], i);
	facrev[4 * MAXN - 1] = inv(fact[4 * MAXN - 1]);
	for (int i = 4 * MAXN - 1; i > 0; i--)
		facrev[i - 1] = mul(facrev[i], i);
	
	int ans = 0;
	for (int i = 0; i < n; i++)
		ans = add(ans, dp[a[i] + MAXN][b[i] + MAXN]);


	for (int i = 0; i < n; i++)
		ans = add(ans, -C(2 * (a[i] + b[i]), 2 * a[i]));
	ans = mul(ans, inv(2));
	cout << ans;
}


Measured memory_bytes: 64640
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

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

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

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

const MOD: usize = 998244353;

fn add(a:usize, b:usize) -> usize {
    (a+b) % MOD
}

fn pow3(n: usize) -> usize {
    let mut ret = 1;
    for _ in 0..n {
        ret *= 3;
        ret %= MOD;
    }
    ret
}

fn mul(a: usize, b: usize) -> usize {
    (a*b) %MOD
}

fn main() {
    input!{
      n: usize,
      aa: [usize; n],
    }
    let sum: usize = aa.iter().sum();
    let mut dp = vec![vec![0; sum+1]; n+1];
    dp[0][0] = 1;

    let mut dp2 = vec![vec![0; sum+1]; n+1];
    dp2[0][0] = 1;

    for i in 0..n {
        for s in 0..sum+1 {
            dp[i+1][s] = add(dp[i+1][s], dp[i][s] * 2); // B or C
            if s+aa[i] <= sum {
                dp[i+1][s+aa[i]] = add(dp[i+1][s+aa[i]], dp[i][s]);
            }

            dp2[i+1][s] = add(dp2[i+1][s], dp2[i][s]); // B
            if s+aa[i] <= sum {
                dp2[i+1][s+aa[i]] = add(dp2[i+1][s+aa[i]], dp2[i][s]);
            }
        }
    }

    let half = (sum+1)/2;
    let mut ng = 0;
    for i in half..sum+1 {
        ng = add(ng, dp[n][i]);
    }
    if sum%2 == 0 {
        ng = add(ng, MOD - dp2[n][sum/2]);
    }
    ng = mul(ng, 3);

    let mut ans = pow3(n);
    ans = add(ans, MOD - ng);
    println!("{}", ans);
}


Measured memory_bytes: 618748
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() /4;
const ll linf = numeric_limits<ll>::max() /4;
const ull ulinf = numeric_limits<ull>::max()/4;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////

char c[4];

string dfs(int n,string s,int a){
    if(n > 3){
        if(a == 7)ret s+"=7";
        else ret "";
    }

    string r = dfs(n+1,s+"+"+c[n],a+(int)(c[n]-'0'));
    if( r != "")ret r;
    
    ret dfs(n+1,s+"-"+c[n],a-(int)(c[n]-'0'));
}
int main(){
    rep(i,0,4)cin >> c[i];
    string s = "";
    s += c[0];

    P(dfs(1,s,(int)(c[0]-'0')));
    
	return  0;
}

Measured memory_bytes: 256
n = int(input())
s = [0] * n
inc = [[] for _ in range(1100000)]
zeros = []
dec = [[] for _ in range(1100000)]

for i in range(n):
    s[i] = input()
    start = 0
    minimum = 0
    now = 0
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        minimum = min(minimum, now)
    end = now
    
    if end == 0:
        zeros.append(i)
    elif start < end:
        inc[minimum].append(i)
    else:
        minimum = minimum - end
        dec[minimum].append(i)

now = 0
for m in range(0, -1000000, -1):
    for i in inc[m]:
        for c in s[i]:
            if c == '(':now += 1
            else: now -= 1
            if now < 0:
                print("No")
                exit()
        
for i in zeros:
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        if now < 0:
            print("No")
            exit()
            
for m in range(-1000000, 1):
    for  i in dec[m]:
        for c in s[i]:
            if c == '(':now += 1
            else: now -= 1
            if now < 0:
                print("No")
                exit()
                
if now != 0:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 284560
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define repi(i, a, b) for (int i = (a); i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ull << (b))

using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
using pii = pair<i32, i32>;
using vi32 = vector<i32>;
using vu32 = vector<u32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf64 = vector<f64>;
using vf80 = vector<f80>;
using vstr = vector<string>;
using vpii = vector<pii>;
using vvi32 = vector<vi32>;
using vvu32 = vector<vu32>;
using vvi64 = vector<vi64>;
using vvu64 = vector<vu64>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;

template<typename T, typename S> bool amax(T &x, S y) { if (x < y) { x = y; return 1; } return 0; }
template<typename T, typename S> bool amin(T &x, S y) { if (y < x) { x = y; return 1; } return 0; }

i64 calc_sum(i64 n, i64 b) {
  i64 sum = 0;
  while (n) {
    sum += n % b;
    n /= b;
  }
  return sum;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  cerr << fixed << setprecision(16);
  i64 n, s;
  cin >> n >> s;
  if (n == s) {
    cout << n + 1 << endl;
    return 0;
  }
  for (i64 b = 2; b * b <= n; b++) {
    if (calc_sum(n, b) == s) {
      cout << b << endl;
      return 0;
    }
  }
  for (i64 p = (i64) sqrt(n); p >= 1; p--) {
    i64 b = (n - s) / p + 1;
    if (b <= 1) continue;
    if (calc_sum(n, b) == s) {
      cout << b << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
import heapq
n,q = map(int,input().split())
Q = [[] for i in range(n)]
for i in range(q):
    a = input().split()
    t = int(a[1])
    if a[0] == "0":heapq.heappush(Q[t],-int(a[2]))
    elif a[0] == "1" and Q[t]: print(-Q[t][0])
    elif a[0] == "2" and Q[t]: heapq.heappop(Q[t])


Measured memory_bytes: 13180
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
using namespace std;
int main(){
    long long n,m,maxl=1,minr=100000;
    cin>>n>>m;
    long long l[m],r[m];
    f(i,0,m){
        cin>>l[i]>>r[i];
        if(l[i]>maxl){
            maxl=l[i];
        }
        if(r[i]<minr){
            minr=r[i];
        }
    }
    if(minr>=maxl){
        cout<<minr-maxl+1<<endl;
    }
    else{
        cout<<0<<endl;
    }
    return 0;
}


Measured memory_bytes: 5156
n = int(input())
num_list = list(map(int, input().split()))

even_list = [i for i in num_list if i % 2 == 0]

approved = True

for j in even_list:
    if (j % 3 != 0) and (j % 5 != 0):
        approved = False

if approved:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;

int main(){
  int h,w; cin >> h >> w;
  char cell[h][w];
  rep(i,h){
    rep(j,w){
      cin >> cell[i][j];
    }
  }

  rep(i,h){
    rep(j,w){
      if(cell[i][j]=='.') continue;
      bool ok = false;
      if(i!=0&&cell[i-1][j]=='#') ok=true;
      if(i!=h-1&&cell[i+1][j]=='#') ok=true;
      if(j!=0&&cell[i][j-1]=='#') ok=true;
      if(j!=w-1&&cell[i][j+1]=='#') ok=true;

      if(!ok){
        puts("No");
        return 0;
      }
    }
  }

  puts("Yes");
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void){
  int a, b;
  int i;
  scanf("%d %d", &a, &b);
  if(a==b){
    for (i = 0; i < b;i++){
      printf("%d", a);
    }
    printf("\n");
  }else if(a>b){
    for (i = 0; i < a;i++){
      printf("%d", b);
    }
    printf("\n");
  }else{
    for (i = 0; i < b;i++){
      printf("%d", a);
    }
    printf("\n");
  }


  return 0;
}

Measured memory_bytes: 128
use std::io;
use std::collections::VecDeque;

fn main() {
    let mut input = Input::new();
    let n: usize = input.next();
    let mut p: Vec<usize> = vec![0;n];
    let mut a: Vec<i64> = vec![0;n];
    let mut b: Vec<i64> = vec![0;n];
    for i in 0..n {
        p[i] = input.next::<usize>() - 1;
        a[i] = 30000 * (i + 1) as i64;
        b[i] = 30000 * (n - i) as i64;
    }
    for i in 0..n {
        a[p[i]] += i as i64;
        b[p[i]] += i as i64;
    }
    for i in 0..n {
        print!("{} ", a[i]);
    }
    println!("");
    for i in 0..n {
        print!("{} ", b[i]);
    }
    println!("");
}

struct Input {
    queue: VecDeque<String>,
}

impl Input {
    fn new() -> Input {
        Input { queue: VecDeque::new() }
    }

    fn next<T>(&mut self) -> T
        where T: std::str::FromStr,
              T::Err: std::fmt::Debug
    {
        if self.queue.is_empty() {
            let mut line = String::new();
            let _ = io::stdin().read_line(&mut line);
            for x in line.split_whitespace() {
                self.queue.push_back(String::from(x));
            }
        }
        return self.queue.pop_front().unwrap().parse::<T>().unwrap();
    }
}



Measured memory_bytes: 6780
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<tuple<ll, ll, ll>> tup(N);
    for (int i = 0; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        tup[i] = make_tuple(a + b, a, b);
    }
    sort(tup.begin(), tup.end(), greater<tuple<ll, ll, ll>>());
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            ans += get<1>(tup[i]);
        } else {
            ans -= get<2>(tup[i]);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<string>

int main(){
	int a, b;
	std::string s, t,u;

	std::cin>>s>>t>>a>>b>>u;

	if (s == u) {
		a = a - 1;
	}

	if (t == u) {
		b = b - 1;
	}



	std::cout << a << std::endl;
	std::cout << b << std::endl;
	return 0;
}

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

int n;

int main()
{
	cin >> n;
	if (n == 0) printf("0\n");
	else {
		string res;
		while (n) {
			int got = bool(n % (-2));
			res += string(1, '0' + got);
			n -= bool(got); n /= -2;
		}
		reverse(res.begin(), res.end());
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 256
s = str(input())
t = str(input())


# 全探索
k = len(t)
li = []
for i in range(len(s) - len(t) + 1):
    # print(i)
    tmp = k
    for l in range( k ):
        if t[l] == s[i+l]:
            tmp -= 1
    li.append(tmp)
print(min(li))
     

Measured memory_bytes: 8960
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
sys.setrecursionlimit(1000000)


def solve(stns, idx, mem):

    if idx >= len(stns) -1:
        return 0

    if idx in mem: 
        return mem[idx]

    if idx == len(stns) - 2: 
        #cant take more than one step
        final_step = abs(stns[idx] - stns[idx+1])
        mem[idx] = final_step
        return final_step
    else: 
        # step: i + 11
        step1 = solve(stns, idx + 1, mem) + abs(stns[idx] - stns[idx+1])
        # step: i + 2
        step2 = solve(stns, idx + 2, mem) + abs(stns[idx] - stns[idx+2])

        min_cost = min(step1, step2)
        mem[idx] = min_cost 

        return min_cost



def take_input():
    n = input()
    stns = [int(x) for x in input().split()]
    mem = {}
    res = solve(stns, 0, mem)
    print(res)

take_input()

Measured memory_bytes: 109696
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int q;
    string s,t;
    cin>>q;
    vector<int> v;
    while(q--){
    	cin>>s>>t;
    	int n=s.length(),m=t.length();
    	int dp[n+1][m+1];
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    			if(s[i-1]==t[j-1])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
    		}
    	}
    	v.pb(dp[n][m]);
    }
    for(auto& i:v){
    	cout << i<<endl;
    }
    return 0;
}



Measured memory_bytes: 7088
MOD = (10 ** 9) + 7
n, k  = map(int, input().split())
a = list(map(int, input().split()))

negs = [-x for x in a if x < 0]
non_negs = [x for x in a if x >= 0]

if len(non_negs) == 0 and k % 2 == 1:
    negs.sort()
    ans = 1
    for i in range(k):
        ans = ans * -negs[i] % MOD
    print(ans)
    exit()

negs_p, non_negs_p = 0, 0

negs.sort(reverse = True)
non_negs.sort(reverse = True)

for i in range(k):
    if negs_p == len(negs):
        non_negs_p += 1
    elif non_negs_p == len(non_negs):
        negs_p += 1
    elif negs[negs_p] > non_negs[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1

if negs_p % 2 == 0 or k == n:
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()

if negs_p == len(negs) or non_negs_p == 0:
    negs_p -= 1
    non_negs_p += 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()

if non_negs_p == len(non_negs) or negs_p == 0:
    negs_p += 1
    non_negs_p -= 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()


a = negs[negs_p - 1]
b = negs[negs_p]
c = non_negs[non_negs_p - 1]
d = non_negs[non_negs_p]

if a * b > c * d:
    negs_p += 1
    non_negs_p -= 1
else:
    negs_p -= 1
    non_negs_p += 1

ans = 1
for i in range(negs_p):
    ans = ans * -negs[i] % MOD
for i in range(non_negs_p):
    ans = ans * non_negs[i] % MOD
print(ans)


Measured memory_bytes: 31864
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
const ll mod = ll(1e9) + 7;
const int INF = int(1e9);
int main()
{

    ld W, H;
    cin >> W >> H;
    ld x, y;
    cin >> x >> y;
    cout << W / 2 * H << " ";
    if (x == W / 2 && y == H / 2)
    {
        cout << 1 << endl;
    }
    else
        cout << 0 << endl;
    return 0;
}


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

int main(){
  int n = 0;
  cin >> n;
  for(int i = 1; i < n + 1; i++){
    if(i % 3 == 0){
      cout << " " << i;
    }  
    else{
      int x = i;
      while(x > 0){
        if(x % 10 == 3){
          cout << " " << i;
          break;
        }
        x /= 10;
      }
    }
  }
  cout << endl;
}


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

using namespace std;

#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define FOR(i,m,n) for(int i=(m) ; i<(n) ; i++)
#define FORR(i,m,n) for(int i=(m) ; i>=(n) ; i--)

#define All(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;

int main(){
   int a,b,c,d;
   cin >>a >>b >>c >> d;
   if(b < c || d < a){
      cout << 0 <<endl;
   }else{
      vector<int> n(4);
      n[0] = a;n[1] = b;n[2] = c;n[3] = d;
      sort(All(n));
      cout << n[2] - n[1] << endl;
   }
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll      = long long;
const int mod = 1000000007;
int main() {
    ll n, r = 0, s = 0, t = 0;
    cin >> n;
    vector<ll> a(n), b(n);
    for (ll& i : a) cin >> i, (s += i) %= mod;
    for (int i = 0; i < n; ++i) (r += a[i] * s % mod) %= mod;
    for (int i = 0; i < n; ++i) (t += a[i] * a[i] % mod) %= mod;
    cout << ((r - t + mod) % mod * 500000004) % mod;
}

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

 int main(){
  long int n, i;
  int k;
  cin>>n>>k;
  long arr[n];
  for(i=0; i<n; i++)
    cin>>arr[i];
  sort(arr, arr+n);

  for(i=0; i<n; i++){
    if(arr[i]>=k)
      break;
  }
  cout<<n-i<<endl;
  return 0;
 }


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

int main(){
	ios::sync_with_stdio(false);

	string s, t;
	cin >> s >> t;
	string p;
	while(p.size() < s.size() + t.size()){
		p += t;
	}
	int n = p.size();
	vector<int> mp(n + 1, -1);
	int j = -1;
	for(int i = 0; i < n; ++i){
		while(j >= 0 && p[i] != p[j]){ j = mp[j]; }
		mp[i + 1] = ++j;
	}
	string u;
	while(u.size() < s.size() + t.size() * 2){
		u += s;
	}
	int cur = 0, mx = 0;
	for(char c : u){
		while(cur == n || (cur >= 0 && p[cur] != c)){ cur = mp[cur]; }
		++cur;
		mx = max(mx, cur);
	}
	int ans;
	if(mx >= (int)(s.size() + t.size())){ ans = -1; }
	else{ ans = mx / t.size(); }
	cout << ans << endl;
}


Measured memory_bytes: 11464
def main():
    _, m = map(int, input().split())
    cities = [[i] + list(map(int, input().split())) for i in range(m)]
    cities = sorted(cities, key=lambda x: x[2])
    orders = {}
    ids = ['' for _ in range(m)]
    for c in cities:
        p = c[1]
        if p in orders:
            orders[p] += 1
        else:
            orders[p] = 1
        ids[c[0]] = '{0:06d}{1:06d}'.format(p, orders[p])
    [print(i) for i in ids]


main()


Measured memory_bytes: 38752
def main():
    origin = list(input())
    goal = list(input())
    flg = 0
    for i in range(len(origin)):
        pre = origin[:i]
        aft = origin[i:]
        now_data = aft + pre
        if now_data == goal:
            flg = 1
            break


    if flg:
        print('Yes')
    else:
        print('No')




if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
import java.util.Scanner;


public class Main {
	public static void main(String args[]){
		Scanner input = new Scanner(System.in);
		while(input.hasNext()){
			String[] st = input.nextLine().split(",");
			int sum = 0;
			int as = Integer.parseInt(st[10]);
			int bs = Integer.parseInt(st[11]);
			for(int i = 0 ; i < 10 ; i++){
				sum += Integer.parseInt(st[i]);
			}
			double t = (double)sum / (as+bs);
			int sc = (int)Math.round(t*as);
			int nsum = 0;
			for(int i = 0 ; i < 10 ; i++){
				nsum += Integer.parseInt(st[i]);
				if(sc <= nsum){
					System.out.println(i+1);
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 17220
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        int x = scanner.nextInt();
        int cnt=0;

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

        System.out.println(cnt);
    }
}

Measured memory_bytes: 35600
import itertools

l = int(input())
a = [int(input()) for _ in range(l)]

e_cs = [int(not (v % 2)) for v in a]
o_cs = [2 if v == 0 else v % 2 for v in a]

cs = [0] + list(itertools.accumulate(a))
cost = [a, o_cs, e_cs, o_cs, a]

# dp = [[None] * 5 for _ in range(l + 1)]
# def dfs(i=0, t=0):
#     if dp[i][t] is not None:
#         return dp[i][t]
#
#     if i == l:
#         dp[i][t] = 0
#         return 0
#     if t == 4:
#         dp[i][t] = cs[l] - cs[i]
#         return dp[i][t]
#     dp[i][t] = min(dfs(i + 1, t) + cost[t][i], dfs(i, t + 1))
#     return dp[i][t]

dp = [[None] * 5 for _ in range(l + 1)]
dp[l] = [0] * 5

for i in reversed(range(l)):
    for t in reversed(range(5)):
        if t == 4:
            dp[i][t] = cs[l] - cs[i]
            continue
        dp[i][t] = min(dp[i + 1][t] + cost[t][i], dp[i][t + 1])

print(dp[0][0])


Measured memory_bytes: 72588
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("Ofast")
#include <cstdio>

constexpr int MOD = 1e9 + 7;

constexpr long long exp(const int &a, const int &b) {
  // Calculate a ** b by binary exponentation
  long long ret  = 1;
  long long base = a;
  int exponent   = b;

  while (exponent) {
    if (exponent & 1) {
      ret *= base;
      ret %= MOD;
    }
    base *= base;
    base %= MOD;
    exponent >>= 1;
  }

  return ret;
}

constexpr long long binomial(const int &n, const int &r) {
  // Calculate binomial(n, r)
  //
  // to do this, we need to calculate these values:
  //  - n * (n-1) * (n-2) * ... * (n-r+1)
  //  - 1/r! (inverse of the r factorial)
  //
  // Calculate n * (n-1) * (n-2) * ... * (n-r+1) using for loop
  long long prod_r = 1;

  for (int i = n - r + 1; i <= n; i++) {
    prod_r *= i;
    prod_r %= MOD;
  }

  // Calculate a! using for loop
  long long r_factorial = 1;

  for (int i = 1; i <= r; i++) {
    r_factorial *= i;
    r_factorial %= MOD;
  }

  // Calculate 1/a! by Fermat's little theorem
  //
  // Fermat's little theorem:
  //   x^(p-2) = 1/x (mod p)
  constexpr int exponent    = MOD - 2;
  long long inv_r_factorial = exp(r_factorial, exponent);

  // Return binomial(n, a)
  return (prod_r * inv_r_factorial) % MOD;
}

int main() {
  // Input
  int n, a, b;
  scanf("%d%d%d", &n, &a, &b);

  // Want to calculate 2 ** n - binomial(n, a) - binomial(n, b) - 1
  //
  // Calculate 2 ** n
  long long two_to_the_n = exp(2, n);

  // Calculate binomial(n, a), binomial(n, b)
  long long binomial_n_a = binomial(n, a);
  long long binomial_n_b = binomial(n, b);

  // Output
  long long ans = (two_to_the_n - binomial_n_a - binomial_n_b - 1) % MOD;

  printf("%lld\n", ans < 0 ? ans + MOD : ans);
}

Measured memory_bytes: 1736
// inputに入力データ全体が入る
function Main(input) {
    input = input.trim();
    input = input.split("\n");
    var N = parseInt(input[0].split(" ")[0],10);
    var K = parseInt(input[0].split(" ")[1],10);
    var S = input[1];

    var SK = S.slice(K-1,K).toLowerCase();
    var output;

    if(N == 1){
        output = SK;
    }
    else if(K == 1){
        var Safter = S.slice(K);
        output = SK + Safter;
    }
    else if(K == N){
        var Sbefore = S.slice(0,K-1);
        output = Sbefore + SK;
    }
    else{
        var Sbefore = S.slice(0,K-1);
        var Safter = S.slice(K);
        output = Sbefore + SK + Safter;
    }
    console.log(output);
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include <stdio.h>

#define MAX 10000
#define INF (1000000001)

#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[MAX*100][3];
int d[MAX], color;
int count;

void diks() {
    int i;
    int v, u;

    d[0] = 0;
    color = GRAY;
    while (color != BLACK) {
        color= BLACK;
        for (v = 0; v < count; v++) {
            if (d[M[v][1]] > d[M[v][0]] + M[v][2]) {
                d[M[v][1]] = d[M[v][0]] + M[v][2];
                color = GRAY;
            }
        }
    }

    for (i = 0; i < n; i++) {
        printf("%d %d\n", i, (d[i] == INF) ? (-1) : d[i]);
    }
}

int main() {
    int i, j;
    int k, c, u, v;

    scanf("%d", &n);

    count = 0;
    for (i = 0; i < n; i++) {
        d[i] = INF;
        scanf("%d %d", &u, &k);
        for (j = 0; j < k; j++) {
            scanf("%d %d", &M[count][1], &M[count][2]);
            M[count][0] = u;
            count++;
        }
    }

    diks();

    return 0;
}


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

int N, K;

int main() {
  cin >> N >> K;
  int dmax = N - K + 1;
  int dmin = 1;
  if (K == 1) dmin = dmax;
  cout << dmax - dmin << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  int answer=0;
  for(int i=0;i<n;i++)
  {
  	cin>>a[i];
    while(a[i]%2==0)
    {
      answer++;
      a[i]/=2;
    }
  }
  cout<<answer;
 return 0; 
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
#define N 53
#define mod 1000000007
int dp[N][N*4][N],fr[N],ifr[N],n;
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
int main()
{
	scanf("%d",&n);
	fr[0]=ifr[0]=1;for(int i=1;i<=n;i++)fr[i]=1ll*fr[i-1]*i%mod,ifr[i]=pw(fr[i],mod-2);
	for(int i=n+1;i>=1;i--)dp[i][n][0]=1;
	for(int i=n;i>=0;i--)
	for(int j=0;j<=n*2;j++)
	for(int k=0;k<=n;k++)
	if(dp[i+1][j][k])
	{
		int st=(j-n)*2;
		if(st>n-k+1||st+n-k-1<0)continue;
		for(int s=0;s<=n-k;s++)
		for(int t=0;s+t<=n-k;t++)
		if(s+t)
		{
			int ns=n+st+s-t,nk=k+s+t;
			if(ns<0||ns>n*2)continue;
			if(j<n&&s<n-j)continue;
			if(j>n&&t<j-n)continue;
			if(!i&&s+t>1)continue;
			dp[i][ns][nk]=(dp[i][ns][nk]+1ll*dp[i+1][j][k]*ifr[s]%mod*ifr[t])%mod;
		}
	}
	printf("%d\n",1ll*dp[0][n+1][n]*fr[n]%mod);
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define intt long unsigned int
#define pb push_back
#define ff first
#define ss second
int mod =1000000007;

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	intt k;cin>>k;
	string str;cin>>str;
	intt i=0;
	if(str.size()<=k)
		cout << str <<"\n";
	else
	{
		//intt dot=str.size()-k;
		str.erase(str.begin()+k,str.end());
		cout <<str;
		for(intt j=0;j<3;j++)
			cout <<".";
	}

}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define INF 9223372036854775807
const ll mod=998244353;



int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i=0;i<n;i++)
        cin>>a[i];
    vector<ll> ans(n),pref(n),suff(n);
    pref[0]=a[0];
    suff[n-1]=a[n-1];
    for(ll i=1;i<n;i++)
        pref[i]=a[i]^pref[i-1];
    for(ll i=n-2;i>=0;i--)
        suff[i]=a[i]^suff[i+1];
    cout<<suff[1]<<" ";
    for(ll i=1;i<n-1;i++)
        cout<<(pref[i-1]^suff[i+1])<<" ";
    cout<<pref[n-2];

    return 0;
}


Measured memory_bytes: 9504
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll k, a, b;

int main() {
	cin >> k >> a >> b;
	if (b / k * k >= a) {
		cout << "OK" << endl;
	}
	else {
		cout << "NG" << endl;
	}
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

ll n, a, ans, M=1e9+7, c[65][2];
int main() {
	ll j, t;
	cin >> n;
	while(n--) {
		scanf("%lld", &a);
		for(j=0; j<60; j++) c[j][a>>j & 1]++;
	}
	for(j=0; j<60; j++) {
		t = (1LL<<j) % M;
		t = t * c[j][0] % M;
		t = t * c[j][1] % M;
		ans = (ans + t) % M;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();  //文字列S
		int sCount = 0;  //Sの文字数カウント変数

		sCount = s.length();

		//文字数分for文を回してxを表示
		for(int i=1 ; i<=sCount ; i++) {
			System.out.print("x");
		}
		sc.close();
	}
}

Measured memory_bytes: 23252
///
// File:  b.cpp
// Author: ymiyamoto
//
// Created on Sun Jan  7 21:15:48 2018
//

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

int32_t main()
{
  uint32_t N;
  cin >> N;

  vector<int32_t> mochi(N);
  for (uint32_t i = 0; i < N; i++) {
    cin >> mochi[i];
  }

  sort(mochi.begin(), mochi.end());
  int32_t dia = -1;
  int32_t count = 0;
  for (uint32_t i = 0; i < mochi.size(); i++) {
    if (dia != mochi[i]) {
      dia = mochi[i];
      count++;
    }
  }

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int
main(void)
{
    int m, f, r;
    while (scanf("%d %d %d", &m, &f, &r) && (m != -1 || f != -1 || r != -1))
        if (m == -1 || f == -1 || m + f < 30)
            puts("F");
        else if (m + f >= 30 && m + f < 50)
            if (r >= 50)
                puts("C");
            else
                puts("D");
        else if (m + f >= 50 && m + f < 65)
            puts("C");
        else if (m + f >= 65 && m + f < 80)
            puts("B");
        else
            puts("A");
    
    return 0;
}


Measured memory_bytes: 2104
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int64_t, int64_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int64_t sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  const int64_t dx = tx - sx;
  const int64_t dy = ty - sy;
  string result = "";
  result += string(dx, 'R') + string(dy, 'U');
  result += string(dx, 'L') + string(dy, 'D');
  result += string("D") + string(dx + 1, 'R') + string(dy + 1, 'U') + string("L");
  result += string("U") + string(dx + 1, 'L') + string(dy + 1, 'D') + string("R");
  cout << result << endl;

  return 0;
}


Measured memory_bytes: 256
/*
=============================================================

------------------Welcome To My Code-------------------------

---------Ankit Kumar || IIITBH || CSE || 2018-2022-----------

=============================================================
*/

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

#define FASTIO  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long int
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vl(p) vector<p>
#define w while
#define For(i,s,x) for(i=s;i<x;i++)
#define Fore(i,s,x) for(i=s;i<=x;i++)
#define FOR(i,x) for(i=0;i<x;i++)
#define Rof(i,s,x) for(i=s;i>=x;i--)
#define all(v) v.begin(),v.end()
#define it(r,v) for(auto r=v.begin();r!=v.end();r++)
#define pb push_back
#define in insert
#define sz size()
#define F first
#define S second
#define nl cout<<"\n"
#define pr(a) cout<<a<<" "
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define pr3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n"
#define mod 1000000007
map<ll, ll>::iterator itr;
vector<ll>::iterator it, it1;
const double PI = 3.141592653589793238;

int main()
{
	FASTIO;


        ll i,j,k,x,y,z,m,n,a,b,c,c1=0,c2=0,flag=0,sum=0;
	string s1,str;
	map<ll,ll>MAP;
	vector<ll>v;
	set<ll>s;

	cin>>str;

	n=str.size();
	cout<<str;
	if(str[n-1]=='s')
    {

        cout<<"es";
    }
    else
    {
        cout<<"s";
    }

    nl;

	

}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn 200000
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;

int fa[maxn+5],mx[maxn+5];

int main()
{
    int h,w; scanf("%d%d",&h,&w);
    set<int> s;
    set<pii> ss;
    rep(i,1,w+1) 
    {
        fa[i]=i; mx[i]=i;
        if(i==w+1) mx[i]=-inf;
        s.insert(i);
        ss.insert(mp(i-mx[i],i));
    }
    rep(i,1,h)
    {
        int l,r; scanf("%d%d",&l,&r);
        int R=-inf-11;
        while(1)
        {
            auto it=s.lower_bound(l);
            if(it!=s.end() && (*it)<=r+1)
            {
    //printf("?? %d\n",*it);
                int now=*it;
                s.erase(it);
                ss.erase(mp(now-mx[now],now));
                R=max(R,mx[now]);
            }
            else 
            {
    //printf("! %d\n",R);
                if(R!=-inf-11)
                {
                    mx[r+1]=r==w?-inf:R;
                    s.insert(r+1);
                    ss.insert(mp(r+1-mx[r+1],r+1));
    //printf("?? %d: %d\n",r+1,r+1-R);
                }
                break;
            }
        }
    //for(auto it: ss) printf("????? %d: %d\n",it.SE,it.FI);
        if(ss.begin()->SE==w+1) puts("-1");
        else printf("%d\n",ss.begin()->FI+i);
    }
    return 0;
}


Measured memory_bytes: 24040
n, x = map(int,input().split())
l_list = list(input().split())


cnt = 0
sum = 0
size = len(l_list)


for i in range(size):
  sum = sum + int(l_list[i])

  if int(sum) <= int(x):
    cnt = cnt + 1


print(cnt+1)

Measured memory_bytes: 3060
import java.util.Scanner;
 
public class Main {
	public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n, A[], cnt;
        n = sc.nextInt();
        A = new int[n];
        for (int i = 0; i < n; i++)
            A[i] = sc.nextInt();
        cnt = mergeSort(A, 0, A.length);
        for (int i = 0; i < n; i++) {
            System.out.print(A[i]);
            if (i != n - 1) System.out.print(" ");
        }
        System.out.println();
        System.out.println(cnt);
    }
	
    private static int merge (int A[], int left, int mid, int right) {
        int cnt = 0;
        int n1 = mid - left;
        int n2 = right - mid;
        int L[] = new int[n1+1];
        int R[] = new int[n2+1];
        for (int i = 0; i < n1; i++)
            L[i] = A[left + i];
        L[n1] = Integer.MAX_VALUE;
        for (int i = 0; i < n2; i++)
            R[i] = A[mid + i];
        R[n2] = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        for (int k = left; k < right; k++) {
            cnt++;
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            }
            else {
                A[k] = R[j];
                j++;
            }
        }
        return cnt;
    }
 
    private static int mergeSort(int A[], int left, int right) {
        int cnt = 0;
        if(left + 1 < right) {
            int mid = (left + right) / 2;
            cnt += mergeSort(A, left, mid);
            cnt += mergeSort(A, mid, right);
            cnt += merge(A, left, mid, right);
        }
        return cnt;
    }
 
    
}

Measured memory_bytes: 169504
n = list(map(str,input().split()))
a = b = c = d = 0
for i in range(4):
    if n[i] == '1':a += 1
    if n[i] == '7':b += 1
    if n[i] == '9':c += 1
    if n[i] == '4':d += 1
if a == 1 and b == 1 and c == 1 and d == 1:
    print('YES')
else:print('NO')

Measured memory_bytes: 3064
using System;
using System.IO;
using System.Linq;

class Program{
    static void Main(string[] args){
        var n = int.Parse(Console.ReadLine());
        var arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        var max = arr.Max();
        var count = new int[max + 1];
        for (int i = 0; i < n; i++){
            count[arr[i]]++;}
        var isMultiples = Enumerable.Repeat(true, max + 1).ToArray();
        foreach (var value in arr.Distinct()){
            for (int i = value * 2; i <= max; i += value)
                isMultiples[i] = false;}
        var answer = 0;
        for (int i = 0; i < n; i++){
            if (isMultiples[arr[i]] && count[arr[i]] == 1) answer++;}
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Console.WriteLine(answer);
        Console.Out.Flush();}}


Measured memory_bytes: 52960
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
using Pair = pair<ll,pair<int,int>>;
#define pq priority_queue<Pair, vector<Pair>, greater<Pair>> 
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
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; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



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

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

  cout << a*b/2 << endl;


}

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

signed main() {
    vector<int> fp;
    vector<int> is_prime(60001, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= 60000; ++i) {
        if (is_prime[i]) {
            for (int j = i + i; j <= 60000; j += i) {
                is_prime[j] = false;
            }
            if (i % 5 == 1) fp.push_back(i);
        }
    }

    int n;
    cin >> n;
    rep(i, n) cout << fp[i] << ' ';
    cout << endl;
}


Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int H, W; cin >> H >> W;
    vector<string> lines;

    for(int i = 0; i < H; i++){
        string l;
        cin >> l;
        lines.push_back(l);
    }

    for(string l : lines){
        cout << l << endl;
        cout << l << endl;
    }

    return 0;
}

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

using namespace std;

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

int a[100010];

int main() {
    int N;
    cin >> N;
    rep(i, N)cin >> a[i];

    int ecou = 0;
    int eecou = 0;
    rep(i, N) {
        if (a[i] % 4 == 0) {
            eecou++;
        }
        else if (a[i] % 2 == 0) {
            ecou++;
        }
    }
    if (N % 2 == 0) {
        if (ecou + eecou * 2 >= N)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    else {
        if (eecou > 0) {
            if (ecou + (eecou * 2 + 1) >= N)cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else {
            if (ecou >= N)cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 640