akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 12 10:38:04 2019
D - Decayed Bridges
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
400
 点
@author: justwah
"""

import sys
read = sys.stdin.readline

n, m = map(int, read().split())
score = n * (n-1) // 2

l = reversed([list(tuple(map(int, input().split()))) for i in range(m)])

parent = [i for i in range(n+1)]
rank = [0]*(n+1)
size = [1]*(n+1)

def root(x): #recursively find root for a node
    if parent[x] == x: # if at root, return self
        return x
    else:
        parent[x] = root(parent[x])  # while searching rejoint queried node to a common parent for hierarchical tree
        return parent[x]
    
def merge(a, b):
    a = root(a)
    b = root(b)
    if rank[a] < rank[b]: # joint lower rank node to a higher rank one
        parent[a] = b
    else:
        parent[b] = a
        if rank[a] == rank[b]: # rank only change if two same rank node joined
            rank[a] +=1
    size[a] += size[b]
    size[b] = size[a]
    return

ans = [score]
for a, b in l:
    a = root(a)
    b = root(b)
    if a != b:
        score -= size[a] * size[b]    
        merge(a, b)
        ans.append(score)
    else:
        ans.append(score)

print(*reversed(ans[:-1]))


Measured memory_bytes: 30788
import collections
import itertools

N, Q = map(int, input().split())
S = input()+'0'

A = [0]*(N+1)
for i in range(1, N+1):
    if S[i] == 'C' and S[i - 1] == 'A':
        A[i] = 1
    else:
        A[i] = 0

A = list(itertools.accumulate(A))
for _ in range(Q):
    l, r = map(int, input().split())
    print(A[r-1] - A[l-1])


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

const double pi = 3.14159265358979;

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout << fixed << setprecision(20);

    double a,b;
    cin>>a>>b;
    double r = max(a,b);
    double ans = 4.0/3.0 * pi * r*r*r;
    cout << ans << endl;
    
}


Measured memory_bytes: 3280
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(int i=st,i##end=ed;i>=i##end;--i)
template<typename T>bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>T read(){
	T x=0,f=1;
	char c=getchar();
	while((c<'0')||(c>'9')){if(c=='-')f=-1;c=getchar();}
	while((c>='0')&&(c<='9'))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
#define read() read<int>()
template<typename T>void write(T x,char c){
	static char t[25];
	static int tlen;
	t[tlen=1]=c;
	if(x<0)putchar('-'),x=-x;
	do t[++tlen]=(x%10)^48;
	while(x/=10);
	while(tlen)putchar(t[tlen--]);
}
const int maxn=10005;
struct data{
	int val,id;
	bool operator < (const data &A) const {
		return val==A.val?id<A.id:val<A.val;
	}
};
int n,x[maxn],y[maxn],val[maxn*2];
data idx[maxn*2];
int idx_cnt,pl[maxn*2],pr[maxn*2];
bool mark[maxn*2];
stack<int>stk;
bool dfs(int u){
	int v=u>n?u-n:u+n;
	if(mark[u])return 1;
	else if(mark[v])return 0;
	mark[u]=1;
	stk.push(u);
	REP(i,pl[u],pr[u]){
		int t=idx[i].id;
		if(t==u)continue;
		t=t>n?t-n:t+n;
		if(!dfs(t))return 0;
	}
	return 1;
}
bool check(int k){
	memset(mark,0,sizeof(mark));
	while(!stk.empty())stk.pop();
	REP(i,1,2*n){
		pl[i]=lower_bound(idx+1,idx+1+idx_cnt,(data){val[i]-k,0})-idx;
		pr[i]=upper_bound(idx+1,idx+1+idx_cnt,(data){val[i]+k,0x3f3f3f3f})-idx-1;
	}
	REP(i,1,n){
		if(!dfs(i)){
			while(!stk.empty())mark[stk.top()]=0,stk.pop();
			if(!dfs(i+n))return 0;
			else while(!stk.empty())stk.pop();
		}else while(!stk.empty())stk.pop();
	}
	return 1;
}
int main(){
	n=read();
	REP(i,1,n){
		x[i]=read(),y[i]=read();
		val[i]=x[i],val[i+n]=y[i];
		idx[++idx_cnt]=(data){x[i],i};
		idx[++idx_cnt]=(data){y[i],i+n};
	}
	sort(idx+1,idx+1+idx_cnt);
	int l=0,h=idx[idx_cnt].val;
	while(l<=h){
		int mid=(l+h)>>1;
		if(check(mid))l=mid+1;
		else h=mid-1;
	}
	write(h+1,'\n');
	return 0;
}

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

int main(){
    ll n;
    ll point = 0;
    cin >> n;

    while (n >= 500){
        n -= 500;
        point += 1000;
    }
    while (n >= 5){
        n -= 5;
        point += 5;
    }

    cout << point << endl;
    return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	int k;
	cin >> k;
	int a[100005];
	int ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] >= k)ans++;
	}
	cout << ans;
}

Measured memory_bytes: 640
# -*- coding: utf-8 -*-

import sys
import os

for s in sys.stdin:
    H, W = map(int, s.split())
    if H == W == 0:
        break

    M = []
    for i in range(H):
        s = input().strip()
        M.append(s)

    is_loop = False
    x = 0
    y = 0
    walk = 0
    while True:
        mark = M[y][x]
        walk += 1
        if walk > H * W:
            is_loop = True
            break

        if mark == '.':
            break

        if mark == '>':
            x += 1
        elif mark == 'v':
            y += 1
        elif mark == '^':
            y -= 1
        elif mark == '<':
            x -= 1

    if is_loop:
        print('LOOP')
    else:
        print(x, y)

Measured memory_bytes: 7664
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int x = sc.nextInt();
        int[] array = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            array[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int p = sc.nextInt();
            array[p] = 1;
        }
        int a = 0;
        int b = 0;
        for (int i = 0; i < x; i++) {
            a += array[i];
        }
        for (int i = x; i < n; i++) {
            b += array[i];
        }
        
        System.out.println(Math.min(a, b));
        
    }
}


Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b + c == 17 && max({a, b, c}) == 7 && min({a, b, c}) == 5) cout << "YES";
    else cout << "NO";
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String args[]) {
       ///値を取得
       Scanner sc = new Scanner(System.in);
       int a1 = sc.nextInt();
       int a2 = sc.nextInt();
       int a3 = sc.nextInt();
       int sum = a1 + a2 + a3;
       
       //出力
       if(sum >= 22) {
           System.out.print("bust");
       } else if(sum <= 21) {
           System.out.print("win");
       }
    }
}

Measured memory_bytes: 35740
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define F first
#define S second
#define pb push_back
#define PI 3.14159265
#define sz(c) (int)c.size()
#define len(c) (int)c.length()
#define hcf(a, b) __gcd(a, b)
#define all(c) c.begin(), c.end()
#define vint vector<int>
#define vll vector<ll>
#define vpint vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define tr(container, it) \
    for (typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define fr(it, a, b) \
    for (int it = (a); it < (b); it++)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element) (find(all(container), element) != container.end())
#define maximum(a, b, c) (a > b ? (a > c ? a : c) : (b > c ? b : c))
#define minimum(a, b, c) (a < b ? (a < c ? a : c) : (b < c ? b : c))
typedef long long ll;
typedef long double ld;
typedef unsigned long long lu;
const ll mod = 1e9 + 7;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b, c;
    cin >> a >> b >> c;
    cout << c << " " << a << " " << b << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 100005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
int N;
int64 A[MAXN],B[MAXN],all,C[MAXN];
multiset<int64> S;
void Solve() {
	read(N);
	for(int i = 1 ; i <= N ; ++i) {
		read(A[i]);all += A[i];
	}
	for(int i = 1 ; i <= N ; ++i) {
		read(B[i]);all -= B[i];
		if(A[i] - B[i] >= 0) S.insert(A[i] - B[i]);
	}
	if(all < 0) {puts("-1");return;}
	int cnt = 0;
	while(!S.empty()) {
		int64 p = *S.begin();
		S.erase(S.begin());
		if(all >= p) {all -= p;++cnt;}
		else break;
	}
	out(N - cnt);enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
}


Measured memory_bytes: 6144
let N = Int(readLine()!)!
let a = readLine()!.split(separator: " ").map({Int($0)!})
let T = a[0]
let A = a[1]

let H_line = readLine()!.split(separator: " ").map({abs(T*1000 - 1000*A - Int($0)! * 6)})
print(H_line.firstIndex(of: H_line.min()!)! + 1)

Measured memory_bytes: 8368
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define all(obj) obj.begin(), obj.end()
#define dbg(x) cerr << #x << ":" << x << " "
#define dbgl(x) cerr << #x << ":" << x << "\n"
#define dbgv(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define dbgvv(vv) cerr << #vv << ":\n"; for (auto vec : vv) { for (auto e : vec) cerr << e << " "; cerr << endl; }
#define YN(f) cout << (f ? "YES" : "NO") << endl
#define Yn(f) cout << (f ? "Yes" : "No") << endl
#define yn(f) cout << (f ? "yes" : "no") << endl
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

static int MOD = 1000000007;

ll modadd(ll x, ll y) {
	ll xp = x % MOD;
	if (x < 0) x += MOD;
	ll yp = y % MOD;
	if (y < 0) y += MOD;
	return (x + y) % MOD;
}

ll modsub(ll x, ll y) {
	return modadd(x, -y);
}

ll modmul(ll x, ll y) {
	return x * y % MOD;
}

// power(mod) x^n
ll modpow(ll x, ll n) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = modmul(res, x);
		x = modmul(x, x);
		n >>= 1;
	}
	return res;
}

// inverse(mod) x^(-1)
ll inv(ll x) {
	return modpow(x, MOD - 2);
}

ll moddiv(ll x, ll y) {
	return modmul(x, inv(y));
}

// factorial(mod) n!
ll fact(ll n) {
	ll res = 1;
	while (n > 1) {
		res = modmul(res, n);
		n--;
	}
	return res;
}

// permutation(mod) nPr
ll permu(ll n, ll r) {
	if (r < 0 || n < r) return 0;
	else {
		ll res = fact(n);
		res = moddiv(res, fact(n - r));
		return res;
	}
}

// nPr(mod) (O(r))
ll mypermu(ll n, ll r) {
	if (r < 0 || n < r) return 0;
	else {
		ll res = 1;
		for (ll i = 0; i < r; i++) {
			res = modmul(res, n - i);
		}
		return res;
	}
}

// combination(mod) nCr
ll combi(ll n, ll r) {
	ll res = permu(n, r);
	res = moddiv(res, fact(r));
	return res;	
}

// nCr(mod) (O(r))
ll mycombi(ll n, ll r) {
	ll res = moddiv(permu(n, r), permu(r, r));
	return res;
}

ll sumcombi(ll r, ll c) {
	return mycombi(r + c + 2, r + 1);
}

int main () {
	ll r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
	ll ans = sumcombi(r2, c2);
	ans = modsub(ans, sumcombi(r2, c1 - 1));
	ans = modsub(ans, sumcombi(r1 - 1, c2));
	ans = modadd(ans, sumcombi(r1 - 1, c1 - 1));
	cout << ans << endl;
}

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

template <typename T> vector<T> readVector(int n) { vector<T> res(n); for (int i = 0 ; i < n ; i++) cin >> res[i]; return res; }

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

    int n;
    cin >> n;

    vector<int> mark(n+1, 0);
    //int x, y, z;

    for(int x=1; true; x++) {
        int c1 = 6*x*x;
        if(c1 > n) break;
        for(int y=x; true; y++) {
            int c2 = (x*x + 3*y*y + 2*x*y);
            if(c2 > n) break;
            for(int z=y; true; z++) {
                int sum = (x*x + y*y + z*z + x*y + x*z + y*z);
                if(sum > n) break;
                int times = 6;
                if(x == y && x == z) times = 1;
                else if(x == y || y == z || x == z) times = 3;

                mark[sum] += times;
            }
        }
    }
    for(int i=1; i<=n; i++) {
        //cout << i << " = ";
        cout << mark[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3536
#include<stdio.h>
#include<iostream>

using namespace std;

int main(){

  int i;
  int n, d, x;
  int sum=0;
  
  cin >> n;
  cin >> d >> x;

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

 
  for(i=0; i<n; i++){
    int j=0;
    while( (a[i] * j + 1) <= d){
      sum++;
      j++;
    }
  }
  
  cout << sum+x << endl;



  return 0;
}


Measured memory_bytes: 256
#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; })

const ll MOD = 998244353;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;
	vector<pll> bots;
	FOR(i,0,n) {
		ll x, d;
		cin >> x >> d;
		bots.eb(x,d);
	}
	sort(all(bots));
	
	set<ll> todo;
	vvl children(n);

	FORD(i,0,n) {
		ll x, d;
		tie(x,d) = bots[i];
		
		while (sz(todo)) {
			ll j = *begin(todo);
			if (bots[j].xx >= x+d) break;
			children[i].pb(j);
			todo.erase(begin(todo));
		}
		todo.insert(i);
	}
	
	vl dp(n);
	FORD(i,0,n) {
		dp[i] = 1;
		for (ll j: children[i]) dp[i] = dp[i] * dp[j] % MOD;
		dp[i] = (dp[i]+1) % MOD;
	}
	
	ll res = 1;
	for (ll i: todo) res = res*dp[i] % MOD;

	cout << res << endl;
}



Measured memory_bytes: 17516
const N,M=map(x->parse(Int,x),split(readline()))
const G=[Int[] for _=1:N]
const used=zeros(Int,N)
function dfs(u,d)
	used[u]=d
	for v=G[u]
		if used[v]>0||dfs(v,d+1)
			return true
		end
	end
	used[u]=0
	return false
end
function recur(ps,id)
	nxtid=Int[]
	for i=id
		if used[i]>0
			push!(nxtid,i)
			nxt=Int[]
			for v=G[i]
				if used[v]>0
					push!(nxt,v)
				end
			end
			G[i]=nxt
		end
	end
	id=nxtid
	s=t=-1
	for i=nxtid
		for v=G[i]
			if used[i]+1!=used[v]&&v!=ps
				s=i
				t=v
				break
			end
		end
		if s>=0
			break
		end
	end
	if s<0
		println(length(nxtid))
		println.(nxtid)
		exit()
	end
	for i=nxtid
		used[i]=0
	end
	used[s]=1
	dfs(t,2)
	return s,nxtid
end
function main()
	for _=1:M
		u,v=map(x->parse(Int,x),split(readline()))
		push!(G[u],v)
	end
	id=[i for i=1:N]
	ps=-1
	for i=id
		if dfs(i,1)
			ps=i
			break
		end
	end
	if ps<0
		println(-1)
		exit()
	end
	while true
		ps,id=recur(ps,id)
	end
end
main()


Measured memory_bytes: 173588
#include<iostream>
using namespace std;
int n,f,i;
main(){
	cin>>n;
	for(i=1;i<=2e6;i++){
		f=(f*10+7)%n;
		if(!f){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
	return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,a,min1=99999;
    cin>>n>>x;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        if(a<min1)min1=a;
        x-=a;
    }
   printf("%d",n+x/min1);
    return 0;
}


Measured memory_bytes: 256
import sys
mod=10**9+7
x,y=map(int,input().split())

a=(-x+2*y)//3
b=(2*x-y)//3

if a<0 or b<0:
  print(0)
  sys.exit()
  
f=[1]
for i in range(1,a+b+1):
    f.append(f[-1]*i%mod)

if a+2*b==x and 2*a+b==y:
    print(f[a+b]*pow(f[a]*f[b],mod-2,mod)%mod)
else:
    print(0)

Measured memory_bytes: 29460
import java.util.Scanner;

class Main{




	public static void main(String[] args) {





		Scanner sc = new Scanner(System.in);			//文字の入力
		long x = sc.nextLong();

		long a = x/11;
		int b = 0;
		
		
		if(x % 11 == 0){
			b = 0;
		}else if(x%11 <= 6){
			b=1;
		}else{
			b = 2;
		}
		System.out.println(a*2+b);

	}
}


class Pair implements Comparable{
	Character from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}




Measured memory_bytes: 23380
import math
N = int(input())
a = []
def so(k):
    n = True
    if k % 2 == 0 and k != 2:
      return False
    for divisor in range(2, math.floor(math.sqrt(k))+1):
      if k % divisor == 0:
        n = False
    return n
for i in range(2,55555):
  han = so(i)
  if han == True and i%5 == 1:
    a.append(i)
a = a[:N]
print(" ".join(map(str,a)))

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

int N,K;
int a[10000000];
bool Nbit[10000000][50];
int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	int countnum = 0;
	for (int i = 0; i < N; i++) {
		long long int num1 = 0;
		for (int j = i; j < N; j++) {
			num1 += a[j];
			long long int num2 = num1;
			for (int k = 0; k < 41; k++) {
				Nbit[countnum][k] = num2 % 2;
				num2 /= 2;
			}
			countnum++;
		}
	}
	long long int ans = 0;
	list<int> v;
	for (int i = 0; i < countnum; i++) {
		v.push_back(i);
	}
	int nowbit = 41;
	while (true) {
		/*
		for (auto itr = v.begin(); itr != v.end(); itr++) {
			cout << *itr << endl;
		}
		*/
		if (nowbit == -1)break;
		int count = 0;
		for (auto itr = v.begin(); itr!=v.end(); itr++) {
			count += Nbit[*itr][nowbit];
		}
		if (count >= K) {
			ans += pow(2, nowbit);
			int vsize = v.size();
			int inum = 0;
			for (list<int>::iterator itr = v.begin(); inum<vsize; itr++) {
				if (Nbit[*itr][nowbit]) {
					v.push_back(*itr);
				}
				inum++;
			}
			for (int i = 0; i < vsize; i++) {
				v.pop_front();
			}
		}
		nowbit--;
	}
	/*
	for (int i = 0; i < N; i++) {
		for(int j=30;j>=0;j--){
			cout << Nbit[i][j];
		}
		cout << endl;
	}
	*/
	cout << ans << endl;
	cin >> N;
	return 0;
}

Measured memory_bytes: 46080
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		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++){
			String cd=sc.next();
			int cn=sc.nextInt();
			switch(cd){
			case "S":
				s[cn-1]++;
				break;
			case "H":
				h[cn-1]++;
				break;
			case "C":
				c[cn-1]++;
				break;
			case "D":
				d[cn-1]++;
			}
		}
		for(int i=0;i<13;i++){
			if(s[i]==0){
				System.out.println("S "+(i+1));
			}
		}
		for(int i=0;i<13;i++){
			if(h[i]==0){
				System.out.println("H "+(i+1));
			}
		}
		for(int i=0;i<13;i++){
			if(c[i]==0){
				System.out.println("C "+(i+1));
			}
		}
		for(int i=0;i<13;i++){
			if(d[i]==0){
				System.out.println("D "+(i+1));
			}
		}
	}
}

Measured memory_bytes: 26184
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bug1( x ) {cerr << (#x) <<"="<< x << endl;}
#define bug2( x , y ) {cerr << (#x) <<"="<< (x) << "    " << (#y) << "="<< (y) << endl;}
#define bug3( x , y , z ) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << endl;}
#define bug4( x , y , z , w) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << endl;}
#define bug5( x , y , z , w ,p) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << endl;}
#define bug6( x , y , z , w ,p , q) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << "    " << (#q) <<"="<< q << endl;}
#define bugn( x , n ) {cerr << (#x) <<":";for(int i=0;i<n;i++)cerr << x[i] <<"  "; cerr << endl;}
#define bugnm( x , n , m ) {cerr << (#x)<<endl;for(int i=0;i<n;i++){cerr << "Row #" << i<< ":";for(int j=0;j<m;j++)cerr << x[i][j] << "   ";cerr << endl;}}
typedef long long ll;
typedef long double ld;
using namespace std;


const int maxn = 1e5+10;
vector<int>g[maxn],vis(maxn),clr(maxn);
int cnt[2]={0,0};
int n,m,biparite=1;
void dfs(int u,int c){
	vis[u]=1;
	clr[u]=c;
	cnt[clr[u]]++;
	for(auto v:g[u]){
		if( !vis[v]){
			dfs(v,c^1);
		}else if( clr[v] == c){
			biparite=0;
		}
	}
}
			
int32_t main(){
	IOS
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	if( ! biparite ){
		cout << ( n * ( n - 1 ) / 2 - m ) << endl;
	}else{
		cout << cnt[0] * cnt[1] - m << endl;
	}
}
/*
 * long long or int?
 * index out of bound?
 * Tested on own test case?corner?
 * Make more general solution.
 * Read Read Read Read ....
 */


Measured memory_bytes: 11888
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>

const int INF = 1000000009;
const long LINF = 1123456789012345678;

long n, p, p1;
long ans = 1;

long power(long num1, long num2){
	if(num2 == 1){
		return num1;
	}
	if(num2 % 2 == 1){
		return num1 * power(num1, (num2-1));
	}
	long r = power(num1, num2/2);
	return r*r;
}

int main(){
	scanf("%ld %ld", &n, &p);
	p1 = p;
	if(n == 1){
		printf("%ld\n", p);
		return 0;
	}
	for(long i = 2; i*i <= p; i++){
		//printf("%ld %ld\n", i*i, p);
		long cnt = 0;
		while(p1 % i == 0){
			p1 /= i;
			cnt++;
		}
		if(cnt >= n){
			ans *= power(i, cnt/n);
		}
	}
	printf("%ld\n", ans);
	return 0;
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

h,w,n = map(int,readline().split())
rc = [(1,1)]
for i in range(n):
    r,c = map(int,readline().split())
    rc.append((r,c))
rc.sort(key = lambda x: sum(x)*-1)
mod = 10**9+7

max_n = 3 * 10**5
fac, finv, inv = [0]*max_n, [0]*max_n, [0]*max_n

def comInit(max_n):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max_n):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max_n)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

dp = [0] * (n+2)
dp[0] = 1
for i in range(n+1):
    ri,ci = rc[i]
    dp[i+1] = com(h+w-ri-ci,h-ri)
    for j in range(i):
        rj,cj = rc[j]
        if(ri<=rj)&(ci<=cj):
            dp[i+1] -= com(rj+cj-ri-ci,rj-ri) * dp[j+1]
            dp[i+1] %= mod

print(dp[-1])

Measured memory_bytes: 81880
#include <bits/stdc++.h>
using namespace std;
int main() {
	int k; cin >> k;
  	string s; cin >> s;
  	for (int i = 0; i < min(k, (int) s.length()); i++) {
   		cout << s[i]; 
    }
  	if (k < s.length()) cout << "...";
}


Measured memory_bytes: 3572
sx, sy, tx, ty = map(int, input().split())
dx = tx - sx
dy = ty - sy

print("U" * dy + "R" * (dx + 1) + "D" * (dy + 1) + "L" * (dx + 1) + 
      "UL" + "U" * (dy + 1) + "R" * (dx + 1) + "D" * (dy + 1) + "L" * dx)





Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i,a,b) for(int(i)=(a);(i)<(b);++(i))
#define RREP(i,a,b) for(int(i)=(a)-1;(i)>=(b);--(i))
#define ALL(x) (x).begin(),(x).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = 1e9;

int H,W;
char s[60][60];
int d[60][60];

int main()
{
  cin >> H >> W;
  REP(x,0,H) REP(y,0,W) cin >> s[x][y];

  // 最短距離の初期化
  REP(x,0,H) REP(y,0,W) d[x][y] = INF;

  // (H-1,W-1)への最短距離を求める
  queue<P> que;
  d[0][0] = 0;
  que.push(P(0,0));
  while (!que.empty()) {
    int x,y;
    tie(x,y) = que.front(); que.pop();

    //上下左右の4方向
    for (int dx = -1; dx <= 1; ++dx) {
      for (int dy = -1; dy <= 1; ++dy) {
        if (dx * dx + dy * dy == 1) {
          int nx = x + dx;
          int ny = y + dy;
          if (0 <= nx && nx < H && 0 <= ny && ny < W &&
              s[nx][ny] == '.' && d[nx][ny] == INF) {
            d[nx][ny] = d[x][y] + 1;
            que.push(P(nx,ny));
          }
        }
      }
    }
  }
  // cout << d[H-1][W-1] << endl;

  int ans;
  if (d[H-1][W-1] == INF) ans = -1;
  else {
    int count = 0;  // .を数える
    REP(x,0,H) REP(y,0,W) {
      if (s[x][y] == '.') ++count;
    }
    // 最短経路上以外のすべてを#に変えることが可能
    ans = count - (d[H-1][W-1] + 1);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // [b,c) イテレータ
#define MOD 1000000007
#define INF 1000000000
typedef pair<int64_t, int64_t> PII;
typedef vector<int64_t> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

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

int N, M; cin >> N >> M;
VI X(M); rep(i, 0, M) cin >> X[i];
if (N >= M) {
    cout << "0\n";
    return 0;
}

sort(ALL(X));
VI diff(M-1); rep(i, 0, M-1) diff[i] = X[i+1] - X[i];
sort(ALL(diff));
cout << accumulate(RANGE(diff, 0, M - N), 0) << endl;

}
// 書いて考える
// 境界，出力文字列 チェック
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．求めたい量の変域．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり



Measured memory_bytes: 1792
number = 4
fare = [int(input()) for a in range(number)]
 
fare_added = []
fare_added.append(fare[0] + fare[2]) #A + C
fare_added.append(fare[0] + fare[3]) #A + D
fare_added.append(fare[1] + fare[2]) #B + C
fare_added.append(fare[1] + fare[3]) #B + D

for i, elem in enumerate(fare_added):
  # 初期化
  if i == 0:
    fare_min = elem
  if fare_min > elem:
    fare_min = elem

print(fare_min)

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    const ll MOD = 998244353;
    ll n, a, b, k;
    cin >> n >> a >> b >> k;
    int max_number = n;
    
    vector<ll> fac(max_number+1,1);
    vector<ll> inv(max_number+1,1);
    vector<ll> finv(max_number+1,1);
    vector<ll> nCk(max_number+1,1);
    for(i = 2;i <= max_number;++i){
        inv.at(i) = MOD - inv.at(MOD%i)*(MOD/i)%MOD;
    }
    for(i = 1;i <= max_number;++i){
        fac.at(i) = fac.at(i-1)*i%MOD;
        finv.at(i) = finv.at(i-1)*inv.at(i)%MOD;
    }
    for(i = 1;i <= max_number;++i){
        nCk.at(i) = fac.at(max_number)*finv.at(i)%MOD*finv.at(max_number-i)%MOD;
    }
    ll ans = 0;
    for(i = 0;i <= n;++i){
        ll num = k - a*i;
        if(num < 0) break;
        else{
            if(num%b == 0 && num/b <= n){
                ans += nCk.at(i)*nCk.at(num/b)%MOD;
                ans %= MOD;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 12716
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5;
int head[N],nxt[N],to[N],st[N];
int fa[N];inline int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
LL ans,sum[N],siz[N];
bool vis[N];
inline int dfs(int k) {
	int t;
	for (int i=head[k];i;i=nxt[i])
		if (!vis[to[i]]) {
			vis[to[i]]=true;
			t=dfs(to[i]);
			ans+=abs(t);
			siz[k]-=t;
		}
	return siz[k];
}
inline void get(int k) {
	for (int i=head[k];i;i=nxt[i])
		if (to[i]!=fa[k])
			fa[to[i]]=k,get(to[i]);
}
int main()
{
	int n,m,i,tot=0,a,b,A,B,top=0,t,k;cin>>n>>m;
	for (i=1;i<=n;i++) fa[i]=i,siz[i]=1;
	for (i=1;i<=m;i++) {
		cin>>a>>b;
		if (find(a)==find(b)) A=a,B=b;
		else {
			fa[fa[a]]=b;
			to[++tot]=b,nxt[tot]=head[a],head[a]=tot;
			to[++tot]=a,nxt[tot]=head[b],head[b]=tot;
		}
	}
	if (m==n-1)
		vis[1]=true,printf("%lld\n",dfs(1)?-1:ans);
	else {
		for (i=1;i<=n;i++) fa[i]=0;
		get(A);
		for (k=B;k;k=fa[k]) st[++top]=k;
		if (top&1) {
			vis[A]=true;t=dfs(A);
			for (i=1;i<=n;i++) vis[i]=false,siz[i]=1;
			if (t%2) return puts("-1"),0;
			siz[A]-=t/2,siz[B]-=t/2;
			ans=abs(t/2);
			vis[A]=true;dfs(A);
		} else {
			for (i=1;i<=top;i++) vis[st[i]]=true;
			for (i=1;i<=top;i++) sum[i]=sum[i-1]+(i&1?-1:1)*dfs(st[i]);
			if (sum[top]) return puts("-1"),0;
			sort(sum+1,sum+1+top);
			for (i=1;i<=top;i++) ans+=abs(sum[top/2]-sum[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 8448
n=int(input())
s=list(input())

a=[0]*n

for i in range(n):
    if s[i]=="o":
        a[i]=1
    else:
        a[i]=-1

ans=[0]*n

flag=-1
S=["0"]*n

ans[0]=1
ans[1]=1

for i in range(2,n):
    ans[i]=a[i-1]*ans[i-1]*ans[i-2]
else:
    c1=a[0]*ans[0]*ans[n-1]
    c2=a[n-1]*ans[n-1]*ans[n-2]
    if c1==ans[1] and c2==ans[0]:
        flag=1
        for i in range(n):
            if ans[i]==1:
                S[i]="S"
            else:
                S[i]="W"
        print(''.join(S))

if flag<0:

    ans[0]=-1
    ans[1]=1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:

    ans[0]=1
    ans[1]=-1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:

    ans[0]=-1
    ans[1]=-1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:
    print(flag)

Measured memory_bytes: 8524
// Bismillahirrahmanirrahim
// by Batrrr Tolkynbayev
#include <bits/stdc++.h>
// skripi krasava
#define respa return 0
#define all(x) x.begin(), x.end()
#define sz size
#define pb push_back
#define eb emplace_back
#define forn(i, x, n) for(int i = x; i <= n; ++i)
#define forr(i, n, x) for(int i = n; i >= x; --i)

using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 3e5 + 17, M = N << 2, mod = 1e9 + 7; 

ll tt = 1, n, c, k, t[N], ct, res, that;

void solve () {
	cin >> n >> c >> k;
	forn(i, 1, n) cin >> t[i];
	sort(t + 1, t + n + 1);
	forn(i, 1, n) {
		if (i == 1 || ct == c || that + k < t[i]) {
			that = t[i];
			ct = 0;
			++res;
		}
		++ct;
	}
	cout << res;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// cin >> tt;
	while (tt--) solve();
	respa;
}

Measured memory_bytes: 4400
// Ver19.02
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 1 << 29
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

ll collatz(ll x)
{
  if (x % 2 == 0)
  {
    return x / 2;
  }
  else
  {
    return 3 * x + 1;
  }
}

int main()
{
  ll s;
  ll a[1000001];
  scanf("%lld", &s);
  a[0] = s;
  for (int i = 1;; i++)
  {
    ll maybe = collatz(s);
    for (int j = 0; j < i; j++)
    {
      if (a[j] == maybe)
      {
        printf("%d\n", i + 1);
        return 0;
      }
    }
    a[i] = maybe;
    s = maybe;
  }
}

Measured memory_bytes: 128
package main

import "fmt"

func main() {
	var n, k int
	var s string
	fmt.Scan(&n, &s, &k)

	c := s[k-1]
	for i := 0; i < n; i++ {
		if s[i] == c {
			fmt.Print(string(c))
		} else {
			fmt.Print("*")
		}
	}
	fmt.Println()
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()

using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;

int main() {
  string A;
  cin >> A;

  string res;
  string op[2] = {"-", "+"};
  for (int tmp = 0; tmp < (1 << 3); tmp++) {
    bitset<3> s(tmp);
    int sum = 0;
    rep(i, 4) {
      if (i == 0)
        sum = (int)(A[i] - '0');
      else
        sum = (s[i - 1]) ? sum + (A[i] - '0') : sum - (A[i] - '0');
    }
    if (sum == 7) {
      rep(i, 4) {
        if (i == 0)
          res = A[i];
        else
          res += op[s[i - 1]] + A[i];
      }
      res += "=7";
      break;
    }
  }

  cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
using namespace std;



int main(){
    string s;
    int a;
    cin >> a >> s;
    if (a < 3200){
        cout << "red" << endl;
    }
    else{
        cout << s << endl;
    }
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

void Print(int pw) {
	long long x = (1LL<<pw);
	cout << x << "\n";
}

void Solve() {
	long long n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;

	for (int i = 0; i <= n-1; ++i) {
		long long pos = i;
		long long neg = n-1-i;

		if (pos * c + neg * -d <= b - a && b-a <= pos * d + neg * -c) {
			cout << "YES\n";
			return;
		}
	}

	cout << "NO\n";
}

int main() {
	int tests = 1;
	for (;tests; --tests) {
		Solve();
	}
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace At
{
    class Program
    {
        static void Main(string[] args)
        {
            var x = ReadInts();
            if (x[0] + x[1] == x[2] + x[3])
            {
                WriteLine("Balanced");
            }
            else if (x[0] + x[1] > x[2] + x[3])
            {
                WriteLine("Left");
            }
            else
            {
                WriteLine("Right");
            }

        }

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


Measured memory_bytes: 13140
import java.util.Scanner;

public class Main {

    public static void main(String[] args)  {
        //input
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] s = sc.next().toCharArray();
        char[] t = sc.next().toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length && i < t.length; i++) {
            sb.append(s[i]);
            sb.append(t[i]);
        }
        System.out.println(sb.toString());
    }
}

Measured memory_bytes: 22228
#include<bits/stdc++.h> 
using namespace std;
 
typedef long long int ll;
typedef pair<int,int> pii;

#define ff first
#define ss second
#define vi vector<int>
#define fo(n) for(int i = 0;i < int(n);i++)
#define foo(a,b) for(int i = int(a);i <= int(b);i++)
#define mk make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define fastio ios_base:: sync_with_stdio(false)


const int MAXV = 1e5;
const int mod = 1e9 + 7;
const int inf = 1e9;
const ll linf = (ll) 1e17;



int main(){	
	fastio;
	int n;
	int W;
	cin >> n >> W;

	vi wt(n), v(n);

	fo(n) cin >> wt[i] >> v[i];

	vector<ll> dp(MAXV+1,linf);
	dp[0] = 0;


	fo(n){
		for(int value = MAXV-v[i]; value >= 0; value--){
			dp[value + v[i]] = min(dp[value+v[i]], dp[value]+wt[i]); 
		}
	}

	int ans = 0;
	for(int value = MAXV; value >= 0; value--){
		if(dp[value] <= W){
			ans = value;
			break;
		}
	}

	cout << ans << endl;
	return 0;
 }	

Measured memory_bytes: 1024
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>

using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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; }
typedef pair <ll,ll> P;

int main()
{
    string S;
    cin >> S;
    map<char, ll> mp;
    rep(i, S.size()) {
        mp[S[i]] = 1;
    }
    if (mp['N'] == 1 & mp['S'] == 0) no;
    else if (mp['S'] == 1 & mp['N'] == 0) no;
    else if (mp['E'] == 1 & mp['W'] == 0) no;
    else if (mp['W'] == 1 & mp['E'] == 0) no;
    else yes;
    return 0;
}


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

int cnt[26];
int main() {
	string s, t;
	while (cin >> t)s += t;
	for (char c : s) {
		if (!isalpha(c))continue;
		if (islower(c))c = toupper(c);
		cnt[c - 'A']++;
	}
	rep(i, 26) {
		cout << (char)('a' + i) << " : " << cnt[i] << endl;
	}
}

Measured memory_bytes: 3192
N = gets.strip.to_i
P = gets.strip.split(' ').map(&:to_i)
Q = gets.strip.split(' ').map(&:to_i)
nums = []
permuted = []
N.times { |v| nums.push(v+1) }
nums.permutation(N).each do |v|
  permuted.push v
end
puts (permuted.find_index(P) - permuted.find_index(Q)).abs

Measured memory_bytes: 6908
<?php

fscanf(STDIN, "%d", $N);
for ($i = 0; $i < $N; $i++) {
    fscanf(STDIN, "%f %f %f %f %f %f %f %f", $x1, $y1, $x2, $y2, $x3, $y3, $x4, $y4);
    $abx = $x2 - $x1;
    $aby = $y2 - $y1;
    $cdx = $x4 - $x3;
    $cdy = $y4 - $y3;
    if ($abx === 0.0 || $cdx === 0.0) {
        echo $abx === $cdx ? 'YES' : 'NO';
        echo PHP_EOL;
        continue;
    }
    $ab = $aby / $abx;
    $cd = $cdy / $cdx;
    echo $ab === $cd ? 'YES' : 'NO';
    echo PHP_EOL;
}

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

#define int long long
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define fs first
#define sc second
#define mpr make_pair
#define iter iterator
#define all(X) X.begin(),X.end()
#define sau(X) sort(all(X)),X.resize(unique(all(X))-X.begin())
#define exist(X,ele) binary_search(all(X),ele)
#define y0 I_love_Ryougi_Shiki_0
#define y1 I_love_Ryougi_Shiki_1

template<typename T1,typename T2>
ostream& operator << (ostream& out,const pair<T1,T2>& X)
{
	out<<"{"<<X.fs<<","<<X.sc<<"}";
	return out;
}

template<typename T>
ostream& operator << (ostream& out,const vector<T>& X)
{
	for(auto i:X) out<<i<<" ";
	return out;
}

template<typename T>
inline void cmin(T& x,T y)
{
	if(!(x<y)) x=y;
}

template<typename T>
inline void cmax(T& x,T y)
{
	if(x<y) x=y;
}

const int inf=5000000000000000ll;

int N,M;
map<int,int> mp;
vector<int> v;
int a[100010];
vector<pii> e[100010];
bool vis[100010];
bool used[200010];

void DFS(int p)
{
//	cout<<"DFS "<<p<<endl;
	vis[p]=true;
	for(auto to:e[p])
	{
		if(!vis[to.fs])
		{
			DFS(to.fs);
			if(a[to.fs]==1)
			{
//				cout<<" use "<<to.sc<<endl;
				used[to.sc]=true;
				a[to.fs]=0;
				a[p]^=1;
			}
		}
	}
	return;
}

main()
{
	ios::sync_with_stdio(false);
	
	cin>>N>>M;
	for(int i=0;i<N;i++)
	{
		int x,y; cin>>x>>y;
		mp[x]=y;
		v.pb(x);
	}
	v.pb(-1);
	sort(all(v));
	for(int i=1;i<v.size();i++)
	{
		a[i]=mp[v[i]];
	}
	for(int i=0;i<=N;i++)
	{
		a[i]=a[i]^a[i+1];
	}
	for(int i=0;i<M;i++)
	{
		int L,R; cin>>L>>R;
		L=lower_bound(v.begin(),v.end(),L)-v.begin();
		R=upper_bound(v.begin(),v.end(),R)-v.begin()-1;
		if(L>R) continue;
//		cout<<" = L,R="<<L<<" "<<R+1<<endl;
		e[L-1].pb(mpr(R,i+1));
		e[R].pb(mpr(L-1,i+1));
	}
	for(int i=0;i<=N;i++)
	{
		if(!vis[i])
		{
			DFS(i);
			if(a[i]==1)
			{
				cout<<"-1"<<endl;
				return 0;
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=M;i++)
	{
		if(used[i]) cnt++;
	}
	cout<<cnt<<endl;
	for(int i=1;i<=M;i++)
	{
		if(used[i]) cout<<i<<" ";
	}
	cout<<endl;
	
	return 0;
}






















Measured memory_bytes: 24948
N = int(input())
abc = [[int(_) for _ in input().split()] for i in range(N - 1)]
Q, K = [int(_) for _ in input().split()]
xy = [[int(_) for _ in input().split()] for i in range(Q)]

from collections import defaultdict
from heapq import *

V = list(range(1, N + 1))
E = defaultdict(lambda:{})
for a, b, c in abc:
    E[a][b] = c
    E[b][a] = c

def Dijkstra(s, V, E):
    # https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
    d = defaultdict(lambda:10**20)
    prev = defaultdict(lambda:None)
    d[s] = 0
    Q = []
    for v in V:
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heappush(Q, (alt, v))
    return d, prev

d, prev = Dijkstra(K, V, E)

for x, y in xy:
    print(d[x] + d[y])


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

int main(){
    int c;
    int sum = 0;
    cin >> c;
    
    sum += c / 100;
    c = c - c / 100 * 100;
    sum += c / 10;
    c = c - c / 10 * 10;
    sum += c;
    
    cout << sum << endl;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
#include<boost/math/common_factor.hpp>

namespace adaptor = boost::adaptors;

boost::optional<int> check(int n, int N, std::vector<std::vector<int>>const& child, std::vector<int>const& weight)//�����̐F�łȂ����̏d���̍��v
{
	int sum = 0;
	std::set<int> dp = { 0 };
	for (auto c : child[n])
	{
		auto v = check(c, N, child, weight);
		if (!v)
		{
			return boost::none;
		}
		sum += *v + weight[c];
		std::set<int> next;
		for (auto d : dp)
		{
			next.emplace(d + *v);
			next.emplace(d + weight[c]);
		}
		std::swap(next, dp);
	}
	if (*std::begin(dp) > weight[n])
	{
		return boost::none;
	}
	auto my_weight = weight[n] - *std::prev(boost::range::upper_bound(dp, weight[n]));
	sum += my_weight;
	return sum - weight[n];
}
void Main()
{
	int N;
	std::cin >> N;
	std::vector<std::vector<int>> child(N);
	std::vector<int> weight(N);
	for (int i : boost::irange(1, N))
	{
		int c;
		std::cin >> c;
		child[c - 1].emplace_back(i);
	}
	for (auto& w : weight)
	{
		std::cin >> w;
	}
	if (check(0, N, child, weight))
	{
		std::cout << "POSSIBLE" << std::endl;
	}
	else
	{
		std::cout << "IMPOSSIBLE" << std::endl;
	}
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


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

vector<int> par(100010);

int root(int x)
{
    if (par[x] == x)
        return x;
    else
        return par[x] = root(par[x]);
}

void unite(int x, int y)
{
    x = root(x);
    y = root(y);
    if (x == y)
        return;
    par[x] = y;
}

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

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

    return 0;
}

Measured memory_bytes: 640
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    p = LIR(m)
    d = defaultdict(lambda : -1)
    for i,j in p:
        i -= 1
        if d[i] >= 0 and d[i] != j:
            print(-1)
            return
        d[i] = j
    ans = ""
    for i in range(n):
        if i == 0:
            if d[i] < 0:
                if n == 1:
                    ans += "0"
                else:
                    ans += "1"
            else:
                if d[i] == 0:
                    if n == 1:
                        print(0)
                        return
                    print(-1)
                    return
                ans += str(d[i])
        else:
            if d[i] < 0:
                ans += "0"
            else:
                ans += str(d[i])
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


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

set<int> um;
vector<int> ok;

int main() {	
	int n;
	scanf("%d",&n);
	while(n--) {
		int a;
		scanf("%d",&a);
		if(um.count(a)) {
			um.erase(a);
			ok.push_back(a);
		} else
			um.insert(a);
	}
	sort(ok.rbegin(),ok.rend());
	if(ok.size() < 2) printf("0\n");
	else printf("%lld\n",1LL * ok[0] * ok[1]);
}

Measured memory_bytes: 4992
A, B = map(int, input().split())
ans = 0
for i in range(A, B + 1):
    digit_1 = i % 10
    digit_2 = (i % 100)//10
    digit_4 = (i % 10000)//1000
    digit_5 = i//10000
    if digit_1 == digit_5 and digit_2 == digit_4:
        ans += 1
        #print(i)
print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long int64;

int N, M;
int64 A[5001];
int B[5001][200];
int ans[200];

int main()
{

  scanf("%d %d", &N, &M);
  for(int i = 1; i < N; i++) {
    scanf("%lld", &A[i]);
    A[i] += A[i - 1];
  }
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) scanf("%d", &B[i][j]);
  }

  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    memset(ans, 0, sizeof(ans));
    int64 res = 0;
    for(int j = i; j < N; j++) {
      for(int k = 0; k < M; k++) {
        if(ans[k] < B[j][k]) {
          res += B[j][k] - ans[k];
          ans[k] = B[j][k];
        }
      }
      ret = max(ret, res + A[i] - A[j]);
    }
  }

  printf("%lld\n", ret);
}





Measured memory_bytes: 4224
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] h = new int[n];
		for (int i = 0; i < n; i++) {
			h[i] = sc.nextInt();
		}
		sc.close();

		int ans = h[0];
		for (int i = 1; i < n; i++) {
			if (h[i - 1] < h[i]) {
				ans += h[i] - h[i - 1];
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 21972