akhauriyash/Code-Regression huggingface dataset:
S = input().strip()

ans = [1] * len(S)

x = 0
for i in range(0, len(S), 2):
    if S[i:i+2] == 'RL' or S[i-1:i+1] == 'RL':
        ans[i] += x
        x = 0
    else:
        if S[i] == 'R':
            x += ans[i]
            ans[i] = 0

for i in range(1, len(S), 2):
    if S[i:i+2] == 'RL' or S[i-1:i+1] == 'RL':
        ans[i] += x
        x = 0
    else:
        if S[i] == 'R':
            x += ans[i]
            ans[i] = 0

for i in range(len(S)-1, -1, -2):
    if S[i:i+2] == 'RL' or S[i-1:i+1] == 'RL':
        ans[i] += x
        x = 0
    else:
        if S[i] == 'L':
            x += ans[i]
            ans[i] = 0

for i in range(len(S)-2, -1, -2):
    if S[i:i+2] == 'RL' or S[i-1:i+1] == 'RL':
        ans[i] += x
        x = 0
    else:
        if S[i] == 'L':
            x += ans[i]
            ans[i] = 0

print(' '.join(map(str, ans)))

Measured memory_bytes: 53872
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;string s;cin>>n>>s;
  s+=s[0];vector<string> m={"SS","SW","WS","WW"};
  for(int x=0;x<4;x++)
    for(int i=2;i<=n+1;i++)
      m[x]+=((m[x][i-2]=='S')^(m[x][i-1]=='S')^(s[i-1]=='o')?'S':'W');
  for(int x=0;x<4;x++){
    if(m[x][0]==m[x][n]&&m[x][1]==m[x][n+1]){
      cout<<m[x].substr(0,n)<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <set>
using namespace std;
int read()
{
	char a=getchar();int res=0,f=1;
	while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();}
	while(a>='0'&&a<='9')res=res*10+a-'0',a=getchar();
	return res*f;
}
const int inf=0x3f3f3f3f;
struct TR{
	int l,r;
	int tag,max;
}tr[300005*4];
#define ls ro<<1
#define rs ro<<1|1
void build(int ro,int lt,int rt)
{
	tr[ro].l=lt; tr[ro].r=rt;
	tr[ro].max=tr[ro].tag=0;
	if(lt==rt) return ;
	int mid=(lt+rt)>>1;
	build(ls,lt,mid); build(rs,mid+1,rt);
}
void ins(int ro,int lt,int rt,int c)
{
	if(lt>rt) return ;
	if(tr[ro].l==lt&&tr[ro].r==rt)
		tr[ro].tag+=c,tr[ro].max+=c;
	else {
		int mid=(tr[ro].l+tr[ro].r)>>1;
		if(rt<=mid) ins(ls,lt,rt,c); else if(lt>mid) ins(rs,lt,rt,c);
		else ins(ls,lt,mid,c),ins(rs,mid+1,rt,c);
		tr[ro].max=tr[ro].tag+max(tr[ls].max,tr[rs].max);
	}
}
#undef ls
#undef rs
struct P{
	int x,y;
}p[300005];
bool comy(P a,P b){return a.y<b.y;}
struct N{
	int id,v;
	N(){}
	N(int a,int b):id(a),v(b){}
}q1[300005*2],q2[300005*2];
int n,m,K,ans=0;
void work()
{
	sort(p+1,p+1+K,comy);
	int t1=0,t2=0,mid=n>>1;
	q1[++t1]=N(-1,mid); q1[++t1]=N(0,0);
	q2[++t2]=N(-1,mid+1); q2[++t2]=N(0,n);
	build(1,0,K); ins(1,0,0,n);
	for(int i=1;i<=K;i++){
		ans=max(ans,(tr[1].max+p[i].y)*2);
		if(p[i].x<=mid){
			while(t1&&p[i].x>q1[t1].v){
				ins(1,q1[t1-1].id+1,q1[t1].id,q1[t1].v-p[i].x);
				t1--;
			} q1[++t1]=N(i-1,p[i].x);
		} else{
			while(t2&&p[i].x<q2[t2].v){
				ins(1,q2[t2-1].id+1,q2[t2].id,p[i].x-q2[t2].v);
				t2--;
			} q2[++t2]=N(i-1,p[i].x);
		} q1[++t1]=N(i,0); q2[++t2]=N(i,n);
		ins(1,i,i,n-p[i].y);
	} ans=max(ans,(tr[1].max+m)*2);
}
int main()
{
	n=read(); m=read(); K=read();
	for(int i=1;i<=K;i++)
		p[i].x=read(),p[i].y=read();
	work();
	for(int i=1;i<=K;i++)
		swap(p[i].x,p[i].y);
	swap(n,m);
	work(); printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 23680
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <bitset>
#include <time.h>
#include <set>
#include <algorithm>

#define ll long long
using namespace std;

ll A[333333];
ll cumul[333333];

int main() {
    int N;
    cin>>N;
    for(int i=0;i<3*N;i++)
        cin>>A[i];
    
    sort(A,A+3*N);
    
    int curr=3*N-2;
    int ct=0;
    ll ans=0;
    while(1) {
        ans += A[curr];
        curr-=2;
        ct++;
        
        if (ct >= N)
            break;
    }
    

    
    cout << ans << endl;
    
    
    // k,k,
    
}

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

#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define TEN(n) ((ll)(1e##n))
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define let const auto
#define USE_T template <typename T>
#define USE_Ti template <typename T = int>
#define USE_TU template <typename T, typename U>

USE_Ti using duo = std::pair<T, T>;
USE_Ti using vec = std::vector<T>;
using ll = long long;
// clang-format off
USE_TU inline bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE_TU inline bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE_Ti inline T in(){T x;std::cin>>x;return x;}
USE_Ti inline vec<T> in(int n){vec<T> v;v.reserve(n);rep(i,n)v.pb(in<T>());return v;}
USE_T inline void in(T*x,int n){rep(i,n)x[i]=in<T>();}
struct IoSetup {
  IoSetup(){
    using namespace std;
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<setprecision(10);
    cerr<<setprecision(10);
  }
} iosetup;
// clang-format on
// }}}
using namespace std;
const int inf = 1001001001;
const ll infll = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

signed main() {
  ll a, b;
  cin >> a >> b;

  if (1 <= a) {
    cout << "Positive";
  } else if (a <= 0 and 0 <= b) {
    cout << "Zero";
  } else {
    if ((abs(a) - abs(b)) % 2 == 0) {
      cout << "Negative";
    } else {
      cout << "Positive";
    }
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var a, b int
	fmt.Scan(&a, &b)

	if a == 1 {
		a = 14
	}
	if b == 1 {
		b = 14
	}
	if a == b {
		fmt.Println("Draw")
		return
	}
	if a < b {
		fmt.Println("Bob")
		return
	}
	fmt.Println("Alice")
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a.size())
const int N = 1005;
int n , m , k;
string s[N];
int t[305][305];
int cnt = 0;
void putLetter(int lX , int rX , int lY , int rY , int letter)
{
	for(int i = lX; i <= rX; i++)
		for(int j = lY; j <= rY; j++)
			t[i][j] = letter;
}
void solve(int lX , int rX , int lY , int rY)
{
	if(lX > rX || lY > rY) return;
	int L = lX;
	vector<pair<int , int> > prevCoords;
	for(int i = lX; i <= rX; i++)
	{
		vector<pair<int , int> > coords;
		for(int j = lY; j <= rY; j++)
			if(s[i][j] == '#')
				coords.pb({j , s[i][j] - '#'});
		if(sz(coords))
		{
			if(sz(prevCoords))
			{
				for(int j = 0; j < sz(prevCoords); j++)
				{
					int l = j == 0 ? lY : prevCoords[j - 1].x + 1;
					int r = j + 1 == sz(prevCoords) ? rY : prevCoords[j].x;
					putLetter(L , i - 1 ,l, r  , ++cnt);
				}
				L = i;
			}
			
			prevCoords = coords;
		}
	}
	for(int j = 0; j < sz(prevCoords); j++)
	{
		int l = j == 0 ? lY : prevCoords[j - 1].x + 1;
		int r = j + 1 == sz(prevCoords) ? rY : prevCoords[j].x;
		putLetter(L , rX  , l , r  , ++cnt);
	}

}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++)
		cin >> s[i];
	
	solve(0 , n - 1 , 0 , m - 1);
	
	
	for(int i = 0; i < n; i++){for(int j = 0; j < m; j++)
		cout << t[i][j] << " ";
		cout << endl;
	}
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
#define PI 3.1415926535897932384626433832795
int MOD=1e9+7;
int powmod(int a,int l, int md){int res=1;while(l){if(l&1)res=res*a%md;l/=2;a=a*a%md;}return res;}
int binpow(int a,int l){int res=1;while(l){if(l&1)res=res*a;l/=2;a=a*a;}return res;}
typedef long long ll; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii;
#define pb push_back
int __set(int b, int i) {return b|(1<<i);} //set ith bit
int __unset(int b, int i) {return b&(~(1UL<<i));}
int __check(int b, int i) {return b&(1<<i);} //returns 0 if ith bit is 0
int mulmod(int a, int b, int md) {return ((a%md)*(b%md))%md;}
int addmod(int a, int b, int md) {return (a+b)%md;}
int submod(int a, int b, int md) {return (((a-b)%md)+md)%md;}
int divmod(int a, int b, int md) {return mulmod(a, powmod(b, md-2, md), md);} //if md is prime;
const ll inf = 0xFFFFFFFFFFFFFFFL; //very large number
priority_queue<int, vector<int>, greater<int> > pq; //for min priority_queue
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
clock_t time_p=clock();
void time()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}


signed main(void)
{
	IOS;
	int h,n; cin>>h>>n;
	vi a(n);
	int sum=0;
	for(int i = 0; i < n; i++) {
		cin>>a[i];
		sum += a[i];
	}
	if(sum >= h)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

// auto mod int
const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

// combination mod prime
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
} comb(2000005);

mint g(int r, int c) {
    return comb(r+c+2,r+1) - 1; 
}

int main() {
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    --r1; --c1;

    mint ans = g(r2,c2);
    ans -= g(r1,c2);
    ans -= g(r2,c1);
    ans += g(r1,c1);
    cout << ans.x << endl;

    return 0;
}

Measured memory_bytes: 31488
hh,n = map(int,raw_input().split(' '))
spells = [map(int, raw_input().split(' ')) for _ in range(n)]
h = {}
h[0] = 0

#h[health] = cost in points
for health in range(1, hh+1):
	for u,v in spells:
		h[health] = min(h[health] if health in h else +float('inf'), h[max(0,health - u)] + v)

print h[hh]

Measured memory_bytes: 33948
import math
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N):
  for j in range(i+1, N):
    d2 = sum([(a-b)**2 for a, b in zip(X[i],X[j])])
    if float(int(math.sqrt(d2))) == math.sqrt(d2):
      ans += 1
print(ans)




Measured memory_bytes: 38384
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define o_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main(){
		ios_base::sync_with_stdio(0);cin.tie(0);
		long double a,b;
		cin>>a>>b;
		cout<<(int)(a*b);
}

Measured memory_bytes: 3812
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
int INF = 1000000000;
int main()
{
  ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);
  int n,k;
  cin>>n>>k;
  vector<int> h(n);
  rep(i,n) cin>>h[i];
  sort(h.begin(), h.end());
  int hmin = INF;
  rep(i, n - k + 1){
    int tmp = h[i+k-1] - h[i];
    hmin = min(hmin, tmp);
  }
  cout << hmin << endl;
}

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args){
		FastScanner sc = new FastScanner(System.in);
		long n = sc.nextLong();
		long m = sc.nextLong();
		long out = 0;
		long min = 2020;
		if (m-n < 2018) {
 
			for (long i=n;i<m;i++) {
 
				for (long j=i+1;j<=m;j++) {
					min = Math.min(min, (i*j)%2019);
				}
 
			}
			out = min;
 
		}
		System.out.println(out);
 
	}
 
}
 
class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
 
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }
 
    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
 
    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
 
        return tokenizer.nextToken("\n");
    }
 
    public long nextLong() {
        return Long.parseLong(next());
    }
 
    public int nextInt() {
        return Integer.parseInt(next());
    }
 
    public double nextDouble() {
         return Double.parseDouble(next());
     }
 
    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }
 
    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    }
}

Measured memory_bytes: 22996
N,M = map(int,input().split())
es = [[] for _ in range(N)]

for i in range(M):
    a,b = map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)


from collections import deque

q = deque()
INF = float("inf")
dist = [INF] * N
dist[0] = 0
come_by = [0] * N
q.append((0,0))
while q:
    cost, curr = q.popleft()
    for nxt in es[curr]:
        if cost + 1 < dist[nxt]:
            dist[nxt] = cost+1
            come_by[nxt] = curr+1
            q.append((dist[nxt], nxt))

print("Yes")
print(*come_by[1:], sep="\n")

Measured memory_bytes: 98248
require 'prime'

Max_prime = 1000000
@prime = [false] * (Max_prime + 1)
Prime.each(Max_prime).to_a.each do |i|
    @prime[i] = true
end

def solve(table, sx, sy, max_n)
    max = 0
    cur_n = 0
    dp = 1001.times.map{[0] * 1001}
    y = sy
    l = r = sx
    if @prime[table[sy][sx]]
        dp[sy][sx] = 1
        max, cur_n = 1, table[sy][sx]
    end
    loop do
        (l..r).each do |x|
            a = table[y + 1][x + 1] if inCheck(x + 1, y + 1, table, max_n)
            b = table[y + 1][x] if inCheck(x, y + 1, table, max_n)
            c = table[y + 1][x - 1] if inCheck(x - 1, y + 1, table, max_n)
            pre = dp[y][x]
            max, cur_n = update(pre, dp, a, x + 1, y + 1, max, cur_n) if a
            max, cur_n = update(pre, dp, b, x, y + 1, max, cur_n) if b
            max, cur_n = update(pre, dp, c, x - 1, y + 1, max, cur_n) if c
        end
        l -= 1 if inCheck(l - 1, y + 1, table, max_n)
        r += 1 if inCheck(r + 1, y + 1, table, max_n)
        y += 1
        break if y >= 1000 || (l..r).to_a.all?{ |x| !inCheck(x, y, table, max_n) }
    end
    [max, cur_n]
end

def update(pre, dp, n, x, y, max, cur_n)
    if dp[y][x] < pre + 1 && @prime[n]
        dp[y][x] = pre + 1
        max, cur_n = dp[y][x], n if max < dp[y][x] || max == dp[y][x] && cur_n < n
    elsif dp[y][x] < pre && !@prime[n]
        dp[y][x] = pre
    end
    [max, cur_n]
end

def inCheck(x, y, table, n)
    0 <= x && x <= 1000 && 0 <= y && y <= 1000 &&
    table[y][x] <= n
end

def tabulate
    table = 1001.times.map{[0] * 1001}
    place = (Max_prime + 1).times.map{ [] }
    dir = [[1, 0], [0, -1], [-1, 0], [0, 1]]
    c = 0
    n = 1
    x = 500
    y = 500

    while n <= Max_prime do
        dir.each_with_index do |(dx, dy), i|
            c += 1 if i == 0
            c += 1 if i == 2
            c.times do
                table[y][x] = n
                place[n] = [x, y]
                x += dx; y += dy
                n += 1
            end
        end
    end
    [table, place]
end

table, place = tabulate
loop do
    m, n = gets.split.map(&:to_i)
    break if m == 0 && n == 0
    sx, sy = place[n]
    puts solve(table, sx, sy, m).join(' ')
end

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;


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

    string s, t, u;
    cin >> s >> t >> u;

    queue<char> a, b, c;
    rep(i, s.size()) a.push(s[i]);
    rep(i, t.size()) b.push(t[i]);
    rep(i, u.size()) c.push(u[i]);

    char p = a.front(); a.pop();
    char ans;
    while(1){
        if(p == 'a'){
            if(a.empty()){
                ans = 'A';
                break;
            }else{
                p = a.front(); a.pop();
            }
        }else if(p == 'b'){
            if(b.empty()){
                ans = 'B';
                break;
            }else{
                p = b.front(); b.pop();
            }
        }else{
            if(c.empty()){
                ans = 'C';
                break;
            }else{
                p = c.front(); c.pop();
            }
        }
    }


    cout << ans << endl;

    return 0;
}



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

buff = []
mul = 1
# for i in range(k):
	# mul *= a[i]
# last = mul
for i in range(k, n):
	if a[i] > a[i-k]:
		buff.append("Yes")
	else:
		buff.append("No")
print('\n'.join(buff))

Measured memory_bytes: 107472
N = int(input())
l = [int(i) for i in input().split() ]

counter = 0
f = False
while True :
	for i in range(len(l)) :
		if (l[i] % 2 == 0) :
			l[i] = int(l[i] / 2)
		else :
			f = True
			break;
	
	if (f == True) :
		break
	
	counter += 1

print(counter)

Measured memory_bytes: 3060
n, k = map(int, input().split()); m = 998244353; a = []
for i in range(k): a.append(list(map(int, input().split())))
b = [0]*n; b.append(1); c = [0]*n; c.append(1)
for i in range(1, n):
    d = 0
    for j in range(k): d = (d+c[n+i-a[j][0]]-c[n+i-a[j][1]-1])%m
    b.append(d); c.append(c[-1]+d)
print(b[-1]%m)

Measured memory_bytes: 31064
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#include <map>
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using Graph = vector<vector<int>>;


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
ll modinv(ll a, ll m){
    ll b = m, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if(u < 0) u += m;
    cout << u << endl;
    return u;
}


int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n){
        cin >> a[i];
    }
    ll ans = 0;
    REP(i, n){
        if(i % 2 == 0){
            if(a[i] % 2 == 1){
                ans ++ ;
            }
        }
    }
    cout << ans << endl;
}



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

int main(int argc, char const* argv[])
{
	int n;
	scanf("%d", &n);
	int *S = new int[13];
	int *H = new int[13];
	int *C = new int[13];
	int *D = new int[13];
	for(int i = 0; i < 13; i++){
			S[i] = 0;
			H[i] = 0;
			C[i] = 0;
			D[i] = 0;
	}
	for(int i = 0; i < n; i++){
			char a;
			int b;
			// scanf("%c%d", &a, &b);
			std::cin >> a >> b;
			if(a == 'S')S[b-1] = 1;
			else if(a == 'H')H[b-1] = 1;
			else if(a == 'C')C[b-1] = 1;
			else if(a == 'D')D[b-1] = 1;
	}

	for(int i = 0; i < 13; i++){
			if(S[i] == 0)printf("S %d\n", i+1);
	}
	for(int i = 0; i < 13; i++){
			if(H[i] == 0)printf("H %d\n", i+1);
	}
	for(int i = 0; i < 13; i++){
			if(C[i] == 0)printf("C %d\n", i+1);
	}
	for(int i = 0; i < 13; i++){
			if(D[i] == 0)printf("D %d\n", i+1);
	}
	return 0;
}



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

int main(){
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(a>=k){
        cout<<k<<endl;
        return 0;
    }
    int sum=0;
    sum=a;
    k-=a;
    if(b>=k){
        cout<<sum<<endl;
        return 0;
    }
    k-=b;
    sum-=k;
    cout<<sum<<endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  if (N == 1) {
    cout << 1 << endl;
  }
  
  if (N >= 2) {
    vector<uint64_t> vec = {2,1};
    for (int i = 2; i <= N; i++) {
      vec.insert(vec.end(), vec.at(i-1) + vec.at(i-2));
      if (i == N) {
        cout << vec.at(N) << endl;
      }
    }
  }
}

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

bool f(int x){
    int keta = 0;
    while (x) {
    keta++;
    x /= 10;
    }
    return keta % 2 == 1; 
}
    
int main() {
 int s;
    cin >> s;
    
    int ans = 0;
    for(int i = 1; i <= s; i++) {
     if(f(i)) ans++;
    }
    
    cout << ans;
    
    
}

Measured memory_bytes: 3616
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <sstream>
#include <iomanip>
using lint = long long;

int main()
{
    std::string s;
    std::cin >> s;

    std::string t;
    std::cin >> t;

    std::map<char, std::unordered_set<char>> smap;
    std::map<char, std::unordered_set<char>> tmap;

    for (int i = 0; i < s.size(); ++i)
    {
        char s_char = s[i];
        char t_char = t[i];

        smap[s_char].insert(t_char);
        tmap[t_char].insert(s_char);

        if (smap[s_char].size() > 1 || tmap[t_char].size() > 1)
        {
            printf("No");
            return 0;
        }
    }

    printf("Yes");

    return 0;
}


Measured memory_bytes: 776
#include <iostream>
#include <string>
#include<math.h>
using namespace std;

int main() {
	int N;
	int A[210];
	int max,min;
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> A[i];
	max = A[0];
	min = A[0];
	for (int i = 1; i < N; ++i) {
		if (max < A[i])max = A[i];
		if (min > A[i])min = A[i];
	}

	cout << max-min << endl;
}

Measured memory_bytes: 256
/***************************************************************
	File name: F.cpp
	Author: huhao
	Create time: Thu 16 Jan 2020 07:02:36 PM CST
***************************************************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define fr(i,a,b) for(int i=(a),end_##i=(b);i<=end_##i;i++)
#define fd(i,a,b) for(int i=(a),end_##i=(b);i>=end_##i;i--)
int read()
{
	int r=0,t=1,c=getchar();
	while(c<'0'||c>'9')
	{
		t=c=='-'?-1:1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=r*10+c-48;
		c=getchar();
	}
	return r*t;
}
#include<set>
#define i64 long long
const int N=200010;
int n,F[N],f[N];
i64 ans[N],a[N],b[N];
struct cmp{ int operator()(int x,int y){ return b[x]*a[y]==b[y]*a[x]?x<y:b[x]*a[y]<b[y]*a[x]; } };
std::set<int,cmp> s;
int getf(int u){ return u==f[u]?u:f[u]=getf(f[u]); }
int main()
{
	n=read();
	fr(i,2,n) F[i]=read();
	fr(i,1,n) f[i]=i;
	fr(i,1,n)
		if(read()) b[i]++;
		else a[i]++;
	fr(i,2,n) s.insert(i);
	while(!s.empty())
	{
		int u=*s.begin(),_f=getf(F[u]);
//		printf("%d %d\n",u,_f);
		f[u]=_f; s.erase(u); if(_f!=1) s.erase(_f);
		ans[_f]+=ans[u]+b[_f]*a[u]; a[_f]+=a[u]; b[_f]+=b[u]; if(_f!=1) s.insert(_f);
	}
	printf("%lld\n",ans[1]);
	return 0;
}

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

namespace abc140_c
{
    static class Program
    {
        static void Main(string[] args)
        {
            var n = Console.ReadLine().ToInteger();
            // var a = new int[n];
            var b = Console.ReadLine().ToIntArray();

            // b[i] >= Math.Max(a[i], a[i + 1]);
            var ans = b[0];
            // a[0] = b[0];
            for (int i = 0; i < b.Length; i++)
            {
                if (i + 1 < b.Length && b[i] > b[i + 1])
                {
                    // ただし、i > i + 1 の時はi + 1を入れる
                    // a[i + 1] = b[i + 1];
                    ans += b[i + 1];
                }
                else
                {
                    // 基本的にはbの値を入れる
                    // a[i + 1] = b[i];
                    ans += b[i];
                }
            }

            // Console.WriteLine($"{string.Join(" ", a)}");
            Console.WriteLine($"{ans}");
        }

        static int ToInteger(this string s)
        {
            return int.Parse(s);
        }

        static int[] ToIntArray(this string s, char separator = ' ')
        {
            return s.Split(separator).Select(m => m.ToInteger()).ToArray();
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,k;
	cin>>a>>b>>k;
	vector<int> v;
	for (int i=1;i<=min(a,b);i++)
		if (a%i==0 && b%i==0)
			v.push_back(i);
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	cout<<v[k-1]<<endl;
	return 0;
}


Measured memory_bytes: 256
using System;
using static System.Console;

namespace Main
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] day = { "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT" };
            string S = ReadLine();
            WriteLine(7 - Array.IndexOf(day, S));
        }
    }
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : (x))
#define all(x) x.begin(), x.end() // sort(all(x))
#define sz(x) (int)(x).size()
#define mp(x, y) make_pair((x), (y))

typedef long long ll;

typedef double T;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<T> vt;
typedef vector<vt> vvt;
typedef vector<pii> vpi;
typedef vector<pii> vpl;
typedef vector<vpi> graph;
typedef complex<T> Pt;
typedef pair<Pt, Pt> Line;

const ll MOD = 1000; // 998244353;
const T EPS = 1e-10;
const int INF = 1e9 + 1;

/* Mod Library */

struct Mod {
    ll x;
    Mod (ll x = 0) : x(x) {}
    Mod operator+(Mod b) { return Mod((x + b.x)%MOD); }
    Mod operator-(Mod b) { return Mod((x - b.x + MOD)%MOD); }
    Mod operator*(Mod b) { return Mod((x * b.x)%MOD); }
    Mod operator/(Mod b) { return *this * inverse(b); }
    Mod operator%(Mod b) { return Mod(x % b.x); }

    static ll euclid(ll a, ll b, ll &x, ll &y) {
        if (b) {
            ll d = euclid(b, a%b, y, x);
            y -= a/b*x;
            return d;
        }
        x = 1; 
        y = 0;
        return a;
    }
    
    Mod inverse(Mod a) {
        ll x, y, g = euclid(a.x, MOD, x, y);
        assert(g == 1);
        return Mod((x + MOD)%MOD);
    }

    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this^(e/2);
        r = r*r;
        return e&1 ? *this*r : r;
    }
};

/* Input Library */
template <typename A, typename B>
istream& operator>>(istream &in, pair<A, B> &p) {
    in >> p.first >> p.second;
    return in;
}

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

template <typename I>
istream& operator>>(istream &in, vector<I> &a) {
    trav(i, a) in >> i;
    return in;
}

template <typename I>
ostream& operator<<(ostream &out, vector<I> &a) {
    rep(i, 0, sz(a)) {
        if (i) out << " ";
        out << a[i];
    }
    return out;
}

void fast_io() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    //cout.tie(0);
    cin.exceptions(cin.failbit);
} 

/* Solution */

void solve_test() {
    int n, k;
    cin >> n >> k;
    vi p(n);
    cin >> p;

    int run = 1;
    vi in_order(n, 0);
    rep(i, 1, n) {
        if (p[i] < p[i-1]) {
            run = 1;
            continue;
        }
        ++run;
        if (run >= k) {
            in_order[i] = 1;
        }
    }

    int ans = 1, ns = in_order[k-1] - 1;
    set<int> st;
    rep(i, 0, k) {
        st.emplace(p[i]);
    }
    rep(i, k, n) {
        bool diff = p[i-k] != *st.begin();
        st.erase(p[i-k]);
        diff |= sz(st) && p[i] < *st.rbegin(); 
        st.emplace(p[i]);
        ans += diff;
        ns += diff && in_order[i];
    }
    cout << ans - max(0, ns) << endl;
}

void setup() {

}

int main() {
    setup();
    srand(time(0));
    fast_io();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve_test();
    }
}


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

int main(){
	int n,c;cin>>n>>c;
	int cnt=0;
	rep(i,c){
		int a;cin>>a;
		cnt+=a;
	}
	cout<<(cnt/(n+1))+(cnt%(n+1)>0)<<endl;
}



Measured memory_bytes: 3100
def main():
    N = int(input())
    S = []
    for _ in range(N-1):
        c,s,f = map(int,input().split())
        S.append([c,s,f])

    for i in range(N-1):
        t = S[i][1] + S[i][0]
        for j in range(i+1,N-1):
            t = max(S[j][1],-(-t//S[j][2])*S[j][2]) + S[j][0]

        print(t)

    print(0)


main()

Measured memory_bytes: 9252
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <cstdlib>
#include <cmath>

using namespace std;
typedef long long ll;

int main() {
	ll h, w;
	cin >> h >> w;
	if (h % 3 == 0 || w % 3 == 0) {
		cout << 0 << endl;
		return 0;
	}
	ll ans = h * w;
	if (h > 3)ans = min(ans, w);
	if (w > 3)ans = min(ans, h);
	
	ll ht, wt;
	ht = h / 2;
	wt = w / 3;
	ans = min(ans, (ht + h % 2)*(w - wt) - h * wt);
	ans = min(ans, h * (wt+1)-ht*(w - wt-1));
	wt = w / 2;
	ht = h / 3;
	ans = min(ans, (wt + w % 2)*(h - ht) - w * ht);
	ans = min(ans, w * (ht + 1) - wt * (h - ht - 1));
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long lli;
int main()
{
	lli x; cin >> x;
	for(lli i = -2000; i <= 2000; i++)
	{
		lli tmp = x + (i * i * i * i * i);
		for(lli j = -2000; j <= 2000; j++)
		{
			if(tmp == j * j * j * j * j)
			{
				cout << j << ' ' << i << '\n';
				return 0;
			}
		}
	}
}

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


int main() {
    int64_t x, k, d;
    cin >> x >> k >> d;

    if (x < 0) x = -x;
    int64_t res = 0;
    if (x / d >= k) {
        res =  x - k * d;
        cout << res << endl;
        return 0;
    }

    //　原点はさんでちょこまかするパタン
    int64_t restK = k - abs(x) / d;
    if (restK % 2 == 0) {
        res = abs(x - d * (k - restK));
    } else {
        res = abs(x - d * (k - restK + 1));
    }
    cout << res << endl;
    return 0;

}


Measured memory_bytes: 3564
using System;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var nd = ReadInts();
            var ans = 0;

            var list = new List<string>();
            for (int i = 0; i < nd[0]; i++)
            {
                var x = Read();
                list.Add(x);
            }

            for (int i = 0; i < nd[0]; i++)
            {
                var x1 = list[i].Split(' ');
                for (int i1 = i + 1; i1 < nd[0]; i1++)
                {
                    var x2 = list[i1].Split(' ');

                    double tmplist = 0;

                    for (int i2 = 0; i2 < nd[1]; i2++)
                    {
                        double t = (int.Parse(x1[i2]) - int.Parse(x2[i2])) * (int.Parse(x1[i2]) - int.Parse(x2[i2]));
                        tmplist += t;
                    }
                    var x = Sqrt(tmplist);
                    if (x % 1 == 0)
                    {
                        ans++;
                    }
                }

            }

            WriteLine(ans);
        }


        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        //最大公約数

        public static int Gcd(int a, int b)
        {
            if (a < b)
            {
                return Gcd(b, a);
            }
            while (b != 0)
            {
                var reminder = a % b;
                a = b;
                b = reminder;
            }
            return a;
        }

        //最小公倍数
        public static int Lcm(int a, int b)
        {
            return a * b / Gcd(a, b);
        }

        //文字数を数える
        public static int CountChar(string s, char c)
        {
            return s.Length - s.Replace(c.ToString(), "").Length;
        }
    }
}


Measured memory_bytes: 13268
import sys
import random

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def query(i):
    print(i)
    sys.stdout.flush()
    s = in_s()

    if s == 'Vacant':
        exit(0)
    elif s == 'Male':
        return 0
    elif s == 'Female':
        return 1


def main():

    N = in_n()

    min_i = 0
    max_i = N

    min_fm = query(0)
    max_fm = min_fm

    while max_i - min_i != 1:
        now_i = (min_i + max_i) // 2
        now_fm = query(now_i)

        if abs(now_i - min_i) % 2 == 0 and now_fm != min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - min_i) % 2 == 1 and now_fm == min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - max_i) % 2 == 0 and now_fm != max_fm:
            min_i = now_i
            min_fm = now_fm
        elif abs(now_i - max_i) % 2 == 1 and now_fm == max_fm:
            min_i = now_i
            min_fm = now_fm


if __name__ == '__main__':
    main()


Measured memory_bytes: 9492
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    vector<vector<ll>> c(3, vector<ll>(3));
    rep(i, 3) rep(j, 3) cin >> c[i][j];
    reps(i, 1, 3) {
        ll diff = c[0][0] - c[i][0];
        rep(j, 3) {
            if ((c[0][j] - c[i][j]) != diff) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

const int MAX_N=1<<17;

using namespace std;

int n,bit[MAX_N+1];

int sum(int i){
  int s=0;
  while(i>0){
    s+=bit[i];
    i-=i&-i;
  }
  return s;
}

void add(int i,int x){
  while(i<=n){
    bit[i]+=x;
    i+=i&-i;
  }
}

int main(void){

  int q,com,a,b;

  cin >> n >> q;
  n++;
  while(q--){
    cin >> com >> a >> b;
    if(com)cout << sum(b+1)-sum(a) << endl;
    else add(a+1,b);
  }

  return 0;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

ll MOD = 1000000007;

int main(){

  ios_base::sync_with_stdio (false);
  cin.tie(NULL);
  ll N;
  cin >> N;
  vl arr = vl(N, 0);
  vl sums = vl(N, 0);
  FOR(i, 0, N) cin >> arr[i];
  FORD(i, 0, N-1) sums[i] = (sums[i+1]+arr[i+1])%MOD;

  ll sol = 0;
  FOR(i, 0, N) sol=(sol+(arr[i]*sums[i])%MOD)%MOD;

  cout << sol << endl;
}


Measured memory_bytes: 6340
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

int main() {
  string s;
  cin>>s;
  int num_n=0,num_w=0,num_s=0,num_e=0;
  for(int i=0;i<s.size();i++){
    if(s[i]=='N') num_n++;
    else if(s[i]=='W') num_w++;
    else if(s[i]=='S') num_s++;
    else num_e++;
  }
  if((num_n>0 and num_s==0) or (num_s>0 and num_n==0)) cout<<"No"<<endl;
  else if((num_e>0 and num_w==0) or (num_w>0 and num_e==0)) cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool pp[1000005],used[1000005];
int a[200001]; 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		if(used[a[i]]==1)
			pp[a[i]]=1;
		used[a[i]]=1;
		if(pp[a[i]]==0)
			for(int j=a[i]*2;j<=1000000;j+=a[i])
				pp[j]=1;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(!pp[a[i]])
			ans++;
	cout<<ans; 
	return 0;
}


Measured memory_bytes: 6284
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
string s;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> s;
    for(int i=0;i<min((int)s.size(), n);i++) cout << s[i];
    if(n < s.size()) cout << "...";
}

Measured memory_bytes: 3652
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let a: usize = iterator.next().unwrap().parse().unwrap();
    let b: usize = iterator.next().unwrap().parse().unwrap();

    if a > b {
        return String::from("0");
    }

    if n == 1 {
        return if a != b {
            String::from("0")
        } else {
            String::from("1")
        }
    }

    return format!("{}", (n - 2) * b - (n - 2) * a + 1);
}


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

using namespace std;
typedef long long ll;

constexpr ll MOD = 998244353;

ll calc_pow(ll x, ll pow) {
    if (pow == 0) return 1;
    ll a = calc_pow(x, pow / 2);
    a = a * a % MOD;
    if (pow % 2 == 1) a *= x;
    return a % MOD;
}

ll calc_div(ll a, ll b) {
    return a * calc_pow(b, MOD - 2) % MOD;
}

vector<ll> fact;

void init_fact(int n) {
    fact = vector<ll>(n);
    fact[0] = 1;
    for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i % MOD;
}

ll calc_comb(ll n, ll r) {
    if (n < r)return 0;
    return calc_div(fact[n], fact[r] * fact[n - r] % MOD);
}

int main() {
    init_fact(250000);
    int n, m, k;
    cin >> n >> m >> k;
    ll ret = 0;
    for (int i = 0; i <= k; i++) {
        ll now = calc_comb(n - 1, i) * calc_pow(m - 1, n - 1 - i);
        ret += now % MOD, ret %= MOD;
    }
    cout << ret * m % MOD << endl;
    return 0;
}

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

const int MAX = 10; // 横
const int MAX2 = 101; // 高さ
const int MOD = 1000000007; // 今回使う余り

const bool DEBUG = false; // デバッグ表示用、提出時にfalseにするよ
int main() {
	int H, W, K;
	cin >> H >> W >> K;
	
	int64_t fib[MAX]; // あみだくじの場合、長さnはfib(n)を参照(ただしf(0)=0とする)
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2;i <= W + 1;++ i) fib[i] = fib[i - 1] + fib[i - 2]; // ここまででO(W)
	
	int64_t dp[MAX2][MAX]; // 番兵付きなので間違えないように！dp[i][j]は高さiにおける左からj番目に辿れる組み合わせ
	for (int i = 0;i <= H;++ i) for (int j = 0;j <= W + 1;++ j) dp[i][j] = 0;
	dp[0][1] = 1;
	for (int i = 1;i <= H;++ i) {
		for (int j = 1;j <= W;++ j) {
			dp[i][j] = dp[i - 1][j - 1] * fib[j - 1] * fib[W - j + 1] + dp[i - 1][j] * fib[j] * fib[W - j + 1] + dp[i - 1][j + 1] * fib[j] * fib[W - j];
			dp[i][j] %= MOD; // 忘れずに！
			if (DEBUG) cerr << dp[i][j] << " ";
		}
		if (DEBUG) cerr << endl;
	}
	cout << dp[H][K];
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

上から考えていこう
まず、高さ1の時点での1の存在は、1-2に線が引かれていない場合は1に行き、その組み合わせは2からWまでの全ての横線を引く組み合わせに等しい
そして、1-2に線が引かれていれば2に行き、その組み合わせは3からWまでの全ての横線を引く組み合わせに等しい

……a-b間における組み合わせは先に計算すると良さそうなのでまず考えてみよう
平行移動しても同じなので、b-a=xとする長さを考えてf(x)で定義しよう
まず、f(0)=0, f(1)=1なのは自明
f(2)=f(1)(引かない場合)+f(0)(引いた場合)
以下、f(n)=f(n-1)+f(n-2)と導出できるので、これはフィボナッチ数列になるね

次に、今辿っている位置がxにある時の次の組み合わせを考えよう
・x-1に移動する組み合わせ
・xに移動する組み合わせ
・x+1に移動する組み合わせ
これ以外はあり得ないので、これだけ考えれば良いね
まず、x-1に移動する場合、(x-1)-xにあみだが引かれたので、(x-2)-(x-1)とx-(x+1)にはあみだが引かれない
よって、この組み合わせは1-(x-2)間×(x+1)-W間の組み合わせ、よってf(x-1)*f(W-x+1)となる
次にxに移動する場合は(x-1)-xとx-(x+1)にはあみだが引かれないので、f(x)*f(W-x+1)となるね
最後にx+1に移動する場合はx-(x+1)にあみだが引かれ、(x-1)-xと(x+1)-(x+2)にはあみだが引かれないのでf(x-1)*f(W-x)となる

ということは、これであみだくじを1個下に動く遷移がO(W)でできたので答えはO(HW)、間に合うね
*/

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <utility>
using namespace std;

typedef long long ll;

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

int m;
int d[22][22];
void init(){
  for(int i=0;i<22;i++){
    for(int j=0;j<22;j++){
      if(i==j)d[i][j]=0;
      else d[i][j]=100000000;
    }
  }
}
void solve(){
  for(int k=0;k<m;k++){
    for(int i=0;i<m;i++){
      for(int j=0;j<m;j++){
	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }
  int ans=INT_MAX,p=0;
  for(int i=0;i<m;i++){
    int sum=0;
    for(int j=0;j<m;j++)sum+=d[i][j];
    if(ans>sum){
      ans=sum;p=i;
    }
  }
  cout<<p<<" "<<ans<<endl;
}

int main(void){
  int n;
  while(cin>>n,n){
    m=0;
    init();
    for(int i=0;i<n;i++){
      int a,b,c;
      cin>>a>>b>>c;
      d[a][b]=d[b][a]=c;
      m=max(m,max(a+1,b+1));      
    }
    solve();
  }
}

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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

template<class T> inline bool chmin(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}
vector<bool> seen;
void dfs(const Graph &G, int v){
    seen[v] = true; // vを訪問済みにする
    
    for(auto next_v: G[v]){
        if(seen[next_v]) continue; // next_vが探索済みならスルー
        dfs(G, next_v); // 再帰的に探索
    }
}

int main(){

    int n, k;
    cin >> n >> k;
    vector<int> H(n);
    for(int i = 0; i < n; i++){
        cin >> H[i];
    }
    sort(H.rbegin(), H.rend());
    ll sum = 0;
    for(int i = 0; i < n; i++){
        if(k > 0){
            k--;
        }
        else{
            sum += H[i];
        }
    }
    cout << sum << endl;
    return 0;
}

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

min = 1e9
max = -1e9
sum = 0
for i in range(len(a)):
    if a[i] > max:
        max = a[i]

    if a[i] < min:
        min = a[i]

    sum += a[i]
print(min, max, sum)


Measured memory_bytes: 6600
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main(){
    double r;
    cin >> r;
    cout << fixed;
    cout << setprecision(6);
    cout << r*r*M_PI << " " << 2*r*M_PI << endl;
    return 0;
}


Measured memory_bytes: 3264
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		long ans = 0;
		ans += (x / 11) * 2;
		x %= 11;
		for (int i = 0; x > 0; i ^= 1) {
			if (i == 0) {
				x -= 6;
			} else {
				x -= 5;
			}
			++ans;
		}
		System.out.println(ans);
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}


Measured memory_bytes: 9796
N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7

A=tuple(sorted(A))

if N % 2 == 1:
  nums=[0]
  for i in range(2,N+1,2):
    nums.append(i)
    nums.append(i)
else:
  nums=[]
  for i in range(1,N+1,2):
    nums.append(i)
    nums.append(i)
    
nums = tuple(nums)
if A != nums:
  print(0)
  exit()
  
print(2**(N//2) % mod)

Measured memory_bytes: 20584
#include<stdio.h>
int m,s;
int calc(int num,int sum,int p){
	if(num==m&&sum==s)return 1;
	if(p>9)return 0;
	return(calc(num+1,sum+p,p+1)+calc(num,sum,p+1));
}
int main(void){
	while(1){
		scanf("%d%d",&m,&s);
		if(m==0&&s==0)break;
		printf("%d\n",calc(0,0,0));
	}
return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n; string s;
	cin >> n >> s;
	vi v(n + 1);
	REP(i, n)
	{
		v[i + 1] = v[i] + (s[i] == 'W');
	}
	int ans = n;
	REP(i, n)
	{
		int tmp = 0;
		tmp += v[i];
		tmp += n - i - 1 - (v[n] - v[i + 1]);
		chmin(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
    int x, y;
    string ans = "No";
    cin >> x >> y;
    
    if (x == 2 && y == 2) {
        ans = "Yes";
    } else if (
        (x == 4 || x == 6 || x == 9 || x == 11) &&
        (y == 4 || y == 6 || y == 9 || y == 11)) {
        ans = "Yes";
    } else if (
        (x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12) &&
        (y == 1 || y == 3 || y == 5 || y == 7 || y == 8 || y == 10 || y == 12)) {
        ans = "Yes";
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256